ZOJ Monthly, January 2011
A ZOJ3457 Absence Number 19.32% (23/119)
B ZOJ3458 A Simple Math Problem 8.33% (7/84)
C ZOJ3459 Extraordinary 24-Point Game 0.00% (0/0)
D ZOJ3460 Missile 21.73% (20/92)
E ZOJ3461 Money Transfer 30.43% (7/23)
F ZOJ3462 Nobita’s New Filesystem 11.53% (3/26)
G ZOJ3463 Piano 40.74% (11/27)
H ZOJ3464 Rugby Football 42.37% (114/269)
I ZOJ3465 The Hive 28.51% (71/249)
J ZOJ3466 The Hive II 11.11% (1/9)

因为学校忙完才到家,所以monthly的准备显得有些仓促,结果原本推迟安排在这个月的几道题还是没有整理出来,转而挑了几道不那么需要fix的题。下个月的monthly在两周后,寒假应该有些闲暇去整理他们了,争取能放出来。J题有人过了,但C题没人提交,原本以为I题是最水的,结果比较意外,没被圆满,值得庆幸。已经是2011年了,summer2010的题也用了过大半了,之后就是校赛和省赛了,然后离summer2011也不远了^ ^

ZOJ3457. Absence Number

downloadsource code (ZOJ3457.cpp) [misc]

给定一个两位数N,求最小的m,使得1/m的十进制表示中恰好包含除N以外的所有两位数。

最大的解是N=0时m=76344。题目的输入只有100种,所以可以暴力跑表,1/m十进制表示是循环小数,且在m步内开始循环,所以很容易求得其包含的所有两位数,最后判断一下是否满足条件就好了。注意不要漏数了两个循环节头尾组成的那个两位数,否则有几个数据会WA。更简单的方法是不判断循环节,直接循环m+1步。加上一些优化后,这个表实际可以在1s之内跑出。

ZOJ3458. A Simple Math Problem

downloadsource code (ZOJ3458.py) [math]

find \lfloor(\sqrt{a}+\sqrt{b})^n\rfloor \mod 2(a+b) , where 0 < b - a < 1 + 2\sqrt{a} \text{ and } n \text{ is even}

结果就是

