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非常松。应该不难，但大家都被提交少吓跑了，相反内部训练的时候只有一个队伍没过这题。

This entry was posted on Saturday, August 14th, 2010 at 5:15 pm and is filed under solution. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.