这是第8届浙江省大学生程序设计竞赛(The 8th Zhejiang Provincial Collegiate Programming Contest)的比赛点评。这不是官方的解题报告,裁判组也将不会提供官方的解题报告和测试数据。


第8届浙江省大学生程序设计竞赛
A ZOJ3487 Ordinal Numbers 39.24% (312/795)
B ZOJ3488 Conic Section 21.27% (160/752)
C ZOJ3489 Old Labels 2.00% (1/50)
D ZOJ3490 String Successor 10.86% (88/810)
E ZOJ3491 Wall-nut Bowling 0.00% (0/12)
F ZOJ3492 Kagome Kagome 38.00% (233/613)
G ZOJ3493 Palm Up and Palm Down 0.00% (0/1)
H ZOJ3494 BCD Code 18.75% (3/16)
I ZOJ3495 Lego Bricks 8.33% (2/24)
J ZOJ3496 Assignment 11.11% (2/18)
K ZOJ3497 Mistwald 16.66% (13/78)
L ZOJ3498 Javabeans 28.44% (225/791)
M ZOJ3499 Median 30.47% (263/863)

原定的题目只有A-L,比赛前一周姐姐看过题目后表示还是太难,于是又加了一道M。13道题,是姐姐的吉利数字(参考试机赛B题Lucky Number)。其中水题有5道,结果开场对于OJ来说压力实在太大,ZOJ上一长排的Queuing,直到90min后system load才降下来。由于省赛专科和本科在一起比,实力跨度也很大,所以难度控制一直是比较困难的。这次简单题稍微多了一些,而原本我们以为只是中等题的K和I似乎对于很多队伍来说还是太难了。最主要的是,除了冠军队HDU-Knuth外,其它队伍的跳坑顺序完全出乎裁判们的预料= =b 有很多队伍都热衷于折腾赛前被认为是不适合在中期搞的题,而悲剧的是,他们也确实没有搞出来……


The 8th Zhejiang Provincial Collegiate Programming Contest (online)
A ZOJ3487 Ordinal Numbers 51.24% (413/806)
B ZOJ3488 Conic Section 29.45% (291/988)
C ZOJ3489 Old Labels 5.26% (6/114)
D ZOJ3490 String Successor 15.50% (198/1277)
E ZOJ3491 Wall-nut Bowling 0.00% (0/13)
F ZOJ3492 Kagome Kagome 55.55% (345/621)
G ZOJ3493 Palm Up and Palm Down 10.52% (4/38)
H ZOJ3494 BCD Code 15.90% (7/44)
I ZOJ3495 Lego Bricks 10.20% (5/49)
J ZOJ3496 Assignment 12.19% (10/82)
K ZOJ3497 Mistwald 10.97% (46/419)
L ZOJ3498 Javabeans 46.88% (339/723)
M ZOJ3499 Median 51.83% (381/735)

赛前vls曾预测冠军会有10~11题,而我表示今年题目虽然和去年相当,但冠军只有9题,最后还是我猜对了。六年之后,浙大又一次省赛丢杯,不过这一次丟得毫无意外,虽然如此,我还是很看好现在这一批集训队或有意进入集训队的xpies的。比较意外的是我原以为同步赛会有11题的,结果是只有4个10题的。也许是由于我们的失误,J题赛后rejudge了,影响了某些队伍向11题进发的脚步吧。

ZOJ3487. Ordinal Numbers

downloadsource code (ZOJ3487.cpp) [if-else]

输入基数词,输出序数词。为了降低难度,还直接把规则给你了,题目描述里还附带无数测试数据。

题目描述简直就是伪代码了。厚道的签名题。顺带一提,RoR里Fixnum自带ordinalize哦(ZOJ3488rb)。现场一共289个AC,是之前预测得最准的一道题,出色完成了签名题的使命。

ZOJ3488. Conic Section

downloadsource code (ZOJ3488.cpp) [if-else, yet-another-easy-problem]

