这是第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

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

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

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

ZOJ3488. Conic Section

source 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

source 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

source 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

source 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

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

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

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

ZOJ3493. Palm Up and Palm Down

source 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

source 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

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

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

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

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

ZOJ3496. Assignment

source 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

source 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

source 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

source code (ZOJ3499.cpp) [sorting]

求n个浮点数的中位数。

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

• 第8届浙江省大学生程序设计竞赛最终排名
• The 11th Zhejiang University Programming Contest (online) Final Standing
• 陈越姥姥拍的傻照片
• 彩票哥的解题报告

This entry was posted on Sunday, April 17th, 2011 at 11:41 pm and is filed under summer2011. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.