集训队作业ioi2007hom第二轮

1、中国国家集训队第二轮WorldFinals给出由水平垂直线段组成的两幅图，判断第一首先,可以证明至少存在一个方案使得有个幅图有的交点(线段的的端点或线段的交点)。因为如果某个方案中没有的交点，不管情况如何总可以通过平移、缩放来构造一个有的交点的方案。然后说到具体做法，枚举重复交点后，就要枚举比例。设（小图、（大图）分别是通点交点的两条水平线（两条竖直线，然后随便找小图中的另一条水平线（竖直线），再枚举C对应于大图中的（竖直线BD的间隔与C的间隔之比。注意到C与BD的间隔都有不能为。接下来就判断小图平移和缩放的图与大图的局部图（与前者位置一样）是不是相同。总结：此题主要编程能力，分析能力，观察能

2、力。为第二分局部放大得少有一个端点同时出现在两幅图中洗牌时每次最多犯一个错误（交换两张牌。给如果还是多解则输出字典定理：在洗牌过程换了两个牌 A、B 就等价于在最终结果换A、B。方法就是*IDA首先限定步数 depth。接下来就枚举次数。然后就进行搜索。在搜索过程序中，需要的一个剪枝就是用当前至少还需要的交换次数是否不超过还能交换次数。而至少需要的交换次数等于P是不进行任何交换的洗牌结果。对于在搜索中所有已经进行的交换（A，B，在P 换A，B 的位置，得到新P。然后P 至少要交换多少次才能变而言之就是 52 减去置换中循环的个数给出边与坐标轴平行的简分析一个图可以覆盖整个平面当且仅当找到六个点

3、 (包含 4 个点的情况)按顺序的 A、B、C、D、E、F，ABED相同，BCFE相同，CD AF 相可以证明 A，C，E 中至少有两个点在多边形点上B，D，F 中至少有两个点在多边形的顶首先可以枚举这个位于多边形顶点上的点其余两个再分情况求出来Wall Game用最少移动棋子使得它们当共线是行共线时，把所有的棋从按行从小到大排序。最优的共线就是正中间的那个棋子所在的行。首先棋子通过上下移用都移到那一行。然后再将第一次棋当共线是列共线时，方法与情况（1）类当共线是主对角线时，对于每一个棋子主对角线上有连续的几个格子是移动距离最少的情况下该棋子走到对角线的位置。设 i 个棋子走到对角线上的第i

4、到B i 走最短距离。不难发现，如果第i 走到K 个格子，而K 不在，B i就要多走- i|B |分配问题了。考虑先分配第一个格子，再 K个格子，找出所到尚未分配的棋子的集合 。就分配这些这棋子中 B 值最小的棋子。SA 值最小的棋子,如果有多个A时间复杂度程序：找不WorldFinalsn*n*n 的积木有的地方空面颜色相同6 个方程序CERC任务 A 人选的需任务 B 需要小于平均 ，任务 C 没有限分析首先把所有的人分成两个部分，一部分是大于等于平均的，另一部分的是小于平均的。在同一部分里，又分成多个连通块。对于每一个连通块，2T 染色，又成两部分，其中必定有一部分在任务C 里。也就是说

5、通块有两个属性哪一部分在任务C里。对于两个不同的连通块A、BA选择某个属性时，B就可能不能选择某个属性。这时，AB就以某种方式产生。这时又再次转化为2-SAT。最后再通过简单构造输出一个方状态：无数据2n 个工厂分配到河一些工厂之间必须直，有两架直升飞机可以分析有度为 1 的点后，连通块就变成了一连链。算法对于每通分块，首先看它是否符合上述性质。如果不符合，就在剩余图中尝试删去一条边使之满足以上的性质，这时有两种情况：所有节点的度都为，图的形态就是O字形，删去任意一边；有一个点的度为，形态是就6字形，删去与这个点相连并在环上的一边就可以。如果还不符合，就在剩余图中找到度最大的点，若该点的度D