输入非退化的实圆锥曲线的一般方程,并保证xy项的系数为0。要判断它到底是圆,椭圆,双曲线还是抛物线。

原本要判断非退化的实圆锥曲线就不难,加上xy项的系数为0这个条件以后使得这道题瞬间成为一道水题。不过这题也有坑人的地方,注意xy项的系数为0并不表示圆锥曲线就是标准方程或标准方程加平移,还有可能是旋转了直角的倍数。这道题骗了很多WA,基本都是因为对情况考虑不周。比如:

-x^2-y^2+1=0 is also circle
-x^2-2*y^2+1=0 is also ellipse
x^2+4y=0 is also parabola
y^2-x^2-1=0 is also hyperbola

最简单的判断规则应该是:

a==c is circle
a*c>0 is ellipse
a*c<0 is hyperbola
a*c=0 is parabola

这题还使用eps就有点画蛇添足了……

ZOJ3489. Old Labels

downloadsource code (ZOJ3489.cpp) [greedy, construction, sorting]

题目相当于给你一个有向的树,要给所有边标号得到一个Trie树,最后要使得所有叶子对应的单词集合是字典序最小的。题目以查询的形式要求字典序第c小的单词。

比赛时有不少尝试,但挺多都不靠谱的,最后只有moon姐AC此题。正确的做法是贪心构造,其实关键就是要给一个节点的几个儿子节点排一个序,使得解最优,只要按层次处理就好了。首先,叶子节点比非叶子节点小,因为{a, ba}<{aa, b}。如果两个都是非叶子节点,那么递归地比较他们排序后的叶子节点。如果其中一个恰是另一个的前缀,那么它是更的,这点和通常的字典序比较不同,因为{aa, ab, ac, ba, bb}<{aa, ab, ba, bb, bc}。需要注意的是这里我们不能暴力的递归,否则要TLE的。事实上我们按层次处理后,只要记录节点直接的大小关系 or rank,而不需要记录实际的集合就可以快速的比较大小了。这里的处理技巧和求后缀数组中的技巧感觉有点类似。

排好序后,就可以给所有的边附上标号,于是单词集合只要dfs一遍就出来了。后面的问题就很简单了。注意

for (int i = 0; i < n; ++i) {
	printf("%d%c", a[i], i == n - 1 ? '\n' : ' ');
}

这种写法在n=0时什么也不输出,而事实上应该输出空串。最初的标程被我cha了,moon姐也在这里PE了一次。

ZOJ3490. String Successor

downloadsource code (ZOJ3490.cpp) [simulation, string manipulation]

根据题目所给的规则求字符串的后继。

暴力的从右往左扫描,按规则求后继就好了。除了Sample已给出的,还有一些需要注意的地方:

  • 9的后继是10,而不是00;
  • (z)的后继是(aa),而不是a(a);
  • 输入虽然最长只有100,但输出最长可能有102。

事实上题目中给的字符串后继规则,也是Ruby中String#succ或String#next所用的规则(ZOJ3490rb)。

ZOJ3491. Wall-nut Bowling

downloadsource code (ZOJ3491.cpp) [simulation, data structure]

题目就是以植物大战僵尸中的坚果保龄球为背景的。有n个水平线路,上面有m个僵尸,有k个坚果,按给定顺序从给定线路水平滚出。坚果撞倒僵尸或遇到边界的时候都会改变线路以45度角滚动,最后问有多少僵尸被撞倒了。

模拟?不过需要数据结构或算法优化之。首先想到对所有僵尸按x排序,复杂度为O(mlgm)。然后我们就可以建立链表来按顺序维护这些僵尸,与普通链表不同的是,这里每个节点对应着僵尸,每个链表对应某条坚果的线路,一个节点在三个(y=1或y=N时是两个)链表中。我觉得可以取一个形象的名字,叫“麻花链表”,熟悉十字链表和Dancing Links(DLX)的童鞋应该明白我在说什么吧。建好“麻花链表”后,就可以直接模拟了,每次都是根据当前轨迹找出当前节点的某个后继,然后删掉该节点,直到后继为nil,所以复杂度是O(m+k)的。具体做法可以参考彩票哥的解题报告

