Semi-live已经结束。从ranklist上看,online队伍的表现要比onsite稍稍逊色一筹。


The 2011 ACM-ICPC Asia Dalian Regional Contest
A ZOJ3539 Compress the String 0.00% (0/53)
B ZOJ3540 Adding New Machine 9.03% (16/177)
C ZOJ3541 The Last Puzzle 17.73% (25/141)
D ZOJ3542 Hexadecimal View 31.36% (281/896)
E ZOJ3543 Number String 27.64% (81/293)
F ZOJ3544 Draw a Mess 3.97% (17/428)
G ZOJ3545 Rescue the Rabbit 19.66% (70/356)
H ZOJ3546 Advanture of Xiaoxingxing 16.66% (1/6)
I ZOJ3547 The Boss on Mars 17.17% (136/792)
J ZOJ3548 Chess Board 16.00% (8/50)

简要介绍一下各题的思路吧,不打算写详细的解题报告了,最近也不打算写套题的解题报告。遇到有人问ZOJ Monthly解题报告的事,于是说一下。首先ZOJ Monthly没有官方的解题报告,我过去写的解题报告只是个人兴趣而已,一开始便没有打算一直做下去。不过ZOJ近两个月的解题报告可以在猛犸也钻地Fancy的blog找到。

ZOJ3539. Compress the String


downloadsource code (ZOJ3539.cpp) [Search and Prune, Branch and Bound]

其实这道题的idea来自2011 TCO Marathon Round 3。基本的算法就是搜索加剪枝了,比如能生成的最长的串也不够长的时候就可以剪掉。对剪枝要求较高,如果没有足够的剪枝的话就会超时。

ZOJ3540. Adding New Machine

downloadsource code (ZOJ3540.cpp) [SegmentTree]

离散化以后线段树做。

ZOJ3541. The Last Puzzle

downloadsource code (ZOJ3541.cpp) [DP]

隐藏在模型后面的,其实是一个经典得不能再经典的动态规划问题了。很容易证明,如果有解的话,下面的方案一定能求到一个最优解。需要按下的开关总是一个区间,每次要么按下最左边的开关,要么按下最右边的开关。所以dp[l][r][0 or 1],转移是O(1)的,复杂度为O(n^2)。

ZOJ3542. Hexadecimal View

downloadsource code (ZOJ3542.cpp) [String]

签名题。

ZOJ3543. Number String

downloadsource code (ZOJ3543.cpp) [DP]

非常简单的动态规划,dp[i][j]表示长度为i以j结尾的合法排列的个数,那么有

if (s[i] == 'I' || s[i] == '?') {
	for (int k = 0; k < j; ++k) {
		dp[i][j] += dp[i - 1][k];
	}
}
if (s[i] == 'D' || s[i] == '?') {
	for (int k = j; k < i; ++k) {
		dp[i][j] += dp[i - 1][k];
	}
}

这个算法是O(n^3)的,但利用部分和,很容易转成O(n^2)的算法。

ZOJ3544. Draw a Mess

downloadsource code (ZOJ3544.cpp) [Path Compression]

这题用n个实现较好线段树是可以AC的,不过有更好实现也更高效的算法。维护n个大小为m的list,然后倒着做所有操作,每次染色后,就把对应节点删掉。利用路径压缩优化,查找并删除节点的均摊复杂度为O(1),总的复杂度为O(nm+nq)。

ZOJ3545. Rescue the Rabbit

downloadsource code (ZOJ3545.cpp) [AhoCorasick, DP]

建立AC自动机,然后在上面DP。DP的状态是

bool dp[LENGTH][NODE][GENE_MASK];

ZOJ3546. Advanture of Xiaoxingxing

downloadsource code (ZOJ3546.cpp) [Computational geometry]

计算几何。

ZOJ3547. The Boss on Mars

downloadsource code (ZOJ3547.cpp) [Number Theory, Inclusive-Exclusive Principle]

容斥原理的基本运用。

\sum_{i=1}^n{i^4}=\frac{1}{30}n(n+1)(2n+1)(3n^2+3n-1)

ZOJ3548. Chess Board

downloadsource code (ZOJ3548.cpp) [Bipartite Graph]

可以通过解二元一次方程组求出a和b,退化情况需要枚举a和b。然后白色部分就是直接计数,黑色部分的最优解本质上就是二分图最小覆盖数,可通过解二分图最大匹配数求得。

