ZOJ Monthly, February 2011
A ZOJ3467 3D Knight Moves 7.14% (5/70)
B ZOJ3468 Dice War 39.82% (92/231)
C ZOJ3469 Food Delivery 13.33% (24/180)
D ZOJ3470 Magic Squares 42.85% (72/168)
E ZOJ3471 Most Powerful 21.23% (86/405)
F ZOJ3472 Play Bridge 66.66% (2/3)
G ZOJ3473 Radio Matrix 20.40% (20/98)
H ZOJ3474 Taekwondo 11.62% (15/129)
I ZOJ3475 The Great Wall I 46.15% (6/13)
J ZOJ3476 The Great Wall II 11.11% (1/9)

summer2010的题用得差不多了,无论简单题还是中等题都有些紧俏了,自己的几个idea又准备留给校赛和省赛,不舍得扔出来,于是从summer2008和summer2009里抠了几道题出来。即使去掉校赛和省赛两个monthly,到7月还要再坚持整理两套monthly呢,果然每场比赛都用10+道题太贅沢了么,难道要求助summer2007了……总觉得一场比赛有太多的圆满不太好,不过有好几道题没人过或没提交也不是太漂亮呢,选题验题好难啊 >______<

ZOJ3467. 3D Knight Moves

downloadsource code (ZOJ3467.cpp) [双向搜索, Bidirectional search]

判断在三维棋盘中,一步能跳(x, y, z)的马能否在6步之内从(x1, y1, z1)跳到(x2, y2, z2)。如果有,输出步数最少的字典序最小的方案。

马一步能跳到最多6*8=48个新的位置,6步能到的位置太多了,直接搜索空间太大,因为只要考虑6步,所以可以双向搜索,正搜3步,反搜3步。双向搜索还要求字典序最小的方案比较麻烦,不过因为只有3步,不妨在map中直接记录整个方案,然后要注意0步的case。

ZOJ3468. Dice War

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

签名题,可以DP求出n个骰子掷出m点的方案数/概率。事实上才8个骰子,哪怕是6^8枚举也OK。

ZOJ3469. Food Delivery

downloadsource code (ZOJ3469.cpp) [DP]

注意题目给的速度是v^-1,而不是v,所以答案总是整数。动态规划,最小费用dp[i][j][k],表示左边到第i个,右边到第j个都已近送出,而k={0, 1}分别代表最后是停留在左边还是右边。转移是O(1)的。

ZOJ3470. Magic Squares

downloadsource code (ZOJ3470.cpp) [counting, binary search]

在编号的回形方阵中,给定一个格子的编号,要求输出其上下左右格子的编号。

关键就是实现(x, y)和id的相互转换,找规律。暴力sqrt(id)的算法会超时,事实上再加上二分优化,lg(sqrt(id))的算法就好了,还可以不二分,得到O(1)的算法。

ZOJ3471. Most Powerful

downloadsource code (ZOJ3471.cpp) [DP, bitwise]

两个原子相撞,其中一个消失,产生若干能量。为给定的10个原子最多能产生多少能量。

很显然的mask DP,每次枚举哪两个原子相撞,哪个原子消失。

ZOJ3472. Play Bridge

downloadsource code (ZOJ3472.cpp) [simulation]

不算复杂的模拟题,直接模拟就好了,不过要注意看题,别漏了什么细节:

  • 出牌时总是出能出的最大的,这里只考虑SHDC的花色顺序,不考虑trump
  • 第一轮最先出牌的不是叫牌的,而是他的下家

ZOJ3473. Radio Matrix

downloadsource code (ZOJ3473.cpp) [counting, Number theory]

在三维空间的第一象限每一个整点有一个基站。(1, 1, 1)这个坐标的基站一开始是发送状态,并且发送编号为1的信息,而除此之外的其他基站一开始都处在接收信息状态。当一个基站接受到所有它能解码的信息之后,它就转为发送状态,并且发送它所接收到的最大编号+1的信息。能解码定义为:(x, y, z)能解码(x’, y’, z’)当且仅当x’|x且y’|y且z’|z。现在问从(1, 1, 1)到(x, y, z)的所有节点一共发送多少信息。

首先考虑一维情形。f(1) = 1,而f(n) = max{f(m) | m | n},于是可以得到,f(n)的n分解质因数后因数的个数+1,如果p是n的质因数,那么有f(n) = f(n / p) + 1。再来考虑三维情形,那么f(i, j, k) = (f(i) – 1) + (f(j) – 1) + (f(k) – 1) + 1 = f(i) + f(j) + f(k) – 2。也就是这三维其实是独立的,互不相关的,所以可以分开来计算,所以答案就是:


