ゆっくりでいいさ

狗狗(WishingBone orz)从ZOJ前6个Volumn精调细选的40题，虽然每年集训都见，但一直没有好好做掉。今年最后一次集训了，最近忙的事情也不多，特别是实习+毕设搞的我手的完全生疏了，于是下定决心重头开始把这40道题完全重做一遍。

说来半年多没怎么水题，SRM也没做，退化得真是厉害，集训新手选拔第一场的时候，我在旁边打酱油，然后我突然问于指导，“诶，C++的注释是怎么样的啊”。我发现我先写了个”–”，又写了个”#” (perl写多了)，再改成个”%” (latex……毕业论文害的)，vim都没有高亮，好不容易想起来”//”，自己也冷得不行。重写这40题的时候也是，以前轻松搞定的问题也WA个几次，还有些就都不会写了，好在慢慢找回点状态。最后几个大自然还是折腾了比较久，特别是”ZOJ1448 Pattern Matching Using Regular Expression”，数据实在是太不厚道了啊。还有”ZOJ1230 Legendary Pokemon”，蘑菇题什么的最讨厌了。

还是先推荐两道构造题2363 Strange Counter和2368 Royal Federation。2361 Areas是一道coding量很大的计算几何题，而2367 PL/Cool是一道考验基本功的蘑菇题。2363 Data Transmission是一个值得再研究的分层图的阻塞流问题。

ZOJ2361/SGU209 Areas

source code (ZOJ2361.cpp) [geometry, 计算几何, dfs]

题目描述很简单，问给定的n条线把平面分出了几个有限的区域。

规模为80，不得不ym那些用优化的半平面交轻松AC这道题的牛人们，但我觉得这不能算a right approach。

我的算法是O(n^2lg(n))的。

ZOJ Monthly, June 2010，也是今年ACM-ICPC集训选拔赛的一部分。赛前hhanger放出话：

史上最easy的一次月赛，believe me

这也是atouSk, Bzu, CError和Django奉献的最后一次Monthly了。没题啊，没题啦……

ZOJ3343 Accident Tree

source code (ZOJ3343.cpp) [bitwise, tree, parser, scanf]

计算中心218原因不明地起火了，据专家Frozen的表示，起火原因可用一棵XML树表示：

• 非叶子节点有两种：”and”代表的条件成立当且仅当其所有的子条件都成立；而”or”节点只要有一个子条件成立，这个节点就成立；
• 叶子节点都表示一个元条件，包含名字和概率。注意具有相同名字的叶子节点总是同时成立或不成立的。

要求这棵树（根节点）成立的概率。最多只有10种不同名字的元条件。

由于只有10种不同名字的元条件，很容易想到2^10枚举所有情况，再判断根节点是否成立。最后的答案就是所有成立情况的加权和，复杂度为2^10*200。题目的麻烦之处再于读入XML并parse成树，其实灵活运用scanf的话，还是比较轻松的，具体看代码。

ZOJ3344 Card Game

source code (ZOJ3344.java) [counting, BigInt]

略

其实问题的本质是求将n个数的排列分解为不超过k的奇数个环的方案数。把n个数的排列分解为恰好k个环的方案数就是第一类斯特林数：

ZOJ3345 Language

source code (ZOJ3345.cpp) [string]

虽然zip诞生之初只支持cp437，但对UTF-8的支持早已加入zip格式的标准之中，原本这样就该天下太平了。但这个世界爱自作主张和固守陈规的软件太多了，尤其是悲剧只发生在Linux用户的头上的时候（当然Win用户从JP下回的zip乱码的可能性也有，不过Win下JP的东西什么都是乱码，所以无所谓了）。于是常常会解压一个zip得到一大堆乱码的文件，如果运气好的话，可以convmv解决；但是遇到解压完的文件名里有一堆的“(invalid encoding)”，那convmv也回天乏术；更不幸的是直接解压不能，说什么

checkdir error:  cannot create ?R?X?v???-?^?Wblabla
                 Invalid or incomplete multibyte or wide character
                 unable to process ?R?X?v???-?^?Wbalbla/gao.

早先的unzip，比如UnZip 5.52，有个在usage, help和manpage等各种文档中都没提到的神秘参数-O可以指定文件名的编码，从而解决GBK/BIG5/shift_JIS等编码的乱码问题。比如：

unzip -O CP936 怎样打飞机.zip

可是到了新版本的unzip，比如UnZip 6.00，这个-O参数便名花有主了，而原来的-O功能似乎神隐了。用力搞了很久没搞定，最后求助perl。利用Archive::Zip和Encode，写了个简短的脚本，这个问题瞬间解决。

