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

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

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

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

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

ZOJ3511. Cake Robbery

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

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

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

ZOJ3512. Financial Fraud

source 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

source 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

source 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

source code (ZOJ3516.cpp) []

略

略

ZOJ3517. Tower VII

source 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

source code (ZOJ3518.cpp) []

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

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

ZOJ3519. Who is the Smartest Man

source code (ZOJ3519.cpp) [greedy]

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

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

This entry was posted on Sunday, August 7th, 2011 at 1:58 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.