Posts Tagged “geometry”


Andrew Stankevich’s Contest #3
ZOJ2361 SGU209 Areas 18.12% (62/342)
ZOJ2362 SGU210 Beloved Sons 45.40% (173/381)
ZOJ2363 SGU211 Strange Counter 28.12% (63/224)
ZOJ2364 SGU212 Data Transmission 11.95% (104/870)
ZOJ2365 SGU213 Strong Defence 36.40% (83/228)
ZOJ2366 SGU214 Weird Dissimilarity 13.31% (84/631)
ZOJ2367 SGU215 PL/Cool 22.91% (33/144)
ZOJ2368 SGU216 Royal Federation 24.80% (64/258)
ZOJ2369 SGU217 Two Cylinders 15.71% (94/598)

还是先推荐两道构造题2363 Strange Counter2368 Royal Federation2361 Areas是一道coding量很大的计算几何题,而2367 PL/Cool是一道考验基本功的蘑菇题。2363 Data Transmission是一个值得再研究的分层图的阻塞流问题。

ZOJ2361/SGU209 Areas

downloadsource code (ZOJ2361.cpp) [geometry, 计算几何, dfs]

题目描述很简单,问给定的n条线把平面分出了几个有限的区域。

规模为80,不得不ym那些用优化的半平面交轻松AC这道题的牛人们,但我觉得这不能算a right approach。

我的算法是O(n^2lg(n))的。

Comments 10 Comments »

这套体中推荐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 »