信息学集训队作业cerc2004report

1、ACM/ICPC Central European 2004/2005 Report Yali ACM/ICPC Central European 2004解 题 报 告雅礼中学陈丹琦【Art of War】问题简述平面上有n个简单多边形, 每个多边形是由若干条线段连接而成, 每条线段的两侧或者是两个不同的多边形或者有一侧是空的现在给你一些线段集合, 以及n个简单多边形内部的一点, 求哪些多边形是相邻的相邻的定义是至少有一条边公共n 600, m 4000算法分析对线段的端点离散化, 这样将每条线段转化为一条无向uv, 把一条无向边拆成两条有向边uv和vu对于每个点u, 将所有与它相连的边uv

2、按极角排序考虑没有“洞”的情况：每次找一条未覆盖的边, 从它出发不断地往一个方向走, 直到走回起点由于每个顶点相连的边都已按极角排序, 因此可以在O(1)的时间确定下一步走到哪个点, 这样就可以把所有的环找出来而对于每个多边形内部的点, 选择一个包含它的面积最小的环即找到所对应的多边形了这样可以记录每条线段属于哪个多边形, 而uv和vu如果属于不同的多边形, 那么这两个多边形一定相邻这种情况下时间复杂度为O(nm)有“洞”的情况比较麻烦：相当于要考虑一个多边形完全包含另一个多边形, 并且它们相邻的情况我的思路是每次找包含一个多边形内部的那个点的面积最小的两个多边形, 但是这样会有反例, 即这个

3、两个多边形是包含关系, 但是不相邻, 比如右边这幅图中1包含2, 但是1和2不相邻我的程序又加了一层判断, 判断这个多边形上的是否存在一条边uv对应的vu属于另外一个多边形, 这样算法就应该没有问题了实现比较麻烦, 算法总的时间复杂度为O(nm) 【Beijing Guards】问题简述有一个由n个人组成的圈，第i个人想要Ai种不同的东西，相邻两个人不能得到同一种东西，最少需要多少种东西才能满足所有人的需要? 算法分析如果n为偶数，那么答案为p = ，即相邻的两个人的A值之和的最大值这个结论比较明显：1) 它是答案的下限，至少需要p样东西才能保证任意两个相邻的人没有同样的东西；2) p足够了，

4、编号为奇数的人取1Ai, 编号为偶数的人取p-Ai+1p, 这样一定是满足题目要求的考虑n为奇数的情况，上述的贪心不成立的原因是1和n均为奇数且它们相邻，如果都取1Ai，一定有冲突稍微改变一下贪心的思路：假设已知一共有p种东西，判断是否可以将每个人分配1p中的Ai样东西，使得相邻的人没有冲突不妨设第一个人取1A1，那么最优的分配策略一定是：编号为偶数的人尽量往前取，编号为奇数的人尽量往后取，这样编号为n的人在不冲突的前提下，尽可能地往后取了An样东西，最后判定编号为1和编号为n的是否冲突即可例如n = 5，A = 2, 2, 5, 2, 5, p = 8，那么1取1, 2, 2取3, 4, 3

5、取8, 7, 6, 5, 2, 4取1, 3, 5取8, 7, 6, 5, 4，这样1与5不冲突，所以p = 8是可行的算法实现：二分答案p，判断p是否可行依次考虑每一个人取哪些，只需要记录每个人在1A1的范围内取了几个，A1+1n里取了几个即可，最后判断第n个人在1A1里面是否有取东西 总的时间复杂度为O(nlog2R)【Crime】问题简述给一个无向图（可能有重边），选择一些点，使得所有边恰好有一个端点被选择，要求所选点尽量少，可能无解算法分析 对于每一个连通分量，判定是否为二分图，如果不是二分图，无解，否则选择X, Y部中|X|, |Y|中较小的一边实现的时候只需要一遍Dfs作黑白染色，

6、时间复杂度为O(m + n)【Desert】问题简述平面上有n个点, 要求在中间选择三个点作为电视台, 每个电视台选择一个信号发射方向后使得所有的点都能收到这个三个电视台的信号一个点能收到一个电视台的信号当且仅当它与这个电视台的方向和电视信号的发射方向的夹角不超过45度每个点有一个安装费用, 要求选的三个点的总的安装费用最小n 20000算法分析事实上三个电视台之间是相互独立的, 我们需要判断哪些点可以通过发射电视信号后所有的点都可以收到这个信号, 然后选择费用最小的三个即可对n个点求凸包, 首先一个点如果在凸包内部, 那么它无论如何发射信号, 与其他的点的向量的夹角不可能全部在-45, 45

