信息学集训队作业

1、IOI2008 中国国家集训队第二轮作业(截止时间：2008 年 5 月 3 日)：作业提交：r在提交之前请将没有填写的表格删除不要留下大量的空白影响阅读鉴于完整性，一些重要比赛的简单题目也列在表里，这些题目可以不写，但如果碰巧做过，或者有的说明，以节约做，也欢迎写出。表格中已有的“题目大意”和“算法”是对此题的看题时间，可以有针对性的选择自己感的题目研究。填写表格之前不必编程通过测试数据（不少题目无测试数据并且无法提交），但如果已写程序，请注明（包括是否已通过数据），并把代码放到作业附件中。至少要有 50 个通过测试数据的程序。如果表格中没有给出题目大意，填写算法之前必须写出题目大意。由于部

2、分题目有相当的难度，仅靠自己完成的表格需要独立完成写，但是思路可以相互启发。会比较大，希望大家多多交流与。评分仍然兼顾质量和数量，尤其看重态度。如果做的题目难且写的比较详细，那么可以少写一点。表格中的文字量没有硬性规定，但是请记住：这些作业以后是会，留给后辈作为参考的，所以相信大家会自觉的做好榜样 大家都是认真填写的典范。去年 YY 和 QRQ 的表格，另: 这份表格主要是提供作业内容选择上的参考（同时也是准备CTSC 时的训练参考！），欢迎以其他形式提交作业，见附件包中的 readme.txt注：所有写过程序的题目都已用黄色背景色标出，均通过测试数据。1. ACM/ICPC 欧洲赛区部分题目

3、提交：()提示：由于上次已经自行把去年的表格粘贴过来。过 CERC20042006，这次没有写在里面。如果准备填写，请NEERC 2007历届 NEERC 题目和测试数据、参考程序：4043Ants给n 个白点和n 个黑点的坐标，要求用线段把他们连接起来，要求每个白点恰好连接一个黑点，且每个黑点恰好连接一个白点。n=100题意补充：线段之间不能相交，任意三点不共线这道题有许多做法，以下是我认为比较简单也容易实现的方法，用到了分治策略：设 P1，P2，Pn 为白点；Pn+1，Pn+2， P2n 为黑点。采取分治策略寻找序列PlPr中的配对方案(初始时为P1P2n)：1、在PlPr中找出一个最低位

4、置(Y 坐标值最小)的一个点 Pt（如果这样的点有多个，则选取最左边的点），将 Pt 与 Pl 交换。2、将其余点Pl+1Pr按相对 Pl 的极角递增的顺序排列。显然 Pl 与其余点 Pl+1Pr 之间的任何线段是不会交叉的。3、从 Pl 开始寻找一个黑点和白点成对的最小子区间 PlPi(lir)。若该子区间仅剩一个元素，配对结束；否则点 Pl 与点 Pi 配对。这样使得尚未配对的黑点和白点分布在两个子区间Pl+1Pi-1，Pi+1 Pr。4、继续按上述分治策略分别递归求解Pl+1Pi-1和 Pi+1Pr时间复杂度为 O(n2)，空间复杂度为 O(n)4048Fund Management你有

5、 c，但没有。给你 m 天时间和 n 支供你。每天持有的总 lot 数都过 k，且最后一天结束时不能持有任何。第 i 只的一个 lot 是 si 股，且每天持有的 lot 数过 ki。已知每个每天的价格，每天只能买一只 或卖一只 的一 lot，搜索出所有可能持有股的情况，放入 hash 中。设 fi,t为过了 i 天且持有股情况为 t 时最多能剩，做状态压缩动态规划。可以用滚动数组优化空间。最后最多能剩多少钱？c=108,m=100,n=8, k=8,Si=106,ki=k, 0pi,j=10004049Gamen 个人围成一圈，一开始第 k 个人手上有一个球。然后每个人随机往左或往右传球（往

6、右传的概率为 pi，往左为 1-pi）。所有人至少拿过一次球时 结束，最后一个拿到球的人获胜。求第 N 个人的获胜概率。N=50先通过预处理求出当球在 i/j 处时，球先到达 i-1 还是先到达 j+1：用 gi,j,L,L表示球在 i 处先到达 i-1 的概率；用 gi,j,L,R表示球在 i 处先到达 j+1 的概率；用 gi,j,R,L表示球在 j 处先到达 i-1 的概率；用 gi,j,R,R表示球在 j 处先到达 j+1 的概率。可知 gi,i,L/R,L=1-pi，gi,i,L/R,R=pi。因此，可以通过以下递推式求出所有的 gi,j：gi,j,R,R=pj/(pj+(1.0-p

7、j)*gij-1RL) gi,j,R,L=1-gi,j,R,Rgi,j,L求法类似接下来，出当刚好有 d 个人拿过球时，各个状态的概率：用 fi,j,L/R表示刚好有 j-i+1 个人拿过球时，ij拿过球且球在 i/j 手上的概率，也可以通过递推计算：fk,k,L=1 fi,j,L=fi+1,j,L*gi+1,j,L,L+fi+1,j,R*gi+1,j,R,Lfi,j,R求法类似最终的就是 f1,n-1,L+f1,n-1,R注：具体实现时要注意精度问题NWERC 2007测试数据、参考程序：3972Marchofthe Penguins网格上有 n 片荷叶，坐标为(xi,yi)，上面有 ni

