Posts Tagged “andrewzta”


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 »


Andrew Stankevich’s Contest #1
ZOJ2313 Chinese Girls’ Amusement 34.16% (233/682)
ZOJ2314 Reactor Cooling 26.61% (297/1116)
ZOJ2315 New Year Bonus Grant 35.25% (239/678)
ZOJ2316 Matrix Multiplication 44.19% (293/663)
ZOJ2317 Nice Patterns Strike Back 24.05% (115/478)
ZOJ2318 Get Out! 19.91% (94/472)
ZOJ2319 Beautiful People 26.34% (254/964)
ZOJ2320 Cracking’ RSA 31.41% (82/261)

大妈题第一套的解体报告。个人推荐ZOJ 2318ZOJ 2320。AC代码含,可直接看或下载

ZOJ2313 Chinese Girls’ Amusement

downloadsource code (ZOJ2313.cpp) [number theory]

求最大的k<=n/2使得gcd(n,k)=1。

如果n是2m+1形式的,那么k=m就是答案;
如果n是4m形式的,那么k=2m-1就是答案;
如果n是4m+2形式的,那么k=2m-1就是答案。
证明略,需要简单的高精度。

ZOJ2314 Reactor Cooling

downloadsource code (ZOJ2314.java) [FlowNetwork, 上下界最大流]

求一个无源汇的上下界网络流的可行流。

裸的上下界网络流问题,规模也很小,最暴力的网络流算法也没问题。至于上下界网络流可行流转化为普通网络流最大流的构图和原理,看论文吧(明白了很简单,虽然要独立想到绝对不容易)。

ZOJ2315 New Year Bonus Grant

downloadsource code (ZOJ2315.java) [graph, greedy]

给定一棵树,要求找出一个最大的边集合,要求一个顶点上至多只有一个边属于这个集合。

对于一个图,这是一个一般图最大匹配问题;如果这个图没有奇环,那还是一个二分图匹配问题;而

Comments 10 Comments »