7、度内, 因此点一定取自凸包上枚举凸包上的每个点i, 设点i的上一个点和下一个点分别为j, k, 向量ij和向量ik的夹角180度且其余的向量ip一定介于ij和ik之间, 相当于只要判断ij和ik是否90度即可然后对于所有满足条件的点i选择费用最小的三个即可时间复杂度为求凸包的时间复杂度, O(nlog2n)【Explore Tibet】问题简述平面上有n个村庄, 选择一个点开始旅行, 每天最多走30km你可以选择在任何村庄过夜, 但是不能在野外过夜每个村庄都有一定数量的修道院, 要求可以访问到的修道院数量总数尽可能地多同一个村庄可以遍历多次, 但是修道院只访问一次n 1000算法分析这个题目相

8、当无聊每个村庄可以任意遍历多次, 因此如果两个点距离 30km, 连一条无向边问题相当于要求出每个连通块, 统计每个连通块内修道院的总数, 选择一个修道院总数最多的连通块输出即可时间复杂度为O(n2)【Fixing the Great Wall】问题简述一条线段上从左到右有n个损坏点, 要来修复所有的损坏点每个点有三个参数(Xi, Ci, Di), 表示这个点的位置, 以及修复这个点的代价为Ci+Di*t, t表示修复这个点的时间0时刻位置在X, 速度为v, 表示单位时间可以移动v的距离问按怎样的顺序来依次修复所有的损坏点使得总的修复代价最小, 修复一个点的时间可以忽略n 1000算法分析将所

9、有的点按照Xi从小到大排序, 如果从点j移动到点k(j k), 还存在一个点p(j p k)没有被修复, 由于修复的时间可以忽略, 那么从点j移动到点k的过程中顺便把p修复了, 总代价会变小, 因此每次修复的点一定是一段连续的一段考虑动态规划, 由于t是实数, 无法把t记入状态, 换个角度, 任何时候从x移动到y, 可以将|x - y| / v * 所有还未修复的点的D值之和累计到当前的状态中这样我们就可以作动态规划, 设fijk表示修复完(i, j)这一段后, 当前位于点i(k = 0)或者点j(k =1)这个状态下当前修复的总代价加上当前时间对后面的所有未修复的点产生的总代价的最小值fij

10、k + (SumD(1, i - 1) + SumD(j+1, n) * |Xi-1 Xp| / v + Ci-1fi-1j0fijk + (SumD(1, i - 1) + SumD(j+1, n) * |Xj+1 Xp| / v + Cj+1fij + 11其中k = 0的时候p = i否则p = jSumD(i, j) = Di+Di+1+Dj算法的时间复杂度为O(n2)【Gambling】问题简述给你一个初始的数x，你可以对它进行以下四个操作：The fire ：如果x 11，那么你可以付x1的代价使得x x -11The dragon：如果x mod 3 = 0，你可以支付x / 3

11、的代价使得x x * 2/ 3The eagle：你可以付x2的代价使得xx + 7The courage：你可以付x + 1的代价使得x2x + 1任何时候当前操作的数都不能大于x，问要得到0需要的最少代价 算法分析 按题目给的四种操作构图，求x到0的最短路若使用Dijkstra + Heap优化求最短路，时间复杂度为O(Elog2V) = O(xlog2x)【History】问题简述有两个人写历史书，第一个人写了n1章，第二个人写了n2章每一个章节包括了mi个事件，每个事件由一个二元组(ai, bi)表示即事件ai发生在bi这一年如果两个章节记录了相同的历史事件且发生的年份不一致那么说这两

12、个章节有冲突，注意同一个人写的章节是不可能冲突的现在要求你删除尽量少的章节使得剩余的章节没有冲突，算法分析 构图，如果两个章节之间有冲突，那么它们之间连一条无向边由于同一个人写的章节是不可能有冲突的，因此这是一个二分图，问题转化为求这个二分图的最大独立集二分图的最大独立集 = n1+n2二分图的最大匹配，因此算法包括两个部分：构图和求二分图的最大匹配构图数据范围非常大，而且同一个事件可能写在同一个人的多个章节里(发生的年份一致)对每一个事件记录两个个链表分别表示两个人的哪些章节记录了这个事件，如果两个人对某个事件是矛盾的，那么两个链表上任何一对点都是矛盾的，但是这样做最坏情况下会退化为O(n1 * n2 * mi)考虑使用位压，对每一个事件，我们记录第一个人的哪些章节记录了它，本来是一个2n1的二进制数，我们将每64位即0264-1用一个64位的整数来存储，那么我们只需要30个64位的整数即可存下这个状态枚举第二个人的每一个章节，枚举它记录的每一个与第一个人矛盾的事件， 利用或(or)运算得到一个30个64位整数的状态表示第一个人的哪些章节与它矛盾再枚举n1，如果n1与n2矛盾，连一条边这一步构图的时间复杂度降低