\sum_{i=1}^x{f(i)yz}+\sum_{j=1}^y{xf(j)z}+\sum_{k=1}^z{xyf(k)}-2xyz

通过筛法预处理后,可以O(1)求得。

ZOJ3474. Taekwondo

downloadsource code (ZOJ3474.cpp) [greedy]

首先,对于打倒某个对手至少需要多少体力,我们可以通过DP求得,实际上考虑背包大小只有7,只有三种物品,所以直接暴力三个for循环更简单。然后这个问题就和ZOJ3077 Move to Baggage Office类似了。所以可以直接参考这题的解题报告和证明。详见《ZOJ月赛的三个tooold解题报告》。根据证明可以知道,对于恢复的体力小于消耗的体力的战斗,应该按照恢复体力降序排列的顺序打。而对于恢复体力大于消耗体力,我们要用另一种贪心方式:按消耗体力升序排列的顺序打,这个证明非常显然,就不详细说明了。当然,总的顺序是先打恢复体力大于消耗体力的。所以是O(nlgn)的贪心。

PS: 原题是O(2^n)的DP,而且数据非常弱,任何错误的算法都可以过。现在我加强了数据,卡掉了很多错误的算法,不过规模还很小,复杂度较高的算法应该还能过。

ZOJ3475. The Great Wall I

downloadsource code (ZOJ3475.cpp) [Emuration, Flow network, Max-flow min-cut theorem]

在一个20*20的方格中,建造一些围墙,使得X和某些A与E和外界都不联通,建造围墙有对应的花费,而对于满足条件的A,有对应的收入。

首先2^5枚举哪些A要被围住,然后就要求所需的最小费用,这就是典型的最大流最小割问题。其中X和所枚举的A同源连一条流量为inf的边,E和边界同汇连一条流量为inf的边。

ZOJ3476. The Great Wall II

downloadsource code (ZOJ3476.cpp) [Computational geometry, DP, Emuration, Shortest path]

与上一题类似,惟一的区别是要求X和A要连通。

首先,我们预处理出包围任意国家的组合所需的最小建墙花费。对于一个网格中的多边形轮廓,要判断一个点是否在内部,只要看其上方的边数是否是奇数就可以了。首先枚举起点(x0, y0),d[x][y][z]表示到达点(x, y),且向上的射线与轮廓相交次数为奇数次的国家的mask为z的最小建墙花费。这相当于求10*10次10*10*2^6个点的最短路,其中起点为(x0, y0, 0)。求得最短路后,用d[x0][y0][z]更新包围国家组合z的最小建墙花费dp[z]。

由预处理出的dp数组,就能简单的求得将任意国家组合包围在一个单连通区域内的最小花费。不过最优解未必是单联通的,可能是从一个单联通区域内挖掉几个不相交的单连通子集!所以还要在dp数组的基础上再求一个子集枚举的动态规划得到的才是最优解。

