

Andrew Stankevich’s Contest #11解题报告
Posted by watashi in solution, tags: andrewzta, solution, ZOJ
Andrew Stankevich’s Contest, Warmup | |||
---|---|---|---|
A | ZOJ3362 | Beer Problem | 23.95% (92/384) |
B | ZOJ3363 | Another Brick in the Wall | 16.66% (1/6) |
C | ZOJ3364 | Black and White | 15.47% (41/265) |
D | ZOJ3365 | Integer Numbers | 17.54% (239/1362) |
E | ZOJ3366 | Islands | 15.70% (38/242) |
F | ZOJ3367 | Counterfeit Money | 22.22% (24/108) |
G | ZOJ3368 | Chinese New Year | 0.00% (0/23) |
H | ZOJ3369 | Saving Princess | 13.10% (68/519) |
I | ZOJ3370 | Radio Waves | 15.28% (70/458) |
J | ZOJ3371 | Cheater’s Shuffle | 11.11% (4/36) |
K | ZOJ3372 | Gone Swimming | 44.82% (13/29) |
首先还是为8月22日的ACM × Touhou:东方专场ZOJ月赛做个宣传 (*广告时间结束*)
比较多中等题的一套题,这么多需要SPJ的题,让我写SPJ写到吐血。在ACM_DIY有不少人反映TL有点紧,于是以后注意放得更宽一点吧。
ZOJ3362. Beer Problem
source code (ZOJ3362.cpp) [FlowNetwork, MinCostMaxFlow]
城市1可以生产任意数量的啤酒,销往城市2~n,每个城市都有不同的售价,但销量是无限的,但连接城市的道路只能运输有限数量的啤酒,并且产生运费。要求最大收益。
比较明显的一个最小费用最大流,城市1就是源,增加一个汇,每个节点到汇的流量无穷大,费用为售价的相反数,然后可以最短增广路算法做。不过赔本的买卖可是不做的哟,所以如果关于费用的最短路长度是正的,就break。内部训练的时候只有ForWarD过了这道题,我想了也没敢写,但ZOJ上在戴牛的带领下却成了过题数第二多的题目 orz
ZOJ3363. Another Brick in the Wall
source code (ZOJ3363.cpp) [bitwise, DP, if-else]
给出一个砖块是稳定的四种条件,问有多少种第一层为m个连续砖块,一共n层的砖墙?
规模不算太大,注意到某一行是否稳定只和上下两行有关,于是可以用二进制记录状态来动态规划,用2^(n+n)来最后两行的状态,再2^n枚举行加上行的掩码,并要保证中间那行的所有砖块都是稳定的。可以用二进制来判断中间那行是否稳定。假设从下到上的三行分别是a, b, c,那么:
if (b == (b & ( (a & (a << 1)) | // case 2 (a & c & ~(c << 1)) | // case 3.1 ((a << 1) & (c << 1) & ~c) | // case 3.2 (a & (b << 1)) | // case 4.1 ((a << 1) & (b >> 1)) // case 4.2 ))) { if (i & 1) { dp[i + 1][(b << n) ^ c] += dp[i][j]; } else { dp[i + 1][(b << m) ^ (c << 1)] += dp[i][j]; } }
当然,比赛的时候还是怎么暴力,怎么简单,就怎么写,程序实在慢了就打表交。注意最大的答案刚好超出int,可以用unsigned int。
ZOJ3364. Black and White
source code (ZOJ3364.cpp) [area, counting, off-by-1]
问一个无限国际象棋棋盘内的简单多边形内有多少黑/白格子。
类似于求多边形面积,从头到尾扫一遍就好了。主要要避免off-by-1的bug,比如负数的时候。挺简单的一套题,因为跟风的关系做的人不多。
ZOJ3365. Integer Numbers
source code (ZOJ3365.cpp) [greedy]
修改最少的数,使得结果序列是连贯的。
这里连贯只指公差为1的等差数列,公差-1的不算,也过不了sample,我当时也理解错了,今天也有很多人问。显然对结果有b[i]-i=constant,所以只要对所有a[i]-i计数,取计数count最多的差diff,最优解就是改变n-count个数,得到{diff+i}。只要复杂度正确的算法,应该不会TLE。
ZOJ3366. Islands
source code (ZOJ3366.cpp) [DisjointSet]
在一个六角网格(hexagonal grid),依次加入一些六边形,如果加入后会产生大于s的联通块的话,则该次加入操作被忽略。问执行所有操作后,各个联通块的大小。
利用并查集来维护每个联通块及其大小,每次加入一个六边形,如果新的联通块的大小超过了s,那么不加入它,注意回滚所有操作,不要留下你在判断部分产生的某些副作用。值得注意的是,奇数列和偶数列的相邻六个位置的相对坐标是不一样的。
ZOJ3367. Counterfeit Money
source code (ZOJ3367.cpp) [enumeration, DP, 直方图最大矩形]
求两个由大写字母构成的矩形的最大公共矩形区域。
题目要求一个O(n^4)的算法,首先我们枚举第二个矩形相对第一个矩形的偏移(x, y),这样O(n^2)就用掉了,此后只要考虑对应下标字符相等。记dp[i][j]为从第i行第j列向上,两个矩形一共有连续几个字符相等,这个可以O(n^2)动态规划出来。预处理出dp[i][j]后,对每个dp[i],都可以再O(n)的求出最大矩形区域,这是一个经典问题 (参考ZOJ1985 Largest Rectangle in a Histogram)。
ZOJ3368. Chinese New Year
source code (ZOJ3368.cpp) [geometry, search]
问一个边长为整数a, b, c的三角形里最多能放多少个单位圆,如果超过10个,当作10个。
方法就是——暴力搜索!有三种情况,圆在三角形的角上;圆与两个圆相切;圆与一个圆和一条边相切。要每次不断通过这三种情况求出新的可选圆心的位置,dfs,并且要标记搜过的状态。说起来简单,写起来可不轻松。为了更好debug,我还动用了metapost,把结果转成图像的话,还是很容易发现代码错在哪的(比如有圆相交,或者偌大的三角形就只在角上放了圆)。解题报告最开始的图片就是用mpost画出的所有解的图片,所有eps矢量图打包在这里。
ZOJ3369. Saving Princess
source code (ZOJ3369.cpp) [DP]
嗯……救公主。对每个怪兽你可以选择干它或者睡它。比它强壮才能干它,并掉血长力量;比它聪明才能睡它,并掉魔长智力。
dp[i][j][k],其中i表示搞定前i个怪兽,j表示其中干了几个,那么就睡了i-j个,k表示魔,dp记录血。简单来说就是要把五维的状态降到三维,转移的时候要注意可干性和可睡性的判断。
ZOJ3370. Radio Waves
source code (ZOJ3370.cpp) [binary search, DisjointSet]
二维平面上有n个基站,他们的覆盖半径要相同,且希望最大。每个基站可以使用两个频率中的一个,但是一个地方不能被两个使用相同频率的基站同时覆盖。
首先想到二分覆盖半径,然后如果两个基站的距离不超过覆盖直径的话,那么他们应该使用不同的频率,也就是应该是一个二分图,如果不是二分图,说明二分的半径偏大,判断二分图只要dfs着色就可以了。也可以用并查集来做,如果产生矛盾,说明二分的半径偏大。自己写得程序跑了不到1s,当时设时限觉得5s就足够了,就过好多人TLE,所以改到10s了。
ZOJ3371. Cheater’s Shuffle
source code (ZOJ3371.cpp) [bidirectional search, hash]
给你不超过5种洗牌规则,现在问是否能通过恰好不超过15次操作,把不超过36张牌从一个排列洗到另一个排列。
如果直接bfs或dfs,那么状态多达5^15=30517578125,虽然有一些重复的,但还是太大。改用双向搜索,状态就只有5^8=390625,就在可接受范围了。所以从初状态出发搜floor(t/2)步得到集合S,从末状态出发反搜ceil(t/2)得到集合T,对S里任一状态s,如果T中有相同状态t,那么有解,为了快速判断是否有相同状态,需要哈希,不过map应该也可以。
ZOJ3372. Gone Swimming
source code (ZOJ3372.cpp) [shortest path, simulation]
一个矩形泳池,又分成了一个一个矩形区域,每个区域深度不同,水源再其中一个区域,问整个水池满要多久。满的水会往边界外流,流量和边界长度成正比。
每次计算出每个区域当前的容量和进水速度,然后计算出哪个区域最先满,需要多少时间,然后更新这个区域满后其它区域的容量和进水速度,继续求,直到整个泳池满为止。算法类似最短路加模拟,题目规模很小,TL非常松。应该不难,但大家都被提交少吓跑了,相反内部训练的时候只有一个队伍没过这题。
Passed both my MCSA and MCSE with the dumps from itlibraries, if you plan to go for a certification exam I advise using their dumps.
if (i & 1) {
dp[i + 1][(b << n) ^ c] += dp[i][j];
} else {
dp[i + 1][(b << m) ^ (c << 1)] += dp[i][j];
}
请问B题的这部分代码作何解释?谢谢!
m = n + 1
这个就是计数和偶数行的砖块有半块的错位
可是当 if (i&1) b不是应该左移m的吗?为什么 b<<
可是当 if (i&1) b不是应该左移m的吗?为什么 b<< n ?
还有你的代码过不了- -
ZOJ3371. Cheater’s Shuffle
这题map过不了…无尽TLE…=.=
我把我的代码稍加修改成用map的可以过,不过用了20+s
2266374 2010-08-17 22:51:05 Accepted 3371 C++ 24400 60500 watashi@Zodiac
悲剧~~错过了这场经典的比赛T-T
Saving Princess太合我胃口了。。shi哥这题的解题报告好邪恶O(∩_∩)O
B题的解法太给力了.膜拜shi哥
hope to make the 3370 more clear when using disjointset.thanks
没有人圆满-.-
我校光头
被A题的通过率骗了的某人路过……