网上找的一些综合材料专题phaseiiformxzl

1、第二阶段：初步表格：学校： 芜湖一中一. 对题目的总体感觉（请不要回答得太简略）二. 关于每道题目，写出你的看法序号思路或者解法（请不要写得太简略，可以写在多行里）对题目的评价或对的0001不会做也许要从数学上加以突破。0002似乎可以坐标离散化以后，对每一对相邻的 y1、y2 所确定的横条进行扫描，找出每一段位于多边形的，这样的段都是梯形，可以算出每一段有多少格，把每段累加即可。可能细节上会比较繁吧。0003很容易想到不少种 O(N2)的算法，但暂时想不出 O(NlogN)的算法。可能还是靠二分。0004不会做。不容易想出很好的动规。0005不会做。由于出现了环，所以难度陡增。0006贪心。

2、贪心易想，但证明不容易。0007先求出凸包，然后凸包上的边的倾斜角将 02pi 分成若干个区间，每个区间求出以这个区间的直线为Y 轴的最左和最右点。输入的直线当作Y 轴的话，查找在哪个区间（二分），判断最左点和最右点是否位于同侧即可。 O(mlogn)一道比较好的几何题，难度蛮大的。0008不会做。侯都做不出来，难度太大了。0009不会做。数学味道太浓。0010贪心，但是我不会。骆 出的，他有贪心的算法，但我没搞懂。另外，原题似乎并不一定有解。0011暂时想到先二进制编码，再用 RLE 算法或哈夫曼编码来压缩。但是利用不到可以相差最多 10 个象素这一点。很好的题目，可以综合能力。总体上看，题

3、目难度非常大，但也有可能是因为我。这些题目涉及到各个方面，如果都研究透了，将会大大提高自己在各方面的水平，但是也许时间不够。有些题目者自己会做，但是为了找到更好的方法，或者觉得解法和思考方法还能推广，所以也出来，这种精益求精的精神是值得学习的，同时也希望者能将自己的好方法告诉大 家。国内的题目似乎不是很多，大多数题目是 POI、BOI、USACO、Ural 和 ACM 上的，希望以后能看到的好的国内题目。LML 三位大哥，以及其他的们，加油出啊！的题目也很好，但是可能都没法解决。涉及到几何的题目很多，特别是几何。这正是弱项，希望大家能帮助我。IOI2003 中国国家集训队难题活动0012似乎作

4、者的想法是可行的，当有一些点 M1,M2Mx 与 OPQ 共面时，仅需要O是否在M1,M2Mx 和P,Q 组成的凸包上即可。但即使是这样，依然是繁琐的。空间几何太繁了。0013似乎先产生 8 种不同偏移量的“同步编码”，再进行匹配是可行的，但是可能时间上确实会有作者说 吧。看似简单的题目，但可能在时间上做文章。另外，可能编程上也有些繁琐吧。0014离散化？一个面一个面地扫描吗？这类问题需要一定的空间想象力。0015不会做。只能想到搜索最小表示判重。也许会在数学上（比如Polya 定理）有所突破。0016原题宽搜。但是如果规模大了，就不好办了。也以先判定有没有解，再做。0017想不出来。很好的题

5、目，也很难。0018标准方法是贪心。O(n2)。但证明没有多想。看波兰文的标程真是痛苦呀！0019不会做。是否可以这样认为：对于任意的Ax+By， N|(A0 x+B0y) - N|(Ax+By)成立的充要条件是存在整数t 且 0=t0，就算出这个点顺时针和逆时针转移一个球的Cost，选择较小的一个，转移。计算Cost 的方法，顺时针和逆时针是对称的，以顺时针为例：假设 顺时针地转移，那么会导致 ClockWisei改为顺时针的下一个（相应地，要增加一定的转移步数），然后判断lockWisej是否等于ClockWisei，其中 j 为 i 的顺时针的下一个非零格，若等于，则lockWisej改

6、为顺时针的下一个，同时ClockWisej改为顺时针的下一个，同时更改Cost 中的转移步数。这样，等于是j 又向顺时针转移了一个，可能会造成连锁的反应，所以要继续判断下去。转移一个球和球 Cost 的过程比较类似。每次判断最多绕一圈，所以转移一个球的复杂度为O(n)，整个算法的复杂度为 O(n2)。0020原图显然无环，而且给定的顶点顺序就是拓扑有序的。设合并后的图是较大的点可以走到较小的点。从后向前贪心地做：设colori代表 i 点的颜色，lefti、midi、righti代表 i 点的左、中、右的边所指向的点，m 代表合并以后有多少个点，Si代表原图中的点在合并以后的。开始时m=1，S

