Archive for the “solution” Category


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]

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

Comments 6 Comments »


Andrew Stankevich’s Contest #2
ZOJ2337 Non Absorbing DFA 18.36% (92/501)
ZOJ2338 The Towers of Hanoi Revisited 35.60% (115/323)
ZOJ2339 Hyperhuffman 22.30% (252/1130)
ZOJ2340 Little Jumper 22.22% (72/324)
ZOJ2341 Quantization Problem 42.85% (84/196)
ZOJ2342 Roads 36.70% (116/316)
ZOJ2343 Robbers 37.35% (133/356)
ZOJ2344 Toral Tickets 43.41% (56/129)

最小生成树和二分图最优匹配你可能都熟悉得不能再熟悉了,可是把它们巧妙的隐藏到题目中,再通过不等式组(整数规划问题)联系起来呢?ZOJ 2342 Roads强烈强烈强烈推荐。然后可以通过ZOJ2344复习一下Burnside引理|Polya计数定理;做做ZOJ2338的扩展Hanoi问题;有爱的还可以挑战一下ZOJ2340,一道不简单的数学(物理?)参数搜索题。

ZOJ2337 Non Absorbing DFA

downloadsource code (ZOJ2337.java) [BigIntger, DP, graph]

已知一个DFA,问有多少长度为N的字符串会被accept。与普通DFA不同的是这里多了一个G,如果某边有G(u,c)=1,则沿这条边,字符串的第一个字符不会被移除。

Deterministic finite automation (DFA),好像不需要了解也可以。首先对G做预处理,在某点沿某条边出发,如果有G(u,c)=1的环,说明永远不会accept,否则我们就将这条边指向第一个G(u,c)=0处,经过这样处理以后,问题就是在一个普通的DFA了。然后只要在这个普通的DFA,也就是有向图上,做动态规划就好了,dp的两维状态分别是长度和所在节点。

ZOJ2338 The Towers of Hanoi Revisited

downloadsource code (ZOJ2338.java) [DP, recursive]

解决n个盘m根棍的河内塔(谁翻译的汉诺塔,zhua啊)

相信传统Hanoi问题的解大家都烂熟于胸了,不过这道题能够检验你是否真正理解了Hanoi和背后的递归思想。如果需要,可以看看《具体数学》的第一章补补课哦。

Comments 7 Comments »


Andrew Stankevich’s Contest #4
ZOJ2559 The Smart Bomb 53.76% (321/597)
ZOJ2560 I Just Called … 21.05% (76/361)
ZOJ2561 Order-Preserving Codes 18.28% (126/689)
ZOJ2562 More Divisors 30.14% (322/1068)
ZOJ2563 Long Dominoes 37.94% (148/390)
ZOJ2564 The Magic Wheel 17.11% (83/485)
ZOJ2565 Cracking SSH 50.25% (98/195)
ZOJ2566 Periodic Tilings 33.81% (47/139)
ZOJ2567 Trade 16.66% (97/582)
ZOJ2568 Counting Triangulations 16.31% (101/619)
ZOJ2569 Unfair Contest 28.57% (64/224)

这套题居然有11道,还是有不少好题的,尤其是ZOJ2566 Periodic Tilings,非常好的一道题,利用数学结论,可以转换为美丽的图论。还有ZOJ 2568是非常不错的计算几何模型动态规划;ZOJ 2561也是动态规划,用到了四边形不等式优化;ZOJ 2567,上下界最小流。

ZOJ2559 The Smart Bomb

downloadsource code (ZOJ2559.cpp) [math]

给定三个圆的圆心,要求圆不能相交,但可以相切,要使三个圆的半径和最大,问三个圆的半径各应该是多少。

显然要使三个圆两两相切,设三角形三边为a, b, c,三个圆半径为x, y, z就有
\left\{\begin{array}{l}x+y=c\\y+z=a\\z+x=b\end{array}\right.
有唯一解。

Comments 6 Comments »


Andrew Stankevich’s Contest #5
ZOJ2587 Unique Attack 21.20% (263/1240)
ZOJ2588 Burning Bridges 23.92% (410/1714)
ZOJ2589 Circles 18.57% (120/646)
ZOJ2590 Linear Programming Dual 30.65% (42/137)
ZOJ2591 DVD 13.78% (79/573)
ZOJ2592 Think Positive 40.56% (527/1299)
ZOJ2593 Ranking 21.93% (84/383)
ZOJ2594 Driving Straight 19.64% (168/855)

好像是最水的一套,推荐ZOJ 2589欧拉公式太妙了;再则推荐一下ZOJ 2591的DP吧,还是很值得一写的。

ZOJ2587 Unique Attack

downloadsource code (ZOJ2587.cpp) [FlowNetwork]

恐怖分子计划用最小的代价破坏网络,以阻断AB之间的通信,问其方案是否唯一。

用最小的代价破坏AB间的网络,这就是网络流的最小割问题,于是这题就是问网络流的最小割是否唯一。判断最小割割是否唯一,我的方法是这样的,先求最大流,如果在残留网络中,从A出发bfs得到的割边和从B出发得到的一样,那么割就是唯一的。

ZOJ2588 Burning Bridges

downloadsource code (ZOJ2588.cpp) [Graph]

M个桥连通者N个岛屿,现在一些桥将被烧毁,但岛屿连通性不变,问那些桥一定不会烧毁。

题目要求的正是无向图的割边),dfs可解,可参考黑书2.4.4,注意重边的处理。

