Amethyst: Contest Rank: 23rd / ICPC Rank: N/A
题外话：
下火车的第一感觉是长春明显没有想象的冷啊~
不过长春的轻轨建设方式还是有点那个的……某些路段和马路并行+共用红绿灯，总感觉很容易出问题。
然后是吉林大学~几十个亿建成的校园果然不一般~~ 华丽到我们都在YY这是校园还是公园~~~ 不过校园和我们的住宿处就形成了鲜明的对比-_-
转到比赛。
练习赛那天我们中午吃完午饭回住处拿东西，但是由于大家都错误估计了从宾馆到赛场的时间(单程耗时近30分钟)，我们赶到赛场已经是比赛开始十多分钟之后的事了-_- 自然而然就发生了某件我怀疑让全场都记住我们队的事件-_-bbbbbbbb 这里就不提了 (据说当时声音大到很多人都停止做题去看怎么回事-_-不过之后有个小插曲：我们进场后peter瞬间秒掉一道题，然后我们似乎就变成场上第一个过题的队了……)
正式赛。整场比赛做的很郁闷，大体就是刚开始peter看到A可做，但是由于出了一点xxoo的交流问题，导致我自己冲上去拍……交上去RE, 和peter合作改掉两个bug后TLE. 这个时候我们还是O(2^N*NlogN)的暴力枚举，稍微考虑了一下优化成O(2^N), 再交就过了-_- 而这个时候已经80多分钟了。后来的一段时间我在非常天真纯洁地在想F 的O(MN^2)算法……直到2小时多放弃这个题; 同时Peter证出了E题的枚举可以限制在某个范围之内，然后提交并1Y。
这个时候由于我们没有可以写的题，LynnKaye决定写D。然后我转去看题发现H/I均可写； 但这时LynnKaye说D的程序效率太低 (而这时场上已经有不少队伍3题/4题了) 于是我转去协助D, 同时peter开始打G题的表格。(当然我那时大脑短路没发现D被我们想复杂了。。。 导致莫名其妙计算量多了10倍-_-bbbbbb)
另外我调D的过程中LynnKaye说F题O(MNMlogN)的算法一定可以过， 但当时由于我错误估计了最坏情况下复杂度坚决拒绝去写……比赛后却知道judge们的标准做法就是那样-_-bbbbbb 我错了……
这一段时间场上发生了很多神奇的事情——
1)主办方提示今天比赛很多的题目看起来可能很难但其实不是这样的，鼓励大家去尝试做题……但我们却没有一个人意识到Judge们的意思是今天很多题是可以水的-_-比如那道xx的F题……
2)由于场上过题队数过少裁判宣布放宽A的时限+Rejudge! 然后似乎一次放的时限还不够多，一会儿之后又第二次Rejudge——结果好象就是A无论多暴力的枚举都过了-_-bbbbbbb
3) 据说离比赛结束一个半小时主裁判曾经让大家去做字符串处理题I -_- “字符串处理那题很简单，现在写还肯定来得及.”(不过这句话我没听见……当然听见了我也不会去做的…)
总之过了一段时间就封Board了……这时D的程序仍然很慢（5~10组极限数据就足够让程序超时）而我感觉D我们的算法应该不是最优的但又没有什么更好的思路，无奈之下放弃D去写H；期间同时发现Peter G题的打表效率有问题……最后我拍H直到<10min过样例+自己出的数据提交&返回WA；LynnKaye修改D直到最后发现之前加的某个剪枝有问题，无奈之下删掉所有剪枝后提交居然返回WA而不是TLE-_-
然后比赛结束之后我郁闷的检查H的代码然后在10分钟内发现两个低级错误(当时拍的太急了……)当时有!@#$%^的冲动。。。
总体上说 我们的主要失误首先是我和LynnKaye没有尽早把题目完整地读一遍（我个人开始只读了A和F, 直到过了A之后才去读其他题目），而这直接导致初期错误的做题顺序；其次Peter的代码能力非常强而这两场比赛都主要在想题。再有一点就是我们最后应该集中精力去攻一道题；我相信D和 H如果再多一点时间应该都能过的。另外我们还有一点失误就是D的代码备份不够多 (没记错的话我们一共只留了2份……)
最后虽然这场比赛的题目比较不爽(暴力+打表 …) THU PKU等队伍仍然出了4~5题……我觉得这也说明了我们队存在的一些问题。
暂时到这里。
最后惯例，题目分析。
A: 枚举+凸包。朴素做法(O(2^N*NlogN)),优化后的复杂度是O(2^N). 这道题利用凸性质剪枝应该可以做到赛后裁判长说的N=40, 不过后来我没有测试过。
B: 搜索+打表, 当时据Metaphor队说他们的打表程序跑了2个多小时。
C: 首先枚举R-robot的修理方案，然后对于G-robot网络流检查解是否可行。
D: DP+剪枝-_- 比较郁闷的是我们之前一直在想怎么优化算法……最后10分钟决定交了才发现程序是错的-_-bbb
E: 据说给定的数的可分解性与a^2 + 2 * b^2是否为质数有关~具体我不会证，请参阅P大牛blog~ 但是据说这道题数据水到随便限一下边界枚举都能过……
F: 这是我整场比赛最无语的一道题了-_- 据说O(M*N^3)的算法优化一下常数就能过，而出题者的标准做法居然是O(MN*MlogN)! 而我当时一直在想计算量在10^7左右的算法-_-bbbbbb 另外这题的最优做法是最短路树。
G: DP+打表~~~复杂度应该是是O(N^4*logC)，不过当时我们打表的方式似乎有问题，导致程序效率很低。
H: 分块处理，或者线段树
I: 模拟题，但是当时由于在网络预赛中已经对JLU命的这种题有点心理阴影而没有做-_-
最后, Scoreboard以及成绩……
等奖 学校排名 队伍排名 座位号 题数 总用时 座位号 英文校名 中文校名 队伍 备注
金 1 1 72 5 932 72 Tsinghua University 清华大学 Himalaya Dragoons
金 2 2 28 4 369 28 Tsinghua University 清华大学 Tsinghua - ShangriLa
金 2 3 80 4 623 80 Peking University 北京大学 Code Whisperers
金 3 4 55 4 788 55 National University of Defense Technology 国防科技大学 Robust
金 4 5 40 3 373 40 Peking University 北京大学 eccentrics
金 4 6 37 3 480 37 Beijing University of Posts and Telecommunications 北京邮电大学 Fourth
金 5 7 18 3 541 18 Zhongshan(Sun Yat-sen) University 中山大学 ZSU_Mizar
金 6 8 39 3 599 39 Beijing Jiaotong University 北京交通大学 MagicFlyer
金 7 9 66 3 604 66 Beijing Normal University 北京师范大学 Tendos
金 8 10 4 3 613 4 Ningbo University 宁波大学 Thunder
9 11 67 3 630 67 Ryongsong University 龙城大学 sunrise #
银 10 12 94 3 669 94 Nanjing University 南京大学 Eureka
银 11 13 69 3 692 69 Zhejiang University 浙江大学 Terminal
银 12 14 46 3 708 46 Fudan University 复旦大学 Metaphor
银 13 15 41 3 712 41 University of Electronic Science and Technology of China 电子科技大学 ACMilan
银 16 87 3 745 87 Tsinghua University 清华大学 Y^3 *
银 14 17 35 3 824 35 Shenzhen University 深圳大学 Aspire Final
银 15 18 93 3 944 93 Harbin Institute of Technology 哈尔滨工业大学 Martians
银 16 19 75 3 1044 75 South China Agricultural University 华南农业大学 SCAU_LOL
银 17 20 10 2 134 10 Peking University 北京大学 Ariall
银 17 21 78 2 152 78 Wuhan University 武汉大学 GCC
银 18 22 57 2 202 57 Nanjing University 南京大学 Berserker
银 23 11 2 231 11 Fudan University 复旦大学 Amethyst *
银 18 24 43 2 238 43 National University of Defense Technology 国防科技大学 JaWs
银 18 25 12 2 251 12 East China University of Science & Technology 华东理工大学 Backbone
银 19 26 90 2 253 90 Wuhan University 武汉大学 slash
银 19 27 79 2 287 79 Zhongshan(Sun Yat-sen) University 中山大学 ZSU_Merak
银 19 28 47 2 292 47 Hangzhou Dianzi University 杭州电子科技大学 RPRush
银 20 29 19 2 334 19 Xian Jiaotong University 西安交通大学 Rpbomb
银 21 30 29 2 361 29 Guangdong University of Technology 广东工业大学 la luna GDUT
银 22 31 9 2 393 9 Zhejiang University 浙江大学 Serenity
铜 22 32 77 2 415 77 Hunan University 湖南大学 Hunter
铜 23 33 74 2 423 74 East China Normal University 华东师范大学 kkx
铜 24 34 52 2 435 52 Huazhong Normal University 华中师范大学 AcAres
铜 25 35 68 2 455 68 Ningbo institute of Technology Zhejiang University 浙江大学宁波理工学院 ChqUva
铜 26 36 61 2 470 61 FuZhou University 福州大学 OrOrOrz
铜 27 37 34 2 496 34 Zhongshan(Sun Yat-sen) University 中山大学 ZSU_Alioth
铜 27 38 89 2 521 89 Nanjing University of Aeronautics and Astronautics 南京航空航天大学 XinJieKou
铜 28 39 49 2 526 49 Beijing University of Technology 北京工业大学 Untitled
铜 29 40 13 2 528 13 China University of Geosciences 中国地质大学 Three_Up
铜 30 41 38 2 553 38 Beihang University 北京航空航天大学 BUAA a team
铜 31 42 42 2 580 42 Tianjin University 天津大学 TJU Moment
铜 32 43 15 2 605 15 University of Science and Technology of China 中国科技大学 asdf
铜 33 44 56 2 610 56 Zhejiang Normal University 浙江师范大学 Warcraft
铜 34 45 51 2 674 51 Beijing Institute of Technology 北京理工大学 bit bears
铜 35 46 92 2 712 92 Shanghai University 上海大学 Larva_2
铜 36 47 64 2 723 64 Nanjing University of Aeronautics and Astronautics 南京航空航天大学 cameo
铜 36 48 100 1 33 100 Tongji University 同济大学 Ai Qing Da Mo Zhou
铜 37 49 85 1 78 85 Zhejiang University 浙江大学 Valor
37 50 24 1 82 24 Taiwan University 台湾大学 Rontannygold #
铜 38 51 95 1 88 95 Huazhong University of Science and Technology 华中科技大学 hummer
铜 39 52 86 1 100 86 Hunan University 湖南大学 Footmen
铜 39 53 63 1 134 63 University of Science and Technology of China 中国科技大学 TZX
铜 39 54 5 1 142 5 Ningbo institute of Technology Zhejiang University 浙江大学宁波理工学院 RedRose 女
铜 39 55 8 1 164 8 Southeast University 东南大学 MetaCoding
铜 40 56 71 1 190 71 East China University of Science & Technology 华东理工大学 Reyes
铜 40 57 32 1 194 32 Zhejiang University of Technology 浙江工业大学 ZJUT2
铜 41 58 59 1 199 59 Tianjin University 天津大学 TJU ACMiracle
铜 41 59 101 1 213 101 Beijing Normal University 北京师范大学 Alleyoop 女
铜 41 60 96 1 239 96 Beihang University 北京航空航天大学 BUAA_miyoshi gakusei
铜 42 61 7 1 259 7 Beihang University 北京航空航天大学 BUAA_XGF
铜 42 62 81 1 264 81 Fudan University 复旦大学 Prison Break
备注：*号队伍不参加ACM/ICPC排名，#队伍不参加邀请赛排名
还有Scoreboard, 不过长春没有把队名放到这个rank上。
~http://acm.jlu.edu.cn/cc2007/summary.html