国家集训队作业1

1、IOI2007 中国集训队第二轮作业(截止时间：2007 年 4 月 30 日)：作业提交：r, liurjmail本次作业主要为算法讨论。注意：所有表格的各列都是：题号、题目名称、题目大意（如没有填写或者觉得写得不够详细则请大家写算法时请补充完整）、算法讨论/说明。最果后一列在填写时应先删除的说明文字。请选择至少 50 道表格中的题目（表格中需填写详细内容），提交带注释程序(Commented Program)。本文档很长（50 页），但并不是所有表格都需要填写。事实上，只有小部分需要填写。之所以有这么长的表格主要是提供一个做作业的灵活性，而题目大意也是给没有做过这些题目的同学为选择题目提供

2、便利。第一部分 算法讨论题目为推荐（但不是必须）讨论。鉴于完整性，一些重红色题目至少需要写一半。要比赛的简单题目也列在表里，这些题目可以不写，但如果碰巧做过，或者有做，也欢迎写出。表格中已有的“题目大意”和“算法讨论”是对此题的说明，以节约同学们的看题时间，可以有性的选择感的题目研究。填写表格之前不必编程通过测试数据，但如果通过，请注明。由于部分题目有相当的难度，仅靠完成的会比较大，希望大家多多交流与讨论。表格需要完成写，但是思路可以相互启发。1. ACM/ICPC World Finals 2002-2006 (10 红 21 蓝)部分题目提交：()简介：有不少有启发意义的题目，不卡时间，值

3、得讨论。另外不少的题目的细节比较关键，看上去比较简单但实际上并不容易通过。World Finals 20063561LowCost Air Travel给一些机票信息与旅行安排，求花费最小的方案。最短路，但是容易想错3562Remember theALa Mode!计算冰激凌派的最小和最大销售额费用流3563Ars Longa由球关节连接的轻杆系统是否静止、稳定判定平衡的问题已经很好的解决，时间复杂度、正确 性和编程复杂度都很好。但是，稳定性的判定，我暂时没有想到好的办法。如 果稳定是指附加一个力，仍然平衡的话，WC 的那个方法应该是对的吧，只要 XYZ6 个方向都加个力试下就可以了，O（N4

4、）的。我试过这种算法，没 TLE， 是 WA。如果不是精度问题，或者我写错的话，就是稳定性理解错了。物理上，稳定还有另外一种理解（和重力势能有关）：对此，WC 期间那个任意加一个力，方程组是否有解的方法是错的：比如把某铰链看成一个吊钟，被一个轻杆垂直连接，竖直地吊着；此时，任意给一个水平的力，方程显然都是无解的，但此是稳定的。因此，不难想到一种物理上经常用到的 稳定性的方法：对于任何微小的扰动， 整个系统的中心是否下降，如果有下降，那么系统是不稳定的；如果系 统的重心不论怎么动，只会上升的，那么系统是稳定 的；如果系统对于某一扰动重心不变，那么这个系统 是随遇平衡的（也就是扰动一下，系统就动一

5、下，扰 动停止，系统就马上又静止，比如光滑水平面上的一 个球，它是随遇平衡的），这种情况在题目中，应该也属于平衡的状态。3564Bipartite Numbers给出 n，求最小倍数使得它只包含两个数字比较有启发意义的数论题3565Bit Compressor给一种不可逆的压缩方法， 给定压缩后文本与压缩前的长度与 1 的个数，是否可以解压缩动态，理论上状态比较多但实际用到的很少。有 的同学可以仔细研究一下。3566Building Clock给出一些不同类型的齿轮和无限量的轴（其中一个的转速恒定），要求让两个轴的转速分别等于时针和分针。每个轴上最多三个齿轮。细节不知道哪里处理错了3567Pi

6、lgrimage一些人去朝圣，途中有人离开或者加入，每次需要分钱时总钱数恰好都是人数的整数倍，求原先的人数可能值一道看上去比较迷惑人的题3568Pockets把n*n 纸片折叠成1*1 后统计 Pockets 的个数我将每个正方形的信息都储存下来了，总的复杂度是 O（N3）的，想起来感觉很简单，正确性很显然， 程序也很好写，但就是 WA。YEAH！REJUDGE 了，AC 了，正确率有 90%，看来这题不应该红的3569Degreesof Separation求出无向无权图最短路的最大值简单题，不用写了。3570Routing给出有向无权图，求出点 1到点 2 与点 2 到点 2 的两条路，使

