ZOJ Monthly, May 2011
A ZOJ3500 Electron Cloud 27.20% (139/511)
B ZOJ3501 Roman Order 30.79% (400/1299)
C ZOJ3502 Contest 15.11% (78/516)
D ZOJ3503 Quadratic Surface 2.28% (4/175)
E ZOJ3504 P-norm 49.43% (262/530)
F ZOJ3505 Yet Another Set of Numbers 28.00% (42/150)
G ZOJ3506 Cut the Tree 17.94% (21/117)
H ZOJ3507 Fractal 13.20% (66/500)
I ZOJ3508 The War 13.53% (226/1670)
J ZOJ3509 Island Communication 4.24% (7/165)

一是准备给包括在去年参加过集训在内的xpies一次新手上路前热身的机会。二是因为神奇的原因,存有summer2009和summer2010数据的ZOJ服务器在省赛后被拔网线了。所以这次的题目来自校赛省赛未用题(ABCD)、summer2007(J)和summer2008(EFGHI)。就算题目总体看来水题很多啦,不过两个小时被圆满什么的>_<,何方神圣啊orz(台大一队?)……不管怎样把五月份混过去了,下次Monthly大概在六月底了吧……

ZOJ3500. Electron Cloud

downloadsource code (ZOJ3500.cpp) [math]

求两个球的并的体积。

判断两个球的位置关系和圆没有区别,在相离、相切和包含的时候很简单,所以主要就是要考虑相交的情况。这时候的体积是两个球冠的体积,球冠的体积可以很简单的积分得到:

\int_{z=-r}^{h}{\pi\sqrt{r^2-z^2}^2}=\pi r^2(h+r)-\frac{1}{3}\pi(h^3+r^3)

而要求h1h2,也只要解:

\left\{\begin{array}{ccccl}h_1 & + & h_2 & = & d_{12} \\ h_1^2 & - & h_2^2 & = & r_1^2 - r_2^2 \end{array}\right.

vls特意把精度和数据都出得很低,所以数值积分也是行得通的。

ZOJ3501. Roman Order

downloadsource code (ZOJ3501.cpp) [sorting]

将数字按它们的罗马数字表示排序。

将数字转成pair<roman, arabic>,然后直接sort就好了。最近才知道,原来这种常见的技术有个名字叫“Schwartzian Transform”

ZOJ3502. Contest

downloadsource code (ZOJ3502.cpp) [DP]

按顺序尝试10道题,每道题的AC概率与前面尝试过的题目有关,由给定的概率表决定。要求字典序最小的最优尝试顺序。

很显然的动态规划,2^10表示尝试过的题目,记录字典序最小的最优方案和对应的期望。注意比较浮点数时要使用eps。实现得好搜索应该也没问题。

ZOJ3503. Quadratic Surface

downloadsource code (ZOJ3503.cpp) [math, 秩, 行列式, 一元三次方程]

Conic Section的姊妹题,原计划是一起出在省赛的。作为“圆锥曲线”的加强版,“二次曲面”没有b=0这样的简化条件,要求一个一般的三元二次方程对应的二次曲面类型。不过题目中给出了判别的算法,所以只要实现就好了。

根据题目中所给的算法,需要求矩阵的秩(rank)和行列式(det),这个可以用高斯消元法求得。求k比较麻烦,可以通过求对称矩阵的特征根(eig)或解一元三次方程的根求得。求三次方程的根可以用卡丹公式,不过我用了不同的算法。首先,我们知道三次方程一定有一个实根(事实上对于这题三个都是实根),且对于首相系数为1的三次方程,f(-inf)=-inf,f(inf)=inf,所以我们可以用数值的二分法求出一个实根。然后方程降为我们熟悉的一元二次方程,轻松求解。

这题的数据是通过先随机出一个二次曲面类型,再随机出对应的标准方程,最后通过随机的镜面、旋转和平移后去掉可能的ill-formed case生成的。生成器是ruby写的ZOJ3503gen.rb

ZOJ3504. P-norm

downloadsource code (ZOJ3504.cpp)

求两个N维复向量的差的P-范数。

dead do。比较麻烦的就是输入了。用std::complex和istream可以直接读入”(Re,Im)”格式的复数,所以如果用istringstream读入的话,是一件很轻松的事。

ZOJ3505. Yet Another Set of Numbers

downloadsource code (ZOJ3505.cpp) [DP, counting]

比较经典的DP加计数问题模型,可以算这类问题里比较简单的一个例子。只要实现str2id和id2str两个函数就好了。DP只是简单的sum{3^i},而计数部分,也就是str2id和id2str这两个函数,也和最经典的那种求第k个C(n, m)组合的算法一样。PS: 题目所描述的集合其实是相当于是给一个深度为n的三叉树的每个节点进行遍历标号。

ZOJ3506. Cut the Tree

downloadsource code (ZOJ3506.cpp) [DP]

对一棵树做恰好k次cut操作,每次可以cut一条边,然后丢掉其中一部分而得到一棵新的树。要求最后得到的树的最小/最大权值和。

比较经典的树形DP模型,其中每个节点对所有儿子又是一个二维DP。DP记录以该节点为根,cut了0 ~ k次所能得到的最小/最大权值。每次有两种选择,一种是保留child,这样update(dp[parent][a + b], dp[parent][a] + dp[child][b])。另一种是直接舍去这棵子树,这样update(dp[parent][a + b], dp[parent][a]),其中b可以取1 ~ sizeOfSubtree(j),而不仅仅是1。最后的答案包括两种情况,一种是根在最优解中,那么就是dp[root][k]。否则假设i是最优解中离根最近的点,那么最优解是dp[i][k - j],其中j可以取1 ~ (n – sizeOfSubtree(i)),同样j不仅仅可以取1。

附上更强大的测试数据

Sample Input:

6 2
-3 1 -2 3 4 0
1 2
1 3
2 4
3 5
3 6
6 3
-3 1 -2 3 4 0
1 2
1 3
2 4
3 5
3 6
6 4
-3 1 -2 3 4 0
1 2
1 3
2 4
3 5
3 6
6 5
-3 1 -2 3 4 0
1 2
1 3
2 4
3 5
3 6

Sample Output:

-5 4
-5 4
-5 4
-3 4

ZOJ3507. Fractal

downloadsource code (ZOJ3507.cpp) [recursion]

打印分形,要求rstrip(trailing spaces)。

对于分形问题,递归什么的也是很经典的算法了。不能输出trailing spaces是稍微麻烦一点的地方,最简单的办法是先把答案存到一个string/char[]里,去掉trailing spaces后再输出。事实上也可以通过相似的递归算法的判断一个字符是不是这一行的最后一个非空格字符,这样就不需要用那么多内存了。

ZOJ3508. The War

downloadsource code (ZOJ3508.cpp) [greedy]

n个士兵,每个士兵有可以装备重量在[ai, bi]的装备。然后有m个重量在wi的装备。问最多可以装备多少士兵。

很经典的排序加贪心模型。首先按b排序,然后扫描,每次选取尽量小的满足a<w<b的装备装备该士兵,如果不存在,则–ans。正确性挺容易证明的,不再赘述。

ZOJ3509. Island Communication

downloadsource code (ZOJ3509.cpp) [graph]

有n个岛,初始没有桥,每次可以在i和j间建一座桥,拆一座桥,或查询i和j是否联通。点数n=500,操作数m=50000。i和j之间最多只会建一次桥。

由于点数只有500,其实这题不需要任何高级的数据结构就有一个O(n*m)的算法。注意到点数很少,而要求i和j是否联通,我们只要保留这幅图的生成森林就足够了,即控制边的个数为O(n)。对于查询操作,直接dfs一次即可。对于加边操作,如果i和j不联通,那么直接加上这条边就好了。否则,加上这条边后一定形成一个圈,如果我们把这个圈中最早被删去的边提前删掉,是不会影响后面操作的结果的,所以我们删掉这条边,以保证图中始终没有圈。对于删边操作,如果这个边已经被提前删掉了,那么什么也不做,否则简单删掉就好了。要知道哪条边先被删掉,可以先读入所有操作,预处理之。对于每次操作,复杂度均为O(n),总的复杂度O(n*m)。

46 Responses to “[题解]ZOJ Monthly, May 2011”
  1. left_hand says:

    弱问巫教,您的ZOJ3502. Contest标程是不是有点小BUG。。。
    可能本弱菜想错了。。。特来请教

    q > dp[k] – EPS && pre[k ^ (1 << i)] dp[k] – EPS 已经成立。
    如果此时pre[k ^ (1 << i)]=”ABCD“ ,pre[k]=”ABCDE“ ,那么pre[k ^ (1 << i)] < pre[k]返回true(前缀虽然一样,但是因为前者更短所以还是返回true),使得整个if成立。

    那么您的代码接下来会执行:

    pre[k] = pre[k ^ (1 << i)];
    pre[k] += ('A' + i);

    那么有没有可能存在 ('A' + i)=‘F’?这样 pre[k]=”ABCDF“ 反而比原来的 ”ABCDE“ 大了。。。

    • left_hand says:

      复制的时候出了点问题。。。
      第三行代码在这: if ((q > dp[k] + EPS) || (q > dp[k] – EPS && pre[k ^ (1 << i)] < pre[k]))

      • watashi says:

        不知道我当时有没有想过这一点,但是实际这一段代码应该是没有问题的,因为pre[k]永远只会是某__builtin_popcount(k)个字母的permutation,所以不存在同时可以是ABCDE和ABCDF的情况。
        pre[k ^ (1 << i)]实际上可以唯一确定pre[k]。所以比较pre[k ^ (1 << i)]和比较pre[k].substr(0, __builtin_popcount(k) – 1)是等价的。

  2. creepyuncle says:

    island communication是不是有一种利用并查集的,从后往前处理数据的方法?

  3. longpo says:

    cut the tree rejudge了?

  4. bill says:

    [ZOJ3508. The War] 如果我先对b从大到小排序,b相等时a从大到小,武器w也从大到小排,然后用武器从大到小枚举匹配人,这种想法和你的做法有什么不同吗?经测试,这种做法在zoj是wa的, 你能举出反例吗 ?

  5. ssspp says:

    [Cut The Tree]的复杂度是多少???

  6. ssspp says:

    [Cut The Tree]的复杂度是多少?

  7. unique says:

    大神的程序为什么用了这么多的assert() 有什么好处吗

    • watashi says:

      1. 作为出题者或者验题者,应该对输入数据的格式assert,确保输入符合题目描述;
      2. 做题的时候也可以加入assert,帮助debug;提交后如果RE,也可以知道assert fail了;但多余的assert可能让能AC的程序反而RE了

  8. xiaoshua says:

    问一句,3505这题你代码里的dp[i]是什么意思,我是理解成剩下i位,且已经保证第i位与第i-1位不同的方案数,但如果这样理解,dp[i]=4^3(i-1)才对啊,为什么dp[2]=13?

  9. lengxiang says:

    Yet Another Set of Numbers

    数学方法给过的…

  10. Jackie says:

    貌似A题的数据中没有[两个球的相交部分占用了某个球的超过半球大小的体积]的情况,我的程序没有特判这种情况也AC了,请问能不能加强一下数据?thx

    • watashi says:

      我觉得应该有这种数据了
      我加了11组数据rejudge后AC数ms没有变化

      • lccycc says:

        我也没判断这种情况 可是也过了。。。
        按理说这是不对的吧

        • watashi says:

          也许是你虽然没考虑,但是其实能处理?
          你能找到cha掉自己程序的数据吗,如果有的话,可以email一份代码和数据给我吗,我再看看,我现在加了
          0 0 0 50 0 0 x 49 (x = 0, 20, …, 100)
          的数据

  11. Jackie says:

    YMshi神,貌似A题测试数目里面没有[两个球相交部分占用了某个球超过半球的体积]的情况,我的程序没有特判这种情况也AC了,能不能加强点数据.thx

    • xiaoshua says:

      是我们多考虑了,那个积分公式对2种情况都是适用的~~~。。 我看了阿shi的代码 也觉得一定错的,但是随机了几百组数据,都和我程序出来的结果是一致的。现在总算明白了。

  12. caicai says:

    没怎么想C题,直接暴力360000w复杂度,加个剪枝就过了。。。(汗。)

  13. tongjiantao says:

    大神,I题我只看到了网络流,狂超时啊~网络流可解吗??

  14. daizhenyang says:

    ….G居然被随机乱选一部分dp过了

  15. yningc says:

    今天的那个D题圡问为什么高斯消元的eps到1e-6就AC而1e-8死也过不掉,还有就是那个判断三个根的符号是否相同其实不用把根求出来的,MS可以根据方程的系数计算出符号是否相同的几高~

  16. longpo says:

    Fractal 那题,如果10*10的举证扩大12倍应该太大了,存不了,而且输出的也太多了

  17. Scriptkids says:

    板凳。。。

  18. fookwood says:

    我是过来抢沙发的,今天只做了一个题就呼呼睡觉了。。。

    今天瞬间ak的kelvin是谁啊?太威武了。。。

  19.  
Leave a Reply