现在的版本是去阿里巴巴前写好的,之后基本就没什么进展了。最近被数次问到了月赛解题报告,真不好意思,只好发个半成品了 >_< 哎呀呀,题解说不定要烂尾了~


ZOJ Monthly, July 2011
A ZOJ3510 Boring Assignment Expressions 14.28% (3/21)
B ZOJ3511 Cake Robbery 14.04% (66/470)
C ZOJ3512 Financial Fraud 6.35% (22/346)
D ZOJ3513 Human or Pig 18.78% (127/676)
E ZOJ3514 Palindromic Mighty String 8.33% (1/12)
F ZOJ3515 ToT 1.29% (5/387)
G ZOJ3516 Tree of Three 21.06% (357/1695)
H ZOJ3517 Tower VII 0.00% (0/25)
I ZOJ3518 Unsafe Factor 15.57% (246/1579)
J ZOJ3519 Who is the Smartest Man 29.07% (574/1974)

这个月是浙江大学集训队个人选拔赛的日子,而我作为教练也是每天早出晚归。而除此以外,还有许多集训以外的事情要处理,特别是最近两周非常忙+睡眠不足。这也是为什么这次解题报告没有及时发布的原因。不过拖集训队老人和小朋友们的福,下个月的ZOJ Monthly, Auguest 2011将举办第二回东方专场ZOJ月赛(The 2nd Touhou Only ZOJ Monthly),敬请期待。(第一回东方专场ZOJ月赛的详情在这里。)

ZOJ3510. Boring Assignment Expressions

downloadsource code (ZOJ3510.cpp) [bfs, expr_eval, topsort, sp]

有许多赋值表达式,现在要求按顺序执行某些表达式,使得所有变量的值最小。要求输出方案。

注意到只有加法和乘法操作,而加法和乘法操作只会比表达式的值不小于其中任何一个变量的值。所以可以从小的值开始,基于类似拓扑排序的条件,通过best-first search求最短路。至于表达式和输出方案,就考验基本功或模块了。

ZOJ3511. Cake Robbery

downloadsource code (ZOJ3511.cpp) [greedy, simulation, list, SegmentTree]

一个凸包,沿着不相交的对角线切若干次,问最后得到的最大(边数最多)的凸包是多大。

先把所有切操作的按一定顺序排序,这样可以保证每次切出去的部分就不会再被切成两份。然后依次切,每次只要求切出去的蛋糕块大小就可以了。可以用线段树维护没被切出去的节点,复杂度O(nlgn)。不过更好的办法是直接用循环链表(ZOJ3511list.cpp),复杂度只有O(n)。

ZOJ3512. Financial Fraud

downloadsource code (ZOJ3512.cpp) [greedy, LeftistTree, SkewHeap]

已知一个数列a,要构造一个递增数列b,目标是\sum{|a[i]-b[i]|}最小,求这个最小值。

似乎是old题。首先我们知道,如果目标是找一个数c使得\sum{|a[i]-c|}最小,那么c应该取中位数。基本算法是贪心构造b,初始b[1]=a[1]。每加入a[k],先令b[k]=a[k]。然后看b是否满足单调性,如果不满足,假设b[i-1]<b[i]=…=b[j-1]>b[j]=…=b[k],m是a[i..k]的中位数,那么令b[i]=…=b[k]=m,不断重复这个操作,直到b满足单调性。>_< 证明曾今听懂了,现在忘了……

为了快速求得集合的中位数,这题还需要用可并堆(左偏树斜堆)优化。对于对应相等的b的集合a,我们只将较大的一半元素舍去,将包括中位数在内的较小的一半元素插入可并堆。每次,我们都只需要将两个可并堆合并,如果原先两个集合的大小都是奇数,那么还要再pop出一个元素,这样堆顶就是所需的中位数。

ZOJ3513. Human or Pig

downloadsource code (ZOJ3513.cpp) [game theory, golden ratio]

一个具有人猪二象性的东西从(x,y)开始跳跃,每次跳跃可以到(x-k*y,y)或者(x,y-k*x)。作为人的时候,他可以做出选择,作为猪的时候,它会随机跳跃。跳过之后会从人变成猪或者从猪变成人,但是如果跳到河里面就不能变了。这个东西从(x,y)开始跳跃,可以从人和猪里面选择一个身份。如果这个东西想要最终变成人,应该选择什么?

直接类似博弈问题,按题意动态规划或记忆化搜索即可。不过因为x和y都可以很大,而x*y有限制,不能用二维数组,要用一维数组。事实上这题有结论,对于黄金分割率φ=1.618…,如果i/φ≤j≤i*φ,那么(i,j)对应Pig,否则对应Human(ZOJ3513phi.cpp)。

ZOJ3514. Palindromic Mighty String

这题算法不唯一,以后有空再补……

ZOJ3515. ToT

downloadsource code (ZOJ3515.cpp) [math, counting]

要求x=0, y=x和y=H-Y/X*x三条直线围成的三角形内的格点数。

矩形内的格点个数非常显然,所以我们只考虑求满足条件0≤x<Z && 0≤y && y*X≤x*Y的格点个数gao(X, Y, Z)。

