集训队作业IOI2008第二轮

1、IOI2008 (截止时间：200853日：明（包括是否已通过数据50 。作为参考的，所以相信大家会自觉的做好榜样 YY QRQ 另: （同时也是准备CTSCIOI2008 (截止时间：200853日：明（包括是否已通过数据50 。作为参考的，所以相信大家会自觉的做好榜样 YY QRQ 另: （同时也是准备CTSC1.ACM/ICPC 欧洲赛部分题目提交)1.ACM/ICPC 欧洲赛部分题目提交)NEERCNEERC给一个 n 个点本题参考了ZDZD同学心得中的算法基O(M)。潜水员需要从深度为 d 的水里顺着绳子往鱼，在 di 的深vs的速度最大距离为 w员与任何一条鲨鱼的距离不得小于r。潜

2、水员可以以不超过 vd 的速度沿着绳子上移或到初始位置以由于这里的所有鲨鱼的最大距离和速度都相同， 可以把2*w，而这些鲨鱼不转头，不停地向 ，而通过这一样的，所以这样转化以后对 不会有影响，如下图，鲨鱼可 往右走（vs）往右走（vs）而这点的轨迹只能是往右，并且它的倾斜角过某一个定值 (ac而这点的轨迹只能是往右，并且它的倾斜角过某一个定值 (acn(vdv)，求到达水面时他离出发点的最短横向距离（除以 vs即为所求时间然存一条满条件的路径它总是沿着这些圆拐弯，并且只关心它是沿着这个圆的上边，还是这个圆的下边（因为倾斜角的限制，人无法沿着圆的通过圆的左边或者右边并且图很多圆本质相同的同一条鲨

3、鱼，因此状态目只需要有2*N 个状态表要走到圆的上面或者下面至要往右个周期态可用dksra算来求往外推的时候，看当前这个圆是否能往其他圆连边，这些边是否会碰到，由于这里圆有无数多个，因此我这里是限制最多往右推 XN 个周期，这里没有严格的明这一定是对（我感觉推 XN 周期应该就不会有影响最优解的特殊情况了。在判断障碍的时候，就把两个圆的公切线求出来，然后直接枚举横向在这段区间内所有圆否与其交，其有个特情：按 上面的方法，这里两个箭头处都可以推，但事实上无法通过中圆的上表面，这里在 判断的时候需要加一个条件，就是 是从死胡同来的。判断的复杂度为 O(n2)，要进行 O(n2)次递推，总复杂度为O

4、(n4)，并且算法的常数很大。n 期望得到 mi 个不相交（ 但可以接给每个人一块不相交的凸多边形都至少得到了它1/n面n=(1-1/(i+1)*(1/i)=1/(i+1)，因此满足条件， K=i+1 的确也是正确的。O(MAX)，MAX为所需要的精度，要进行O(N2)的操作，复杂度即为O(N2MAX)。测试数据、参考NWERC有一个N*M 的8，要在网格中标出尽量多的B在边界上选出 E，其余点. 使得所有 B都能从 E开始经过一系把这个格子改为B,与它相邻的B改为.，那么这个.可以被 E 度最 8，因此可以用 连通性的集合 DP，对于一排格子中的每个格子 BB还要 它目前有没有与.相交，一开

5、始就搜出所有可能的连通hash表使得 在计算中可以把状态转化成标号，再把所有可能的 状态 下来。在做的时候可以先把所有 先存在一 里，这样对任意多复杂度 O(MAXL4*MAXMASK， 对于所有宽度做一遍 O(MAXL)O(MAXL2)O(MAXL)，设一些不可能存在的连通状态也被 了。C个多边形，多边形可能非使它到所有多区域，对所有多边形的点可以扩充为一个半径为d的圆，对所有边可以向多边形外部扩充成一个宽度为d的矩形，那么问题就转边形的距离的边形点数最多边形的距离的边形点数最多折线的点数最多为 N。 C,N=Q判断无论多大W 都不可能满 2.ACM/ICPC 亚洲赛部分题目提交2.ACM/

6、ICPC 亚洲赛部分题目提交)提示：有很多题目无法提交。这些题目只需要读题(对于我已经给出题目大意的题目最好也重新读题以了解细节)一套比较难的题目思考蓝题和红题（均无人通过，其他题意义不算的模式，(a, b)(c, d )X = (+ c, max(b, d), (a,b)(c,d)Y = (max(a, c), b + d ),那么给定一个长度为N*2-1 的运算表达式，其中的N个元素是数对于N个数对，每个数对又可以从一个最多有K=20 个个运算符可以选 X 或 Y， N=2000，对于每种选择方的数对的积最小。保证最终可以表示成一个 32bit的守恒的，但是这个规则由于max 的存在是不可

7、能找到的，但又由于这里只存在max，因但是看上去把两个分别为L1 和L2 的数对的序列通过计算似乎能得到一个L1*L2*2的序的点对：如果某位置有两个不同可能数对 (a,b)和(c,d)并且满足 a=b,c232 的数，剩下的数一定不会超过 217(每个数对的前一维或后一维在 1216 这个区间内)，这样每个位置的X 运算举例，不妨设前一个序列取出的数对为(a,b)后一个为(c,d),不妨先设b=d，那么运个点对(e,f)，满足b=fd，那么由于序列是好的 ec，那么(a,b)(e,f)X=(a+e,b)，这使 于等于b 的数对，这个数对才满足条件。而最大可能的序列长度就为 4*(L1+L2)

8、并且合并的复杂度仅为 O(L1+L2)。总复杂度 Kaoshiung 上可最大可能的序列长度就为 4*(L1+L2)并且合并的复杂度仅为 O(L1+L2)。总复杂度 Kaoshiung 上可到数据，但似乎H 的数据有问题。重点思考G 和AN 个恰好需要一天完成的所有任务。任务可以并行完有向和无向来表示。AB表示 A 必须在 B 之前完成， AB 表示A 和B 不能在同一是给一棵树的某些边定向后长度为 k，则 为 k 或者 k以后， 只需要判断是否存在可行k天的方案即可，而判断就要比求某个值要来得方便得多， 这里对于树上的每个now，把它最小可能天数先赋为 1，最大可能天数赋为 k，先递归求出它

9、的最小可能天数+1 now 的最小可大可能天数-1 去更新 now 的最大可能天数 (max)，对于无向边所连着儿子，如果它的 min和max不同，那么它对now毫无影响，因为无论now选哪天，它都可以选不同的一天，如果相同，那么这天now就不能选，这个可以用一张bool表来 。全部更新完以min到max之间所有的天now 都不能选，那么 就是 k+1，否则就用这来更新m axJapan 如上图， 需要求出 A，B，C 的坐标，其中的条件就是 AD=DC,C ,BE=EA(满 给一个 给一个要的条件就是所有点坐标的绝对值都=100把所有长度平方为一个定值k 的向 量 都下来，如对于 25 ，有

10、 (5,0),(0,5),(-5,0),(0,-5),(4,3),(3,4),对于大多数k，符合条件的向量个数是相当有限的，可以枚举A，然后利用长度AD，AE 的限制枚举B，C，再判断BF 是否等于CF。而枚举的时候还要注意 ABC列方程计算一下高，这里如果高为0 的话，最大的边界长，MAXP度加上目前点到终点的最短路长度要大于 floyd 求，光加这个剪枝还是不能过的，但是 可以把这个剪枝强化，度加上目前点到终点的最短路长度要大于 floyd 求，光加这个剪枝还是不能过的，但是 可以把这个剪枝强化，floyd求的时1i 的点的最短路，很容易被 过， 可以用 floyd 把所有经过iN 1i-

11、1 都被 过了(或者是终点)就可以用只经过iN的最短距离，这样的优Japan x条铁轨y个中转线路连接辆由 n个车厢（用小写字母表组成的火车（可能分散少的步数从初始状（ 各铁轨上的车厢顺序）变到目标状态。 x=4, n=10这题的规模特别小，并且题目中还注明了 最大为 6，因此这题很显然是搜索，搜索的时候就搜因此每次的决策数就 *10，而由于这题的小， 需要利用的剪枝主要就是估计剩下的至少要几步，从而判断它能否更新 。我一开始去和最终这条铁轨上的 比较，如果两个字符1 2 就的个数，如对于ababaabb，ab3 次，ba 出2次，aa和bb1次，那么对于当前的reverseab的出现要加到(

12、a,b)和(b,a)一行 是非空字符串而当前串是空的，那么还这个方法算，还是无法 AC。结果这个方法算，还是无法 AC。结果最终我把这两个AC 了。P N*N 的矩阵， 数都被染黑那么称 矩Bingobingo 并且bingo 的顺序序可以连续几个一起 bingo)，数值最多100我也看到Rlist 里面许多人都是几秒才出解我接搜数的数值，那么其基础的复杂度即为 100!，法是搜出每个矩阵造成它 bingo 的那行(或者列和对角线)，那么对于每个矩阵，最多只需要搜 10出这个以后，还需要搜出哪些矩阵是一起 bingo的 ， 这 就 是 一 个 顺 序 比 如 说 (1)(2,3,4);(1,2

13、)(3,4);(1)(2)(3)(4)那么对于一起bingo的时候，所有这些矩阵都必须不是bingo的状态。通的，这里由于最多 P 为 4，因此搜索也只有 8P DP也是瞬间出解的，我相信即使 P 再大一些，这样水平移动一个多边形 形B 的距离不小于一个动过程中A和B可以相这道题的算法并不是很难想但是实现有点复杂首先多边形和多边形的距离一定是其中一个多边形的点到另一个多边形的边的距离，因此的想法就是：对于某个多边形的点和另一个多边形中的边，也许会有一段区间(x1,x2)使得当平移长度在这个区间时，这个点和边之间的距离小于，也就是说不符合条件，把所有这样的区间求出来，再求出这些区间的并，就可以知

14、道所有不能平移的长度的区间，但是这样也许会出现错误如下面的两个图，当L 非常小的时候，下面的情况在的算法下是允许的：况， 可以规定边无法与边相交，对于来自不以求出一个区间，而对于第二种情况， 任取数)个 的区间来表示，那么当 把所有的禁况， 可以规定边无法与边相交，对于来自不以求出一个区间，而对于第二种情况， 任取数)个 的区间来表示，那么当 把所有的禁Japan 不错的一套的高都为 10，其中一个柱体的底面在xz坐标平面上，另一个在yz坐标平面上，它们N 个点，都是整点，N=4，上这题的N即使到几千几万也可以做，即使不与xy坐标平面平行的，另一种是平行的，可以只算一遍然后乘以 2条边(x1,

15、y1)-(x2,y2)y1y2就先求出整个多边形夹在y=y1和y=y2中间条边(x1,y1)-(x2,y2)y1=2 且 m=2（如果有m 的话）n=3(没有m)时，原图中的1 的点可以在一个虚拟网络中传输一个n比特非负整数k。各比第i 个比特的发送时间为 i。每个比位有i 0,j 1 的二进制串的个数。由于延迟最多为d，因此在T = i+j+d的时候，原序列的前i+j位必然已经收到，因此状态是合法的。递推的时候从fij推到fi+1j和+ 1， 若忽略限制条件，正常的递推方程为 fi+1j += fij,fij+1fij。其中f001为递推的边界状态，特的网络延迟总是为1到d之特的网络延迟总是

16、为1到d之间的i 个比特的到达时间为 i+1 到 i+d+1 之间若同时有个多个比特收到的整数有多ftot0tot1为最终 tot0,tot10 1i+j+d0的个数，1的个数,如果cnt0 = i,0已经放满了不能放第 i +1 个 0,那么fij不能推到fi+1j,如果 0,1都有，但是第i+10在原串中的位置比第j+11在原串中的位置+dj+11无法delay到i+1发送的时间，那么此时也不能从 fij推到fi+1j，从 fij推到fij + 1的限制条件类似。求最小值最大值用贪心即可，从左向右确定Min的每一位， t0和 t1表示目前Min 中有几个0 和1，此时的限制条件就相当于把

17、t0代给 i,j,fij向外推的限制条件能添0 就添0，否则添1,Max 的求Chengdu很不错的一套一张N 个点M条要去掉两个不同的点使得原图不范 围 是 最多能进行多少次操作？或者能作N 有点复杂的结论题， 。操作并不能改变数的和，因此，0 0 能把所有数都变为 0。当和为正数时，为非负这个结论是由随机操作发现的，我还不知道怎么证明。然而即使知道了这些，要解决这题依然不轻松， 很容易就能高达 O(N3)因此模拟是行不通的。还应发现一些规律来优化，如果有下面一个序列2435125X（的序列与一个负数相邻）可以转化成这样：2 4 3 3 2 1 2 2，1，5 直到这个时候发现数到的数的和5

18、 8 了，此5 2 32125，分割后连续的非负序列就多了一项把原来的5 的位置占了，其需要的操作数即为数过的数的个数为 3。如果把所有非负序列都数光了还是不到那么会怎么样呢：如下：-X 2 1 2 4 2 -15Y，操作后变为-X-4421242Y-156。可以看到，不论如何，下面来考查这样的一个序列-81 1 1 11 11-7下面来考查这样的一个序列-81 1 1 11 11-7111111 1 0，下同，继续转化，会变成-7 1 1 1 11 11 0 1-6 1 1 1 1 1 1 1 0 0把-7转化为-60 了，如果再继续操作下

19、去还会发现，把-巴上的 1，如果这里不是-8，而是-900，那计算到后面每把负O(N2)0 的过程中，00 00添到序列中间，那么复题目不错。提交/器人R G两种机器人每次只能往右或往下走一格，起点任选过这题以后看了下解发现想位置都可G格子，将恰好搜集一个的能量（能不搜，然者被 。R 可以修（标记为 B 的位置上损坏每次R 可以修任所在的位置能才修。能量被取完后E 格将倒塌，两个机器人均无法再通LRLG问是否可以搜集完所有能量。 每个 E 格子的能量点恰好k 次(k 为该点的能源量)的个数为B(=10)，能源点的个数为E (=50)。V=50*50=2500，V2 的匹配复杂度太大。1、枚举准

20、备修哪些桥，复杂度2、对于当前需要修复的x 座桥，确定R-robot 的最网络G：添加源点S，汇点T；对每个桥i 分拆成两个结点i、i，S 到i、i到T 的容量上界为无穷大，下界桥i到桥j 是可达的，添加弧(ij)，容量下限为0，上限为无穷大；求G 的一个最小流f。则2*f 为R-robot3、对于修桥后的新地图，确定G-robot 的最少传送次数。构造容量有上下界的网络G:添加源点S1 格子，最多50 个。B 格子不超过10 个。 容量上界为无穷大，下界为0；添加狐(i, i)，容量下限和上限均为该点的能源量；若能源点i 到能源点j是可达的，添加弧(i, j)，容量下限为0，上限为无穷G 的

21、一个最小流f2*f 为G-robot 所需最少算法总体复杂度为O(2n*flow) FLOW 为网络f=2500, 点v=100, 边e=2500，而且这些上限都是很难达到的。本题时限10 秒，使用O(e * f ) 的朴素网络流即可。当流量较大时更好的做法是使用O(v3的方式构造一个电阻网络，使得电阻值为a/b。 1=a,b1)因此只能搜索加剪枝。用DP，状态转移与上面的搜索是一样的。那么状态 fij就表示i/j 的电阻最小需要的数目，当做完一遍以后，试着让所有fi*kj*k去更新fij，然后再重然后再重新做，直到所有的 fi*kj*k都无法更新 fij为止实践表明只需要DP 两次就能使fi

22、jShanghai 2006POJ可提交很不错的一套题。现场 EFG 三题无人通过。H 参考 ZhangYucheng 的集训一个NM边的有向图除可以走，问它的第 k 短路问题一个点可以重复经过，包括终点，N=100 ，M=500，在一个点上最T时间，等这主要是因为边是周期开启的，但是 注意到边的周期只有可能是1 10，并且都是0 1 10 到更好 ，拆点以后，就可以用普通的 K短路算法了， 每个点的前 K短的路，然后像dijkstra 如果直接这样不停地推直到没法推才停止会超 实上可以再记前K短的到终点的路，如果当前去终点的路已经有K并且这KK并且这KK出的染色边的条数最多1值，为从小到2

23、的幂，如N=1000,M=5000, K=100，其中边数E 最多为着分的大小最大能到299，必须使用高精度，个点上这两个点连一条容量为1，费用为03 话，就要求一个最小的费用流，所有第3类的2 的幂，因此bellmanford 找增广路O(N+M+K)E(E+M+N)，O(N+M+K)个，边最多有 (E+M+N)E 次。给出一个N个节点的图M条边点上放置EMP，EMP 能够覆D 的部分，这里规定不能使两放置 EMP 都有不同其中N=300,M=1000这里1000其实是吓唬人的题目中已经说了两个结点之间最多有一条路径因此M不可能大于。我一开始把图就直接理解成树了这当然是不对的图其实是一个森林

24、。这道题使用的算法是 P，虽然看上去并不难，但不仔细想过的算法是很容易出错的。事实上这道题的P 算法是非常难想到的。规定状态 fij的含义是：离 i 最近的放置 EP 的点是j 时，以i 为根的中最多能覆盖的距离,gij即为实现此距离的最少费用。之所以要加上最近放置的点这一维，是才能满足无后效性，限定才能满足无后效性，限定住 j后，不在 i只要满足它的距离比j到i的距离大，它对i优化，可以优化掉许多无用的状态，即j 到i的距离一定小于等于如果j 到i 的距离大于等于D的话，那么我放一个EMP在i上，AB，我们还需要枚举一下离AC的位置：1：CBC显然也是距离B最近的点（如果存在E，使得E B

25、的CBEA的距离一定也小于C到AC是离A最近的 EMP 放置点 ，那么只需要把 fBC+dABfAC即可。CB C能覆盖到B(dBC=D)CB C能覆盖到B(dBC=D)B的最近点的一种可能是CB 中所有满足下列条件的 EB C，并且 fBE是一个可行状态。如果一个可行点也没有并且也不能是 C，那么这个最小的加入到状态AC中，这里如果 C=A的话最后还要把费用加上A 的费用。这里状态总数 O(N2),每个状态要枚举度数个儿子，但是这里因为是树因此是平摊 还要枚举符合条件的EO(N)，这里枚举的点其实就是在B的 中高度在树优化到 O(logN)。但用线段树实在比较麻烦，并且我一开始用 floyd

26、 来预处理两点间的距离，已经是 O(N3)。因此最终计算状态还是用了 O(N3)的复杂度。但如果嫌时间多的话，O(N2logN)的复杂度也是可以达到的Dhaka 这可能是近年来 Dhaka 赛区最出色的一套题The Dumb 给定一个 32bit 的 unsigned N，需要分成若干个砝码使得所有砝码的重量的和为 且仅有一种取砝码的方法使得取出的重量和刚好为那GYH1 或者左和为 sum，那么可以由左边的这些砝码摆出给定长度为NV给定长度为NV 数组和给出这么一个求R 的公数，数据最多有5000 组1sum 的所有数并且不重复证明了这个以枚举最大的数d(dN)，那么所有不是d 的数的和为d-

27、1,N 便可以表示成 kd-1，也就是说N+1可以表示为kd，问题就可以转化为关于 k-1，设f(x)为x-1，那么 f(x)=sigma(f(d)(d|x,d=a2=a3=.=an)，他的指数表示为 S(x)， 即为 S(a+c)-S(a-1)。这里对于O(NS(x)， 即为 S(a+c)-S(a-1)。这里对于O(N2)。因此总的O(logMaxN3+QN2)logMax是因为 在这里做剩余系中的除法需要用到扩展 因此有个log。4.El 4.El 判断一个有向图是否为 PS-graph.即可以从一条边经 过 若 干 次 double split 操过35000WS了，于是想也许 优美的算

28、法dfssplit 操作。2：若两点间有两条同向的边，那么就进行逆的 然而在具体操作的时候，怎么找到这样的操作是一个问题，在这里我用一个操作列表所有可行的操作，然后每次操作也许能够使图中又多出一些可行的操作，再把这些可行的操作加入到列表中，这里注意plit 的逆操作在时只需要plit 增加的那个中间点，因为随着其他的操作这个点连着的两个点也许会不断的变化，这里可以一下这个点的出入指向的点而double操作的只要那两个点不需要边的标号。每次plit 的逆操作除了删除一个点外，不会影响其他点的度数，因此不会增加新的可行 plit 逆操作，但是会增加 double 的逆操作，这里如何判断是否能增加，

29、的想法是开张所有点到所有点的度数矩阵，但这题空间不允许，所以只能用平衡树来所有的边每次对边来进行删除和查找 ouble的逆操作只能增加新的可行plit操作这个只需要判断dg就可以了。有关正确性的证明：如果 的算法找到一组解了，那么原图 PS-graphPS-graph， 也PS-graph，它必然存在一个可行的逆操作序列可行的逆操作，那么 的算法不会在一开始就找不到逆操作而退出，那么下面就要证明 的逆操作不会使这个图从 PS-graph 变为非PS-graph。 的两点是p 和q，那么p q 中间同向边大于等于两条，p 和 q一定不可执行splitdouble逆操作和p q 中间的这些边产生影

30、响；若这个操作为splitp q 中间的这些边产生影响；若这个操作为split1，split 逆操作不影响度，double 逆操作可能减少一个点的0。因此这个结论是正确的。设原PSgrph 的可行操作序列是it，那么采取的第一个逆操作一定能在it 中找到，它和在它前面相邻的操作的交换是可行的：首先这不会影响到以前的操作，并且它提前一步依然是可行的(它一开始就可行因此无论放在哪里都是可行的)它前面相邻的操作推后一步依是可行的并且这两个操作的顺序不影响操作完以后图中各个点的度数和连到的点，因此后面的操作依然都是可行的。只需把这个操作不断往前交换直到第一位得到一个新的操作序列那么也就是说，进行这个操

31、作以后，依然存在一个可行的操作序列，这也就意味着操作以后的图依然是PSgrph图。算法复杂度 因为是无向边所以每条边要加到treap split，这里split 的5.(Act IV)5.(Act IV)密串长度都为（不2000000含A 到Z。其中，原n 的秘钥生成的，秘钥的每一个元素为 0到25。转换的规律就上，对26取余，从而的字符。当n 小于L也只有 L2 的算是后来想想觉得的确必须要 L2，然后写了个系居然AC 了。这道题主要有200 组数据，然后题目描述其实是说数据大小最大为2MB，因此事实上L 不可能到2000000，估计这里L 最多也就100000 的样子。秘匙是否是不可能的，

32、这里只能 来判断，但是有一个优化如果长度为 k*t 的秘匙是不可行的(这里的t可以规定是质数)那么长度为k的出来，那么就 判断。 判断时顺便可以一个列表 所有当前能惟一确定下求出的值 ，就从列表中删去这个位置，因拉着一条线，CD 拉种操作R S，具体见 SPOJ。给出一个ABCD位置不一定做的，似乎有篇 讲这个问题的，不过我不律:RR=0,SRSRS=R,SRS=0,RS=R(SRS=0O(n)。对应对应，0, fk=0,否则f(k)=2(t-1)那么事实上所有以K为斜边的原始三角形个数 fs(k)其实就是若有K 的约数 d 的 f(d) 之和, 这也可以表达成公式 *(rt*2+1)-1),

33、65 了，首先对于N，把它乘以2 加上1，所得的这就 是 上 面 式 子 中 的 (r1*2+1)*(r2*2+1)*(r3*2+1)*(rt*2+1)，那么怎么样使p1r1*p2r2*ptrt最小呢，首先很显然的是p1,p2,pt 一定是最小的4x+1 的质数那么不妨设它们是递增的那么 r1,r2 rtrk 是 多，N不是很大，因此 应该使t尽量大，也N较小时还是正确的，但当N 多，N不是很大，因此 应该使t尽量大，也N较小时还是正确的，但当N 足够大时会出现问题。就把N*2+1分解质因数，得到一个递减的序列r，那么用前t 个递增的4x+1 的质数当 p，得到的就一定是最小的 K。N*2 可

34、以分成 7 个，而前 7 个 4x+1 的质数为 N 个较小的直角边，这个问题也不好做， 不妨考虑以 K 为斜边的那K 的约数 d 的性质， 知道求以 K 为斜边的原始直角三角形 可以转化为求有哪些 p,q 满足 p2+q2=K。 这样就把 p，q 的范围缩小到32位的 eger，但这样的范围枚举依然是不行的。这里要用到点复数的知识。 先把那些基本的 7 个质数的写成二元组的形 式;5:(1,2);13:(2,3);17:(1,4);29:(2,5);37:(1,6);41:(4,5);53:(2,7) ， 那么碰到两个数相乘时， 如 65=5*13，怎么样由5 13 的二元组来得到655写成(1+2i)(1-2i),13写成 (2+3i)(2-3i)，由(1+2i)(2+3