ZOJ2589 Circles

downloadsource code (ZOJ2589.cpp) [geometry, math, Euler's formula]

给定平面上的N个圆,问整个平面被分成了几个部分。

如果用圆离散化来解就太大自然了。这里可以用传说中的欧拉公式(Euler’s formula),χ=V-E+F来计算,V-vertices表示顶点数,E-edges表示边数,F-faces表示围成的面数。于是面的个数可以这样计算:对于几个相连的圆,其内有F=E-V+1个面,其中1是平面图情况的欧拉欧拉示性数(Euler characteristic);对于一个独立的圆,显然F=1;最后答案还要加上外部那个无穷大的面。通过求圆与圆的交点可以很容易的得到顶点数,边数和圆与圆是否相连,从而求得答案。

ZOJ2590 Linear Programming Dual

downloadsource code (ZOJ2590.cpp) [simulation]

输入线性规划,输出其对偶线性规划。

Comments 1 Comment »

这套体中推荐ZOJ 2674, ZOJ 2673, ZOJ 2676, ZOJ 2675。其中2674是欧拉函数,但模型非常赞;2673是非常不错的DP问题;2676是0-1分式规划与网络流相结合的经典中的经典。

ZOJ2670 Nonoptimal Assignments

downloadsource code (ZOJ2670 .c) [构造]

给定n,构造一个n*n的矩阵,使得按题目所给的“贪心”算法,不能得到正确解。

构造非常简单,下面是我的一种构造
\begin{pmatrix}0&1&1&\cdots&1\\0&2&2&\cdots&2\\0&0&2&\cdots&2\\\vdots&\vdots&\vdots&\ddots&\vdots\\0&0&0&\cdots&2\end{pmatrix}

ZOJ2671 Cryptography

downloadsource code (ZOJ2671.c) [math, SegmentTree]

有n<30000个2×2矩阵,m<30000次查询,每次查询需要快速回答区间[i, j]内矩阵的积(mod r)。

如果把矩阵换成整数,把求矩阵积换成求区间和(或最大/小值),那么这就是线段树一个经典的应用,而且是结构最为简单的一种线段树。而矩阵的乘积运算同样满足结合律((A*B)*C=A*(B*C)),符合应用线段数优化的条件,所以通过线段树,问题能在O(mlg(n))内解决。

ZOJ2672 Fibonacci Subsequence

downloadsource code (ZOJ2672.c) [DP, hash]

给定一个长度为n<=3000的序列,要求满足Fibonacci性质(c[i]=c[i-1]+c[i-2])的最长的子序列。

枚举c[1]=a[i]和c[2]=a[j],那么可以依次在序列中查c[3]=a[k], c[4], …其中k显然应该取满足a[k]==a[i]+a[j]&&k>j中最小的。但可能有很多比较长的序列,而对一个最大长度为m的Fibonacci序列,会被枚举到O(m)次,总的处理复杂度是O(m^2)的,会TLE。为了避免这种重复计算,引入动态规划,dp[i][j]表示c[1]=a[i], c[2]=a[j]的序列的最大长度,那么有dp[i][j]=dp[j][k]+1,DP复杂度为O(n^2)。最后问题的关键是已知i和j,如何得到k,一个map<a[k], k>可以满足要求,但是这里它太慢了,O(n^2lg(n))的复杂度将会超时。所以需要用O(1)的hash_map代替O(lg(n))的map,也可以自己实现哈希。

ZOJ2673 Hexagon and Rhombic Dominoes

downloadsource code (ZOJ2673.c) [DP, bitwise]

问用两个正三角形组成的棱形覆盖变长为n<=7的正六边形三角网格的方案数。

mp.2673

Comments 20 Comments »