55 Responses to “[题解]ZOJ Monthly, February 2011”
  1. AmazingCaddy says:

    “对于恢复的体力小于消耗的体力的战斗,应该按照恢复体力降序排列的顺序打”,这句话不是很理解,我觉得应该是按照消耗体力降序排列的顺序打,因为恢复费体力小于消耗的体力,那么每次战斗之后,体力会越来越少,所以要先打消耗体力最多的对手。

  2. yp says:

    给我说一下3471的思路,不胜感激!

  3. yp says:

    强烈要求解释3470的
    int q = upper_bound(a, a + MAXN, p) – a – 1;
    init();
    要实现什么功能?

  4. 卡卡 says:

    Taekwondo求解释。
    还有一个疑问。当消耗>恢复时,为什么不是按消耗降序打,因为如果刚开始打不过消耗最大的那个对手,那么以后肯定也是打不过的

  5. youKnowMe says:

    Can you see it? More code, better for learning :)

  6. youKnowMe says:

    Dude did you participated in Alberta Collegiate Programming Contest (ArcOfDream) ? Can you post your solutions from there?

  7. agralol says:

    Radio Matrix中的“f(i, j, k) = (f(i) – 1) + (f(j) – 1) + (f(k) – 1) + 1 = f(i) + f(j) + f(k) – 2”式子是如何得出的呢,后面的也不大理解。。可以稍微说的详细一些吗

    • watashi says:

      f(i, j, k)中i和j和k是独立的,你把小规模的打出来,或者手推一下就会明白为什么了

      • agralol says:

        我是这样想的,f(i,j,k)只取决与各自的质因子总数,设质因子总数为k的状态总数为s(k)的话,最后的答案为sum(s(k)*(k+1)),我自己画图的时候也是分层来画的,不知道这样想可不可以
        你的方法感觉很简洁,不过最后那一步真的不大明白。。

  8. mytifa says:

    I题不需要x和所选的A被围在在一起啊 。。。

  9. 死肥羊 says:

    每次来看shi哥的blog都很happyO(∩_∩)O

  10. Yuan says:

    请问一下神牛
    3474的O(2^n)的dp怎么做的呢?
    那个状态仅仅是一个mask吗?
    用不用考虑能量值S?

  11. Yuan says:

    3468
    “After a successful attack, the attacker’s pile of dices will split into two piles, while one of them has only one dice. If the attacker loses, this pile will lose all dices except one.”
    这几句话好像没用的?
    需不需要算一些 前几次attack失败而最后一次成功的那些概率?

  12. guest says:

    个人非常喜欢watashi的代码缩进风格。。。

  13. lengxiang says:

    来这里就是学习的,代码写得很好, 顺序学习位运算和STL…

  14. lxyxynt says:

    赞shi哥代码。。学长强力推荐的~

  15. tracyzhu says:

    您的代码怎么写好像都比别人快点…还各种stl..羡慕啊…

    • watashi says:

      过讲了,代码怎么写都快这是vb的招牌,我可不敢当
      在开-O2优化以后STL本来就不怎么吃亏的,不是极端情况的话,常数优化往往是编译器的工作,自己不得当的`优化`反倒可能不利于编译器的优化,适得其反
      不过我也遇到过针对cache调整for循环顺序或struct结构就让代码加速30%的例子

  16. uwi says:

    my Java code of problem C is almost same as yours, but TLEed..

    • watashi says:

      sorry for that, the TL of prob C seems to be somehow a little bit tight.
      i thought that five times of my solution was enough, but that isn’t always true.
      i will pay more attention to setting the TL next time.

  17. NULL says:

    相当赞shi哥代码风格啊~

  18. xiaoshua says:

    老大,您代码风格能改善下么。。。

    • watashi says:

      土问哪里需要改善……望指教……

      • xiaoshua says:

        看了你很多代码,函数名基本用gao什么的,我觉得应该尽量取些能比较容易看出大致function的名字吧。。。 还有“{”都写在上一行代码后面,虽然可以减少行数,但看起来感觉就是很乱

        • watashi says:

          gao是我从前辈们学来的个人爱好,基本就是整题算法的核心,我觉得和main, work, solve或者doit没什么区别
          其余变量和函数我觉得我还是取得很有意义的

          至于{写在上一行代码后面,你要认为这是不好的风格,你让java程序员情何以堪
          除了C#我还没见过所有大括号都要一行的语言, 虽然每个人都不同的审美,但我个人觉得难看死了,牠不就想显得和java不一样么

          表示从来不压缩行数,哪怕是一句for,一句if都加上括号
          对于代码风格我表示自己还是有洁癖的,一寸自慢的

        • watashi says:

          我觉得你可以看看indent的文档
          与java/C#有统一的标准不同,C++没有统一的风格,indent里就提供了GNU, R&K, Berkeley和Linux至少四套,当然还有MS的

          • xiaoshua says:

            呵呵,好吧,只是感觉看你代码很累。。。。。 我学长跟我说,以前做完ZOJ月赛题目来这里,只看题解,从不看标程代码的

            • watashi says:

              本来我就觉得应该先自己想 => 看提示 => 看题解 => 求助代码
              当然AC以后再看别人代码会另有收获

              • xiaoshua says:

                嗯,明白了。 ps:省赛题目也是你们准备的么? 去年你不也参赛的么? 还有今年省赛具体什么时候啊?

                • watashi says:

                  monthly的题目的主要来源是暑期集训;省赛、校赛的题目来源是退役及现役不参赛的老队员。
                  我已经丧失参赛资格了……
                  至于省赛时间,擦,我也想知道,我前两天问校赛时间都还没有结果的说,我连问谁都不知道

    • hhanger says:

      闻风前来围观。。

    • Yuan says:

      原谅我看代码看得比较少
      但我觉得watashi的代码是非常漂亮、规范
      哪里用STL,而且用了后效率还不会下降

      const int MAXN = 10086
      const long long INF = 12345678987654321LL
      我都觉得非常有才…

      • watashi says:

        STL的设计原本就是运用了各种模板特化的奇技淫巧,不惮使用大量的代码追求效率的
        所以完成一样的工作,STL绝对不差的,通常题目的TL也不会那么紧,所以应该是基本能放心使用的啦

  19. chnlich says:

    Orz

  20. 楚雨荨 says:

    I不需要2^5枚举啊。。。
    把从s连过来的边的边权设为afford,然后用最大流减去所有afford之和就行了诶……

  21.  
Leave a Reply