7、得包含的总结点数尽量少。World Finals 20053269Eyeball Benders给出由水平垂直线段组成的两幅图， 第一幅是否为第二分局部放大得到。至少有一个端点同时出现在两幅图中。枚举匹配的点 N2，难点就是找出比例 K。首先，为了方便起见，我对所有的线段，以及线段的 端点都进行了排序。事实证明，这是很明智的，否则 后面写 if 很有可能写到疯狂。并且，排序以后，最后的匹配就成了 O（N）的，否则要 N2，感觉此题 N4 是要 TLE 的（N = 2*50 = 100）。方法找 K 是 O（N）的，最后匹配时先做一个排序 O（NLOGN），然后 O（N）看一次（有特殊情况，程序

8、里面有说明，不影响总的时间复杂度），所以总的复杂度是 O（N3LOGN）。为了方便，我默认枚举的匹配点是横线的端点，一次 搞好以后，对两个图都旋转 90 度，重新排序，再检查一次，就等于横线竖线都枚举到了。确定 K 分 4 个情况：1、 PUZZLE 中除了枚举的点，还有其它的点，肯定是某线段端点。此时，寻找枚举点到该点的射线 上离枚举点最近的点，并寻找 SOLUTION 中同斜率射线上离枚举点最近的点，既可知道 K。2、 否则，如果 PUZZLE 中有不经过枚举的点的直线（可以证明，该直线必定是极长的、顶牢边框的）。 此时，找到这样的直线中，离枚举点距离大于 0 的最近的直线，与 SOLUT

9、ION 中离枚举点最近的直线做对比，就可以得到 K。3、 否则，如果 PUZZLE 中只有一条线段。不用确定K，直接看 SOLUTION 中有无直线就可以。4、 否则，PUZZLE 只可能剩下一种情况，2 线段， 竖线经过横线枚举的那个端点。也不用确定 K， 只要看 SOLUTION 中有无横线与竖线相交即可。3270Simplified Network总是连接到最近的基站。给出起点和终点，求更换 网络次数最少的路线。从概念上要先求 Voronoi 图，但实际上不需要显式的把它表示出来。3271The Traveling Judges Problem给出无，求连接其中某些点（Judge 和目的

10、地） 且总距离最小的方案。可以枚举附加点，然后求 MST。有的同学可以讨论一下有哪些方法可以减少计算量。3272cNteSahruP fefrlefe洗牌时每次最多犯一个错误（交换两张牌）。给出洗牌后的结果，求出洗牌次数和犯的错误。如果多解则输出犯错误最少的方案。如果还是多解则输出字典序最小的方案。3273LotsofSunlight给出一些房子的层数和距离，计算每个房间被阳光照射的时间段3274Crossing Streets地图上有一些街道，用线段表示。给出起点和终点，求出穿过街道最少的方案。不在街道的端点和交叉点处穿过。很传统的题目，但要简洁、无错的写出代码也需要一 番工夫3275Til

11、ingthe Plane给出边与坐标轴平行的简单多 ， 它是否能覆盖整个平面。3276TheGreat Wall Game用最少移动棋子使得它们共线（行、列、主对角线）可以用二分图最佳匹配求解，但也可以贪心。3277Workshops为一些 Workshop 安排房间，使得无法安排房间的Workshop 数量尽量少。如果 多 解 则 让 参 加 这 些Workshop 的总人数尽量少类似上题，可以用二分图最佳匹配求解，也可以贪心。3278Zones给出 n 个 tower 服务的人数和各个公共服务区域的人数，选择其中一些 tower 使得被服务的总人数尽量大World Finals 20042

12、993Carlthe Ant给出第一只蚂蚁 Carl 的路线，模拟所有蚂蚁的移动。可以讨论一下程序实现细节和容易错的地方2994Heliport给出各边平行于坐标轴的简单多 ，在内部放一个尽量大的圆。2995ImageIs Everythingn*n*n 的积木有的地方空心，其他 。实心块都涂有颜色。同一个 块各面颜色相同。给出从 6 个方向看到的图案，求包含实心块的总数的最大值方法比较有启发性。2996Insecurein Prague给出一种加密方法，求出最长可能的原文。2997Intersecting Dates给出一些已提供股票价格的日期区间，以及需要信息的日期区间，计算出还有哪些日期

