pic

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月赛做个宣传 :D (*广告时间结束*)

比较多中等题的一套题,这么多需要SPJ的题,让我写SPJ写到吐血。在ACM_DIY有不少人反映TL有点紧,于是以后注意放得更宽一点吧。

ZOJ3362. Beer Problem

downloadsource code (ZOJ3362.cpp) [FlowNetwork, MinCostMaxFlow]

城市1可以生产任意数量的啤酒,销往城市2~n,每个城市都有不同的售价,但销量是无限的,但连接城市的道路只能运输有限数量的啤酒,并且产生运费。要求最大收益。

比较明显的一个最小费用最大流,城市1就是源,增加一个汇,每个节点到汇的流量无穷大,费用为售价的相反数,然后可以最短增广路算法做。不过赔本的买卖可是不做的哟,所以如果关于费用的最短路长度是正的,就break。内部训练的时候只有ForWarD过了这道题,我想了也没敢写,但ZOJ上在戴牛的带领下却成了过题数第二多的题目 orz

ZOJ3363. Another Brick in the Wall

downloadsource 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

downloadsource code (ZOJ3364.cpp) [area, counting, off-by-1]

问一个无限国际象棋棋盘内的简单多边形内有多少黑/白格子。

类似于求多边形面积,从头到尾扫一遍就好了。主要要避免off-by-1的bug,比如负数的时候。挺简单的一套题,因为跟风的关系做的人不多。

ZOJ3365. Integer Numbers

downloadsource code (ZOJ3365.cpp) [greedy]

修改最少的数,使得结果序列是连贯的。

这里连贯只指公差为1的等差数列,公差-1的不算,也过不了sample,我当时也理解错了,今天也有很多人问。显然对结果有b[i]-i=constant,所以只要对所有a[i]-i计数,取计数count最多的差diff,最优解就是改变n-count个数,得到{diff+i}。只要复杂度正确的算法,应该不会TLE。

ZOJ3366. Islands

downloadsource code (ZOJ3366.cpp) [DisjointSet]

在一个六角网格(hexagonal grid),依次加入一些六边形,如果加入后会产生大于s的联通块的话,则该次加入操作被忽略。问执行所有操作后,各个联通块的大小。

利用并查集来维护每个联通块及其大小,每次加入一个六边形,如果新的联通块的大小超过了s,那么不加入它,注意回滚所有操作,不要留下你在判断部分产生的某些副作用。值得注意的是,奇数列和偶数列的相邻六个位置的相对坐标是不一样的。

ZOJ3367. Counterfeit Money

downloadsource 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

downloadsource code (ZOJ3368.cpp) [geometry, search]

问一个边长为整数a, b, c的三角形里最多能放多少个单位圆,如果超过10个,当作10个。

方法就是——暴力搜索!有三种情况,圆在三角形的角上;圆与两个圆相切;圆与一个圆和一条边相切。要每次不断通过这三种情况求出新的可选圆心的位置,dfs,并且要标记搜过的状态。说起来简单,写起来可不轻松。为了更好debug,我还动用了metapost,把结果转成图像的话,还是很容易发现代码错在哪的(比如有圆相交,或者偌大的三角形就只在角上放了圆)。解题报告最开始的图片就是用mpost画出的所有解的图片,所有eps矢量图打包在这里

ZOJ3369. Saving Princess

downloadsource code (ZOJ3369.cpp) [DP]

嗯……救公主。对每个怪兽你可以选择干它或者睡它。比它强壮才能干它,并掉血长力量;比它聪明才能睡它,并掉魔长智力。

dp[i][j][k],其中i表示搞定前i个怪兽,j表示其中干了几个,那么就睡了i-j个,k表示魔,dp记录血。简单来说就是要把五维的状态降到三维,转移的时候要注意可干性和可睡性的判断。

ZOJ3370. Radio Waves

downloadsource code (ZOJ3370.cpp) [binary search, DisjointSet]

二维平面上有n个基站,他们的覆盖半径要相同,且希望最大。每个基站可以使用两个频率中的一个,但是一个地方不能被两个使用相同频率的基站同时覆盖。

首先想到二分覆盖半径,然后如果两个基站的距离不超过覆盖直径的话,那么他们应该使用不同的频率,也就是应该是一个二分图,如果不是二分图,说明二分的半径偏大,判断二分图只要dfs着色就可以了。也可以用并查集来做,如果产生矛盾,说明二分的半径偏大。自己写得程序跑了不到1s,当时设时限觉得5s就足够了,就过好多人TLE,所以改到10s了。

ZOJ3371. Cheater’s Shuffle

downloadsource 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

downloadsource code (ZOJ3372.cpp) [shortest path, simulation]

一个矩形泳池,又分成了一个一个矩形区域,每个区域深度不同,水源再其中一个区域,问整个水池满要多久。满的水会往边界外流,流量和边界长度成正比。

每次计算出每个区域当前的容量和进水速度,然后计算出哪个区域最先满,需要多少时间,然后更新这个区域满后其它区域的容量和进水速度,继续求,直到整个泳池满为止。算法类似最短路加模拟,题目规模很小,TL非常松。应该不难,但大家都被提交少吓跑了,相反内部训练的时候只有一个队伍没过这题。

13 Responses to “Andrew Stankevich’s Contest #11解题报告”
  1. Sammie says:

    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.

  2. bird says:

    if (i & 1) {
    dp[i + 1][(b << n) ^ c] += dp[i][j];

    } else {
    dp[i + 1][(b << m) ^ (c << 1)] += dp[i][j];
    }

    请问B题的这部分代码作何解释?谢谢!

  3. poemelife says:

    ZOJ3371. Cheater’s Shuffle

    这题map过不了…无尽TLE…=.=

    • watashi says:

      我把我的代码稍加修改成用map的可以过,不过用了20+s
      2266374 2010-08-17 22:51:05 Accepted 3371 C++ 24400 60500 watashi@Zodiac

  4. 死肥羊 says:

    悲剧~~错过了这场经典的比赛T-T
    Saving Princess太合我胃口了。。shi哥这题的解题报告好邪恶O(∩_∩)O

  5. shǎ崽 says:

    B题的解法太给力了.膜拜shi哥

  6. p03 says:

    hope to make the 3370 more clear when using disjointset.thanks

  7. Navi says:

    没有人圆满-.-

  8. Ramboo says:

    被A题的通过率骗了的某人路过……

  9.  
Leave a Reply