ans = \left\{\begin{array}{rl}-1,&\quad n=4k+2 \\ 2(-(a-b)^2)^\frac{n}{4}-1,&\quad n=4k \end{array}\right. \mod 2(a+b)

下面的证明则给出了更一般的结论,和GCJ某道涉及黄金分割率的题非常像。

题目保证了0<\sqrt{b}-\sqrt{a}<1,考虑x_n=(\sqrt{b}+\sqrt{a})^{2n}=(a+b+2\sqrt{ab})^ny_n=(\sqrt{b}-\sqrt{a})^{2n}=(a+b-2\sqrt{ab})^nz_n=x_n+y_n。那么x_1y_1是方程u^2-2(a+b)u+(a-b)^2=0的根,于是有z_{n+2}=2(a+b)z_{n+1}-(a-b)^2 z_n。又显然y_n<1,所以\lfloor x_n\rfloor = z_n-1,于是由z_0=2z_1=2(a+b),利用矩阵乘法就可以求任意的\lfloor x_n\rfloor \mod m了。取m = 2(a+b)就能得到上面的结论。

ZOJ3459. Extraordinary 24-Point Game

downloadsource code (ZOJ3459.cpp) [enumeration, search, game]

有四张判定牌,司马懿可以用自己的手牌改判定,而张角可以用自己的黑色手牌换判定牌。现在两者博弈,司马懿先手,目标是使得最后判定牌能算出24点,问谁必胜。

首先通过枚举/搜索,预处理出所有能算出24点的组合。之后就是必胜必败的博弈搜索了,因为司马懿的牌越用越少,所以状态显然不会有环,这题的规模不需要考虑记忆化,完全暴搜就足够快了。

ZOJ3460. Missile

downloadsource code (ZOJ3460.cpp) [parameter search, bigraph]

略。

先二分答案再做二分图最大匹配。

ZOJ3461. Money Transfer

downloadsource code (ZOJ3461.cpp) [mst, dp]

/* by quark */

集训队分学校的奖金的时候,由于学校只把钱发给每个队第一个人,然后又由于每个人可能加入了不同的队伍,所以当刚从学校拿到钱的时候,有的人会多拿,有的人会少拿,有些人之间有一定长度的道路联通。

定义一次传送为一个人通过一个的路径把非负的钱送给另外一个人,无论钱数额多少,此过程花费为路径的长度。

现要求最终传送的结果为每个人都拿到自己应得的数额,求最小化所有传送的花费和。

/* by quark */
这个题目可以被理解成:一个无向图,有边权(非负)和点权(整数),把这个图划分成几个连通子图,在每一个子图,点权和为 0,最小化 Sum{i 的边权利和,{i 是一个划分出的子图} }。考虑划分出的一个子图,如果其中的点权和为 0,那么它的传送花费就是这个子图的最小生成树。于是问题转换成把原图划分成几个点权和为 0 的连通子图,最小化它们的 MST 和。

于是问题就是求2^n次部分和,再对部分和为0的mask求最小生成树,最后枚举子集动态规划可解。

ZOJ3462. Nobita’s New Filesystem

downloadsource code (ZOJ3462.cpp) [bitset, misc]

每个文件都有一个tag集合和一个大小,现在查询包含给定tag子集的所有文件的大小之和。

乱搞或利用位压缩优化,用bitset非常好写。

ZOJ3463. Piano

downloadsource code (ZOJ3463.cpp) [dp]

一只手,相对拇指不动,至少要占5个键的位置,至多可以弹到9个键。拇指移动距离x需要花费floor(sqrt(x)),已知左右手初始位置和接下来需要弹奏的1000个键,求最小花费。

DP[k][i][j]表示弹完k个键,左手在i,右手再j的最小花费。每次转移就是枚举左手移到新的位置i’并弹第k++1个键,或右手移到新的位置j’并弹第k+1个键,其它情况不会更优,不需要考虑,对于弹不到第k+1个键的情况,直接设为INF。注意只处理有用的状态,不然要超时的。最后下面的东西可能有一些有帮助的信息。

ticket102

ZOJ3464. Rugby Football

downloadsource code (ZOJ3464.cpp) [greedy]

贪心,策略就是让速度最快的童鞋跑最后T秒,第二快的跑倒数第二棒,依次类推。

ZOJ3465. The Hive

downloadsource code (ZOJ3465.cpp) [the-beginner-problem]

dead do.

ZOJ3466. The Hive II

downloadsource code (ZOJ3466.cpp) [dp, ]

题目要求的就是在一个n*8的六边形网格(蜂巢),其中挖去m个后的部分,用若干个圈划分,有多少不同的划分方法。

基于连通性状态压缩的动态规划、插头DP(参考cdq的ppt)。不同之处就在于问题从正方形转到了正六边形。标程是先按行再按列来做的,需要特殊处理头尾,最吐血的是还要分奇偶,轮廓线上的边数可能是增加的或减少的,需要大量的肉。我的程序则是按行做,但先做偶数列,再做奇数列,这样轮廓线上的边数是固定的,中间只要简单的转换一下就可以了,写起来很简单。

23 Responses to “[题解]ZOJ Monthly, January 2011”
  1. [...] 第一种无疑是最SB的……但是有时候也还是挺有效的。可是万一写错,就是一个个改……实在有点蠢……而且有一些差别容易忘了改掉。 第二种是比较oop的做法,只要设计好接口。但是这样整体的case划分框架还是得弄出来,但是比第一种好多了,也比较容易让人接受。 第三种是最神的,首先得清楚地了解哪些状态可以通过参数合并,然后再设计好对应的参数,不想清楚选这种简直是找死……(详情可以参看shi哥ZOJ3466的代码) 而我发现自己很难做到第三种,大概是因为我在写代码前,根本没有做到完全想清楚每一个转移怎么搞。还有一个原因可能是不太擅于对相似的事物找出共同点并归类。 这种感觉和看functional programming的感觉有点类似,要具备能迅速反应出a其实是b的能力才会比较舒服。 [...]

  2. iSea says:

    表示您的C题标程写错了好像
    算出合法的24点组数少了一些:
    譬如 1 2 7 7
    (((7 * 7) – 1) / 2)
    因为你的测试里面少了
    fabs(invoke(op[0], invoke(op[1], b[3], invoke(op[2], b[1], b[2])), b[0]) – 24) < EPS
    fabs(invoke(op[0], b[0], invoke(op[1], invoke(op[2], b[2], b[3]), b[1])) – 24) < EPS
    这样才能得到正确的 566 组 合法序列
    而必须要写成你这样忽略掉正确的其他6组
    1 2 7 7
    1 3 4 6
    1 6 6 8
    3 3 8 8
    3 8 8 10
    4 4 10 10
    才可以过此题
    搞不懂为什么还有人过了…

    • iSea says:

      ps: 1 3 4 6
      6 / (1 – 3/4) 是合法的吧?

    • iSea says:

      噢… 貌似忽略这几组也可以过…
      是我后面写的有问题…

      • watashi says:

        谢谢指出
        嗯,只能说数据不够强,我碰巧混过了
        原作者应该已经对数据把过关了,但黑箱测试难免有疏漏
        月赛题挂出来前通常有多人验证过,所以数据一般是不会错的

  3. zjut_DD says:

    插头那道我用两个数组记录一行8个洞和上面轮廓线和下面轮廓线接触面搞过了,看了神牛的代码表示…….好短-_-
    int qian[8][20]={
    {3,0,1,2},
    {4,2,3,4,5},
    {2,3,4},
    {4,6,7,8,9},
    {2,7,8},
    {4,10,11,12,13},
    {2,11,12},
    {3,14,15,16}
    };
    int hou[8][20]={
    {3,0,1,2},
    {2,2,3},
    {4,3,4,5,6},
    {2,6,7},
    {4,7,8,9,10},
    {2,10,11},
    {4,11,12,13,14},
    {1,14}
    };

  4. Yuan says:

    请问一下神牛,
    “和GCJ某道涉及黄金分割率”
    您还记不记得是哪题呢?

  5. MatRush says:

    3462题解里有部分是3461的吧>__<

  6. quark says:

    发现自己的解题报告多了一个“利”字,明天开始要赶紧 fix 输入法了 -.-bb

  7. VegetableB says:

    moon姐的题这么大自然的呀……

  8. AekdyCoin says:

    0rz

  9. lccycc says:

    除了膜拜,还是膜拜

  10. chnlich says:

    我只是来膜拜的。。

  11. aaahexing says:

    sf && moondy的标程有一行被转义了==!

  12.  
Leave a Reply