13、需要提供。日期都是1700 年以后。2998Merging根据规则把小地图合并成Maps大地图2999Navigation给出一些由移动信号源发出的信号（可能在不同时刻发出），确定 当前位置与目标位置所成的角度。信号源移动速度和信号速度已知。比赛的时候很少有队伍提交此题，但耐心看完题后稍 加分析就会发现其实不难3000Tree-Lined Streets给一些街道，在上面种尽量多的树。同一街道旁的树距离不小于 50 米，且离街道的交叉口不超过 20 米。3001Suspense!在两个大楼中间架一座桥， 使得任何一只宠物猫都不能通过桥 任何一只宠物鸟。要求桥上的绳索尽量长。一道很有意思的题目。

14、3002Air Traffic Control给出一些飞机的位置和一些中心。每个中心有一个半径，所有距离在半径内的飞机被，恰好等于半径的飞机可能被也可能不被。输出恰好被 0, 1, 2个中心的飞机个数。关键在于边界上的处理。虽然算法不难但其实细节是 比容易错的。World Finals 20032721Building Bridges用尽量少的桥把所有物连在一起2722Light Bulbs每个开关 连续 。操作开关以到达目标状态。多 输出十进制表示最小的一个。2723Ridingthe Bus给出 Bus 的递归描述，求两点间的距离。2724Eurodiffusio n给出一些 和 之间的城

15、市，模拟欧元扩散的过程。2725Covering Whole Holes给出边平行于坐标轴的简单多 洞和盖子，问盖子是否可以覆盖洞。不能旋转只能平移不错的几何题目。2726Combining Images给出两个黑白图形的 Hex四分树表示，求二者的交2727ALinking Loader实现 Linker 的部分功能。2728A Spy in the Metro从站 1 出发，必须在指定时刻到达站 n。设计路线使得他在站台上等待的时间尽量短。2729TheSolar System给出太阳系内两个行星的长短半轴长度，行星 1 的周期，计算行星 2 在特定时刻的位置2730Toll从 A 地到达

16、 B 地需要经过一些村庄和小镇，够成一个无 。若初始时的物品有X 个，则过村庄时要缴纳 1 个 ， 过 小 镇 时 要 缴 纳ceil(X/4)个。为了到达 B 时有 Y 个物品，一开始需要带多少个？World Finals 20022474Ballons in a Box求气球的膨胀顺序使得气球的总体积最大。简单枚举即可。但不知道是否存在一种保证正确的贪 心方案。大家可以讨论一下。2475Undecodable Codes给出一个 01 CodeSet，求出让 方式不惟一的最短串，多 输出字典序最小的。见算法艺术与信息学竞赛p1322476Crossing the Desert在沙漠里走 则

17、消耗 一 。在绿洲里足量的水，也可以储存 以备以后使用。要求在起点处至少要买多少食物。能带的 与水的总量有限制。见算法艺术与信息学竞赛p3102477Ferries连接两地的路线有一些湖泊也有平地。穿过湖泊需要等待渡船，而在平地上可以按任意速度行进。在到达时刻最早的前提下让最大速度尽量小。现场比赛的时候的队伍 WA 了无数次，至今也不知道错在哪里。哎，过了这题就夺冠了2478Island Hopping修建最小生成 让所有岛屿连接在一起并接入Internet。每条光缆的修建速度一样（与长度成正比），计算所有居民接入 Internet 的平均时间。2479Toil for Oil给简单多和一些漏

18、油点，问一共能装多少油。不错的几何题。2480Partitions求两个Partition 的交与并。先求轮廓交与并，然后再改造成合法的 Partition。比较有启发性的题目。2481Silly Sort用交换元素的方法排序，每次交换的费用为两数之和。用尽量少的总费用排序。见算法艺术与信息学竞赛p2472482Merrily, We Roll Along!一个 在水平/垂直线段组成的路径上滚动，求圆心移动的总距离。不错的几何题。思路有两种，见 WinterCamp2007 教练的讲稿2. ACM/ICPC Centrol European 2004-2006简介：这三年的 CERC 从波兰转

19、移到了匈牙利，但题目的质量没有降低。而且命题者和以前比较起来更加幽默（大家可以从题目的文字中感受到这一点）。2004 年的题目更是出人意料的全部和中国有关。CERC 20063713Astronauts给三个任务分配人选。任务 A 人选的 需要大于等于平均 ， 任务 B 需要小于平均，任务 C 没有限制。相互讨厌的人不能分配到同一任务。3714Bridges把 2n 个工厂分配到河的，各 n 个工厂。一些工厂之间必须直接相连，可以造桥（必须在不同岸），也可以空运。桥不能交叉，只有两架直升飞机可以用来空运，求一种可行方案。3715Chimes有若干个正弦波发生器，给出叠加后的采样点，确定各种类型