6、4 （3 条边就枚举该点上要删去的边，枚举后，做法与上述的相如果总共需要的删去的边不2就有解，输出状态：无数据测试数：CERC2005Round Table每次圆桌会议由至少 圆桌旁坐下后相邻骑有多少个骑士不可能分析：不难发现，如果骑士A 到骑士B 之间有一个割点，那么它们俩是不可能组成会议的。因此，我 如果在同一个独立的部分里，如果有奇环的话，也就是不是二分图，那就这部分的骑士都可以参加会议，否则都不行。程序Wild每个人用一个三元组1=a,b,ca要么bb要么 如果求出这M*M 个(a,?,?)组合中不能战胜党的个数，就出（a,?,?）能战胜党的个数Pixel在一n*n 黑白图象上做一个3

7、2个动作pixel 算法：对于每个动作，表示成一个置换。然后求这动作序列对应的置换的乘积P。然后求出P循环，再求出这些循环的长度的最大公约数。这最大公约数就是答案。0 必须先想好每一个操作对应的置换。如果没有相当的把握，程序很可能会写错，这时的程序会相当难调试。程序Word 把一些单词组成一个 word ring，每个单词的后两个字母与后一个单词的前两个字母为一个图的结点。如果一个单词的开头两个字母为 S1,S2,尾部两个字母为 T1,T2。那么就在结点(S1,S2)然后二分答案 K。将图中的每一条都减少 K，看有没有正环。如果有正环，那么就说明答案大于 K，否则答案就小K。郭华阳的程CERC

