集训队作业IOI2003难题讨论活动

1、第二阶段：初步表格：学校： 芜湖一中一. 对题目的总体感觉（请不要回答得太简略）二. 关于每道题目，写出你的看法序号思路或者解法（请不要写得太简略，可以写在多行里）对题目的评价或对的0001可以构造可行解，但是如何尽量减少交换次数值得思考。也许要从数学上加以突破。0002一个似乎正确的想法是可以坐标离散化以后，对每一对相邻的y1、y2 所确定的横条进行扫描，找出每一段位于多边形的，这样的段都是梯形，可以算出每一段有多少格，把每段累加即可。但是实际上这样很可能重复地计算面积，而且不好排除重复。还没有想到好方法，也许这种题目会有标准的方法？0003很容易想到不少种 O(N2)的算法，但暂时想不出

2、O(NlogN)的算法。可能还是靠二分。0004不容易想出可以接受的动规。很奇怪的题目。0005枚举雇佣的总个数，利用Bellman-Ford 方法来判断是否出现负环，若没有则成功。由于出现了环，所以难度陡增，不能简单地贪心。0006贪心。关键是要想到从大到小依次贪心。0007先求出凸包，然后凸包上的边的倾斜角将 02pi 分成若干个区间，每个区间求出以这个区间的直线为Y 轴的最左和最右点。输入的直线当作Y 轴的话，查找在哪个区间（二分），判断最左点和最右点是否位于同侧即可。 O(mlogn)一道比较好的几何题，难度蛮大的。0008不会做。侯都做不出来，难度太大了。0009不会做。数学味道太浓

3、。0010利用“块”的性质，进行贪心。很好的题目。0011暂时想到先二进制编码，再用 RLE 算法或哈很好的题目，可以综合能力。总体上看，题目难度非常大，但也有可能是因为我。这些题目涉及到各个方面，如果都研究透了，将会大大提高自己在各方面的水平，但是也许时间不够。有些题目者自己会做，但是为了找到更好的方法，或者觉得解法和思考方法还能推广，所以也出来，这种精益求精的精神是值得学习的，同时也希望者能将自己的好方法告诉大 家。国内的题目似乎不是很多，大多数题目是 POI、BOI、USACO、Ural 和 ACM 上的，希望以后能看到的好的国内题目。LML 三位大哥，以及其他的们，加油出啊！的题目也很

4、好，但是可能都没法解决。涉及到几何的题目很多，特别是几何。这正是弱项，希望大家能帮助我。IOI2003 中国国家集训队难题活动夫曼编码来压缩。但是利用不到可以相差最多10 个象素这一点。0012似乎作者的想法是可行的，当有一些点 M1,M2Mx 与 OPQ 共面时，仅需要O是否在M1,M2Mx 和P,Q 组成的凸包上即可。但即使是这样，依然是繁琐的。空间几何太繁了。0013似乎先产生 8 种不同偏移量的“同步编码”，再进行匹配是可行的，但是可能时间上确实会有作者说 吧。看似简单的题目，但可能在时间上做文章。另外，可能编程上也有些繁琐吧。0014利用层层降维的，逐步离散把体分解成面，面分解成条来

5、判断。这类问题需要一定的空间想象力。0015不会做。只能想到搜索最小表示判重。也许会在数学上（比如Polya 定理）有所突破。0016原题宽搜。但是如果规模大了，就不好办了。也以先判定有没有解，再做。0017采用构造法。很好的题目，很有难度。首先要看懂题目，然后要大胆猜想，缜密求证。0018标准方法是贪心。O(n2)。但证明没有多想。很好的题目，标程的方法看起来很不严密，做的时候根本就不敢朝那方面想。0019首先证明一条很重要的性质，然后问题就迎刃而解。很好也很难的数论题目，需要很强的数学能力。0020从后向前贪心。O(n2)，也许会有优化？不错的一道题目，乍看无从下手，仔细思考后即可解决。0

6、021定义“加法”是使A=BA+C=B+C成立的运算，则本题中的运算不是加法。而经典的最小生成树算法只能够处理累积效果用加法来计算。所以本题不能套用经典的算法。对于经典的图论模型的很好的推广和变异，但太难了。0022不会做。很好的题目。看起来千头万绪，但没容易利用的条件。0023首先要用合适的方式来表示空间中的面，然后依次处理每条折叠的边。最后用 染色法来判断是否封闭以及算面积。没有编程序，肯定非常繁琐。0024直接计算。用三分法可以证明。很好的题目。0025不会做。也许要在图论方面多想想。0026不会做。的几何题。0027不会做。最终还是道图论题吧？0028宽搜。不是很难呀？0029似乎只有