20、的发生器有多少个在工作。第i 个发生器的频率为10*2iHz，采样频率恰好最后一个发生器频率的两倍。3716DNA Regions给出两条 DNA 链，找出最长的区域使得该区域的突变位不超过p%3717Education Radio Programme在(0,0)处最多放 m 个天线，每个天线可以广播一定角度的范围。求出让 n 个点都被广播到的最小花费。每个天线的费用为它的角度的平方。3718Fast Track给出 n 个城市的位置和人口，建立一个直线铁轨使得能乘坐火车的人数尽量多。城市离铁轨的直线距离不超过 1km 时可以乘坐火车。3719Grass is Green每个人都用所有的钱买土

21、地、种草和修篱笆。土地的价格是统一的，但每个人买的草和的价格不一样。每个人的土地必须是正方形。给出每个人的钱和草与 的价格，统计有多少人的土地比你大3720Highways统计 n*m 网格全连接后有多少条非水平和垂直的线3721Islands给出网格，确定每个岛屿（四连块）并计算出最小/ 最大的面积/ 周长。岛屿可以包含湖泊（ 内边界算在周长中），但湖泊中如果还有其他陆地，则算作不同的岛。3722Jewel-eating Monsters题目说了一个很幼稚的故事：一个人在一个洞里过了 n 个晚上，每个晚上扔一枚金币到湖里第二天金币就变为原来（扔掉金币后） 的 a 倍。后来他到珠宝行里换了珠宝

22、，每个珠宝价值 c 个金币，他换了尽量多的珠宝。最后他遇到了吃珠宝的怪兽，把他所有的珠宝全都吃了。问他最后还剩多少硬币=.=3723Knowledge Transfer给 n 个学生安排 d 天的课程，每天有两个班，长度均为 2 小时，必须在 22:00 之前开班。两个班的时间可以重叠。给出每个学生每天可以学习的时间（为一个区间），安排每天的两个班的开始时间， 并给每个学生分配一个班CERC 2005 (CII)测试数据：3523Knightsofthe Round Table每次圆桌会议由至少3 个骑士参加，骑士的数目必须为偶数，且在圆桌旁坐下后相邻骑士不能相互憎恨。统计有多少个骑士不可能参

23、加任何一个会议。3524The Cow Doctor有一些测试原料可以用来检测疯牛病。每个原料用一个集合表示。有多少个原料可以由其他原料得到（即：它等于其他若干集合的并）？3525Wild West每个人用一个三元组(a,b,c) 表 示 ， 1=a,b,ca要么 bb要么cc。3510Pixel Shuffle在一个 n*n 黑白图象上做一个最多包含 32 个动作的 pixel shuffle（旋转、对称、行混合等）序列，问重复做几次后会得到原图象？3527Find the Clones给 n 个长度为 m 的DNA 串，统计恰好出现 i 次的串的个数3528The Warehouse在一个

24、迷宫中，每次可以移动一格也可以把一个高度为 h 的 box 放倒（然后将占据连续h 个格子）。求到达出口的最小步数。3529Widget Factory给出一些制造 widget 的信息：开始时间、结束时间（均用 weekday 表示） 和制造的各widget 类型，求每个widget 的制造时间（保证为 3 到 9）3530Martian Mining给出 n*m 网格中每个格子的 A 矿和 B 矿的数量，A 矿必须由右向左 ，B 矿必须由下向上 。管子不能拐弯或者间断。要求收集到的 AB 矿总量尽量大。3531Word Rings把一些单词组成一个word ring，每个单词的后两个字母与

25、后一个单词的前两个字母相同。要求单词的平均长度尽量大。3532Nuclear Plants有两种圆：半径 0.58 和 1.31，求覆盖的总面积CERC 2004 (CII)3176Art of War给出地图（用线段集合表示，每条线段的两侧必为不同区域），每个的为首都所在区域哪些在发假设相邻必然发）算法不难但不好写3177Guards给一个圈，圈上第 i 个人想要 i 种不同的东西。相邻两个人不能有同种东西。一共需要多少种东西才能满足所有人的需要？3212Crime给一个无 可能有重边），选择一些点，使得所有边恰好有一个端点被选择。要求所选点尽量少。可能无解初看起来不可做，但仔细3179De

