今年省选赛的题又难又偏，高级算法考了很多，但基础知识一点都没照顾到。
没导向没立场，不由得让人怀疑有多少“奥步”在里面。还好这不是创新大赛，分数永远是最硬的。

自己拜测试数据所赐，多少也靠点运气，算是涉险出线。省选赛写完总结到此为止，国家赛再努力。
分数242, 名次3, kviz100, codes10, checkmate20, knight32, master80.

下载

jloi08-prob-data-sol.zip
题目、数据、官方解题报告、清橙评测包，但没有标程。全部选手的source欠奉，免得伤人。

• 纳米盘：点击进入下载页面
• box.net：点击进入下载页面
• Windows Live Skydrive：点击直接下载

各题总结

A 提示问题 (kviz)

没有要点。注意除3时四舍五入，还有“吭哧塞”和“吭哧喂”代码时仔细检查，不要出错。

B CODES (codes)

(广搜尝试中)

转载的题。解题报告很详细。

C 将军 (checkmate)

问题实质整理一下，实际上就是每条正斜线(／)上最多有1个象，每条反斜线(＼)上最多有1个象，但有一些格子不能用（与预设的棋子冲突）。

每个点占有1条正斜线，一条反斜线。而每条斜线上只能放一个象。当然看起来像n皇后，但不是搜的。

构二分图，一侧是正斜线的编号，另一侧是反斜线的。每一个可以放象的点视为一条边。做二分最大匹配。

帖一幅图帮助理解。红、蓝色是两种对角线的编号，打勾的格可以放象。

下面是构出的二分图

算法可以网络流，也可Hungary算法。但是我写的Hungary总是第10个测试点超上那么零点一几秒。

放“象(bishop)”和放“车(rook)”在本质上是一样的，都用二分匹配做。只有放皇后必须搜。

记得当年和FancyMouse讨论过此题，被大牛告知是最大二分匹配。比赛一看，知道怎么做，开心^_^。
可是赛前准备的网络流有错误，结果本来自鸣得意的题T_T了，应该a掉的题被灭了80。

D 可怜的骑士 (knight)

竟然出现了NP类问题。无话可说。
正确算法是hamilton环的近似算法。不常用，也不想分析，可参见算法导论。

比赛时随机化加卡时跑的-_-b|||。
话说评测机的时限是6秒，结果按1秒估计的，怕出问题还特地卡了0.75秒，亏死了。
这样骗了32分，竟然还是全场最高。我想大概是没有人钻研过近似算法的问题。

E 棋局定式 (master)

啰哩罗嗦了半天，实质就是在原字符串中查找子字符串（只需回答是否存在）。KMP算法理想。

本题用朴素算法也有70分。
我在程序里使了两个小手段：用位运算把每个操作压缩成short int，并使用memcmp()直接比较内存。
结果很神气的多骗10分，并且通过的点也比直接来少花了大约2/3时间。
比赛策略上这样做是很划算的，因为写KMP多得20分，不如花时间写CODES或checkmate。

原创文章，作者：沙渺
本文链接：2008计算机奥赛吉林省选：总结

1. 作者沙渺版权所有。网络转载注明出处，纸质媒体刊载请联系作者。
2. 内容发布行为尊重《知识共享 署名-相同方式共享 2.5 中国大陆许可协议》的规定。