#!/usr/bin/perl

use Archive::Zip;
use Encode qw(decode encode);

sub usage {
	print <<USAGE;
USAGE: unzip.pl ZIPFILE [FROMCODE=utf-8 [TOCODE=utf-8]]
USAGE
	exit;
}

usage unless -e $ARGV[0];
$zip = Archive::Zip->new($ARGV[0]);
$from = $ARGV[1] || 'utf-8';
$to = $ARGV[2] || 'utf-8';

for ($zip->memberNames()) {
	$member = $zip->memberNamed($_);
	$_ = encode($to, decode($from, $_));
	$zip->extractMember($member, $_);
}

现在只要

perl unzip.pl 怎样打飞机.zip GBK

就能顺利解压了。至于开头提到的原因不明的乱码造成的解压不能的情况，可以直接将$_ = encode($to, decode($from, $_))这句修改文件名的代码替换为s#.*?/#gao/#等能解决问题的代码。

继浙大校赛的gensokyo, 浙江省赛的tsukimisakura之后，我+天皇+dd第三次（因为天皇要去香港了，所以也大概是最后一次）合作，组成musoufuuin(むそうふういん；夢想封印)参加浙江理工大学主办的全国邀请赛。

上周不知怎么的病了，开始只是有点头疼，没心思写毕设，于是天天玩游戏，以为过两天就会好。结果不幸的就是比赛的时候病情发展到最严重，开始发烧鼻塞，去下沙前的晚上难以入睡，睡到4点又闹肚子，早上起来又闹肚子，早饭没敢吃，到了下沙又闹肚子了。下午好了点，以为第二天就没事了……结果晚上头疼鼻塞又严重了，开始咳嗽，第二天睡醒也没好，发现眼睛通红。如果早注意点的话，就不至于把病拖到比赛的时候恶化，悲剧啊……

试机的时候就发现我们的网络时好时坏，和工作人员联系后，第二天赛前，工作人员就过来告诉我们昨天晚上检查过了。结果比赛开始我写完A要提交就发现网络挂了……然后联系工作人员，工作人员也自然搞不定这原因不明的网络故障，提了很多无用建议，基本是干等着，结果天皇开始有点怒了。A在10多分钟后，pc^2趁网络恢复的窗口提交返回了Yes，还有工作人员说这只是“网络延时”……肉牛满面……最后换机器，dd用U盘拷了写好的H的代码，第一次没拷过来，只好在拷一次，结果WA，发现点问题改过2y。开局不顺

然后天皇独立写B，我只知道要dp；我给dd讲了C的算法，交给dd写；然后我准备先写I再写F。C和I比较顺利，B打印调试了几次，WA了一次，后来天皇想到一种情况，简单改动后AC；F明明很简单的，可以却把自己加到集训队模块里的RMQ抄错n个地方，导致花了很多时间调试，最后还有个非常幼稚的括号错误，导致WA了一次，还迟迟没有检查出来，浪费了大家的时间。最后dd攻E，我攻G，天皇攻D。E过不了sample，于是天皇和dd一起调试打印；我去写G，一堆问题，搞了很久，效率比较低。E卡了挺久，几经波折最后AC，G还在卡题，问题一堆。天皇写D，dd为D准备了很多组case；我还在G上折腾，WA了4次，大量改动代码后终于AC。最后看D，错了大量case，其实都是模块敲错了n个函数，可是我们三个人居然迟迟没有找出来，花了不少时间1y。J题dd猜想强联通等价有解，而我想到按省赛办法加入随机生成一条路径来寻找解，我们两个合起来就是ATM他们AC的算法。可惜时间不多（虽然可能够），而且看到ATM已经10题，我们就没尝试了。

总的来说比得很烂，网络问题，没有及时换机器，耽误了不少时间，影响了开局，但那不是最主要了。主要责任应该在我，我严重不在状态，耽误了全队更多的时间，而且很多问题都没有参与讨论。A连MST都没一次写对，F这么简单的问题也卡了半天，G更是各种脑残卡了更久，本来我是全队计算几何最熟悉的，却没有早点写D这么简单的题。然后就是模块抄错的问题没有及时发现，F和D都是死在这里，尤其D卡了太久。

从校赛配合不好大悲剧，到省赛完美发挥大优势，到今天悲剧收场，我们队结束了的仅有的三次比赛。也深刻地让我体会到了ACM比赛里配合>>状态>>实力的真理。ACM告一段落，现在还是先养好病把毕设搞定吧……555

ps: 感谢于指导的衣服和牛肉面