7、动态规划。繁琐的题目。0030不会做。贪心吗？如何证明？0031不会做。没头绪呀，郁闷！0032不会做。搜？0033假设 P1 坐标为(x1,y1)，就可以把余下的点用 x1 和y1 来表示，最后又可以表示出 P1=(f(x1),g(y1)，联立 x1=f(x1)和 y1=g(y1)可以解出x1 和y1，也就可以确定原多边形了。一道很巧妙的题目。0034好像只能搜了。期望着强力的剪枝。常规的技巧是注意搜索方向、不要搜对称的情况之类的，大家都知道。0035只能想到者的方法。但精度可能会不够？证明的非常好，也许等周问题首先就应该想到圆？是不是又要向数学方面多想想？0036一种类似于迭代的算法。很奇

8、怪但也很巧妙的博弈题目。0037贪心。数学味道很浓。0038未压缩的可以有一种基于最小表示的好算法，压缩后的似乎稍加修改也可以使用。看了波兰文的解题才会的。很巧妙的。0039听说是求线性方程组的最小二乘解，够繁的。很不好想的题目。0040证明解的唯一性可以利用Fibonacci 数列，很巧妙。而构造的方法好像不能直接套用证明方法？很好的题目。0041首先可以证明一个解决这类题目的一个非常有用的定理，然后往贪心的方面想，细节上我还没有想清楚。不错的题目。0042好像只能搜？强力剪枝？0043类似于贪心或者说是构造。很好的题目，有一定的难度。0044不会做。难道还是搜？0045似乎只是搜索最小表示

9、判重。大概不会有非搜索的算法出现吧？0046原题规模比较小，所以可以用化搜索。规模变大的情况下如何解决？是否有图论方法？0047“弦图”判定问题。考标准算法的题目，但是我不会。0048不会做。侯启明去年的好像讲了这个，但当时就没怎么懂，后来又找不到了。0049解模线性方程组。但也不是很擅长，也没做过。有固定模型的题目。金牌解题指导上有。0050如果是连通图就可以解决，对于非连通图，可不可以稍稍改一下解决呢？听说是 IMO 的题目改编的？反正给人的感觉又是一道数学题。0051仍然不会做。因为增加了某两个人不能在一起的条件，所以不能照搬中的方 法，但是仍然使用变分法估计还可以得到新的构造方法。00

10、52充要条件是能跳到(0,1)、(0,-1)、(1,0)、(-1,0)四个格子，但如何判断呢？难道还是数学题？0053不会做。似乎是构造的题目，难度较大。0054不会做。博弈树alpha-beta 剪枝特殊情况判断也以做出一个很高明的棋手？0055不会做。数论的题目。难度太大。0056好像是离散化，但是和一般的离散化不同，需要一边做，一边离散化。非常繁琐的题。0057不会做。贪心法需要仔细斟酌。0058好像是解模线性方程组。很繁的题目。0059不会做。会不会是动态规划？似乎状态数太多了。0060不会做。看起来是一道很好的题目。难度较是否可以证明：总可以找到某条水平或是竖直的线，把整个矩阵划分成

11、独立的两部分？如果可以，就能用动规了。大。0061不会做。也许是一道图论题目吧。很难。0062逐步调整进行构造。很好的题目。0063度限制生成树，应该有标准的算法。又是考标准算法的题目？0064应该还是搜索。先搜未知字母比较少的单词。类似于算符的题目。需要在搜索方向和剪枝上多下功夫。0065不会做。SGOI 的标程就是搜索。应该还是搜索。0066不会做。很难又很繁的题目。0067不会做。应该只有搜索。省以前的省赛题目很多都是搜的。0068不会做。也许是图论的题目。很难。0069不会做。组合数学上好像有关于拉丁方阵的内容，但是不知道对于解这题是否有帮助。似乎没好方法。0070最短的路肯定没有交叉

12、，所以先求 轮廓，然后在某些地方凹进去，采用动态规划，而且可以用四边形不等式来优化。比较综合的题目。0071会做了。时间O(n2)，空间O(n)。很好的题目。同学的解题也很好，令我开。0072初步的想法是解线性方程组，但是还有不成熟的地方。希望能够把初步想法更加完善。也希望找到求最优解的方法。0073不会做。有O(logN)的方法，但是我不会。0074不会做。非常难。0075利用图的性质，直接产生出仅有的 3 条路径比较一下就行了。很好的题目，有难度。0076有点像 POI 的，也是处理无限长度 01 串，应该是在字母树上考虑。感觉上要构造图论模型。看看的 POI也许会有所帮助。0077利用平

13、面图的性质可以得出很漂亮的算法。看上去简单但实际上值得探讨的一道题目0078好像只有搜索，不过可以只搜一半以节省时间。经典的题目，如何剪枝值得探讨。0079不会做。条件过于繁杂，很难想到好方法。0080首先要确定好搜索的顺序和方向。怎样剪枝值得探讨。昆的里好像谈到过。规模小时不是很难的搜索题，但是规模一旦扩大，就要斟酌了。0081不会做。怎样贪心？如何证明？0082不会做。求出了最少拆多少后，怎样以此构造出方案？0083首先，使每一种物质连续也就是给定了一段必须连续的星球。依次处理每一种物质，就是将这些 交、并的过程，如何利用合适的算法和数据结构做好这个工作值得研究。好像又是经典的算法区间图。

14、0084把漏油点当成特殊的顶点，过每个顶点做水平不错的几何题。三 其中，你会做的题目以及比较有思路的题目，请进一步说明。（说明：这个问题的回答也许对其他人很有帮助，请大家没有保留的把自己的心得和大家交流。这个问题的回答会在集训队平时成绩中有所反映。）0006按照期望值从大到小的次序处理每个人，假如当前要处理的人为i，其期望值为si，那么在未处理且未与i 打过的人当中找到期望值最大的一个，让他们打一场比赛，且 si与 sj同时减 1。重复上述过程直到si等于 0，则处理下一个人；或剩下的所有人均和i 打过比赛，则输出无解。证明略。0007首先，这些点位于直线异侧的充要条件是直线穿过凸包。而凸包是

15、一个凸多边形（废话！）。如果将直线L 看作Y 轴，它的垂线H 看作X 轴，那么这个凸直线穿过的充要条件是凸包上最 “左”和最“右”的两点位于Y 轴的两侧，注意，这里的“左右”是根据直线H 当作X 轴来考虑的。假设一开始X 轴就是原先的X 轴，可以求出最左和最右点Left0、Right0。现在过 Left0、Right0 做X 轴、Y 轴的垂线 Y1、Y2。现在把它们同时以同样的角速度逆时针旋转，可以想象，旋转的角度非常小的时候最左和最右点是不变的，直到 Y1 或Y2 碰到了凸包上的另外一个点，才会变化。不妨设 Y1 碰到了另外一个点P，那么直线Left0P 平行于Y 轴，也就是说，P和Left

16、0 的X 坐标相等，都是最左点，可以想象，如果再旋下去，P 就会代替Left0 成为最左点。而由于Left0 是最左点，所以一开始 Y1 是不在凸包内的，现在 Y1 上第一次有了凸包上的两个点，也直线，和原来的边把整个图形分成若干个部 分，每个部分要么充满油，要么完全没有油，分别判断。0085不会做。也许是构造图论模型？0086不会做。没头绪。0087不会做。感觉上图论没什么希望。0088不会做。这类问题我一向很怕，希望大家指点我！0089不会做。感觉上只能搜。0090不会做。贪心是否可行？0091可以想出N2 的算法。很好的题目，多项式级的算法已经需要一定的巧思，不知可以怎样优化。0092不

17、会做。也许应该在图论方面多想。0093不会做。是否可以用BurnSide 引理来解决？（Polya 定理估计是）0094不会做。但是题目中好像有一句话看不懂，而中文翻译没有翻这句话，也许这就是关键。0095不会做。0096不会做。0097不会做。0098实际上如果给定了出去的方向，那么蚂蚁的路线也就确定了，可以分治，但是处理完全没有的区域要有技巧。很不错的题目。0099可以用递推来解决，但是这样需要推出的状态数比较大，更好的方法据说是 SSS*算法，值得研究。一道比较难的博弈题。0100不会做。就是，Y1 首次进入凸包，那么不难得出：Y1 重合于凸包上的边，也就是说，P 点是与Left0 相邻

18、 的点。所以说，左、右点发生变化只会出现在Y 轴旋转到平行于当前的最左或最右点的逆时针边的时候才会出现。于是可以用上面所说的办法先算出对于每一段倾斜角内的直线作为Y 轴，它的最左和最右点分别是什么，O(n)级。然后对于输入的 Y 轴，二分查找它的倾斜角在那一段内，判断左、右点是否位于这个直线的两侧即可。O(mlogn)。0016原始 很好解决：每个状态可以编码为 16bit 数，宽搜即可。但是如果规模大了，就不好办了。有解的情况用 A*也许很快就能出解。是否可以先用奇偶置换法判定有没有解，再用 A*呢？0018标程是这样的：数组 ition1.n 非零的格子的位置，Rest1.n 对应的非零的

19、格子的小球数减。ClockWise1.n 每个非零格子需要顺时针转移的最远的位置， lockWise1.n每个非零格子需要逆时针转移的最远的位置， ition 和Rest 根据输入确定，ClockWise 和lockWise 开始都等于 ition，也就是。依次处理每一个点i，如果Resti0，就算出这个点顺时针和逆时针转移一个球的Cost，选择较小的一个，转移。计算Cost 的方法，顺时针和逆时针是对称的，以顺时针为例：假设 顺时针地转移，那么会导致ClockWisei改为顺时针的下一个（相应地，要增加一定的转移步数），然后判断lockWisej是否等于ClockWisei，其中 j 为 i

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

21、以后的。开始时m=1，Si=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,时间

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

23、；如果N=(3H-1)/2，那么称 H 次足以保证找到坏球，但以保证知道坏球比标准球轻还是重；4)如果N=(3H-1)/2，而且还另有一个标准球，那么称 H 次足以保证找到坏球和知道，知道坏球比标准球轻还是重。将在冬令营的中详细地讲这题，所以我就不多写了。0025宽搜，队列里只存在模M 的意义下彼此不同的各类数中的最小的一个。开始时队列中从大到小地填入X1,X2Xm，当然，要保证它们模M 的值不等，否则只填最小的那个。然后依次扩展，即将待扩展的数乘以 10 再加上X1,X2Xm，如果余数是新的，就填到队尾。直到产生出余数为 0的为止。一个技巧是不需要存数，只需要存余数和数的最后一位以及从哪里扩

