ZOJ Monthly, September 2010
A ZOJ3396 Conference Call 10.73% (208/1937)
B ZOJ3397 Change the Major 11.20% (13/116)
C ZOJ3398 Warden 1.50% (2/133)
D ZOJ3399 Classes Division 6.87% (9/131)
E ZOJ3400 Treasure Hunting 3.67% (16/435)
F ZOJ3401 Guitar 34.04% (96/282)
G ZOJ3402 Marble 10.00% (2/20)
H ZOJ3403 Strange Calendar III 8.78% (194/2208)
I ZOJ3404 Sticker 22.22% (2/9)
J ZOJ3405 Counting Factor Trees 11.62% (137/1179)

因为国内Regional网络赛时间安排的关系,把月赛挪到了九月初,也正好作为一次热身赛吧。希望大家都在接下来两周的网络预赛顺利,然后得继续看时间表安排接下来月赛的时间了。最近这段时间ZOJ各种抽风,好在Monthly的时候还是比较正常,最近ZOJ的dev工作总算看到的重新开始的可能,希望刚成立的ZOJ dev team能够搞好ZOJ 2.1的bug/feature的维护更新,还有传说中的ZOJ 2.7的开发。

ZOJ3396. Conference Call

downloadsource code (ZOJ3396.cpp) [ShortestPath, enumeration]

题目已知的是一个500个点10000条边的无向图,然后有50个查询,每个查询要求选择总权值最小的边集合,使得所查询的三个点连通。

首先以这三个点出发求单源最短路sp(s, t),然后最优答案就是min{sp(x, v) + sp(y, v) + sp(z, v)},所以只要枚举一个中间点v就好了。如果没有注意到Y字型为最优解的情况,直接取min{sp(x, y) + sp(y, z), sp(y, z) + sp(z, x), sp(z, x) + sp(x, y)}是不对的。关于这个问题更一般的结论是:(Steiner tree problem)n个节点的斯坦纳树最多有n-2个中间节点,此题便是n-2=1的情况。

这题最多求3*50=150<<500的单源最短路就够了,不用求出所有点对间的最短路(我的程序很圡,是这么干的),floyd是要TLE的。

ZOJ3397. Change the Major

downloadsource code (ZOJ3397.cpp) [Hanoi Tower, recursive]

这题是河内塔一个有趣的变体,只能移动最小的圆盘变成了只有绩点最高的同学才能转系,而三个杠子化作了计算机系、中文系和数学系。这题的特别之处在于,计算机系和数学系之间不能直接转系,只能通过中文系做跳板。现在已知所有人所在系、目标系和绩点,问最少要经过多少次转系才能满足所有人。

这题由于问题的特殊性,其实中间每个状态都可以简单的转为一个三进制数表示,于是答案就是order(end)-order(begin)。作者用的就是这种方法,不过我和asmn做的时候都没有发现这一点,用的是处理这类问题更一般的方法,也就是用递归解河内塔。河内塔的问题很经典,《具体数学》第一章递归就重点介绍了这个问题,Andrew Stankevich’s Contest #2里也有个打印n个disc,m个peg版河内塔方案的问题。我之前也做过一个求传统的河内塔从一个状态移到另一个状态所需最小步数的题目,不过一时找不到题目了。ZOJ上还有一道求河内塔在第k步的状态的逆问题ZOJ1566. Too Lazy To Move

