5月1日去了传说中的中国国际动漫节，虽然在杭州郊区生活了近四年，去杭州动漫节这还是第一回。毕竟萧山还是很远的，没人组团一个人去太不靠谱了，而且以前也对以家长领着xpies为主的卡通节也有所耳闻。不过这回真是难得，在Apple Birds群里吼一吼居然召集到八个人，平时咋没发现ACM集训队这么有爱呢。加上我的两个室友，一共十个人，虽是抱着「それぞれの望み」，也算是凑一块跑动漫节去了。
原定八点半在纽布里奇盖特(new bridge gate)碰头，自然是拖到九点人才到齐，走到黄龙买票上车，车到休博园堵得厉害，人意料之外的多，临近中午才检票入馆。刚入馆asmn和EZ这两只动机不靠谱的就消失了……A区一看都是CCAV等有势力的主，转了一圈果断下到B区，走马观花后来到C区。发现vb, relive, 我的两个室友都丢了，只剩下我, navi, hhanger和前一天从加拿大飞回来的owen(无限ym)，嘛，除了弄丢室友一只，该在的都在了……
来之前把期望放得不是很大，但好歹在C区里看到了不少摊位，虽然限于主办方，各种有爱物是很难期待了。挑东西果然是痛并快乐着的一种体验，不过似乎是来晚了的缘故，感觉不少好东西都已经被挑走了，还有各种断货……不过最后收获比预想的要大呐，来之前还当心是不是除了35元的门票，一分钱也用不出去。
准备离开C区前，我打算回之前看过的某个摊子买点东西，结果我们迷路了，绕了n圈后才找到，果然我们还是太业余了- -b。算了算似乎一共花掉了152米……也就算我们十人中第三有爱吧……
在C区看到一幅相当赞的东方油画，非常有感觉，起初远看没发现是真画。未标价，询问后答案是8000+ orz，好的，如果是800我会买的（虽然我只带了700块钱）。说800绝对没有任何贬低其价值的意思，不过8000已近远远远远超出我的经济承受能力了，于是只能多看两眼了T_T。我，还有众人，表示这幅画相当赞，胜过另一幅8000+的东方，还有16000+的夏娜，可惜我们加起来也买不起，照片还没拍好，照片效果与原画差好远，悲剧啊。
在C区折腾数小时后回到B区，发现这里还是有一些摊位和好东西的。四点钟所有人集齐，排队回黄龙，队伍好长好长好长呵，更悲剧的是五点半排到我们时断车了……等到我们玉泉正门会合的时候天都黑了，qzw fb后k89回zjg，一天下来真折腾累了，于是全寝室难得地“早睡”了。
9 Comments »
| Andrew Stankevich’s Contest #9 |
| ZOJ2696 |
Chip Designing |
19.15% (41/214) |
| ZOJ2697 |
Electricity |
16.55% (76/459) |
| ZOJ2698 |
Numbers to Numbers |
10.28% (29/282) |
| ZOJ2699 |
Police Cities |
19.35% (66/341) |
| ZOJ2700 |
Quadratic Equation |
30.51% (65/213) |
| ZOJ2701 |
Restore the Tree |
13.99% (76/543) |
| ZOJ2702 |
Unrhymable Rhymes |
28.86% (153/530) |
| ZOJ2703 |
Selling Tickets |
21.79% (51/234) |
灰灰灰灰灰灰长好的一套题，所有题目都推荐！特别是2696 Chip Designing，2701 Restore the Tree和2697 Electricity这三道构造题，一道比一道值得一想。然后是ZOJ 2698，DP虽然简单，但英语转数字可是相当考验基本功啊。2703 Selling Tickets虽然不算难，但把握时间复杂度和编程复杂度的trade off是很有趣的一件事。有些题，尤其是构造题，一定存在更有趣，更简洁，或者更高效的算法。抛砖引玉，欢迎分享或者cha。
source code (ZOJ2696.cpp) [构造, 平面几何]
给你个芯片，要用水平或垂直的线路连接两排输入输出节点，要求线路不相交。
构造，方法应该非常多，bfs应该也可以，我的方法不难想，效率也满高的，不过写起来就不那么轻松了。首先直接构造一个input到output的连线，如果这条连线和先前的连线相交了，那么总可以“绕”过这条连线，绕的时候，可以保持这条连线的距离为u。只要每次的u都小于上回的一半（理论上等于也可以，但会有更多情况需要处理），那么就不可能会和之前的连线相交。这样还可以在计算过程中使用整数运算，不需要分数。上图是sample的情况，下图是对n=4的一个case的解，图片太模糊了，若需要高清无码矢量图，请点链接下载eps格式的文件。
DL 2696-2.ps
DL 2696-4.ps
source code (ZOJ2697.cpp) [构造, 拓扑排序(Topological Sort), acyclic]
给定一个有向无环图，要求每天改变一条边的方向，使得最后一些边的方向恰好与原来相反，要求中间过程始终没有环。
6 Comments »
| Andrew Stankevich’s Contest #2 |
| ZOJ2337 |
Non Absorbing DFA |
18.36% (92/501) |
| ZOJ2338 |
The Towers of Hanoi Revisited |
35.60% (115/323) |
| ZOJ2339 |
Hyperhuffman |
22.30% (252/1130) |
| ZOJ2340 |
Little Jumper |
22.22% (72/324) |
| ZOJ2341 |
Quantization Problem |
42.85% (84/196) |
| ZOJ2342 |
Roads |
36.70% (116/316) |
| ZOJ2343 |
Robbers |
37.35% (133/356) |
| ZOJ2344 |
Toral Tickets |
43.41% (56/129) |
最小生成树和二分图最优匹配你可能都熟悉得不能再熟悉了，可是把它们巧妙的隐藏到题目中，再通过不等式组（整数规划问题）联系起来呢？ZOJ 2342 Roads强烈强烈强烈推荐。然后可以通过ZOJ2344复习一下Burnside引理|Polya计数定理；做做ZOJ2338的扩展Hanoi问题；有爱的还可以挑战一下ZOJ2340，一道不简单的数学（物理？）参数搜索题。
source code (ZOJ2337.java) [BigIntger, DP, graph]
已知一个DFA，问有多少长度为N的字符串会被accept。与普通DFA不同的是这里多了一个G，如果某边有G(u,c)=1，则沿这条边，字符串的第一个字符不会被移除。
Deterministic finite automation (DFA)，好像不需要了解也可以。首先对G做预处理，在某点沿某条边出发，如果有G(u,c)=1的环，说明永远不会accept，否则我们就将这条边指向第一个G(u,c)=0处，经过这样处理以后，问题就是在一个普通的DFA了。然后只要在这个普通的DFA，也就是有向图上，做动态规划就好了，dp的两维状态分别是长度和所在节点。
source code (ZOJ2338.java) [DP, recursive]
解决n个盘m根棍的河内塔（谁翻译的汉诺塔，zhua啊）
相信传统Hanoi问题的解大家都烂熟于胸了，不过这道题能够检验你是否真正理解了Hanoi和背后的递归思想。如果需要，可以看看《具体数学》的第一章补补课哦。
1 Comment »
第7届浙江省大学生程序设计竞赛(The 7th Zhejiang Provincial Collegiate Programming Contest, 7th ZPCPC)，我+商天皇+dd继续组队，不过队名由校赛时的gensokyo(幻想郷)改成了省赛时的tsukimisakura(月見桜)。《月見桜》其实是东方西瓜theme《砕月》的由のりこ演唱的一首同人Vocal的歌名。
这回还是没什么压力，毕竟没有“任务”在身，不过比赛还是用力投入了，毕竟我们对不是来省赛打酱油的。中午饭后休息时间，先在218把《月見桜》这首歌repeat了十遍。我们队依然把GB的“时光倒流”，浙江大学SRTP成果汇编和圣经带到了赛场，这回还带上了“教练”博麗霊夢，quark的“明明白白用Word”和kid的“C语言调试技术”是左右护法。（<-啊，求真相啊求真相，天师？can哥？谁有真相给我一份啊）
(感谢天师提供的王道)
比赛开始，我搞定vimrc，然后换dd，dd上来就把A(5)B(7)L(9)秒杀掉了，而我和天皇同时把题看得差不多了，讲完题，觉得没有那么秒的了，于是我上去敲E。E我没有暴力枚举验证，用的是一个复杂高点的方法，所以也比较慢，写了一半，dd和天皇讨论出了G是n/2的结果，于是让路，但G居然WA。于是我回去搞E，debug过sample后submit，WA，发现闰年有个off-by-1的bug，改过再交E2y(35)。于是后我也来看G，讨论后我也确认了答案就是n/2没错，而且G当时有一个队过了，最后想到了一种可能——“交错题了”……脑海里隐约想起我在IE提交框好像看到dd交的是一坨我写了一半的E……于是再交一次……G2y(42) @@
5道题，我们爬到了Ranklist的前面。当时我看到D，对其中题意不明，然后让队友帮忙看看，这是个很明智的决定，我要头脑一热占着机器开始写的话，后面搞不好就悲剧了。一看JK都有人AC了，自然成为重点目标，天皇也考虑了H。天皇的H比较快就过sample了但是没AC，于是中间打印，debug了几次。dd对K的结论有印象，于是这题就交给他了，过sample后也WA了。我和天皇讨论了一下J，觉得复杂度没问题，于是我负责这题，在天皇修改H2y(75)后，我迅速敲完J，代码非常短，一次编译过sample，J1y(84)。中间dd和天皇讨论了一下K，具体我就不清楚了，只知道我刚搞定J，dd就上机修改好K2y(89)。我们顺利度过了三人开三题的“艰难时刻”，一看，比赛才过去90min，我们8AC，有两题+的优势了。
当然有点比赛常识的都知道还得继续用力，剩下的题目只有CDFI：
25 Comments »
Entries (RSS)