long long gao(long long x, long long y, long long z) {
	long long ret = 0;
	long long c;
	c = z / x;
	ret += c * ((x + 1) * (y + 1) / 2 - y);	// FULL_TRI
	ret += c * (c - 1) / 2 * (x * y);		// FULL_RECT
	z %= x;
	ret += c * y * z;						// REM_RECT
	if (z > 0) {
		if (x <= y) {
			c = y / x;
			ret += c * z * (z - 1) / 2;		// MOD_RECT
			ret += gao(x, y % x, z);		// MOD_TRI
		} else {
			c = y * (z - 1) / x + 1;
			ret += c * z;					// COMP_RECT
			ret -= gao(y, x, c) - 1;		// COMP_TRI - 1
		}
	}
	return ret;
}


(1)首先对于X*Y的左闭右开的矩形,格点数为X*Y,FULL_RECT对应图中蓝色部分;对于一个完整的三角形,由对称性可以很容易求得其格点数为(X+1)*(Y+1)/2-Y,FULL_TRI对应图中绿色部分;如果X整除Z,那么答案很显然,否则,对应剩下的矩形部分,也可以简单求得,REM_RECT对应图中紫色部分;于是关键就是求最后的红色部分了。

然后分两种情况讨论:(2.1)如果X不大于Y,那么有Y/X大于1,于是我们可以将格点分成两部分,MOD_RECT的矩形部分很好求;而MOD_TRI的三角形部分可以转为gao(X, Y%X, Z%X)递归求。

(2.2)如果X小于Y,那么我们可以考虑求它关于大矩形的补,也就是要求黄色部分,我们转而求红色部分,因为它们的格点数之和就是矩形的COMP_RECT+1,其中定点处重复计算了1。

ZOJ3516. Tree of Three

downloadsource code (ZOJ3516.cpp) []

ZOJ3517. Tower VII

downloadsource code (ZOJ3517.cpp) [tree, dfs, dp, merge, set_operation]

那啥……题目描述很混乱……总之就是给一个有根树,选择k个叶子和一个节点,目标是叶子到该节点的k条路径的总长度最大。

比赛时标程有错,而且TL给得太少了,规模也不太合理,rejudge后hos.lyric AC了。这题有复杂度O(n*k)的算法,不过常数比较大,不知道O(n*k*lg(k))的算法是否能AC。首先通过后序遍历处理出对应子树中的叶子到根的top-2*k。然后通过前序遍历求出非子树中的叶子到自己的top-k。最后再枚举所有节点,求出所有叶子到自己的top-k的总和,更新最优解。求的过程其实就是在不断的merge(merge_sort),每次merge的复杂度是O(k)的,每个节点merge一次,所以复杂度是O(n*k)的。。这里补充一点,其中第二步要用到第一步的结果,这也是为什么第一步求top-m是不够的,一定要求top-2*k。具体过程看代码,具体原因自己想。

ZOJ3518. Unsafe Factor

downloadsource code (ZOJ3518.cpp) []

两条长度均为L的纸带,粘帖在一起成为一个新的纸带。要求最大的连续区域,其中恰有一条纸带是损坏的。

由于纸带长度L不是太大,所以直接桶排序标记,然后扫描就好了。

ZOJ3519. Who is the Smartest Man

downloadsource code (ZOJ3519.cpp) [greedy]

曹操如果打败一个智力比自己高的人,智力加2;否则,智力加1。给定n个人,问曹操能按任意顺序打败他们后能达到的最大智力。

先将所有人按智力由低到高排序,然后顺序扫描。如果当前的人智力不比曹操高,那么留到最后打败;否则,立即打败,智力+2。

17 Responses to “[题解]ZOJ Monthly, July 2011beta
  1. left_hand says:

    ZOJ3513. Human or Pig

    巫教,貌似黄金分割的结论打反了吧?
    i/φ≤j≤i*φ => i*φ≤j≤i/φ

    顺便问下黄金分割的结论怎么推导?有相关资料么?

    • watashi says:

      fixed
      没有严格的证明,思路可能是,如果人的时候在一个自由度大于1的地方是OK的,然后黄金分割率应该来自于gcd过程中的Fibnacci数列

  2. fuch says:

    Financial Fraud:设f(i,b)是只考虑a1,a2,…,ai范围,bi不超过b的最优解。对于固定的i,f(i,b)关于b递减,并且函数图像是由若干段斜率为整数的线段构成。从f(i,b)推f(i+1,b)其实就是维护这些线段的斜率,然后用个树状数组就行了。O(n*logn*logn)的时间。

  3. creepyuncle says:

    shi哥去阿里实习了?tip:可以蹭网易班车哦,免费得。。。

  4. VeegtableB says:

    zoj那里写错了你也跟着错……

  5. 猛犸也钻地 says:

    假,明显是有妹子所以无心ACM了

  6. 木子日匀 says:

    哦哈哈哈。我也是Gao

  7. xiaodao says:

    膜拜函数名叫 “gao(){}” 的。。。T T)

  8. xiaodao says:

    。。。真的有。。Orz )

  9. sakuya says:

    原来说好的东方专场真的有~

  10. zplinti1 says:

    终于出来了

  11.  
Leave a Reply