7、i=0（1=in），且 Sn=1。然后依次处理 n-1、n-21。对于一个点i，如果Si=0，就将 m 加一，同时令Si=m，然后依次j=i-1,i-2,1，若colori=colorj and Srighti=Srightj and Smidi=Smidj and Srighti=Srightj，那么 i 和j 可以合并，也就是令Sj=Si。最后的 m 就是要求的。0021目前的想法是：最后肯定是一棵树，那么共有N-1 条边。于是，可以把每个点的花费cost 改为e=F/(N-1)-cost，则假如当前已有的收入为 I，工作时间为T，那么再加上一条边(收入为 i,时间为t)之后的收入为I+i

8、，时间为T+t，且最后的所有收入加起来正好等于减总花费。但之后就不知道怎么做了。0024此题相当于：有一个标准的球和n-1 个球，其中有一个质量与标准的不同，问是不是可以在k次比较之内找到坏球。用三分法可以证明如下结论：现有N 个小球，其中有一个坏球不知比标准球轻还是重。 令H=log3(2N)，其中x表示大于等于 x 的最小整数。要保证在N 个球中找出坏球并知道其轻重，至少需要称H 次。假设N2，有如果N(3H-1)/2，那么称H 次就足够了；如果N=(3H-1)/2，那么称 H 次足以保证找到坏球，但以保证知道坏球比标准球轻还是重；如果N=(3H-1)/2，而且还另有一个标准球，那么称 H

9、 次足以保证找到坏球和知道，知道坏球比标准球轻还是重。将在冬令营的中详细地讲这题，所以我就不多写了。0025宽搜，队列里只存在模M 的意义下彼此不同的各类数中的最小的一个。开始时队列中从大到小地填入X1,X2Xm，当然，要保证它们模M 的值不等，否则只填最小的那个。然后依次扩展，即将待扩展的数乘以 10 再加上X1,X2Xm，如果余数是新的，就填到队尾。直到产生出余数为 0的为止。一个技巧是不需要存数，只需要存余数和数的最后一位以及从哪里扩展出来的，这样打印的时候倒推一遍就可以了。时间复杂度O(n*m)，空间复杂度O(n)。0038对于未压缩的串，有O(n)的匹配算法或是另外一种基于最小表示的

10、算法，对于压缩的串，匹配算法不好推广，但后法似乎很容易推广。将在冬令营的中详细地比较这两种方法，所以我就不多写了。0041上看，应该是先尽量把大盒子的填到大的容器里，看能不能把所有的容器填满，如果能，再从剩下的盒子里由大到小地把选取一些盒子与原来的盒子交换，使价值减少。但是没有证明。0043称所有分割开两个区域的格子为“围墙”，一开始“围墙”就是最一圈的格子。每次找到最低的一个围墙，进行Flood Fill，注意只能扩展比这个围墙低的格子。扩展出的连通区域的水位就是这个格子的高度（于是可以算出这片区域的容积），同时，这片区域周围的格子成为新的围 墙，而这片区域的格子将被标记为“考虑”，因为以后

11、如果和它相连的区域水位高了，就会从这片区域流走。处理过的围墙不能再处理。这样直到所有围墙都被处理完。令 N=n*m，如果用堆来存围墙，时间复杂度为O(NlogN)；如果一开始将所有格子排序，在中途标记围墙，时间复杂度等于排序复杂度，可以是O(NlogN)，甚至 O(N)（如果用计数排序的话）。如果我有时间，会写这题的解题，因为这题确实比较好。0045可以用搜索自身判重（最小表示判重）来解决。正方形的就是经典的“撕邮票”问题，六边形的是“蜂巢问题”， 省有一年省赛考过。这两题我都做过。正三角形应该也类似。如果是六边形和三角形，建立坐标系的时候有一个小技巧可以帮助思考旋转、翻转的公式，是比较巧妙有

12、趣的，我准备（可能没有时间）写一篇小文章来具体讲讲。正方形的可以有很 的剪枝，我不是很擅长，但曾经和 过。0046原题的规模比较小，所以可用化搜索解决：设整数se 对应的二进制串代表了某个人是否出现在已排的队列里，Ss e代表某种s e 对应的不同排列数，很容易得出Ss e的表达式。但是如果规模比较大了，就不好做了，是否有图论的方法呢？0047建立一个先序遍历搜索树，显然，环的情况只会出现在某个顶点连向它的祖先。某个顶点连向最近的祖先的边是有效的，其他的可以忽略，不妨删掉。依次考虑每个顶点，如果它有连向祖先的边，看这个边是否形成一个大于 3 的圈，如果是，那么再看这个圈里有没有别的小圈把它破坏

