2010 Asia ACM-ICPC Regional Harbin

最近很忙,基本上没时间写解题报告了,还是想写写当时比赛的情况,嗯,这篇文章是写的晚了点。

来到哈尔滨的时候是报到前一天中午,我们应该是比较早到的队伍了,到了哈尔滨,刚走出去就感受到了什么是寒冷,9 月的哈尔滨,10°C 不到的温度,我直接套上了大衣,中午吃完饭到了招待所,做的第一件事,就把内衣换上了。。。

热身赛比较悲剧,队友一时头脑发热,BFS 想成堆优化 Dijkstra,没有切圆

A 题是 A+B,秒杀,当时这题交的人很多,导致了评测机卡壳的情况,还好决赛的时候评测机还是很给力的。

B 题是个 KMP 加组合数学,好吧,当时没看出来,被队友的暴力直接水过。。。

C 题简单 BFS,经过了这题才发现某孩子不知道边权为 1 的图可以用 BFS 跑最短路,好吧,我失策了,还好后来即使调整了下状态,没出大岔子。

D 题是多校联合的陈题,给你 N 个点,选择三个点求最小形成的角度,直接枚举点,极角排序扫描即可,复杂度 O(n2×lgn)O(n^2 \times lgn) 的,当时没时间写了,就放弃了

热身赛的后半小时,一直在测试 PC2 的性能,得到结论 RE 很困难,PE 判成 WA

热身赛结束的下午,两个队友和另外一个队的孩子一起去观光了,我没去,没有在比赛前参观的习惯,照例一个人窝房间看了会儿电视,看了下模板

第二天的比赛总体上来说比较正常,就是开题速度比较慢,50 多分钟了才过第一题,算是非常之慢了。。。

50 分钟 F 题 1Y

最短路的题,50 个点的。。好吧,之前被 A 卡了很久,队友看到这题水,就上去拍了,直接水掉。

54 分钟 B 题 1Y

贪心,正反排序直接计算即可,当时我还怀疑其正确性,两个队友都说这个思路是对的,就直接拍了

87 分钟 A 题 1Y

树形 DP,原来想的 DP 思路不怎么好,最短路想用预处理,后来想想,既然是树,就直接 DFS 带上距离了,还是要赞一下现场赛评测机的速度还是很快的。

181 分钟 H 题 1Y

最小费用流,这题是最小费用流的变形,当时队友建图改边权的没想好,卡了将近两个小时,囧死,还好过了这题,士气没有下跌。

195 分钟 I 题 2Y

唯一一题 WA 掉的题目,队友写公式的时候漏了一个 H,查了五分钟。。队友推公式的技术还是很强大的,数值积分 5 分钟出结果,这速度。。。

248 分钟 E 题 1Y

欧拉三角,DP,这题想到了暴小数据,就是没找到规律,百思不得其解为什么其他队伍都是暴小数据得到的递推式。。。这道题三个人一起各种 YY,总算在封榜后 8 分钟 1Y 了。

剩下的时间都在看 J 题,当时没学过斜率优化,DP 方程也写错了,还是很可惜。。

总的来说这次比赛状态不错,觉得能发挥好,不失误,不掉链子就可以了。

瓦尔兹好给力,最后的绝地反超,还是很雷人的。