26、sert在 n 个点中选 3 个安装 ，使得所有点都能收到这三个台的电视 。每个需要选择一个信号发射方向，则 45 度内的点都可以收到 。要求总安装费用尽量小。虽然点不太多，但是也要考虑时间复杂度3180Explore给平面上 n 个村庄，选一个开始旅行，每天最多走 30km，可以在任何村庄过夜但不能在野外过夜。每个村庄都有一定数量的修道院， 要求可以到的修道院总数尽量多。3181Fixing the Great Wall被看作一条直线段，有 n 个点需要修复。每个点的修复费用为 ci+tidi，其中 ti 为修的时间，(ci,di)为描述该损坏点的参数。要求修复总费用尽量小。比较经典的动态了

27、。3182Gambling在一个 中，你有四种方法可以修改你的pebble 个数。每次操作后的 pebble 数目不得超过最初的个数。要求用 最 少 的 费 用 让pebble 数目变为 03183History两个人分别写了 n1 和n2 章历史书，但其中有一些 即相同历史 的发生时间不一致）。扔掉尽量少的章使得余下的部分不3. Polish Olympiad in Informatics XIIXIII简介：不用多说，这两年的题目难度较以前又有提高。POI XIII 2005-20061-1 KRAThe Disks有一个各高度半径不同的空心 Tube，依次扔一些实心圆盘，求每个圆盘在何处

28、停止。1-2 OKRPeriod of Words给一个串，求它的所有前缀的最长重复子串长度之和1-3 PROProfessor Szu给有，可能有重边和自环。其中一个点是主楼，其他点是别墅。选一个别墅使得它到主楼的不同道路个数尽量多。一个点可以经过多次（包括主楼）。如果有多解输出全部。如果解超过 36500 则认为是无穷大。1-4 TETTetris 3D模拟一些长方体的下落，计算最后的高度。虽然是很经典的数据结构题。但如果相关知识不扎实也是做不出来的1-5 ZABFrogs在田里放一些吓唬青蛙的 scarefrog，给青蛙计算一条从 A 到 B 的路径，使得离最近的scarefrog 尽量

29、远。2-1 LISThe postman给有 ，求一条从 1开始到 1 结束的回路，包含一些给定的连续顶点序列，或报告不存在。2-2 MAGWarehouse网格上有 n 个 shop， 每个 shop 需要经过 ti 次 。 寻 找 一 个warehouse 使得总路程尽量小。只能沿着网格走。2-3 METSubway给一棵树，用 L 条无。3184I cant read it!把每个单词的各个字母倒过来公共点的路径覆盖尽量多的结点。2-4 NAJThe invasion在 n 个顶点中选出三个组成三角形，使得三角形内的 factory 权和尽量大。每个 factory 的 可负。2-5 O

30、RKPloughing给一个 n*m 网格，每个格子有个非负整数。每次切下一个宽度为1 的 slice，里面的数之和不得超过 k。每次切完后剩下的部分仍应是个矩形。要求切成尽量少的 slice。2-6 SZKSchools给出 n 个 1n 之间的整数，把它变成 1n 的排列。每个新数 mi 必须在区间ai bi内， 改变费用为ki|mi-mi|， 其中 mi 为第 i 个数原来的值。3-1 ESTAesthetic Text把 n 个单词分成若干行，每行的各个单词由一个空格隔开，要求相邻两行长度差的绝对值之和 sum|Li-Li+1| 尽量小。其中 Li 为第 i 行的长度（即所有单词长度和

31、加上单词的个数减 1）3-2 KRYCrystals给 出 n 和m1,m2,mn，求方程a1 xor a2 xor xor an=0 的 解 ， 要 求0=ai=n-10)。POI XII 2004-20051-1Bankomat (ban)给出某client 输入的 n 个场景，统计它的有多少种可能1-2Points (pun)给两个点集是否相似1-3Toy cars (sam)一个孩子要依次玩一些玩具。每次玩时需要把玩具放在地上，地上放不下时就必须把一些玩具放回到架子上。让从架子上拿玩具的次数尽量小。1-4Piggy banks (ska)有两种方式可以拿到罐里的东西：用钥匙开、 打碎。