24、展出来的，这样打印的时候倒推一遍就可以了。时间复杂度O(n*m)，空间复杂度O(n)。0038对于未压缩的串，有O(n)的匹配算法或是另外一种基于最小表示的算法，对于压缩的串，匹配算法不好推广，但后将在冬令营的法似乎很容易推广。中详细地比较这两种方法，所以我就不多写了。0041上看，应该是先尽量把大盒子的填到大的容器里，看能不能把所有的容器填满，如果能，再从剩下的盒子里由大到小地把选取一些盒子与原来的盒子交换，使价值减少。但是没有证明。0043称所有分割开两个区域的格子为“围墙”，一开始“围墙”就是最一圈的格子。每次找到最低的一个围墙，进行Flood Fill，注意只能扩展比这个围墙低的格子。

25、扩展出的连通区域的水位就是这个格子的高度（于是可以算出这片区域的容积），同时，这片区域周围的格子成为新的围墙，而这片区域的格子将被标记为“考虑”，因为以后如果和它相连的区域水位高了，就会从这片区域流走。处理过的围墙不能再处理。这样直到所有围墙都被处理完。令 N=n*m，如果用堆来存围墙，时间复杂度为O(NlogN)；如果一开始将所有格子排序，在中途标记围墙，时间复杂度等于排序复杂度，可以是O(NlogN)，甚至 O(N)（如果用计数排序的话）。如果我有时间，会写这题的解题，因为这题确实比较好。0045可以用搜索自身判重（最小表示判重）来解决。正方形的就是经典的“撕邮票”问题，六边形的是“蜂巢问