8、只企鹅，最多能有 mi 只企鹅能从上面跳走。要求所有企鹅在同一片荷叶上集合，哪些荷叶可以成 为 这 个 汇 合 地点？ 一只企鹅每次最多跳 D 距离。 n=100可以构建如下的网络流模型：把每个荷叶拆成两个节点：ai、bi，并从 ai 到 bi 连一条容量为 mi 的边。当两荷叶 i、j 距离不超过 D 时，从 bi 到 aj、bj 到ai 各连一条容量为的边。判断荷叶 i 是否能成为汇合地点时，从源点 s 到 ak（ki）连一条容量为 nk 的边，从 ai 到汇点连条容量为的边。若最后流量为nk（ki），则表示荷叶 i 可以成为汇合地点。3975EscfromEnemy Territory在

9、一个（0，0）到（X， Y）的矩形网格内有 N 个的点。给定始末两点，要求找出一条路径（路径的所将所有点放入队列，通过一次广搜求出网格中的每个点到最近的点的距离 gi,j。设 fi,j表示从初始位置到（i，j）的所有路径中，距离点的最小距离 fi,j。然后，可以通过最短路算法作状态转移。算出最后结果后，再对符合要求的有边都是水平或竖直的），使得该路径到所有点的曼距离最小。如果有多条这样的路径，选出其中长度最小的。N10000；X、 Y1000所有点的图做一次 bfs，求出最短路。 这样做，时间复杂度为 O(XYlog(XY)。当然，该问题还可以将动态规划改为用二分并 判 断 连 通 性 的 方

10、 法 来 做 ， 时 间 复 杂 度 为O(XYlog(X+Y)。3976Flight Safety海面上有 C 个互不的 Mi 边形陆地。给出一个折线形的航线，折线拐点不超过 N，求航线中离开陆地的最远距离。 C 和N 都不超过 20， Mi 不超过 30。不妨转换一下看问题的角度，求当所有大陆的海岸线扩张多少时才能包含整个航线。因此可以二分 ，判断大陆海岸线扩张 d 时是否能包含整个航线。现在， 可以把所有大陆拆成这样几个图形：原来的那些多边形、由所有顶点扩展出去的半径为 d的圆、由所有边扩展出去的矩形。这样，就只需要判断是否整 线都包含于这些图形即可。3977Summits在一个矩形网格

11、中，每个点都用一个数字表示该点的高度。称一个高度为 h 的点为 d ，当且仅当不经过小于等于 h-d 的点无法到达更高的点（点之间是四连通的）。找出所有的为 d 的点。网格边长不超过 500。按高度从大到小依次处理每个点；处理高度 h 时，用并查集高度大于 h-d 的每个连通块中的最高高度。判断某个点时：只需判断它相邻的 4 个点，若点 t 高度大于 h-d，则查询点它所属连通块的最高高度。若高度等于该点则表示该点为 d 。设网格 n 个点。对于判断和 并查集，时间复杂度都为 O(n)，由于需要排序，所以总时间复杂度为 O(nlogn)。3978Obfuscation一句话，将所有单词的字母打

12、乱（除首尾两字母外），再将所有空格去掉，得到一堆乱码给出大 n 的字典，将乱码翻译成原来的句子。n10000，乱码长度不超过 1000，每个单 词 长 度 不 超 过 100。先预处理乱码中可能出现的所有单词，再做动态规划。预处理时可以预先计算出字典里所有单词除首尾外的其它字母出现次数，这样可以加快比较速度。设 bi,j表示i-ji 是否能为字典里的某个单词。接下来动态规划就很好做了。设 fi表示乱码是否可以从 1 翻译到 i，则 fi=fi or (fk and bi,i-k-1)，其中 i-100ki-1。NWERC2006测试数据、参考程序:3634TheSetStack Compute

13、rAlpha 的 设备只有一个栈，栈的每个单元都只能放置开一个集合表，表里的信息只有增加不会有修改，集合表里的集合的元素就是集合表里的一些集合，每次产生的新的集合都要判断是否在集合表里存在，如一个集合。一开始，栈是空的，在每个操作结束后，计算机就会输出位于栈顶单元的那个集合的势。 Alpha 拥有五种不同的指令，他们的功能如下：PUSH：把一个空集压入栈； DUP：取出位于栈顶单元的集合一遍以后再把两个同样的集合压入栈； UNION：取出位于栈顶单元的前两个集合，然后把它们的并 集 压 入 栈 ； ERSECT：取出位于栈顶单元的前两个集合，然后把它们的交集压入栈； ADD：取出位于栈顶单元的

14、前两个集合，首先取出的记为 S，其次取出的记为 T，最后把 TS压入栈。指令总数 n 2000。果没有，那么就在表里添加该集合，而栈里元素只指向集合表中对应集合。由于最多只有 2000 次操作，每次操作最多生成一个新的集合，因此这样做时间效率还是挺高的。 集合信息时，将元素有序化，时间复杂度可以做到 O(n2)。当然，这道题可以设计一个诡异的 hash 函数来表示每种集合，比较时只比较 hash 函数的值。这样做 RP 高的话也能 AC。3637The Bookcase给出 N（N70）本书的高度（150H 300 ） 和宽度（ 5T30），现有 3个书架，要求将这些书放在 3 个书架，使得

15、3 个书架中，每个书架高度的最大值的总和*每个书架总宽度的最大值，最小。定义 Ft1,t2表示当另两个书架的书的宽度分别为 t1 和 t2 的时候高度之和最小。由于高度已排序，如果 t1,t20，那么后面的书可以任意放在这两个书架上，但如果 t1=0 或 t2=0，那么就需要累加高度。当依次处理第 i 个书架的时候，枚举所有的 t1 和t2，分以下几种情况做动态规划：1、 若 t1=ti，则 Ft1,t2=minFt1,t2,F0,t2+hi（第 i 本书放在 2 号书架，且之前没有书）2、 若 t1ti，则 Ft1,t2=minFt1,t2,Ft1-ti,t2（第 i 本书放在 2 号书架，

16、且之前已有书）3、 若 t2=ti，则 Ft1,t2=minFt1,t2,Ft1,0+hi（第 i 本书放在 3 号书架，且之前没有书）4、 若 t2ti，则 Ft1,t2=minFt1,t2,Ft1,t2-ti（第 i 本书放在 3 号书架，且之前已有书）最后枚举所有的 t1 和 t2，记总的宽度为 S，Ans=min(Ft1,t2+h1)*max(t1,t2,S-t1-t2)时间复杂度 O(NC2)。（C 为总宽度）3641Leonardos Notebook给定一个 A-Z 的排列 P，求 P 是否有可能是 ABCDEF.YZ经过 2 次同一排列 M 做 2 次替换加密得到的结果。可以用

17、置换群做：将每次加密的过程看作一个置换 F。如果没告诉你密文经过 2 次加密，那看上去和只经过一次加密后的置换G 没有区别。问题化简为：是否存在置换 F2=G。显然，每个循环可以单独处理，于是可以得出以下算法：找出 G 中所有的循环，若对每种长度的偶循环个数都为偶数则存在 F 使得 F2=G，否则不存在。NWERC 2005测试数据、参考程序：3408Unequalled Consumption有不超过 n(n5)种重量为wi(wi10)的糖果（不同的糖果可以有相同重量），给一个整数 P1015，要求一个最小的重量 w，使得做一个重量为 w 的糖果盒的不同方法数至少是 P。不妨用生成函数解决该

18、题。n 种糖果，重量分别为 w1,w2,w3,用生成函数中 xn 项的系数表示做重量为 n 的糖果盒的方法数，那么 对 应 的 生 成 函 数 就 是 ： f(x)=1/(1-xw1)(1-xw2)(1-xw3)。这个形式是没有办法直接利用的，因为里面三个因子的展开式都有无穷项，要直接找系数的通项公式也不容易。但是利用一个简单的技巧就可以解决这两个问题。为描述方便，不妨设 n=3,w1=2,w2=3,w3=5，则 g(x)=(1-x30)/(1-x2)(1-x30)/(1-x3)(1-x30)/(1-x5) ，h(x)=1/(1-x30)3，f(x)=g(x)h(x)。这样，g(x)是一个一般

19、的多项式，h(x)虽然有无穷项但形式很规整，f(x)只是 g(x)和 h(x)的乘积。g(x)只需直接展开即可，展开的结果是一个次数小于 3*30=90 次的多项式。对于 h(x)，为方便起见，作一个换元，记 h(y)=1/(1-y)3。通过计算可以知道 h(y)中 yn 项的系数为组合数 C(3-1,n+3-1)，其中的 3 就是 h(y)的 式中 1-y 的次数。因此 h(x)中 x30n 的次数也是 C(3-1,n+3-1)，而其他项的系数都是 0。综合上面的，可以得到计算 f(x)中 xn 项的系数的方法。记 p(x)中 xn 项的系数为 c(p,n)。对于 n90， c(f,n)可以

20、直接利用动态规划或者限制次数地直接展开 f(x)得到。对于 n90，记 n=30k+r，其中 0r30，那么根据 f(x)=g(x)h(x)，有以下公式 c(f,n)=C(2,k+2)，c(g,r)+C(2,k+1)c(g,r+30)+C(2,k)c(g,r+60)。和 f(x)直接相关的计算已经基本解决。剩下求最小 ，方法还是二分法。虽然从整体看，c(f,n)关于 n 不一定是单调的，但是假如把 n 写成 n=90k+r，其中 0r90，就可以发现对固定的 r，c(f,90k+r)关于 k 是单调的。因此只需枚举 r，对 k 应用二分法，然后从所有候选的 n=90k+r 中选取最小的即可。参

21、考资料：http:/user2/frkstyc/archives/2006/11 80760.shtml3415Guardianof Decency有 N 个人，已知它们的身高、 、喜欢的音乐、喜欢的体育活动。假设这几种人之间不会产生恋爱关系：身高差超过 40cm；同性；喜欢不同的音乐、喜欢相同的体育运动。从这些人中选出最多的人，使它们之间不存在可能发生的恋爱关系。 N500把所有人根据 分成两组，建立二分图匹配模型：如果两人之间可能发生恋爱关系，则连边。最后就是求二分图的最大独立集。在二分图中，最大独立集=最小覆盖集的补集=总点数-最大匹配数。时间复杂度为 O(N3)。SEERC 2006历

22、届 SEERC 题目和测试数据：2659Sudoku编程求解 4*4 的 Sudoku（ 保证唯一）。搜索到一个状态后，用“唯一数法”和“一数法”确定所有能够确定的状态。“唯一数法”指这个格子只能填某个数字；“一数法”指除了该格子外，该行/列/子矩阵都不能填某个数字。然后先搜索可能解数量小的格子，以减少搜索树的度。2682Sherlock Holmes有 n 个 box，每个里面有Wi 个白球和 Bi个黑球，每个 box 都满足 Wi+Bi=m。把这些 box 分成两组各 n/2 个 box，使得有一种颜色的球在两组里都占多数。设这个颜色的球在两组的百分比分别为 m1 和 m2 ，要求 m 1

23、,m2尽量大。 n,m=10000只想到了随机调整的算法。先把所有球随便分成两组，然后随机取出第一组中的一个球，放入第二组，再在第二组中取出一个球放入第一组使得放好后情况最优。2911um已知 整数 m(m 2000)、p12 为偶数、a、b，求实数 x1,x2,xm 满 足令 y=x/sqrt(a),则-1/ay0 则先取 b 个y 为1，否则取 a*(-b)个 y 为-1/a，剩下的 y 的和为 0,则取 1出发，一直往左走，经过一些点到最右边的点 B，再一直往右走，经过一些点到达 A。求如果需要经过所有点所需走过的最短距离。状态转移方程为：边界条件：f2,1=dis1,2对于每个 fi,

24、j (ij)：fi+1,jfi,j+disi,i+1fi+1,ifi,j+disj,i+1最后结果为：minfn,i+disi,n时间复杂度：O(n2)3306Mothy平面有一些多边形区域，它们是不可到达的。求从某点到另一点的最短路。把多边形的顶点及始末两点看做图中的节点。若某两节点连成的线段不在多边形内则连边。最后直接求单源最短路即可。判断线段是否在多边形内是一个经典算法，这里不在细写。3308Computer Transformations数串初始为 1，每次变化后，0 变成 10， 1 变成 01。问经过 n次变化后有多少个 “00”。n1000序列中所有 00、01、10、11 的出

25、现次数。可以在 O(n)的时间内求出所有。要用到高精度计算。SEERC 200327552756Hidden PasswordCrazy tea party一个长度为 L 的由小写英文字母的字符串，可以向左循环 L 个字符串， 从 0 开始编号。求这些字符串中最小的，最小是几号。若 ai.i+k=aj.j+k，但 ai+k+1aj+k+1，当 ai+k+1aj+k+1时，i . i+k+1 也都不可能是所求的解。基于上述想法， 可以 两个指针 i，j，从左往右扫描。由于两个指针都只往右移动，且移动数和比较次数一致，因此其时间复杂度是线性的。n 个人围成一圈。每分钟内可以将相邻两人交换。问最少需

26、要多长时间，才能颠倒相邻关系（即原来左边的人到了右边，原来右边的人到了左边），n32767这个题容易找出以下规律：设s(u)，生产了一些能量 p(u)pmax(u)，消 耗 了 一 些 能 量 c(u)mins(u),cmax(u)，出 d(u)=s(u)+p(u)-c(u) 的能量。所有节点被分为三种：能量站、消费站、发报站。能量站的 c(u) 必须为 0，消费站的 p(u)必须为 0 ， 发报站的p(u)和 c(u)必须为 0。有向边可以传递一定的能量 l(u,v) lmax(u,v)。求c(u)的最大值。一条容量为 cmax(u)的边。最后求整个网络的最大流即可。SEERC 200225

27、10Beer Land求一个 n 边形，连接所有对角线后，最大交点个数当 n3 时：交点数为 0否则：当 n 为奇数时，每条边最多与 n-3 个边交叉，所以交叉点最多是2516Sly NumberSly Number 定义为全由 0、1、2 组成的数组 A0.N-1；一个特殊的 Sly Number “ONE”为 A0=1，A1.N-1=0；定义乘法 运 算 为 Ck=SWERC 20053503Bin Packing将 n(n105)个大小已知的 item 放入大小固定的 bin 中，每个bin 中最多放入两个 item。问最少用几个 bin？可以用贪心做。将所有 item 按大小排序，每次

28、找一个最大的 item 和最小的item，若能一起放入 bin 中，则一起放入，否则只放入大的那个 item。如果用两个指针去模拟这个贪心过程，时间复杂度为 O(n)，总时间复杂度为 O(nlogn)。3505Buy or Build在一个平面图中，有8)个选择，可以使一定数量的点互相连通，每次选择需要一定的费用。此外，还可以直接在任意两点间连边，费用为平面距离的平方。求使所用点都连通的最小费用。先对原图求最小生成树。可以证明，当选择决定后，剩下的要连的边一定可以在最小生成树中。接下来，只需枚举每个选择是否需要，再用类似 kruskal 算法，从小到大不断对剩余图加边并判圈。若用并查集，该操作

29、时间复杂度为 O(n)。故总时间复杂度为 O(n2+2qn)。35064 Values whose Sum is 04 个 n(n4000)元集 A、B、C、D，问一共 有 多 少 个 数 对（ a,b,c,d） （ A,B,C,D ）， 使得a+b+c+d=0？分成两组，每组 n2 个数。第一组为 A、B 中两集合各取一个元素的和，第二组为 C、D 中两集合各取一个元素的和。然后第一组从小到大，第二组从大到小，找出 Ai=-Bj 的所有情况，两个指针统计一下，就是最后的解。空间复杂度为 O(n2)，时间复杂度为 O(n2logn)。3507Keep the Customer Satisfie

30、d有 n 个工作，每个工作需要时间 qi 和截止时间 di。问最多能接受多少个工作？n800000。可以证明以下命题：存在一最优解，中间所有工作顺序按截止时间排序。于是得到一个贪心策略：尽量接受花费时间少的工作。具体实现方法如下：将所有工作按截止时间排序，依次处理各工作。一个最优解的工作序列，对于工作 i，若能加入该序列，则直接加入。否则如果存在序列中某个工作 j的所需时间 qj 大于 qi，则将 i 替换j，得到一个更优的工作序列。直接模拟上述操作，总时间复杂度为 O(n2)。若用二叉堆来 接受的工作序列，则时间复杂度降为 O(nlogn)。3511Consecutive ones在一个矩阵

31、中，所有数都是 0 或 1，交换列的顺序（第一列固定），使得每行的 1都是连续的。矩阵边长不超过 400。没想到什么好的算法，写了个搜索程序，就过了。2. ACM/ICPC 亚洲赛区部分题目提交：()提示：有很多题目无法提交。这些题目只需要读题(对于我已经给出题目大意的题目最好也重新读题以了解细节)、思考算法并在表格里写出，并不需要写程序。4039Sightseeing无向图的中国邮路。2=|V|=100, 1=|E|=4950, w=1000经典算法，具体实现方法如下：1.如果Taipei 2007一套比较难的题目，思考蓝题和红题（均无人通过），其他题意义不大4035Undetectable

32、 TourN*N 网格上有 k 个监视器，每个监视器能发现 Manhattan 距离不超过 d 得所有东西。所有监视器得 d 相同。给出 d 的分布概率（每个取值的概率，最多 m 种取值），求左下到右上存在监视不到的路径的概率。 k=300, N=10000,m=100将所有的 m 种取值从小到大排序。二分 ，求出存在监视不到的路径的最大可能取值 f。最后 就是所有满足df 的取值的概率之和。在已知 d 时，如何判断是否存在监视不到的路径呢？需要建立图论模型：把每个监视器看作一个节点 ai，附加两点 s，t。如果第 i 个监视器距离左边界或下边界小于等于 d，则 s 和 ai 之间连一条边；如

33、果第 i 个监视器距离右边界或上边界小于等于 d，则 t 和 ai 之间连一条边。如果两个监视器 i 和 j 之间距离小于等于 2d，则在 ai和 aj 之间连一条边。之后就只要判断节点 s 和 t 的连通性，若不连通则表示存在监视不到的路径。时 间 复 杂 度 为 ：O(k2logm)4036Uggla Mis给 k 个整点，找一条穿过点数尽量多的直线。k=1000枚举任意一个点，将其它点与该点的连线按极角排序，再扫描极角相同的直线个数。时间复杂度为 O(k2logk)。的顶点集；3.求出Problem要求用最少的时间完成所有任务。任务可以并行完成，但必须满足一些约束，用有向和无向来表示。A

34、B表示 A 必须在 B 之前完成，AB表示 A 和 B 不能在同一天完成。本题给出的约束图都是给一棵树的某些边定向后得到的。题目种给出了一个定理：设由有向边组成的最长路长度为 k，则 为 k 或者 k+1。 N=200出 k。接下来只需判断 为k 时是否存在一组解。用状态 fi,j表示节点 i 的值为 j 时，以节点 i 为根的子树是否存在。可以很轻易的将状态转移时间降为 O(1)。这样总的时间复杂度为 O(nk)。Taipei 2005一套不错的题目，比较平衡。3347Dome of Tuxville给 n 个建筑物的平面坐标(x,y)和高度 h，找一个底面在地上的半球，覆盖所有建筑物。建筑

35、物看成垂直底面的无限细的棍。N=30可以证明选出的半球一定符合如下两个条件之一：某 3 个建筑物的最高点都在球面上；某 2 个建筑物的最高点都在球面上且球心在两个建筑物平面坐标的连线上。这样，枚举 2/3 个建筑物，然后在 O(n) 时间内判断是否符合题意。总时间复杂度为 O(n4)3350Verifying Experimental Data给无自环的多重有向图，求有多少条 边 至 少 在 一 个 有 向 圈 内 。 N=1000,M=10000通过 dfs 预处理求出任意点对 i、j 之间是否存在从 i 到 j 的路径。最后查看每条边，假设从 i 指向 j，若 j 到 i 存在路径，则表示

36、该边在一个有向圈内。时间复杂度为 O(n2)3353Optimal Bus Route Design给 n 个点的有向带权图，找若干个圈，每个顶点恰好属于一个圈。要求总长度尽量少。注意即使(u,v)和 (v,u)都存在，它们的长度也不一定相同。N=100可以建立最小费用最大流模型：将每个原图中的顶点，拆成两点 ai,bi。对于原图中的每条边(u,v)，从 bu 到 av连一条容量为 1，费用为边权的有向边。从源点到每个 bi、从每个 ai 到汇点都连一条容量为 1、费用为 0 的边。最后只需要求出最小费用最大流。若最大流为 n，则存在解，且总长度为最后的费用。Kaohsiung 2003281

37、5Tiling Up Blocks有 n 个箱子，每个箱子都有两个参数，若一个箱子的两个参数都大于等于另一个如果没有参数大小限制，该题只能这样做，按一个参数排序，再做动态规划，其中可以用一个栈来 决策的单调性，状态转移时使用二分查箱子对应的两个参数，则可以放在它下方。问最多能叠放多少个箱子。n 不超过 10000，两个参数不超过 100。找去寻找最有决策。时间复杂度为 O(nlogn)。但其实该题还有一个更简单的方法：直接把两个参数的所有可能组合作为状态。状态数只有 100*100=10000 个。而状态转移时间只需 O(1)。2818The Geodetic Set Problem给出一张图

38、，节点数 n40。接下来给出一些询问，询问一些节点 集 合 是 否 geodetic。节点集合 geodetic 定义为图中所有节点都在该集合中某两节点间最短路上。预处理求出图中任意两节点间最短路。对于每个询问，判断某节点是否在集合中某两节点间最短 时，可以枚举集合中的任意点对 (u,v)，然后判断 dis(u,v)是否等于 dis(u,w)+dis(w,v)。Seoul 2007 (第 1 名 8 题)无数据，因此只需要填写表格即可，不必写代码(如果以前有写，请附在作业里)3901Editor给字符串 S，求至少出现两次（可以）的最长连续字串。S 不超过 5000 字节，均为小写字母二分长度

39、，用 hash 表记录所有出现过的长为的子串，并判断有否重复出现。最坏情况可能比较慢，但期望时间复杂度为 O(LlogL)，L 为串的长度。3902Networkn 结点的无根无权树上已经有一个 server。再放尽量少的 server 使得每个叶子到最近 server 距离不超过一个给定的 k。N=1000该题存 性算法。将距离服务器小于等于 k的所有点删去，这样原来的树就被拆成了几棵树，对每棵树都按如下方法做树形动规：从下往上标号，叶结点都标-k，表示离它距离在 k 以内必须设置一个服务器。如果一个点的标号为正数 i，表示距离在 i 以内已经至少有一个服务器。如果一个点的标号为-i，表示距

40、离 i 以内至少还要建一个服务器。父结点的一个标号=子结点标号+1。如果一个点从子结点推出的标号有正也有负，只要保存正数的最小值和负数的最大值，即绝对值最小。例如是（-i，j），如果 k-i=j，则都覆盖到了，此点就标 j；否则，此点标-i。如果标号是 0，就表示一定要建服务器了。如果标号大于了 k，就改为-k。最后如果树根标号为负，则要加一个服务器。3905Meteor给一个矩形照相机，还有 n 个流星的初始位置和速度，求能照到的流星最多的时刻。n=100,000将所有流星进入照相区域和走出照相区域的时间都算出，然后将所有事件点按时间排序后扫描一遍即可。3907Puzzle给 s 个不能出现

41、的 子串，求不包含它们为连续子串的最长串（可能无限长）。s=1000，每个子串不超过 50 个字符。将所有子串 到 trie中，建立 trie 图。于是问题就转化为再 trie 图中找最长路径（或圈），这一步只需一次 dfs。由于 trie 图的建立时间和输入规模一致，因此总时间复杂度为 O(sL)，其中 L 为子串长度。Seoul 2006无数据，因此只需要填写表格即可，不必写代码(如果以前有写，请附在作业里)3604Travel给一个 N 个点的无向图，其中两个边是景点，还有 F 个“经过时需要交买路钱”的边。是否可以找到一条 两个景点但不经过任何“需要交买路钱”的边的回路。任何边或点都不

42、能经过两次，但回路经过的 结 点 和 边 没 有 其 他 限 制 。 N=1000。设两个景点对应的边分别为(a1,b1),(a2,b2)，“忽略”那些需要较买路钱的边，及景点对应的两条边。于是问题转化为问点对(a1,b1) 到点对(a2,b2)是否存在两条不相交路径。我们可以建立网络流模型解决这个问题。将每个点 i 拆成两点 Xi， Yi。若存在边(u,v)且没被“忽略”，则从 Yu 到 Xv、Yv 到 Xu各连一条容量为 1 的边。从源点到a1 和b1 各连一条容量为 1的边；从 a2 和 b2 到汇点各连一条容量为 1 的边。最后只需判断是否最大流为 2 既可。实现时，只需从源点到汇点做

43、两次 dfs（或 BFS）既可。时间复杂度为 O(n2)。3606Gas给 n 个线性函数 fi(x)=aix+bi，求出一组整数 xi 满足 x1+x2+xn=M，且所有 fi(xi)都相等。例如 3x+5, 4x+3和 1x+7 当 M=27 时 存 在 解设所有 fi(xi)。枚举的值并判断。情况下，时间复杂度为 O(N(maxaiM+maxbi)，3608Period二分 k，然后做动态规划判断 k 近似周期是否可行。状态为 fi,j，表示 x 串的第 i 位配 y 串的第 j 位所用的操作次数。状态转移方程如下：fi,j=两个串的编辑距离为进行的修改、删除和操作次数的最小值（每次一个

44、字符）。如果 x 可以分成若干部分，使得每部分和 y 的编辑距离都不超过 k，则 y 是 x 的 k-近似周期。给出 x 和 y，求最小的 k 使得 y是x的k- 近 似 周 期 。 如x=abcdabcabb, y=abc, k=1。|y|=50,|x|=5000 x1=6,x2=5,x3=16，但 M=26 时无解。 N20,0ai=10,0bi=1000, 0M10000实际的效率要好得多。有偶数个 时要判断两个数）即可。由于取中位数的算法是线性的，因此时间复杂度为 O(n)。3231Fair Share需要把 M 个任务分配给 M 个处理器。每个任务有两个候选处理器，可任选一个分配。任

45、何两个不同任务的候选处理器不全相同。要求所有处理器种分配任务最多的任务数尽量少。1=M=10000设为 k。可以建立网络流模型：从源点到任务连一条容量为 1 的边；从每个任务到两个候选处理器各连一条容量为 1 的边；从每个处理器到汇点连一条容量为 k 的边。接下来，需要选择最小的 k 使最大流为 M。下面将两种实现方法：二分 k 的值，再做网络流判断，时间复杂度为 O(kM2)。由于实际情况下，网络流的效率远比 O(M2)好，所以该算法还是不错的。初始设 k 为 1。找增广路（DFS 和 BFS 均可），若找到则增广。否则判断总流量，若为 M 则停止，否则 k+1，并继续找增广路。最后，一共需

46、找 M（找到的）+k（未找到的）=M+k 次增广路。又 kM，因此，总时间复杂度为O(M2)。该算法的实际效率也相当不错：若能找到增广路，速度一定很快；而 k 又不会太大，因此找不到增广路时所花费的时间也很少。3232Weak Key给 k 个整数组成的序列 Ni，判断是否存在四个整数 Np,Nq,Nr 和 Ns（ 1=pqrsNsNpNr 或者 NqNsNpNr。 4=k=5000枚举 p，移动 s 指针并维护 p+1 到 s-1 之间的最大最小值，并判断。时间复杂度为 O(k2)。Taejon 2002 (POJ 可提交)2527Finding Liars有 n 个人，有的是 true-l

47、er 总说真话，有的是 liar，有时说真话，有时说假话。现在让他们进行循环测试，即 a1 测试 a2 是否为 liar，然后告诉你一个 b1（1 表示是，0 表示否）， a2 测试 a3，an 测试 a1。假设测将每个人看作两个节点， Xi 表示说真话，Yi 表示说假话。若 ai 说 aj 是 liar，则它们中必有一个是 liar，从 Xi 到 Yj、Xj 到 Yi 各连一条有向边；试总是能成功进行，只是只有 i 是 true-ler 时结果 bi 才一定是真的，否则 bi 不一定是真的。给出 liar 数的上限，找出所有一定是 liar 的人。 n=1000若 ai 说 aj 是 tru

48、e- ler，且 ai 是 true- ler，则 aj 也是 true- ler，从 Xi 到 Xj 连一条有向边。接下来就转化为求解 2SAT 了。求解 2SAT 后， 分别处理各个连通分支。判断是否一定是 liar 时，假设它是 true- ler，再令其它连通分支中的 liar 最少，看看是否超过 liar 数的上限，若超过，则表示此人是 liar。2531The K-League有 n 支队伍进行比赛，每支队伍需要打的比赛数目相同。每 赛恰好一支队伍胜，另一支败。给出每支队伍目前胜的场数和败的场数，以及每两个队伍 下的比赛场数，确定所有可能得冠军的球队（获胜场数最多的得冠军， 可以用

49、并列）。N=25可以枚举每只队伍，判断是否有希望夺冠。首先，这个队此后的比赛自然是赢越多越好，所以先让这个队把以后的比赛都赢下来，算出这个队最高能拿多少分。下面关键就看是否有可能让其他队的积分都低于刚才计算出的最高分。 可以建立网络流模型：建立一个网络，所有的球队作为图中的节点，每两个队之间的比赛也作为图中的节点。从网络的源各连一条边到 “比赛的节点”，容量为两队间 的比赛场数。从“每个队的节点”都连一条边到网络的汇，容量为这个队当前的积分与最高分之差。如果一个 “比赛的节点”代表的是 A 与 B 之间的比赛，那么从这个节点连两条边分别到“A 队的节点”和“B 队的节点”，容量为无穷大。如果这

50、个网络的最大流等于所有还未进行的比赛的场次之和，那么需要判断的那个队抗有可能夺得冠军。Japan 20073884Minimal Backgammon在一个N个格子的1D 棋盘上玩一个色子 （掷几点就走几步），求恰好 T 轮成功（走到 Goal）的概率。用状态 fi,j表示 i 轮走到 j 的概率， 状态转移时间为 O(1) ， 所以总时间复杂度为棋盘上有的格子会有“停一轮”或 “回到起点”的格子。 N=100, T=100O(NT)3887Slim Span给一个 n 结点的图，求 slimness（最大边减最小边的值）尽量小的生成树。N=100将所有边排序， 两个指针，指向最小最大边。移动

51、左指针的同时，移动右指针以保持整个由可行边的图连通。由于边权最多 O(n2)种，每次判断连通的时间复杂度为 O(n2)，所以总时间复杂度为 O(n4)。3888TheMorning afterHallonw*h 网格上有一些（最多 3 种）小写字母（鬼），分别移动它们对应的大写字母里。每步可以有多个时移动，但每步结束之后任何两个鬼不能占用同一个位置，也不能在一步之内交换位置。所有空格连通，所有格连通。任何一个 2*2 子网格至少有一个格。w,h=16。用每个鬼的位置表示状态做双向广度优先搜索，并用 hash 判重。状态转移时可以枚举各个鬼的移动顺序后再做状态转移。Japan 20063624E

52、njoyable Commuionn 结点有向简单图中的简单 k 短路（结点不能重复经过）。路径长度相同时按照字典序排列。 n=50, k=200,不妨将题目转化为判断问题，判断是否存在 k 条长度不大于 ans 的路径。由于 k 比较小， 不妨采取搜所策略。我使用的是启发式搜索算法。当搜索到某个状态时，做 dijkstra 求出所有未走过的点到终点的最短距离 di。设当前位置的节点为 u，则按照 dis(u,i)+di 从小到大依次扩展状态，若当前已走过的距离加上 dis(u,i)+di已经超过了 ans，则不继续扩展。应该以什么顺序来枚举 ans 呢？一开始我使用了二分查找。后来我采用了倍

53、增思想：依次倍增 ans 的值，直到存在 k 条路径，再二分求解区间ans/2,ans。发现速度是原来的 1.5 倍左右。Japan 20053399SumofConsecutive给出 2 到 10000 中的一个数，问有多少种方法，使它能被分解为几个预处理求出所有 2 到10000 内的素数，统计所有连Primbers连续素数的和？续的素数和中 2 到 10000 的出现次数。时间复杂度为 O(n2)，其中 n1300 为 2 到 10000 内的素数个数。接下来就可以在 O(1)时间内回答每个询问。Japan 20032796ConcertHall Scheduling你有两个房间，有

54、n 个预定请求 (i,j,w)，表示打算从时间 i 到 j 租用一个房间，出价为 w。接受一些请求使得总收益尽量大。注意时间有的请求不能占用同一个房间。n=1000该题虽然可以用最小费用最大流来解决，但由于房间只有两个，存在一个时间复杂度为 O(n2)的动态规划算法。将各个请求按 j 排序，依次处理。设 fi,j为当一个方间的最后请求的标号不超过 i、另一个方间的最后请求的标号不超过 j 时的最大收益。状态转移方程如下：NEXT(NEXT(.)=V 为止。这时就求到一个环。每个环都代表一个多边形（虽然可能有重复，但无所谓），接下来只需判断点是否在其中一个多边形中即可。Beijing 2006近

55、年来最难的 Regional 之一，命题者都是以前的 IOI 国家集训队员3660Robot有一个 N*M 的场地，每一个格子中站有一个机器人，每次可以给每个机器人发出如下 4 种指令之一：NORTH、SOUTH、 EAST、WEST, 即令所有机器人往相应方向走一格，如果一个机器人在执行某一命令后走出了场地，则它会立即炸毁。给出四种指令的总条数, 求一种指令顺序使得所有机器人执行 令总数最大。（炸毁的机器人不再执行命令）。N,M,Cx R，U D，先沿 LR 方向移动，那 么 移 动 的 策 略 就 是 LRLR LLL UDUD UUULULU。关键在于确定 LLL的次数，由于其他的计算可

56、以都做到 O(1)，因此可以直接枚举次数。3661Animal Run在一个网格中每个 方格都带一条从左上到右下的对角线. 删除权和尽量小的边集 , 使得左上到右下没有通路 。 N,M=1000原题是求最小割，可以将平面图转换成其对偶图，再做最短路。具体方法如下：先构建对偶图：原图是平面图，所有平面是新图中的点，两个平面相邻的边是新图中连接两个点的边。新增源点 s、汇点 t，若原图的某平面为上（下）边界或右（左）边界的一部分，则与 s（t）连边。最后求 s 到 t 的最短路即可 ， 时 间 复 杂 度为 O(NMlogNM)3662Another Minimum Spanning Tree平

57、面 点 集 P 给 成 完 全 图 , 权 w(i,j)=|xi-xj|+|yi-yj|, 求最小生成树。提示：存在一个 MST 使得每个点 A 最多与 A 的右方与右上方所夹 45 度区域内的一个点相连。N=X,Yi=Y，所以只需找 Xi+Yi 最小的点（这里可以用树状数组）。这样就可确定出 045 度中的那个点。其它七个方向可以通过类似方法得到。3663Connect It, If You Can!给出 2n*2n 的网格, 是否存在一条线段或者恰好一个拐点的折线, 连接两个给定格子的中心, 但不穿越任一 的 . 线段/折线不能与大圆(与网格中心重合,半径为 2n)相交, 但拐点可以在圆上

58、. 最多 400个非空格子。N=50枚举两点，判断是否能直接相连，且不经过任何黑格。枚举所有这些连线中的两条，判断交点是否小于这两条线最长能延伸的长度，并且在圆内。如果可以，则找到一个解。3664Guess有 n 位选手参加编程比赛. 比赛有三道题目, 每个选手的每道题目都有一个测试之前的预得分. 如果某道题目未通过测试,则该题得 0 分, 否则得分等于预得分. 得分相同时 ID 小的排 面.给出所有 3n 个得分以及最后的实际名次,问是否可能. 如果可能，输出最后一名的最高可能得分。N=16384不妨采用贪心策略：让每个队的分数尽量大，但是又不超过前一个人的分数。注意精度问题，最好转化为整数来处理。3665XAR机器XAR08 有若干8 位寄存器, 可以8 位无符号整数, 支持四种操作：1. X n (0=n256), 即 V = V XOR n2. A