回过头来还是说我对这题一般解法的理解。首先假设这题是要打印步骤,那么显然是要按绩点从低到高处理:

  • 如果他已在目标位置,那么不动;
  • 如果他要从计算机(数学)到中文,或者从中文到计算机(数学),那么首先把绩点更高的人移到数学(计算机),这部分递归做,然后实现转系;
  • 如果他要从计算机(数学)到数学(计算机),那么就相当于先做从计算机(数学)到中文,再做从中文到数学(计算机);
  • 而这题要求步数,直接模拟复杂度太大。其实只要做一个变化就可以了,就是当要做把n个人都从一个系转到另一个系的时候,直接返回预先DP求得步数就可以了。把n个人从计算机转到中文需要(3^(n-1)-1)/2步,而转到数学需要3^(n-1)-1步。说了一大堆,其实代码很短的……

    ZOJ3398. Warden

    downloadsource code (ZOJ3398.cpp) [蘑菇, 记忆化搜索]

    这题题目需要考虑的情况比较复杂,问题的状态有五维,包括sarchmage, swarden, mana, hp和poison,然后就是枚举Warden的各种决策做搜索,如果不加上记忆话的话会超时。题目有很多人肉的超强case,不要过度优化,每一个错误的优化都可能会导致WA。

    ZOJ3399. Classes Division

    downloadsource code (ZOJ3399.cpp) [动态规划, 单调队列]

    分班,要求把相邻的学生分到同一个班,班级的大小在A和B之间,班级的数量不超过K个,每个班级有一个值g[i],假设第i个同学在G[i]班,则目标是要sum{(x[i]-L)^2*g[G[i]]}尽量小,其中L是所有x的平均数。

    援引moon姐的解题报告:

    设dp[n][k]表示将前n个小朋友分到前k个班中,易写出状态转移方程:

    • dp[n][k] = min {dp[i][k - 1] + gk * (sum[n] – sum[i]) | A ≤ n – i ≤ B}
    • sum[n] = sigma {(xi – L)2 | i ≤ n}

    但现在的状态数为10000×200,转移复杂度为O(n),显然会TLE。将转移方程整理一下:

    • dp[n][k] = gk * sum[n] + min {dp[i][k - 1] – gk * sum[i] | n – B ≤ i ≤ n – A}

    固定k时,当n增大,方程的形式不变,只是可选范围改变。对于n转移到n+1时,i=n-B的状态不可再选,而i=n-A的状态应该加入可选范围内。故可维护一个单调递增队列,每次转移之前将新的可选状态从队列尾插入,且把比其大的都pop出,同时保证队列头的元素在可选范围之内。这样每次转移就可以只取队列头的元素,将转移复杂度降为O(1)。总的时间复杂度为O(n*k),空间复杂度为O(n)。

    ZOJ3400. Treasure Hunting

    downloadsource code (ZOJ3400.cpp) [计算几何]

    已知不超过n条端点是格点线段,问有多少不同的格点在线段上。

    首先处理overlap的线段,把overlap的线段合并成新的线段,要注意合并的顺序,确保该合并的都合并了。然后对于只有一条线段的情况,假设其两个端点分别是(x1, y1)和(x2, y2),那么它上面有gcd(x1 – x2, y1 – y2) + 1个格点。对与多条线段的情况,我们只要减去重复计算的部分,这只要和前面的线段求出格点交点,然后放到set里(或者sort | uniq一下)就能统计出来。复杂度是O(n^2)的。

    最好都使用整数运算,然后中间过程int是可能会溢出的。

    ZOJ3401. Guitar

    downloadsource code (ZOJ3401.cpp) [_]

    题目有点长,不过读完了题的话,这显然是个简单题。

    ZOJ3402. Marble

    downloadsource code (ZOJ3402.cpp) [misc, 循环节]

    简单来讲就是有一个n*m的board,每一秒每个格子都会做一个操作,问t秒后值最大的格子的值。

    注意到所有序列长度都不超过6,所以取LCM=60就是一个公共循环节,很容易想到矩阵乘法,复杂度是O(x^3(60+lgt)),这里x=n*m。我用的则是O((60*x)^2)的算法,我还以为后者比前者小,显然是我脑残了……我的算法应该可以再改到O(60*x^2),验题的时候没认真想,结果悲剧了。

    算法其实不复杂,就是注意到,所有的弹珠都是产生后就只是不断移动,要么是循环移动,要么会某一步后消失,所以我们只要预处理出所有位置在各种可能的时间产生的弹珠的轨迹就好了。之后就是把相同的部分做合并,然后简单的统计求出最后各个格子内的弹珠数。

    ZOJ3403. Strange Calendar III

    downloadsource code (ZOJ3403.cpp) [_]

    对这种求间隔问题,我通常喜欢写一个函数求得某个点关于选定原点的间隔,然后答案就是两个间隔的差。这题有一个trick,就是题目要求的是”between the two days”,后面的日期可能比前面的要早!

    ZOJ3404. Sticker

    downloadsource code (ZOJ3404.cpp) [graph, DP, math, counting]

    那个,首先背景和配图什么的就略过了。题目说的就是你有m种交换方式,用a交换别人的b,这可以看成一个a到b的有向边,题目保证了每个顶点的入度和出度都不超过1。题目问的是有多少种不同的序列,能够通过变换,最后成为一个n的排列。

    注意每个顶点的入度和出度都不超过1,所以每个联通分量只有可能是链或环。对于环的情况,显然就可以任意分配了,所以环内部任意交换的顺序有mm(A000312)种。对于链的情况,这是一个非常经典的问题,答案是m+1m-1(A000272)种(一个非常漂亮证明),也可以通过动态规划dp[i][j] = sum{c[j][k] * dp[i - 1][k]}求得,其中答案就是dp[m][m],c[j][k]表示{j \choose k}。有了这些基础,就只要先构图,再求出所有联通块的大小,并判断它是链还是环,最后直接算出答案。

    ZOJ3405. Counting Factor Trees

    downloadsource code (ZOJ3405.cpp) [factorization, DP, counting]

    题目定义了所谓的“因数树”,它是一个二叉树,每个父亲节点都是两个子节点的乘积,叶子节点都是素数,节点是有序的。问根节点为给定n的“因数树”一共有多少种。

    首先可以对题目所给的n做因数分解,于是我们知道有多少个叶子节点,他们分别都是什么。然后答案就是两个部分的乘积,一个就是m个叶子节点所能构成的不同的二叉树,另一个则是这m个叶子节点的顺
    序。前者就是Catlan数(A000108)\frac{{2n \choose n}}{n + 1},也可以通过动态规划dp[i]=sum{dp[j] * dp[i - j] | j = 1 … i – 1}求得。而假设n=p1^r1p2^r2…pk^rk,那么后者就是{m \choose r1}{m-r1 \choose r2}\cdots{rk \choose rk}如果注意计算顺序的话,是可以避免使用大数,只需long long的(我的程序比较圡,用了大数)。

    这题和Sticker的算法差不多,不过简单多了。

    32 Responses to “ZOJ Monthly, September 2010解题报告”
    1. [...] 今天鱼头组织了第一次组队赛,用的是浙大2010年九月份的月赛。题目质量不错,发现有一份watashi的解题报告,大家可以过去围观,上面还有各题的代码,对于想要赛后AK的队员非常有帮助。 [...]

    2. zsasuke says:

      请问,zoj3404中的那个dp【i】【j】表示的是什么含义呢?谢谢

    3. mark1989 says:

      一个学习的好地方!
      希望博主继续开下去,支持!

    4. 3xian says:

      好喜欢这个博客哇

    5. wangzhihao says:

      我在你的代码3402的第47行加了一句 if( (end – begin) != LCM)while(1); 。结果发现end – begin == LCM, 我不明白这是为什么。谢谢~

      • watashi says:

        这没什么奇怪的啊
        比如1×1的格子,永远做1这种操作

        • wangzhihao says:

          但是为什么所有情况,都是相等呢

          • watashi says:

            未必吧,最有可能的就是LCM的一个倍数,或者走成死路吧

            • wangzhihao says:

              当然如果不考虑走成死路的情况,我加if( (end – begin) != LCM)while(1);交了一遍,也能通过.这说明数据中的所有循环节都等于LCM,也就是60!!这非常奇怪。然后 val[xy.first][xy.second] += p * (op[i][j][k % LCM] – ’0′);是否是说相同格子的每隔LCM会走到同一个终点xy?一共有p个相同的格子。这个我不明白, 这 p 个格子是什么意思?

    6. a ques says:

      请问 ZOJ 3404 。

      假设 是 0 –> 1 –> 2 —>0的 环 。。
      那么总的情况有 3^3
      难道 ( 0 , 0 , 0 )这种 也算了的 。 。
      这个如何交换成 ( 0 , 1 ,2)的 呢 ?

    7. xo.jam says:

      话说ZOJ3404的数据怀疑有错,怀疑n有负数。

    8. XWR says:

      对Counting Factor Trees题解中的一点疑惑 :
      然后答案就是两个部分的乘积,一个就是m个叶子节点所能构成的不同的二叉树,另一个则是这m个叶子节点的顺序。
      我想问的是:1。其中的二叉树是指题目定义的因数树吧?
      2。其中的m个叶子节点,叶子节点不是素数么?还能构成不同的二叉树?

    9. tt says:

      oooooooooooooooooooorz…

    10. 慕容云海 says:

      D output 里的 There is a blank between cases. 是什么意思。。。。

    11.  
    Leave a Reply