vls的标程和navi的验题程序都是按这个算法写的。而我觉得这样写的代码好长啊好长啊,于是想了另一种算法。前面的算法的主要思路是,利用数据结构来优化模拟的效率,具体还是坚果按顺序撞倒每个僵尸的。我的思路则刚好是反过来的,我按x坐标的顺序扫描所有僵尸,然后快速求出会被哪个坚果撞倒,或不会被撞倒。做法很简单,用3*n个优先队列维护不同线路的坚果。对于每个僵尸,它可能被来自三个(y=1或y=N时是两个)不同线路的坚果撞倒,而如果有多个可能,实际上应该是被标号最小的坚果撞倒了。所以如果这三个优先队列都为空,那么–ans;否则,假设k是这三个优先队列中最小的堆顶元素,那么将它从原优先队列中删除,根据规则计算出其新的线路,并加到对应的优先队列中去。这个算法的复杂度是O(m\lg k)的,实际效率比很多O(m)的实现还要好,而且写起来简单。

需要注意的是,相同位置可能有多个僵尸。这两种算法为处理这一情况都要稍作修改。

ZOJ3492. Kagome Kagome

downloadsource code (ZOJ3492.cpp) [array, linear search]

题中有偶数个孩子围成一个圈在玩かごめかごめ(笼中鸟)。假设孩子们在圈中是均匀分布的,“鬼”知道他们逆时针的站位顺序,“鬼”又偷看了她的正前方是谁,于是“鬼”应该猜测她的正后方是谁?

假设有n个孩子,正前方的是第i个,那么显然正后方应该就是第(i+n/2)%n个。这题无非要在一个字符串数组中线性查找某个字符串。

ZOJ3493. Palm Up and Palm Down

downloadsource code (ZOJ3493.cpp) [bitwise operation, dynamic programming, probability theory]

要从n个人中通过黑白配多去少留,如果只有两个人则剪刀石头布来选出一个苦力。要求选出苦力所用时间的期望,还有哪些人最有可能成为苦力,及其成为苦力的概率。

看到题目和规模就很容易想到用2^n表示剩余哪些人,以此为状态动态规划。题目中的求期望和求概率可以作为两个问题分别计算,不过算法都很类似。思路上都是用2^n来记录对应信息,如果只剩两个人,那么按照剪刀石头布的规则转移。否则,利用下面的for循环

for (int sub = (mask - 1) & mask; sub > 0; sub = (sub - 1) & mask) {
}

枚举出白的子集,于是出黑的就是它的补集。然后按照黑白配的规则转移,要注意空集,全集和两个大小相等集合的情况是不转移的。转移的方程都是概率论中的基础,就不一一说明了。空间复杂度O(2^n),时间复杂度O(3^n)。

实现的时候,还有不少细节需要注意,这也正是这一题的难点。

  • 绝对不要算出NaN(Not a Number)来;
  • 要能够处理好Inf或/0的情况;
  • 比较概率需要加上eps;
  • 概率该归一化的时候要归一化。

这是一道看起来就有想法,实际却未必能搞定,特别是很难1y的题目。有30+个手造的测试数据。

ZOJ3494. BCD Code

downloadsource code (ZOJ3494.cpp) [Aho-Corasick, dynamic programming, counting]

问A到B之间的所有整数,转换成BCD Code后,有多少个不包含属于给定非法字符串集合的子串。

