Andrew Stankevich’s Contest #9
ZOJ2696 Chip Designing 19.15% (41/214)
ZOJ2697 Electricity 16.55% (76/459)
ZOJ2698 Numbers to Numbers 10.28% (29/282)
ZOJ2699 Police Cities 19.35% (66/341)
ZOJ2700 Quadratic Equation 30.51% (65/213)
ZOJ2701 Restore the Tree 13.99% (76/543)
ZOJ2702 Unrhymable Rhymes 28.86% (153/530)
ZOJ2703 Selling Tickets 21.79% (51/234)

灰灰灰灰灰灰长好的一套题,所有题目都推荐!特别是2696 Chip Designing2701 Restore the Tree2697 Electricity这三道构造题,一道比一道值得一想。然后是ZOJ 2698,DP虽然简单,但英语转数字可是相当考验基本功啊。2703 Selling Tickets虽然不算难,但把握时间复杂度和编程复杂度的trade off是很有趣的一件事。有些题,尤其是构造题,一定存在更有趣,更简洁,或者更高效的算法。抛砖引玉,欢迎分享或者cha。

ZOJ2696 Chip Designing

downloadsource code (ZOJ2696.cpp) [构造, 平面几何]

给你个芯片,要用水平或垂直的线路连接两排输入输出节点,要求线路不相交。

2696-2

构造,方法应该非常多,bfs应该也可以,我的方法不难想,效率也满高的,不过写起来就不那么轻松了。首先直接构造一个input到output的连线,如果这条连线和先前的连线相交了,那么总可以“绕”过这条连线,绕的时候,可以保持这条连线的距离为u。只要每次的u都小于上回的一半(理论上等于也可以,但会有更多情况需要处理),那么就不可能会和之前的连线相交。这样还可以在计算过程中使用整数运算,不需要分数。上图是sample的情况,下图是对n=4的一个case的解,图片太模糊了,若需要高清无码矢量图,请点链接下载eps格式的文件。

DL 2696-2.ps
2696-4
DL 2696-4.ps

ZOJ2697 Electricity

downloadsource code (ZOJ2697.cpp) [构造, 拓扑排序(Topological Sort), acyclic]

给定一个有向无环图,要求每天改变一条边的方向,使得最后一些边的方向恰好与原来相反,要求中间过程始终没有环。

首先拿到这个问题真是毫无头绪,想了好久才发现如此巧妙。这真是非常好的一道构造题,其实可以做到k<=m,不知道k<=4m是否是烟雾弹。下面这段文字严重剧透,我建议先独立思考一下问题后再看。


对于一个有向无环图(DAG, Directed acyclic graph),它的一个特点就是可以拓扑排序(Topological sorting),当然这题里的DAG和其拓扑排序之间是一对多的关系。假设拓扑排序里有相邻的两个点a在b的前面,如果ab间没有边,那么交换它们的位置后,DAG还是原来的DAG;否则一定是有a到b的边,那么交换位置后,DAG里a->b的边变成了b->a的边,而其他的边完全不变。于是问题就是如何通过不断交换(swap)相邻元素,从原始排列(permutaion)(初始DAG的拓扑排序)变成目标排列(最终DAG的拓扑排序),复杂度为O(n^2)。而无解发生且只发生在ab间有重边,却要交换这些边的方向的情况下。


ZOJ2698 Numbers to Numbers

downloadsource code (ZOJ2698.cpp) [人肉, if-else, DP]

把一篇文章中英语描述的数字全部转为阿拉伯数字(小自然),要求转化的单词数尽量多,若相同,则要求前面的数尽量大。

首先是考验coding技巧和码农体力的英文数字转化模块,完成之后这道题就七成成功了,这部分真没什么好说的,个人的意见是多点递归/函数调用,少点重复的if-else。注意题目不是简单的转化就足够了,开始我就看错题了,题目要求转化的单词数尽量多,那么”two million two million”就应该是”2000000 2000000″,而不是”2000002 million”,所以应该再做一个O(Ln)的DP,其中L是一个常数,表示最长合法英文单词的长度,n的词语的数量。对于这种要求前面的数尽量大的DP,从后往前DP要方便得多,DP要记录转化的单词数,最前面的数字和转化方案。

ZOJ2699 Police Cities

downloadsource code (ZOJ2699.java) [directed graph, graph connectivity, floyd, DP]

一个国家的n个城市由有向的道路连接,要选出k个城市设立警察局,要求每个城市都能走到某个警察局,也能被某个警察局走到。

首先求强联通分量,这道题n=100,floyd足矣。求好强联通分量后,得到的是一个DAG,按题目要求,每个缩点后入度或出度为0的联通分量都应该至少有个警察局,这是充要条件。可以动态规划求解dp[i][j]表示在前i个入或出度为0的联通分量里安排了j个警察局,那么dp[i+1][j]=sum{dp[i][j-y]*c[x][y]|y>=1},x是这个联通分量里城市的个数。最后答案是sum{dp[m][k-y]*c[z][y]|y>=0},z是所有入出度大于0的联通分量里城市的个数之和。需要大数。复杂度O(n^3)。