32、每个罐都有一把钥匙，并且放在某个罐里。打碎尽量少的罐使得所有其他罐都可以用钥匙打开。1-5Knights (sko)给 knight 的 n(=3)种移动方式，保证能移动到的格子不共线。把它化简成两个移动方式， 使得能到达的格子集合不变。2-1A journey to Mars (lot)给出圆周上 n 个点的位置和油量从每个点出走（可以从两个方向中选择一个） 是否可以回到起点（假设油箱无限大）。2-2Bank notes (ban1)给一些面值的相应的数量，找一个付 x 钱的方法。2-3FibonacciSums (sum)给两个数的 Fibonacci 进制表示，求它们的和。2-4Temp

33、late (sza)找一个尽量短的字符串作为 pattern，把墙涂成一个指定的图案。每次涂的时候必须把整个 pattern 涂上去， 不能只涂一部分。若同一个地方，每次涂的字母应相同后缀数组+线段树思路：枚举K，将所有的后缀（满足它们和的 LCP 大于等于 K） 到线段 ，统计他们间隔的最大值，如果该值小于等于 K，那么说明 K 为一个可行解。总时间复杂度 O(NLogN)用 CENA 测试时，最慢的一个点要 3.59sec，不知道POI 时限是多少后来用了 KMP 扩展算法代替了 SA，速度显著提高， 1.5sec 左右就过了2-5Dicing (kos)给出 n 场比赛，设计它们的结果使

34、得你获胜场数不比其他人少。满足此条件下要求你获胜的场数尽量少。二分+网络流网络流用最简单的 BFS，只要开始的时候加个贪心就可以了，和 NOI 那题一样3-1Hollows (dzi)两棵参天大树上各有一些洞，你的任务是给n 只鸟安排一些洞居住。要求相互熟悉的鸟在不同的树上住，且所在 的连线不交叉（可以有公共点）。鸟住得尽量低。求方案总数。该题没什么技术含量，关键是要把问题想清楚， 想完整。容易遗漏的地方： 星形图形两个度为一的点相连连通块之间的全排列度为 0 的点可能出现在任何地方3-2Double-row (dwu)给两排数，每次可以交换相同列的两个数。要求用最少的交换次数使得每排的各个数

35、都不相同。保证有解。3-3Two parties (dwa)把 n 个人分到两个party，使得“有偶数个朋友与 分到同XOR 方程组一个 party”的人数尽量多.其中一个party 没有人。每个人不是 的朋友。朋友关系是对称的。3-4SpecialForces Manoeuvres (akc)平面上依次放置 n 个圆，求最小的 i 使得前i 个圆没有公共点。3-5Dextrogyrate camel (pra)平面上有 n 个点，初始时在点 1，面朝点 2。每次只能右转（0 到180 度），线路不能交叉，最后回到点 1。要求 尽量多的其他点。由于走过的点有极角序，所以可以 DP。最朴素的

36、DP 是 N3 的，但是递推的时候，可以确定中间的点，然后对可能的两边的点进行排序，然后利用 单调性使得原先比较两边的点从 O（N2）降到 O（N）。最后，总时间复杂度为 O（N2LOGN）3-6The Bus (aut)一个网格，从左下角(0,0) 走 到 右 上 角(m,n)，每次只能往上或者往右走一格。有 k 个交叉点上有正整数， 要求经过的数之和尽量大。 1=m,n=109, 1=k=105。3-7Mirror trap (lus)给一个 围成的trap， 求有多少个格点，使得从中心往它射出激光后，激光将走尽量远的距离后返回中心（用 Manhattan 距离衡量）。4. El Judg

37、e说明：虽然 IOI2004但重点是后面的红色和集训队讨论过前面的题目，这里还是留出位置，以便大家补充。题目（都给出了题目大意）。题目描述有很多语法错误，大家忍耐一下惟一的一道俄文题目下面翻译出了题目大意。数学题和的同学可以试试。题比较多，对这方面感000Sumoftwo integers001Max of Integers002Set intersection003Contest Table004Athletes005Random descending a tree006Three Squares007Space Zoo008Brackets009Fibonacci numbers010Ne

38、wYearcongratulations011Brackets II012Correct dictionary013Boxes014War-cry015One rectangle016Two ractangles017Arithmetica v1.3018Whatisthe number?019Bridges020Island of straight roads021Fraction022Regular Expression I023Way among sticks024Arithmetica 1.0025The optimal path026Operations027Odd number02

