

Andrew Stankevich’s Contest #9解题报告
Posted by watashi in solution, tags: acyclic, andrewzta, graph, greedy, solution, tree, ZOJ, 构造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 Designing,2701 Restore the Tree和2697 Electricity这三道构造题,一道比一道值得一想。然后是ZOJ 2698,DP虽然简单,但英语转数字可是相当考验基本功啊。2703 Selling Tickets虽然不算难,但把握时间复杂度和编程复杂度的trade off是很有趣的一件事。有些题,尤其是构造题,一定存在更有趣,更简洁,或者更高效的算法。抛砖引玉,欢迎分享或者cha。
ZOJ2696 Chip Designing
source code (ZOJ2696.cpp) [构造, 平面几何]
给你个芯片,要用水平或垂直的线路连接两排输入输出节点,要求线路不相交。
构造,方法应该非常多,bfs应该也可以,我的方法不难想,效率也满高的,不过写起来就不那么轻松了。首先直接构造一个input到output的连线,如果这条连线和先前的连线相交了,那么总可以“绕”过这条连线,绕的时候,可以保持这条连线的距离为u。只要每次的u都小于上回的一半(理论上等于也可以,但会有更多情况需要处理),那么就不可能会和之前的连线相交。这样还可以在计算过程中使用整数运算,不需要分数。上图是sample的情况,下图是对n=4的一个case的解,图片太模糊了,若需要高清无码矢量图,请点链接下载eps格式的文件。
ZOJ2697 Electricity
source code (ZOJ2697.cpp) [构造, 拓扑排序(Topological Sort), acyclic]
给定一个有向无环图,要求每天改变一条边的方向,使得最后一些边的方向恰好与原来相反,要求中间过程始终没有环。