

第8届浙江省程序设计竞赛点评beta
Posted by watashi in summer2011, tags: ACM-ICPC, DP, FlowNetwork, solution, summer2011, ZJPCPC, ZOJ, 构造这是第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)的算法啦。
zoj 3494 的数据水了,建议增加如下数据
1
1
00
1 1000
答案应该是21
网上很多错误的都过了,包括我自己的,开始我还以为自己写对了呢。。。。
palm up and palm down的ratio有可能加起来不等于100吗?看你的代码有考虑这种情况
ratio, not percentage
请问神牛
这题ZOJ3491. Wall-nut Bowling 您的标程里的那3个方向的编码是怎样的?
看的不太懂@_@
[0, m) 斜的,好像是对应从(-i, 0)出发的吧
[m, m + n) 水平的,对应从(i - m, 0)出发的
弱问神牛
vector的clear()和resize(0)哪个快呢?
还有,那个erase后面一部分跟直接resize()到目标大小哪个快呢?
复杂度是一样的,差别可以忽略不计……
菜人写ZOJ3496. Assignment的时候遇到一个灵异问题
当二分最大下界时,l=-1,r=INF就一直WA;然后看了大牛的飘逸程序把上界改成maxflow+1就过了,话说这个问题单调性明显,上界取INF和取maxflow+1有啥区别呀?为啥前者错后者对。。
二分不就是基于函数单调性的么,又有啥奥妙玄机呀
我的程序改成INF也会WA,看了一下似乎是会死在边=0的边界case上
请问下神牛
3493这题
是不是计算到最后,所有人的输的概率之和会为1?
表示不太懂题目说的“the maximum probability to lose ”,请问这个可不可以解释一下?
多谢了
不是的,你看样例就有一个是0.0% + 0.0% < 1的
加上死循环的概率之和才是1
这题会不会很卡精度啥的?
我这样写
dp[mask] = fabs(left) < EPS ? 1e30: right / left;错了
这样dp[mask] = right / left;就可以过 T_T
我觉得应该不会才是,只有最后求minimum需要考虑精度吧,中间连EPS都是多余的,直接==0就好了
你是把1e30作为INF么,那么你要注意,在判断答案是不是Infinity的时候要用小得多的数
比如(0.1*1e30+0.9*1)+1 << 1e30……
这个注意神奇丫,学到东西了
Orz
在您的代码
150 dp[popcnt[j] < popcnt[k] ? j : k] += u[j] * d[k] / x * dp[i];
请问为什么求概率时要除以x?
那种“该轮没人离开”的事件不用考虑?
厄。。。还有就是算期望时,请问转移不考虑 黑与白相等、全黑或全白 是为什么呢?
请问下:
假设在运算中浮点数a是除0得到的,如a = 1.0/0.0
这样计算机是将a赋为无穷大吧?
那么即使a * 1e-300 ,最后输出的结果还是无穷大吧?
而手动搞一个INF的话,会因为后面参与运算有可能不再保持INF?
是的,所以这种情况你可能需要几个不同大小的”INF”,或者pair<double, Flag>
用浮,点数中的±Inf要注意Inf*0=NaN, +Inf+-Inf=NaN ……所以还是要小心的
请问下,为什么算期望,算概率时不用考虑“没有人离开”的事件?
归一化不就是对“没有人离开”的处理么……
原来那个是归一化…厄。。。。土了
厄。。。还有一个问题
您的代码那里
150 dp[popcnt[j] < popcnt[k] ? j : k] += u[j] * d[k] / x * dp[i];
请问为什么需要除一个x,那种该轮没有人退出的事件不用考虑吗?
厄。。。还有一个问题
150 dp[popcnt[j] < popcnt[k] ? j : k] += u[j] * d[k] / x * dp[i];
您的代码里,请问为什么求概率时还要再除以x?
那种该轮没有人离开的事件不用考虑吗?
在这里可以求比赛那天拍的傻照片不?网上各种搜不到。。。
姐姐那里这几天回慢慢贴出来吧,我这里没有……
跪求姐姐博客地址~~~~
陈越姥姥拍的傻照片
文章最后不是给了么,估计要一阵子才能更新完吧
求姐姐博客地址~
唉呀呀~看文不仔细的结果呀~
果然是因为我直接跳过了题解部分的结果。。
为什么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,求解释。
我是按我的理解做的,并且能过数据。。。不知道watashi是怎么理解的。。。
背景略过。以奇怪的输入格式给你一个有向图。如果所有到终点的线路长度都是p,输出True;如果存在这样的线路,输出Maybe;否则,输出False.
这个就是watashi和我一致的理解么。。。。
我觉得如果输出是True的话说明一定不存在环,这样的话两种理解得到的结果就是一样的了,所以应该没有矛盾。
怎么可能所有到终点的路径长度都是P 到终点的路径长度可以很多啊……
我错了。。。。
在cc98也有人指出了这点
ms结论是数据比较弱,两种理解都能AC
囧
在比赛时终于见到watashi本人了。= =无心恋战了
木有看出这之间因果关系 @,@
我也干活了。。。。
Assignment如果给每条边一个费用的话,就直接转线性规划了。用单纯形慢慢算吧……
我错了……还有欧阳也帮慢修改了描述
但是线性规划怎么做minmax或maxmin?或者怎么转换?
先求出最大流值f,把它作为已知
然后给每条边上的流量设一个未知数
约束方程是
流量平衡并且到汇点的那些边流量之和等于f
目标函数是 那个费用最小?
这不是线性规划么。。。
费用不需要设未知数么?
如果要的话,这样不关是minmax了,连线性都不是了……
我以为费用是给定的。。。。
线性规划
AX = b
max/min y = C^TX
这里一个人要决策X一个人要决策C,然后一个要最大化y一个要最小化… 这个怎么线性规划…
我错了。。。
如此说来只能枚举要用的边了。。。
今年的金奖竟然多了…
嗯,我也觉得挺不容易的
今年的金奖刚好发到7题,所以增加到了13个,不过结果奖牌不够了,我们学校有两个队似乎没有拿到奖牌……
原来我们146分钟就1Y了J….
浙大年年出题已属不易…百密一疏..我们理解…
momo
感谢理解
没有及时发现比较遗憾,好在定奖之前处理好了
我错了…
ym 100% rejudge
幸亏只对一个队有影响……
赞解题报告
赞美,其实题目应该都蛮好的,但是感觉有些题目描述的晕乎乎的,应该还是有很多队伍能做出后面的那些题目的~可惜大家开坑的位置不好~
3493的复杂度写错了
我错了……
vls v5
这个,貌似排名变成 404 not found 了~
oops
fixed
占个首页看代码
代码看不了404
555 搞定了,多分