39、8Circle Game029Stormina Rectangle030Disclosingof parentheses031Minimalsumof distances032Star War (episode V)033Triangles034Rain给地面的描述，下一场雨后求积水深度。035Camelot036Two cubes037um profit038Roots of polynom039CalculatingXOR via AND040Murder of Mister C041RubiksCube 2x2x2求解魔方042LCS problem043Intervals044Fram

40、e paving045Picture segments046Best clustering047Self-describing sequence048Chess end-game国际象棋中+后对黑单王，要求不。让黑王坚持尽量长的时间。049Minimizing number of steps050Tworegular expressions051Strange Tower052Permutation complexity053Love cycle054Mine Field从 A 到 B，路上离最近的地雷尽量远。055Trip abroad056Best segmentation057Hacke

41、rs attack058Alise and Balisio猜数 。假设 Alise 要用 1, 2, , N 各 ni 次，写程序让猜测的总次数尽量少。每次程序重启（无记忆的）059CD060Defragmentation061Reconstructing permutation062Regular Expression II063Casket给一个棋盘做尽量少的修改使它对称。064Max product065Queue for tickets066Counting figures067Good permutations0682x1-paving069Graph coloring070Squa

42、rerootof permutation071Cables072Chess cube073Enclosingpoint with polygon给 n 个点和点 P，选一些点组成多 ，使得P 在它的内部。多各 不能超过 K，要求多 周长尽量小。074Spheres intersectionn 个球是否有公共点075Rootofthe equation解方程=A。076Bracketstructure correction077Queens078Next word079FenceNEERC 1998 那题080Japanese Crossword给 01 矩阵各行各列的连续 1 的长度，求解的总

43、数。081Swimming pool在矩形中放置一个尽量大圆。有一些圆形障碍点。082Clusterizationof binary words把 01 串分成若干组， 使得每组的任意两个串的 hamming distance 不超过 D。只需找较优解。083SAT-2如题。084Farthest points085Triangle Approximation给 平 面 上 三 个 点ABC，找一个等边三角形 ABC ，使得maxAA,BB,CC 尽量小。086Anti-factorial087Tautology088p-adic numbers把有理数 a/b 写成p-adic number

44、 的形式。0898-puzzle090Graph Planarity无 是否为可平 面 图 V3000, E1000009115-puzzle用不超过 1000 步解决15 数码问题。092Stations093What is the number (Part II)?094PS-scheme095Directed PS-graphs一个有 是否为 PS-graph. 即可以从一条边经过若干次double 和 split 操作得到。096Undirected PS-graphs类似上题，但是无向图。097Cut Rectangle把 n=20 个矩形拼成一个大矩形，要求用一种特殊的方式输出。0

45、98Upgradingto strongly connected在有填加尽量少的边，使它强连通099PS-scheme II用一些 R=1 的电阻组成 R=M/N 的电阻，可以串联和并联。(这是094 的逆问题)100Nim Game - who is the winner?101Stone Game - who is the winner?102Stone Game II - who is the winner?103Nim Game - Give Away!104CamoGame - who is the winner?105MRQ problem106k-harmonious group

46、107Infix to Posfix form给中缀表，转换成后缀形式。108Grammarofa great game给出 8 种产生规则(S 0|1S|2SS|3SSS)，给出串 s，求以它为子序列的最小串，使得它可以由该文法产生。109Half Planes I给一些半平面（包含分界线），从中选尽量少的半平面覆盖整个平面。n=100110Graph Existance给无 任两点的最短距离 它是否可能是一棵树或森林（边长为非负整数）111Reductionto common denominator化简有理式之和，写成p(x)/q(x)或p(x)或 0 的形式。112 (Maze)一个 n

47、*m 迷宫有 K 个出口，有些格子不能经过。可以往四个方向移动。还有一些瞬间转移装置。求从初始位置到任意出口的最短路。俄语题目描述翻译过来以后让我很失望，不做也罢， 没啥意思113Plane Partition给 n 条线段，它们把平面分成了多少部分？114Unique Radix给一些 X*Y=Z 或X+Y=Z 的等式，找一个进位制使得它们同时为真。115The Landing给一个由 dot, hyphen 和 0 组成的表 ，其中 0 表示未知（可能是dot 也 可 能 是hyphen）。恢复尽量多的 0 使得所有连续hyphen 的长度为给定值。比如“.-0.-”，连续-的长度为 2 1，则那个 0 一定是-，“000”连续的“-”长度为 2， 则只