34 Responses to “The 2011 ACM-ICPC Asia Dalian Regional Contest (Cont.)”
  1. pfctgeorge says:

    shi哥,求F题线段树的代码,谢谢啦~~~

    fanjianjin[at]yahoo.com.cn

  2. pnt says:

    E题的DP方法为什么能满足无后效性呢,比如第3位以5结尾,其中一种合法序列为135,那么对于这个序列来说,1和3就不能在第四位出现了,这种情况是如何处理的呢

  3. zhongweizi says:

    D 题 ,非常简单的动态规划,dp[i][j]表示长度为i以j结尾的合法排列的个数,那么有
    if (s[i] == ‘I’ || s[i] == ‘?’) {
    for (int k = 0; k < j; ++k) { //如果前面 i – 1 位里面已经用了 j 怎么办 , 是不是 定义说错了, shi哥 看看
    dp[i][j] += dp[i - 1][k];
    }
    }
    if (s[i] == 'D' || s[i] == '?') {
    for (int k = j; k < i; ++k) { //根据定义 ,为何 不是到 k=j;k<=n;++k
    dp[i][j] += dp[i - 1][k];
    }

  4. SanDie says:

    隐藏在模型后面的,其实是一个经典得不能再经典的动态规划问题了。

    求类似题推荐……求题源……

  5. 45°↗ says:

    弱弱的问一句F题线段树怎么“较好实现”,我正着反着都超时了

  6. SmashAC says:

    把 H 题说一下吧
    好长时间了,都没有AC!郁闷……

  7. alpc32 says:

    B题可以用扫描线+set维护统计吧

    • wkn says:

      有机会帮我看一下代码好么。我也那么写的,就是过不了。。。。(sunnywkn@gmail.com)

  8. xiaoshua says:

    G题我的程序在ZOJ跑了9530MS,如果放到现场赛,会不会超时,另外猛犸也钻地和Fancy是何方神圣?

    • watashi says:

      不确定,现场的时候TL好像是5s
      ZJU ICPC Team Memebers

      • xiaoshua says:

        那不就是必挂无疑嘛。。。 其实这次感觉复杂度太高了,初始化就用了m*2^n*size(trie)==10^8?,刚开始都没敢写,写好了也没敢交,交了还是不敢看statue。。。。。。。

  9. SmashAC says:

    shi哥,为什么没有计算几何解题报告?

  10. VeegtableB says:

    感觉F在zoj上卡得比现场要紧……

  11. aswmtjdsj says:

    F题给的时限太严了吧?
    类似shi哥的想法,用一个vector或者list存所有的点的标号,每次lower_bound和upper_bound查需要删除的节点标号,即没有用路径压缩的做法。
    这个算法应该是您的做法*log(m) 的吧?这样不给过?晕啊。。
    还有,标程既然都2.1s,为啥时限才给5s。。。这。。。。

    • watashi says:

      TL不是我定的,我的程序也不是标程啦
      不过vector erase的话,复杂度是O(m^2)的吧
      list没有随机迭代器,所以不支持lower_bound吧

      • aswmtjdsj says:

        - -| erase为啥是O(m^2)的?又不会重复删除的哈~

        list的没有随机迭代器确实是。。不过lower_bound确实成功了的说,难道我看到的是假象?

        我很好奇比均摊o(1)还快的做法是啥,看到好几分代码比shi哥您的标程还快。。。
        难道是实现的超级好的线段树或者树状数组?

        • watashi says:

          lower_bound用的是distance和advance这两个函数,对vector是O(1)的,对list是O(m)的,所以你的算法是O(m^2lgm)的,不TLE没天理了
          vector::erase的复杂度是O(m)的,所以这个复杂度也是O(m^2)的,也会TLE

          同样的复杂度时间快点慢点不是很正常么

          • aswmtjdsj says:

            orz shi哥,本菜终于把F题过了。用了路径压缩的思想。。。果断就是并查集啊~您这做法太强了~
            话说我终于知道vector那个为啥会超时了。。
            看c++ reference时候看漏了一句话,vector的erase的复杂度=O(删除元素个数+移动后面元素个数),我没看到后半句,囧rz。怪不得O(m),我太二了。
            还有一个疑问,我自己写了个generate,自己的一份ac代码和tle代码跑出来的结果一样,和您的标程对拍发现答案不一样,不知道是什么情况- -我仔细对比了description,好像应该是generate没写错的样子。。
            您邮箱是多少来着?想把我的ac代码和generate给您发过去,看一下到底是哪里有问题。。

  12. Fancy says:

    于是ym

  13. xiaoshua says:

    shi哥终于又发题解了~~~

  14.  
Leave a Reply