ゆっくりでいいさ

灰灰灰灰灰灰长好的一套题，所有题目都推荐！特别是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格式的文件。

DL 2696-2.ps

DL 2696-4.ps

ZOJ2697 Electricity

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

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

所有题目都附上了我AC的代码，不过AC不等于没问题，如果代码显示或下载有问题，或者我的程序有错，请在comment中说明，我会尽快fix。这套题中的ZOJ 2705, 2707, 2708强烈推荐！

ZOJ2704 Brackets

source code (ZOJ2704.c) [bracket, greedy]

给定一个只含()[]的字符串，问其中最长的合法字串是什么。

要判断一个串是否合法，只要维护一个栈进行O(n)的扫描就可以了。但是枚举字串+扫描就O(n^3)，肯定不靠谱了。事实上注意到，如果从左往右扫描到第i个，出现不合法的情况，那么前面无论保留什么，都是非法的，所以把栈清空，继续从位置i+1开始新的扫描，复杂度O(n)。代码是入门的时候c语言写的……

ZOJ2705 Dividing a Chocolate

source code (ZOJ2705.cpp) [Fibonacci, greedy, 逆推]

给定一个m*n（m和n均可以很大）的矩形，初始可以沿任意的整数位置分成两个矩形。然后始终让大矩形减小矩形，直到两个矩形相等，目标是最后的矩形面积最小。题目最后的说明要求：中间不能出现一个矩形大面积大于另一个的两倍的情况。可以说这道题的sample说明才是本体啊。

从描述中可以知道，完成第一刀之后后面的发展是确定的，但由于规模很大，我们不可能去枚举第一刀的情况。可以反过来思考，事实上，知道了最后的结果，比如最后是两个a*b的矩形，那么我们也可以反过来推出之前较大的那个矩形依次是2a*b, 3a*b, 5a*b, 8a*b …，这不正是著名的Fibonacci数列么。目标是a*b尽量小，也就是要找最大的Fibonacci数f，使得m%f==0||n%f==0，10^9内的Fibonacci数不过几十个，枚举就可以了，答案就是m*n-m*n/f。注意要用long long。

ZOJ2706 Thermal Death of the Universe

source code (ZOJ2706.cpp) [SegmentTree, floor/ceil, off-by-1]