一道把AC自动机+DFA上的动态规划+计数问题结合起来的题目。其中AC自动机+DFA上的动态规划已经烂大街了,而通常较复杂的计数问题也是动态规划+递归。这题则把这三者结合在了一起。还有一个比较新鲜的地方是题目所用的BCD Code,所以与通常一个bit一个bit转移不同,我们直接一个nibble一个nibble转移要简单得多,我们可以在通过AC自动机得到DFA后,再预处理出一个状态经过0~9后所转移到的状态,这其实就是一个新的DFA。余下的东西都很常规了,其中计数的时候要注意前导0的处理,其它就不具体介绍了,网上应该有很多经典题目。

ZOJ3495. Lego Bricks

downloadsource code (ZOJ3495.cpp) [geometry, topsort]

有100个圆和100个线段,初始所有的圆是稳定的,然后可以一个一个加入线段,要求加入线段的时候,加入的线段所受力矩和可以为零。问是否存在一个顺序,使得所有线段都能被加入。

力矩和等于零其实等价于线段的两端都有东西支撑。所以我们把每个线段都在中点拆成两个,然后看这半个线段是否被某个圆支撑,即圆心到线段的距离(distoseg)不超过半径。或看这半个线段是否被某个线段支撑,即判线段相交(intersectIn)。然后我们就得到一个依赖关系矩阵,接下来可以类似拓扑排序在O(n^2)复杂度内求解。因为这题n很小,所以哪怕O(n^3)暴力在while循环中找能加的线段加入,找不到时break,也是足够快的。

赛前我们认为很多队伍能过K,然后I将成为决定金牌比较关键的一道题,从实际结果来看是大大失算了……这题在手握模块的情况下应该是相当简单的一道题才是,看来计算几何还是比较容易吓退一批人的。

ZOJ3496. Assignment

downloadsource code (ZOJ3496.cpp) [greedy, parameter search, flow network]

在给定源汇的网络上,A和B博弈,A先给出最大流,然后B可以给每条边一个费用,要求单位费用和恰好等于P。题目分别求A希望总费用尽量小(大)而B希望总费用尽量小(大)的情况下的总费用。

考虑A要小而B要大的情况。显然B的策略很简单,找到流量最大的边,设其费用为P。所以这时候A要使得流量最大的边最小,即限制每条边容量的上界,在保持最大流不变的前提下,要上界尽量小。所以只要二分容量上界,不断求最大流就好了。对于A要大而B要小的情况,B总是设流量最小的边的费用为P。所以A要使得流量最小的边尽量大,即在保持最大流不变的前提下,要每条边流量的下界尽量大。所以只要二分流量下界,不断求上下界最大流就好了。要注意答案可能超int。

如果题目改成B先给每条边一个费用,A再给出最大流,不知道应该怎么做。我+navi+vls都思考过,表示不会做。如果有哪位高人有想法,还望不吝指出。

这题比赛时数据有错,而且临近比赛结束我们才发觉,赛后马上rejudge了,现场只有HDU的三日月通过此题。对于这道题数据问题造成的影响深表歉意,虽然比赛前我们也再三验证过题目描述和数据,但毕竟人手有限(事实上主要干活的只有我+navi+vls三个人),难免百密一疏。

ZOJ3497. Mistwald

downloadsource code (ZOJ3497.cpp) [graph, dynamic programming, powers of matrices]

背景略过。以奇怪的输入格式给你一个有向图。如果所有到终点的线路长度都是p,输出True;如果存在这样的线路,输出Maybe;否则,输出False。

发现所给的图只有25个节点,而线路长度很大。那么可以用矩阵乘法来求从i到j,长度为k的路径是否存在。其实floyd算法求传递闭包就是把k=0~n-1的矩阵或起来。然后就可以判断是不是False,要区分True和Maybe则还要麻烦一点,可以考虑特判True。

我懒得写矩阵乘法,就水了一下。方法很简单,用2^n记录第k步哪些节点是可达的,那么这个状态必定会循环,于是找出循环节就好了。现场似乎有人也有类似的方法过了。关于复杂度,我只能确定有O(2^n)这个上界,但似乎实际数据不可能达到这么大,事实上所有数据都在1000步以内进入了循环节。