8、2004Artof，每个国家的为首都所在发生 假设相邻算法线段AB,BA。把这些有向线段都放到一个集S。对于 S 中的每一条有向线段 AB ，求出它的下有向线段NextAB)。它定义ABB顺时针旋然后，对于每一条有向V，求Next（V为止。这时就求到一个环。求这一个环的有向面积 S如果 S 大于 0，这就说明这就一个多边形的环接下来，还要求一个点 P 所属的环。我们定义这样的环为包含的该点面积最小的环，设为Find(P。有时候，一个外部环可能被一个环所包围。这时，该外部环与包围它的 环是同类的。使用 对于CAPTICAL用FIND 求出它所在的环。把所有与该环同类的都标记为CAPITAL。最后

9、，如果有两个相反的有向线段 S 和 S，那么它们各自对应的 CAPITAL 就是相邻的。已编的程序PolishOlympiadinInformaticsPOIXIII2005-1-4Tetris 模拟一些长方体的下落，计算最后的高度这一个题了很好久好久，一直没有想出来我问过很多的大牛，但是他们就是不能很好地用来表述最后我只好看郭华阳的程序去学二维线段树我这才然大悟我看完郭华阳的程序后，发现我写的一与郭华阳的有很大差别。我以前写的一维线段树一个节点有两个信息：Same,TopTop表示该节点对应的区间的最大高度，如果 Same 为真的话就表示该区间的高度Top。另外，如果一个节点的祖先有Same

10、 为真的情况，就取 same 为真的最高的祖先的值这样的写法有明显的缺点，那就是节点具有传递一维线段树的定义：而另一种写法就是树的每一个区间存两个信息Cover 和 Top。表示某些覆盖该节点的区间的最大高度，Top 表示的就是该节点对应的子树的最大 Cover 值。单个 Cover的值不具有什么意义，并不表示该节点对应的区最大高度一维线段树操作 ：（1 ） 首先谈谈覆盖操作 update_1（c,d,height height。对于底部区间a,b（底部区间指的是线段树中的节点区间被c,d包含并且父亲的区间不被 c,d包含，把其 cover 更新max(cover,height)，并且把祖先的

11、 Top 值也更新了。这样的操作是完备的，就是说覆盖操update_1D（c,d,height）的所有信已经完全加入的线段(2) getmax_1D(c,d)：表c,dd的区间的最大高度。这始讲二维线段树。二维线段树的每一个节P的对应的区间a,b表示横坐标上界b、下界a 的矩形的具体信息。类似地，每一个节点上都Cover2，Top2，它们是以纵坐标为离散对象的。Cover2是一棵一维线段树，它的每一个节点区间c,dCover 表示某些覆c,d对应的子树的最大Cover值。Top2也是一棵线段树，它的一个节点区间c,d的 cover 值表示是所有 P的子树Cover2的节点区间c,dcover值

12、；其 Top 表示该节点c,d对应的子树的最大 Cover 值。二维线段树操作：（1） 覆盖操作 （ab,cd,height：表示把横坐标从 ab，纵坐标从 cd Height。首先找出两维线段树中 ab Cover2 进行 儿子节点的 Cover2 的底部区间的 Cover 更新为 Height ， 所 以 就 要 将 对 Top2 进 行 二 维 线 段 树 操 作 ：（ 2 ） 询 问 操 作 getmax2Db,c)。这等价于求与ab,c)矩形有交的二维线段树中的oer2 的最大ovr 值。对于二维线段树中底部区间，求它的子树与ab,c)矩形有交的最大over 值就等价于求o2 中与(

13、abcd矩形有相的最大 or 值，也就是 对2 求 getmax1D(c,dve2中与(abcd矩形有相的最大cover 值就等于对ve2求geax_c,。总的时间复杂度是 PASCAL程序：tet.pas郭华阳C+程序：tet.cpp2-1The给有向图，求一条从 开始1 结束的连续顶点序列，或不存在参见问题2-3给一棵树，用L条无公共点的路径覆盖尽量多的结点参见问题2-5给一n*m 网格，每每次切下一个宽度为 1slice，里面的数之和不得超过k每次切完后剩下的部分仍应量少slice。分析：矩形被完全切掉时，矩形一定被切下 N 次横 slice 或被切下 M 次竖 slice。假如被切下

14、N 次横 slice，那么就可以认为切下一个slice 的费用0，切下一个slice 的费用为 xi,j1N 行、i 列到j 列的矩形的最少费用。由于横 slice 是免费的，应该尽量的使slice。如果该矩形能够只用slice，那么费用就 0，否则就将矩形的上部、下部能横 slice 都slice，剩下的子矩形如果最左列的总和不大于k，xi+1,j+1去更xi,j，如果最右列的总和不大于 k，那么 xi,j-1+1 去更新 xi,j。最后x1,m+n 去更新答案假如被切下 M 次竖 slice，分析与上述相似。2-6n 1n 之间的整数，把它变成 1n的排列。每个新数 mi必须在区间ai b

15、i内，改变费用为ki|mi-mi|，mi为第i 个数原算法构造带权二分图。二分图左边XN个结点表示原来的NYN 个结点表示改变N 个数。如果mi 可以变成mi，那么就在Xi 和 Ymi之间连一条费用为 ki|mi-mi|的边，否则在 Xi 和 Ymi之间连一条费用为 无穷大的边。求最小费用的完备匹配。这时可以使用 KM算法。这样的时间复杂度是 O（N3。但我写的程序3-2给 出 n 和 m1,m2,mn，求方程 a1 xor a2 xor xor an=0 0=ai=mi，ai 不全为0参见问题3-4n 个回文词，两两拼接的方法有n2种。其中有多少种的拼接结果也是回文词参见问题POIXII20

16、04-Two parties 把 n 个人分到两分析party，使得“有偶数设布尔值 xi为第 i 个人是否在第一个 party。如果i 个有偶数个朋友，那么关于第i 个人的件就可以转化xj1xorxj2xorxixorxj1xorxj2xor然后就要解含有 n 个未知数n xor 方程的。用消元就可以解决这问题个朋友与自己分到同一个 party”的人数尽量多. 允许其中一个party 没有人。每个不是自己的朋友关系是对称的camel (pra)平面上有 n 个点，初每次只能右转（0 到 180 度，线路不能交叉，最后回到点 1。要求尽量多的其他到 i 的最多点的路线的点数。初始条件就是F1,

17、2=2。转移方程就是 观察转移方程中的 i，等式左边和右边都出现了。 就可以猜想，如果i 固定，能否高效地求出所以 如果可以的，应该按什么顺序来枚举 i 呢？想象最优路线的图象，它就像是一个心型。对每Pi 定义一个排序函数，F(Pi)表示向P1Pi 时针旋转多少度才P1P2 同向。并对 P2Pn F(Pi)为关键字从小到大排序。排序后，从小到大的依次枚举上述的iFk,i|ki按极角从小到大排序，同时也把Fi,|按极角从小到大排序。然后从后到前地一个个处理 F,j，不难发现,Fi,j的前趋状态 Fk,i必定排序的序列后面连续多个，并且当前的 Fi,j比上一个 Fi,j的可选策略要多些或相同。这时可以用一个指针动态地可选策略区和最优策时间复杂度程序：了El判断一个有向图是否PS-graph. 即可以从一条边经过若干次 doublesplit操作得分析double的逆向操作删去重split 的B 只和 A,C 相连。那么一个PS-graph