13、掉，如果破坏不掉的话，那么就说明图中存在大于 3 的洞。0066初步的想法是：设needi代表为了拼出某一段的数，在初始的时候数字 i 的最小需求量， increasei代表拼完了这一段数之后，数字 i 的增量（可能为负）。先求 199 的needi和 increasei，然后根据这个可以求 1999 的needi和increasei，就这样，直到 1x999 无法表示，而 1(x-1)999 可以表示，于是所求的数上下界就定下来了，再一位一位地确定。这只是大概想法，也许细节上会很繁。0075首先，原图一定可以排列成： 下面接着一棵二叉树，这个二叉树的每个非叶子节点都有两个儿子。所有的叶子节点

14、从左到右连在一起，边的叶子节点连在一起。对于原图中的二叉树的每个非叶子节点x 定义下面几个数组：Root_To_Rightx代表在以 x 为根的中，从根走到这棵树上最右边的叶子，并且走完这棵树上的每个点的最好代价，类似的，还有Root_To_Left，Left_To_Right，Left_To_Root，Right_To_Root 和Right_To_Left，而这些数组是互相的，但是有阶段性，所以可以用动态规划推出来。最口可以先走到二叉树的根，再走到左边或右边的叶子，最后回到 ；或者先走到左边的叶子，再走到根或右边的叶子，最后回到入口；以及先走到右边的叶子，再走到根或左边的叶子，最后回到 。

15、而这些情况都是可以利用上面的几个数组计算出来的。注意到上面的分析中很多情况是对称的，有些数组方案是等效的，所以还可以优化。0078如果只求方案数的话，可以规定第一行的皇后只能放在左半行，因为放在右半行的情况是对称的。但是这样也只能节省一半的时间。0091先用Dijkstra 算法计算出A、B、C 到每个点的最短距离，也就求出了原来的A 到B、C 的最短距离 SA、SB。然后枚举 X、Y，假设在X、Y 之间建桥符合要求，那么从A 到B 的最短距离 d(A,B)=mind(A,X)+d(X,Y)+d(Y,B)，d(A,Y)+d(X,Y)+d(X,B)，同样d(A,C)=mind(A,X)+d(X,

16、Y)+d(Y,Z)，d(A,Y)+d(X,Y)+d(X,C)，判断：若 d(A,B)SA and d(A,C)SB且d(A,B)+d(A,C)当前求得的最小值，那么就替换当前的方案。0099用S e=(x1,y1,manner1,x2,y2,manner2,x3,y3,x4,y4)代表一个状态，其中前三个数代表第一个 L的“头”的坐标和摆放方式，然后是第二个L 的信息，x3、y3 代表第一个圆片的位置，x4、y4 代表第二个圆片的位置。首先求出所有合法的方案，为它们 ，设为 1 到n。建立S e 到Number的双向 。先标出所有的无法继续的状态为Lose，其余的状态为Unknown。依次处理

17、每个Unknown 状态，如果后继状态有Lose，则标记此状态为Win，如果后继全都是Win，则标为Lose，否则不改动。一遍处理完，再进行下一遍，直到某次没有做出任何改动，停止，标记所有 Unknown 为 Draw。复杂度也许高了一点。四. 除了自己的题目外，这 100 道题目中你最希望别人的题目有哪些？请分别说明理由并的难度。（说明：这里是指你希望大家的题目，而不是你准备参加的题目。或许有些题目，你自己并不拿手或者没什么并写明理由。），但是特别希望听其他人的，本题的意思就是要你把这些题目列出来五. 虽然目前还不会做，但你自己有一定想法，将会积极参与的题目有：00020003001000110002很好的一道离散化的题目？也许有非离散化的方法？0005怎样处理这样有后效？还是贪心吗？00120014空间几何怎么处理才方便呢？00150093像这种求本质不同的方案，怎么做才高效呢？0017非常有趣的题目，感觉上比较有探讨价值。0023像这种折叠的题目该怎么做呢？00490058怎样解模线性方程组比较简便？希望大家教我。0053像这种摸不着头脑的构造题目该怎么做呀？00600095这两道题目有点像：都涉及到“定方向”，是否有类似的解法呢？0062有点像n-S