ZOJ2700 Quadratic Equation

downloadsource code (ZOJ2700.cpp) [boolean, polynomial, gaussian elimination]

求系数在Z/2Z,也就是0, 1的多项式二次方程a(t)x2(t)+b(t)x(t)+c(t)=0的任意一个解,或判断无解。

首先需要注意到一点x(t)=sum{xiti},那么x2=sum{xit2i},证明显然。也就是说x2(t)的各项系数都可以由x(t)的各项系数线性表示,于是a(t)x2(t)+b(t)x(t)+c(t)的各项系数也可以由x(t)的各项系数线性表示。设x(t)的系数为未知数,令a(t)x2(t)+b(t)x(t)+c(t)的系数全为0,得到一个布尔线性方程组,用高斯消元法解之。复杂度O(n^3)。

ZOJ2701 Restore the Tree

downloadsource code (ZOJ2701.cpp) [构造, tree]

要求构造一棵树,满足树的所有叶子之间的距离恰好为输入矩阵。

首先我们只考虑那些关键的节点,也就是不考虑那些度数为2的节点,而认为关键点与关键点间的边是带权的。判断无解也是比较头疼的,因为可能性比较多,而给定树,生成叶子间的距离矩阵是很轻松的,所以我们先求出个解,再检验解,从而判断是否无解。求解方法如下:首先任意取一个叶子节点C,这个叶子节点一定连到了一个父亲节点D,而CD间的距离|CD|就等于min{|AC|+|BC|-|AB|}/2。如果已有点A使得|AC|=|CD|,那么AC连边,边长|CD|,删去点C;否则新增点D,(注意D不一定是叶子)连边CD,边长|CD|,删去点C,而D到各点的距离为|AD|=|AC|-|CD|。这样最后生成一棵树,树的节点数不超过2*n-1。复杂度O(n^3)。

我WA了好久,由于检验解的代码不大会出错,所以WA就应该WA在把有解的判断成了无解。通过生成随机数据测试发现,原因就在第一步,“任取一个叶子节点”,而我可能取的是非叶子节点,结果判断成无解。要保证取的是叶子很简单,由于最长路的两个端点一定是叶子,所以每次取d[i][j]最大的i。

ZOJ2702 Unrhymable Rhymes

downloadsource code (ZOJ2702.cpp) [greedy]

有一些诗句,现在要求选取一个子序列构成最长的诗歌,诗歌应该由AABB, ABAB, ABBA或AAAA这四种形式的小节组成。

实际上合法小节的充要条件就是由两组两句相同的诗句组成。那么假设处理完了前i句,我们就会找最小的满足存在i<j’<j&&a[j']==a[j]的j,再找最小的满足存在i<k’<k&&k’!=j’&&k’!=j&&a[k']=a[k]的k,这样j’, j, k’, k排序后可组成一个小节,而且这种贪心是最优的。通过预处理和维护一个数组c,c[i]表示在可选诗句里,i之前的最后一句与i相同的诗句的序号,扫描一遍可得解。预处理中用到map,所以复杂度为O(nlog(n)),如果利用hash代替map可以做到O(n)。

ZOJ2703 Selling Tickets

downloadsource code (ZOJ2703.cpp) [greedy, enumeration]

一辆车有9个4人座的隔间,现在要安排座位,使得总满意度最大。乘客分成了不相交的1~4人小组,如果有i个来自同一小组的人分在同一个隔间,他们的满意度为i*(i-1)*c,c是一个小组相关的系数。

显然1个人的满意度总是0的,所以别人都安排好后,最后随便塞就好了。4个人的隔间有价值的安排方案无非是2+2, 3和4。3个人的小组要么在一起,要么拆成2+1或1+1+1;4个人的小组要么在一起,要么拆成2+1+1或1+1+1+1,显然3+1和2+2都不会是最优解;且3/4个人的小组里都最多只有一个拆出了2;而且把系数高的安排在一起,系数低的拆开,满意度更大。所以只要枚举3和4有多少组在一起,然后贪心就可以了。

6 Responses to “Andrew Stankevich’s Contest #9解题报告”
  1. Yuan says:

    这里的ZOJ2703 Selling Tickets 我wa了好久…
    我是这样贪心的:
    用一个堆,每次选i*(i-1)*c最大的放
    如果没有位置能够放下这i个人,就拆分
    4 -> 2+2 , 3+1 (我这里没有继续拆,先拆成2,2去试试,不行的话以后自动会再拆为1+1)
    3 -> 2+1
    2 -> 1+1
    这样子贪心是不是有问题呢?
    我拿你的程序对拍了一些数据,那个最大值是相同的,对于安排方案我就没看

  2. saturn says:

    学长救命啊。。。。。能不能给我看一下zoj2866和zoj2865。。。我们暑假作业。。。。要算绩点的~
    谢谢啦~

  3. aaahexing says:

    居然这里有sf!!

  4.  
Leave a Reply