26、题”，省有一年省赛考过。这两题我都做过。正三角形应该也类似。如果是六边形和三角形，建立坐标系的时候有一个小技巧可以帮助思考旋转、翻转的公式，是比较巧妙有趣的，也就是实际上只需要两个向量作为基底，但是分析的时候加一个辅助向量以便于思考，但是最后会将它化掉不用。我准备（可能没有时间）写一篇小文章来具体讲讲。正方形的可以有很变态的剪枝，我不是很擅长，但曾经和过。0046原题的规模比较小，所以可用化搜索解决：设整数se 对应的二进制串代表了某个人是否出现在已排的队列里，Ss e代表某种s e 对应的不同排列数，很容易得出Ss e的表达式。但是如果规模比较大了，就不好做了，是否有图论的方法呢？0071令

27、 f(len,min)代表长度为 len，每个数都不小于min 的合法标号序列的个数，那么各种情况（的解题中有）可以得到 f(h,min)=f(h,min+1)+f(h-1,min+1)+四. 除了自己的题目外，这 100 道题目中你最希望别人的题目有哪些？请分别说明理由并的难度。（说明：这里是指你希望大家的题目，而不是你准备参加的题目。或许有些题目，你自己并不拿手或者没什么并写明理由。），但是特别希望听其他人的，本题的意思就是要你把这些题目列出来0002很好的一道离散化的题目？也许有非离散化的方法？出去的方向为右方或上方出去的方向为左方或上方出去的方向为右方或下方根据 2N*2N 的矩形行走路线已经确定，所以组合起来的路线也是确定的。于是采取分治的策略，但是对于完全没有的矩形，不能分治，和出口之间是有公式计算的，这个