现在的版本是去阿里巴巴前写好的,之后基本就没什么进展了。最近被数次问到了月赛解题报告,真不好意思,只好发个半成品了 >_< 哎呀呀,题解说不定要烂尾了~
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
略
略
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
两条长度均为L的纸带,粘帖在一起成为一个新的纸带。要求最大的连续区域,其中恰有一条纸带是损坏的。
由于纸带长度L不是太大,所以直接桶排序标记,然后扫描就好了。
ZOJ3519. Who is the Smartest Man
source code (ZOJ3519.cpp) [greedy]
曹操如果打败一个智力比自己高的人,智力加2;否则,智力加1。给定n个人,问曹操能按任意顺序打败他们后能达到的最大智力。
先将所有人按智力由低到高排序,然后顺序扫描。如果当前的人智力不比曹操高,那么留到最后打败;否则,立即打败,智力+2。
ZOJ3513. Human or Pig
巫教,貌似黄金分割的结论打反了吧?
i/φ≤j≤i*φ => i*φ≤j≤i/φ
顺便问下黄金分割的结论怎么推导?有相关资料么?
fixed
没有严格的证明,思路可能是,如果人的时候在一个自由度大于1的地方是OK的,然后黄金分割率应该来自于gcd过程中的Fibnacci数列
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)的时间。
shi哥去阿里实习了?tip:可以蹭网易班车哦,免费得。。。
木有啦,临时工而已,已经做完了……
不过我们都打的来回的 =________=b
zoj那里写错了你也跟着错……
555 哪里?
ZOJ Monthly, Auguest 2011
ym 你改过来的么= =b
ZOJ那个就是我写错的!!
范叔改的吧……
范叔v587!
假,明显是有妹子所以无心ACM了
哦哈哈哈。我也是Gao
膜拜函数名叫 “gao(){}” 的。。。T T)
。。。真的有。。Orz )
原来说好的东方专场真的有~
终于出来了