//大概在5周前就写完忘记发了, (2)和(3)大概胎死腹中了.
Climber.pI按: 时隔两年, 故地重游, 大概是高中OI生涯的第二次GDKOI, 也是最后一次GDKOI, 倒数第三场正式比赛了. 结果差强人意, 却也是意料之中. 也就形式化一把, 随记二三.
(1) 关于赛场
大概是前一天晚上一个人逛中大, 结果还没找错了讲评的地方 = =|||
Day0
大概就是各种聊天, 各种扯淡…没敲一行代码, 所以第二天就NC了
Day1
感觉组织工作比NOIp差很多, 比如进去都半个小时了才有水喝.
P1是个DP, 一开始根据数据范围准备的判断了复杂度, 但是后来鉴于题目的背景, 没有进一步的分析题意. 相反, 联想到了USACO Training的job, 二分+贪心经典题, 于是YY了一个贪心. 大概是把所有任务排序, 然后先选大的, 不能再装的时候就选小的, 居然还过了样例.
但当时对贪心的正确性毫无把握, 于是又写了O(a^N)的暴搜, 然后对拍. 大概是手生的缘故, 一个半小时才全部折腾完, 最终的结果是贪心错误. 于是有改写了一个小范围暴搜, 大范围贪心的程序. 当天中午重新看题的时候, 瞬间发现题目实际上是个变形的背包. 一旦在现场思维走偏, 总是难以挽回, 比如去年初赛, 比如去年Day1P2.
这时候有种奇怪的感觉, 时时刻刻想着放弃却又不敢放弃, 完全不能控制比赛进程, 只能顺着身体的惯性写题. 很像初中的时候跑1500的感觉, 带着种无法预知的恐惧.
P2是最短路, 由于边的权值为{1, 2, 3}其中一个数, 所以可以拆成若干边权为1的边, 从而用O(3n)的BFS AC.
当时读题之后认为dij+heap可以A, 但是几乎不记得怎么写了. 大致估计了一下, 认为SPFA可以过80%, 又担心SPFA敲挂, 又多敲了一个Floyd. 敲完折腾完对拍基本上过了3h了, 结果一直不同, 最后手工算了一组数据发现是Floyd挂了, 原因不知. 当然, 由于只开了80%的范围, 也无缘享受4s时限优惠了.
P3是个数学题, 当时只有40+min, 果断放弃. 但事实上30%的做法可以直接手算打表, 50%的做法可以利用DP, 甚至可以通过记忆化搜索打表AC.
P4是字符串, 由于不记得C++的I/O, 只能用字符数组敲. 虽然原理绝对正确, 但是最后还是没调出来.
于是Day1就结束了, 41算是意料之中, 值得庆幸的是SPFA没有写挂. 和NOIp一样, 依旧是全市第二, 尽管wx神牛这次102是我的若干倍.
Day2
大概是被Day1吓到了, Day2晚上回来还是敲了一会儿代码. 第二天的组织工作好了很多.
P1是数学题. 仔细读题之后很快发现了O(N)的做法, 联想到若干次被周期数列坑了, 果断找循环节, 发现前面一部分并不循环, 而循环节一定是N的倍数, 于是果断从后面找N. 考虑了50%的范围, 于是找了400N, 于是只过了60%的数据. 可以证明的是循环节长度不超过O(N^2), 但是我并不知道如何证明, 于是12分没了. 经过一番对拍, 时间已经过了近2h了.
P2的标准做法需要用到线段树/树状数组/平衡树等高级数据结构. 读题之后发现模拟十分好写, 但是由于当时考虑不周, 边写边调浪费了很多时间. 大概是利用一个数组记录某值是否存在, 然后利用数组模拟链表来实现. 终于调对了之后, 发现样例挂了, 特意问了评委30%的范围是否符合50%的要求, 得到肯定答复后. 遂放弃此题的进一步调试, 最终过了4个点.
当时还有70min左右, 在P3和P4犹豫了很久, 发现P4如果用Floyd的话还需要记录路径, 实在不好写, 遂放弃.
第三题是搜索, 可以利用DP预处理状态, 或者充分利用问题性质, 只枚举每个格子需要填否即可. 当时的做法是记录未填格子的位置, 逐个枚举, 如果某行全部枚举后进行可行性剪枝, 最后判断没列是否符合题意. 虽然思路绝对正确, 但是一直调不出来, 在最后几分钟突然发现是初始状态打成1了, 应该为0, 改了之后, 屏幕一闪, 样例过了. 最终过了6个点, 仅超时了两个点, 有两个WA的点多输出了一组解, 不知道哪里写挂了.
于是总分就是18 + 16 + 24 = 58, 又是全市第二, xh64第一, wx牛居然直接3分了…
至此, GDKOI的赛程结束, 在中大西苑一楼大堂看到一等和二等证书发完却不见深圳踪影, 怅然若失之感涌上心头, 差不多退役了.
(2) 一些人一些事
(3) 乱七八糟的想法