赛前,裁判们普遍认为这题属于中档题,或者说是银牌题。结果是,现场所有能过这道题的队伍都凭借7+AC拿到了金牌。很多队伍前期都用没什么前途的方法尝试C和E,直到过K的队伍多起来才注意到这道中档题。我觉得认清哪题该搞,哪题该先放着,是很重要的一种能力。当然,大多数队伍还是习惯跟风,而这次省赛,实力很强的队伍太少,造成了比赛中期无风可跟的悲剧。

ZOJ3498. Javabeans

downloadsource code (ZOJ3498.cpp) [greedy, construction]

一共有n盒爪哇豆,每盒各有1到n个。每天可以选取某几盒,从中各吃掉x个。问最快几天可以吃完。

最优测虐似乎也不唯一。不过最简单的是另x=1, 2, 4, 8, …,也就是2的幂次,显然这样在floor(lg(n))+1天能吃完,也显然是一种最优策略。要计算floor(lg(n))只要一个O(32)的for循环就能搞定了,对于GCC还可以用builtin的clz(Count Leading Zeros)函数,即ans=32-__builtin_clz(n)。常用的还有__builtin_parity, __builtin_popcount和__builtin_ctz(Count Trailing Zeros)。

ZOJ3499. Median

downloadsource code (ZOJ3499.cpp) [sorting]

求n个浮点数的中位数。

先对这n个数排序,插入/冒泡/选择都OK。如果n是奇数,那么答案就是a[n/2];否则,答案就是(a[n/2-1]+a[n/2])/2。事实上这题有O(n)的线性算法^ ^,不过作为一道临时加上的简单题,自然是只要求O(n^2)的算法啦。

