第二次参加省赛，高中身份，自然还是没奖的Guest。
这次比我还强些的coder夏yh(因故)没来，只有自己一个人编码。就像DD所说的，一个人编码的确是很辛苦的事情。最后一小时本来可以试试H题，但我实在是干不动了。
由于夏yh的缺席，我还请了同班的MO强人（但不懂计算机竞赛）鲁z，希望能帮忙做数论和计数问题。但最后让他失望了：数论没有，计数问题也是（和数学关系不大的）搜索剪枝。

最后做出了5道题(ABCDI)，369分钟，全场第9名。
虽然成绩还可以，但AC的几道题毕竟比较水，以这样的水平参加再高级别的比赛会很惨。
自己唯一满意的就是理想的时间：2个小时刷完5道题，罚时总共也只有2次。
和另一支高中的Guest(东北师大附中)相比，很遗憾，输了附中5名。
明年再来吧。

照片三张：

从左至右：杨昕樵(省实验)、沙渺(省实验)、李博闻(附中)、李佩谦(附中)
和东北师大附中的合影。东北师大附中是另一支高中的强队，全场第4。

从左至右：吴晗，王睿通，沙渺，李东晨，杨昕樵
我们学校1队和2队的合影
1队队员：沙渺(主攻coder)、鲁正(数学,没在照片中)、杨昕樵。9名，5题369分钟。
2队队员：吴晗(主攻coder)、王睿通、李东晨。53名，2题137分钟。

官网上我们队唯一一张照片。鲁z在这张照片里。
距离镜头从远到近：杨昕樵、沙渺、鲁正

题目下载

网页打包：jlcpc08-problems.zip。测试数据欠奉，请移步吉大online judge进行练习。

在线练习

吉林大学online judge

• 比赛首页：http://acm.jlu.edu.cn/joj/showcontest.php?cid=103
• A：http://acm.jlu.edu.cn/joj/showproblem.php?pid=2485&contestid=103
• B：http://acm.jlu.edu.cn/joj/showproblem.php?pid=2486&contestid=103
• C：http://acm.jlu.edu.cn/joj/showproblem.php?pid=2487&contestid=103
• D：http://acm.jlu.edu.cn/joj/showproblem.php?pid=2488&contestid=103
• E：http://acm.jlu.edu.cn/joj/showproblem.php?pid=2489&contestid=103
• F：http://acm.jlu.edu.cn/joj/showproblem.php?pid=2490&contestid=103
• G：http://acm.jlu.edu.cn/joj/showproblem.php?pid=2491&contestid=103
• H：http://acm.jlu.edu.cn/joj/showproblem.php?pid=2492&contestid=103
• I：http://acm.jlu.edu.cn/joj/showproblem.php?pid=2493&contestid=103

比赛成绩

全部成绩：jlcpc08-standings.xls（来源：吉大官方：http://acm.jlu.edu.cn/joj/standing_new.php?cid=103）

前20名：

各题总结

A Welcome 2008

不做分析。有这样的水题，还有队伍打0分，我在想这是不是过于丢脸。

B Stock Wave

动态规划，思想和最长XX子序列类似，时间O(n^2)。

题目不难，但全场通过率只有6%，究其原因在于题目中有陷阱。题目的原意是找最长的“波”，但题目要求奇数点(odd)在下(less)，偶数点(even)在上(greater)。也就是说“波”一开始必须是上升的“/”型，而不是下降的“/”型。
因为这个自己当时也交了2遍——交第2遍的时候就知道这个会坑不少人。比完赛一看，提交321全对21（6.54%），果不其然。

C Central Avenue Road

线性规划。

这次的几何题出乎意料的简单：

• 整数问题 - 无误差
• 解析几何即可解决 - 不必动用计算几何
• 数据规模小 - 只需枚举

只能说这样的便宜真是不可多得。

D Function Value

模拟。

比赛当时的素数判定用了打表+试除。托测试数据的福，没有用miller-rabin。
鲁z说n是素数时有f(n)=floor(log2(n))，但裁判机的WA证明这个不对。但我想n是素数时是不是有一种非递归的办法呢？

E Billboard

二分构图，在相同的字母之间加边，容量1，费用等于移动距离。然后最小费用最大流。

比赛当时用的贪心，就是说先选不动的，再选动1格的，再选2格的以此类推。但这么做始终WA，可能某些卡片稍微多动两格，会得到更少的总步数？但我还没找到具体的反例。
注意，这句话是裁判说的：空格也算一张卡片。

F Civilization Map

广度优先搜索。

没难度，但非常的罗嗦。比赛当时也只有第一名（全对）的队伍完全正确。
“要有人能够对付麻烦的题，并保证一定的通过率，大多数的比赛都至少有一道这样的题。”今天才明白这句话是多么的经典，谁说的来着。

G What is your level

抱歉，解法欠奉。

直接算法看到题的同时也想出来了，但200000的规模显然需要nlogn的数据结构加速。现在还没想出来。

H Lamp Matrix

搜索剪枝。暂时没有找到什么有效的特殊性质，3^20的复杂度枚举刚好超时，搜索剪枝只能说可行。
本来最后一小时可以攻这道题，但我实在干不动了-_-b。正是DD所说的体力问题。

I Digit Game

高精度。放在这个位置纯粹是唬人。我在想出个几十万位考考排序还能有点意思。
裁判说的：升序排序时，允许前导0。题目中“不要前导0”只是指最后输出时。

============================================================

链接一个第6名（吉林大学new task队）的小总结：
http://hi.baidu.com/fandywang_jlu/blog/item/b542abef09642eeace1b3e9f.html

第4名（北华大学启航队，牛）的blog：
http://www.bhjsj.cn/aowarmen/?p=8

原创文章，作者：沙渺
本文链接：第2届吉林省大学生程序设计竞赛：观摩总结

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