「こんなきれいな星も、やっぱりここまで来てから、見れたのだと思うから。だから・・もっと遠くへ・・」

PKU Campus 2012

因为不想去APIO上课…… 正好PKU有个ACM校赛…… 问了一下常州的人,他们有个队伍只有一个人,于是就加入了……

注册工作各种不顺利,先是找不到队友在哪里(根本不认识啊……),然后要有效证件但我没带…… 然后又说我们队伍压根没报名…… 但经过一番折腾搞得筋疲力尽后终于进了赛场。。

第1题是防爆零题不解释,但提交系统出了一些问题,导致我们10min时候才成功提交

第二题是构造…… 要构造出一个数a使得a^2+a+1有至少9个不同的质因数…… 队友想出了一个很蛋疼的构造,要各种高精,不过至少是对的,我写了20min才A…… 其实不需要这么复杂,直接暴力枚举a就行了,解出现在60万左右……

然后看了第6题,显然是SG函数找规律…… 于是打了SG表,发现规律是一个值的SG值仅由其三进制中最低出现的2的位置决定。发现了这个规律后还是没用,因为朴素的SG打表要平方级别。于是我YY了一个方法,因为这个规律显然是对的,于是如果我们已经预处理出了2出现在低K位的SG值,那么2出现在第K+1位的SG值可以通过前面的SG值表示出来,这样就做到了线性打表。于是打出每个2的位置对应的SG值就AC了。在1h15min左右时候AC的。

然后看了第3题,直接BFS得到BFS树,然后对于每个点如果都存在一条边连向同层或上层的边,那么可行,否则不可行。在1h25min左右AC的。

这时候时间只过了不到1.5h,我们已经4题了…… 然后如同我以前在网上做ACM时一样,我根本没法保持初期的压制……

看了第8题,网络流可以做,队友正要写,我突然发现点数50W时限1sec…… 立即把他拉下来……

然后看了第5题…… 一开始以为各种分类讨论,我分了十几类,然后发现代码根本不可实现,于是暂时搁置。

然后看了第4题,发现暴力是O(N^2)的,但可以发现转移方程是卷积,貌似可以FFT+倍增优化到O(Nlg^2N),但考虑到太麻烦,而且常数问题和精度问题都非常严重,搁置了

然后看了第7题,感觉离散所有交点和交线,建图,然后就可以把每个3D凸包搞出来,就可以了…… 但3D几何难度可想而知,明显是防AK题…… 果断放弃

然后写第5题…… 写了几个分类后感觉时间复杂度很有问题…… 这时候突然想到可以插头DP,于是立即开始推插头转移…… 让队友写第8题网络流(我没指望能过,但反正没事干)

过了几分种我推出了转移…… 队友居然能把网络流写错,我真是无语了…… 把他换下来后我开始写第5题…… 写了快要1h后写完了交上去WA,于是打印下来调试,让队友继续写网络流……

然后我发现有个地方少判了一个,于是改了,交上去还是WA,于是继续调试……

然后发现循环时候把for i:=1 to n-1打成了for i:=1 to n,虽然是个小错误,但我还是改了后交上去,结果AC了…… 这时候貌似是3h30min……

然后队友继续调网络流,我真的无语了,都准备直接帮他重写一遍了,但突然想到这么搞八成要TLE…… 于是决定自己YY有没有更好的做法……

我YY了第8题,没有想到比网络流更好的做法…… 队友还在调第8题,已经造成了六七个罚时…… 不过我已经懒得管了,反正没指望能AC……

然后又YY了第4题,发现如果考虑中间“翻转”了M次,那么所有指数只与M有关,与安排方案无关…… 于是又推了方案的公式,发现是组合数学…… 推出来后离考试结束只有10min了,写不完了…… 队友还在调第8题……

这时候我们排名rank9……

然后10min后比赛结束时候排名掉到了rank11……

不过还是有个急救包的奖品的

不过我不知道在哪里拿

于是就回去了

感觉这次问题主要在我身上…… 做第5题速度实在太慢了,而且一度掉进坑里去浪费了大量的时间,导致第4题YY出公式(而且貌似和正解差不多)但没时间写了…… 表示这次比赛进程和我以前在OJ上做ACM几乎一样,前场压制的很好,排名很靠前,然后中场就慢慢掉下去了……看来中期压制能力还有待提高啊…… 我还是太弱了TAT……