59 Responses to “第8届浙江省程序设计竞赛点评beta
  1. wuyiqi says:

    zoj 3494 的数据水了,建议增加如下数据
    1
    1
    00
    1 1000

    答案应该是21
    网上很多错误的都过了,包括我自己的,开始我还以为自己写对了呢。。。。

  2. creepyuncle says:

    palm up and palm down的ratio有可能加起来不等于100吗?看你的代码有考虑这种情况

  3. Yuan says:

    请问神牛
    这题ZOJ3491. Wall-nut Bowling 您的标程里的那3个方向的编码是怎样的?
    看的不太懂@_@

  4. Yuan says:

    弱问神牛
    vector的clear()和resize(0)哪个快呢?
    还有,那个erase后面一部分跟直接resize()到目标大小哪个快呢?

  5. CrazyCow says:

    菜人写ZOJ3496. Assignment的时候遇到一个灵异问题
    当二分最大下界时,l=-1,r=INF就一直WA;然后看了大牛的飘逸程序把上界改成maxflow+1就过了,话说这个问题单调性明显,上界取INF和取maxflow+1有啥区别呀?为啥前者错后者对。。
    二分不就是基于函数单调性的么,又有啥奥妙玄机呀

  6. Yuan says:

    请问下神牛
    3493这题
    是不是计算到最后,所有人的输的概率之和会为1?
    表示不太懂题目说的“the maximum probability to lose ”,请问这个可不可以解释一下?
    多谢了

    • watashi says:

      不是的,你看样例就有一个是0.0% + 0.0% < 1的
      加上死循环的概率之和才是1

      • Yuan says:

        这题会不会很卡精度啥的?
        我这样写
        dp[mask] = fabs(left) < EPS ? 1e30: right / left;错了
        这样dp[mask] = right / left;就可以过 T_T

        • watashi says:

          我觉得应该不会才是,只有最后求minimum需要考虑精度吧,中间连EPS都是多余的,直接==0就好了
          你是把1e30作为INF么,那么你要注意,在判断答案是不是Infinity的时候要用小得多的数
          比如(0.1*1e30+0.9*1)+1 << 1e30……

          • Yuan says:

            这个注意神奇丫,学到东西了
            Orz

            • Yuan says:

              在您的代码
              150 dp[popcnt[j] < popcnt[k] ? j : k] += u[j] * d[k] / x * dp[i];
              请问为什么求概率时要除以x?
              那种“该轮没人离开”的事件不用考虑?

              厄。。。还有就是算期望时,请问转移不考虑 黑与白相等、全黑或全白 是为什么呢?

            • Yuan says:

              请问下:
              假设在运算中浮点数a是除0得到的,如a = 1.0/0.0
              这样计算机是将a赋为无穷大吧?
              那么即使a * 1e-300 ,最后输出的结果还是无穷大吧?
              而手动搞一个INF的话,会因为后面参与运算有可能不再保持INF?

      • Yuan says:

        厄。。。还有一个问题
        您的代码那里
        150 dp[popcnt[j] < popcnt[k] ? j : k] += u[j] * d[k] / x * dp[i];
        请问为什么需要除一个x,那种该轮没有人退出的事件不用考虑吗?

      • Yuan says:

        厄。。。还有一个问题
        150 dp[popcnt[j] < popcnt[k] ? j : k] += u[j] * d[k] / x * dp[i];
        您的代码里,请问为什么求概率时还要再除以x?
        那种该轮没有人离开的事件不用考虑吗?

  7. Hi says:

    在这里可以求比赛那天拍的傻照片不?网上各种搜不到。。。

  8. xiaoshua says:

    为什么javaman和你在K题上的解释不一样呢。。。 javaman说:从起点出发,走一条长度为P的路径,路径中间点不能经过终点(但可以反复经过其他点)。如果从起点出发P步后,不能到达终点,就是False,如果可以到达终点也可以到其他别的点,就是Maybe,如果P步后只能到达终点(到别的点没有长度为P的路径),则是Yes。
    比如
    1 2
    1 3
    2 4
    3 6
    4 5,p=2这样的图,按你的解释应该是输出True,但javaman的理解却是输出Maybe,求解释。

    • javaman says:

      我是按我的理解做的,并且能过数据。。。不知道watashi是怎么理解的。。。

      • xiaoshua says:

        背景略过。以奇怪的输入格式给你一个有向图。如果所有到终点的线路长度都是p,输出True;如果存在这样的线路,输出Maybe;否则,输出False.
        这个就是watashi和我一致的理解么。。。。

    • watashi says:

      在cc98也有人指出了这点
      ms结论是数据比较弱,两种理解都能AC

  9. no!no!no! says:

    在比赛时终于见到watashi本人了。= =无心恋战了

  10. javaman says:

    我也干活了。。。。
    Assignment如果给每条边一个费用的话,就直接转线性规划了。用单纯形慢慢算吧……

    • watashi says:

      我错了……还有欧阳也帮慢修改了描述
      但是线性规划怎么做minmax或maxmin?或者怎么转换?

      • javaman says:

        先求出最大流值f,把它作为已知
        然后给每条边上的流量设一个未知数
        约束方程是
        流量平衡并且到汇点的那些边流量之和等于f
        目标函数是 那个费用最小?
        这不是线性规划么。。。

  11. tracyzhu says:

    今年的金奖竟然多了…

    • watashi says:

      嗯,我也觉得挺不容易的
      今年的金奖刚好发到7题,所以增加到了13个,不过结果奖牌不够了,我们学校有两个队似乎没有拿到奖牌……

  12. 原来我们146分钟就1Y了J….
    浙大年年出题已属不易…百密一疏..我们理解…

  13. Navi says:

    我错了…

  14. daizhenyang says:

    赞解题报告

  15. YN!ngC says:

    赞美,其实题目应该都蛮好的,但是感觉有些题目描述的晕乎乎的,应该还是有很多队伍能做出后面的那些题目的~可惜大家开坑的位置不好~

  16. VegetableB says:

    3493的复杂度写错了

  17. xpycc says:

    这个,貌似排名变成 404 not found 了~

  18. liangjiaxing says:

    占个首页看代码

  19.  
Leave a Reply