SDOI2016 Round1 行纪

第一次参加省选,感觉还是要写点什么比较好吧,哪怕记记流水账 ……

Day 0

早上,火车到了济南,打电话问了问老师要坐哪路公交车 …… 到了酒店开了房,感觉还不错 …… 然而老师要到下午才能赶过来 ……

下午正睡觉,老师给我打电话说让我赶紧过去 …… 报道啊啊啊啊 ……

坐公交车去了山师报道 …… 考场在山师附中 ……

路不远这两天不用坐车了吧,走着也没关系诶 ……

下午回去调了道费用流,练练 EK 模板 ……

晚上去超市买了两个士力架,两盒牛奶,一块香皂 ……

回酒店我竟然记得路!果然自己一个人出来一趟学会了认路的技能吗 QwQ ……

晚上调了一道组合数学,还是 yts1999 出的题,%%%!

睡觉睡不着,又用手机上 Blog 看了看模板 ……

Day 1

早上大约七点半到了考点,抽了号 ……
早就知道这里的电脑是 XP 系统,还好之前集训时熟悉的 Windows 下的操作 ……
7:59 准时发题,和 WC 一样是纸质的 ……

喝水看题 ……

第一题:异或?异或有什么性质来着?难道是线性基?肯定不是啊喂 …… 看这样子像个 DP?打个表找找规律吧 ……
30min 过去了 ……
…… 然而并没有什么规律,打好 20 分暴力放在一边 ……

第二题:一个数是另一个数的约数 …… 一个数除以另一个数是质数 …… 等等!数据这么大怎么判断质数!Miller – Rabin 我不会啊啊啊啊 ……
写个线性筛 + 试除吧 ……
匹配?收益大于等于零?看起来像是要二分的样子。跑费用流?等等!这是不是二分图啊!
papapa 敲了个二分图染色,跑了 1000 \times 1000 的数据发现是二分图 …… 虽然不会证就当它是吧反正我不会带花树再说了带花树 O((n + m) ^ 3) 也过不了啊喂!
建图还是要先二分图染色再重建的 …… 常数会不会太大?算了就这样吧 …… 几分钟敲了个 EK 模板,还好昨天刚敲过 ……
一个半小时(具体时间记不清了)后样例过了 ……
写对拍 ……
诶这暴力咋写? 把每个数拆成 b_i 个数搞,复杂度爆炸但是对拍足够了吧 ……
半个小时后开始对拍 ……
Wrong Answer on Test #7?md 暴力写错了 …… 滚去改
Wrong Answer on Test #13?md 又是暴力写错了 …… 滚去改
然后就是一堆 Accepted …… 先放在那里吧 ……

第三题:树?!我会树剖!
这标记是什么鬼 …… 根本不会啊 …… 难道是 SegmentTree Beats?先打个暴力吧 ……
每次询问一遍 BFS 相当的暴力,嗯样例能过 ……
部分分有 a = 0 的点,写个树剖吧 ……
……
十一点半了 …… 树剖写完了,赶紧对拍 ……
Wrong Answer on Test #18?缩小数据范围试试 …… 该不会暴力又写错了吧 ……
Wrong Answer on Test #32 …… 数据范围够小了手算下 …… 嗯我的树剖写错了 ……
md 这线段树什么鬼 …… 改线段树 ……
md 我的树剖根本没有计算出 size 啊怎么剖出来的 ……
s.top() 接着 s.pop() 蛤?……
改完树剖已经 12:40 了 …… 对拍终于不出错了 ……

回去看 T2 …… maya 忘了写静态内存了 …… 改改改 ……
T2 复杂度有点大?就当他是 O( 跑得出 ) 吧 …… 来组 n = 200 试试 ……
答案好几万,跑了 1.5s ……
啊啊啊啊啊啊啊啊啊怎么办来不及优化了啊 ……
算了,T 就 T 吧 …… 回去检查检查文件 ……

下午知道了成绩,140,rank9,还算可以吧 ……

heheda AK 了!
std rank2!

……

感觉明天要考字符串、反演、法法塔之类的 …… 啥都不会,药丸啊 …… 晚上赶紧写了个 KMP 模板 …… 也许明天打暴力用得到?

其实,Day1 成绩好未必是一件好事?起点越高,失败后便摔得越惨吧。 但愿 Day2 不会滚粗。

Day 2

今天不用抽号了,去的晚一点没关系 …… 7:50 进了考场

wow 昨天的目录还在,不用重新写对拍了诶 ……

7:57 准时发题 ……

喝水看题 ……

第一题:maya这不是集训原题的弱化版吗!完了我不会啊啊啊啊怎么办,暴力后缀数组能有 60 分啊啊啊啊,他们肯定至少能写出来 60 分啊啊啊啊,今天注定滚粗了啊啊啊啊啊
先打个 30 分暴力吧,std::set< std::vector<int> > 够暴力吧 ……

第二题:maya计数问题!前段时间写过不少类似的题吧,推推式子看 …… 我们先来求没有稳定数的排列数 …… 然后至少一个稳定的排列数量 …… 诶这个好像要容斥? 二十分钟后,脑海里一片空白 …… 这种题他们肯定都会啊,我怎么就是想不出来啊啊啊啊,第一题怎么办 ……
先打个 10 分暴力吧 …… O(n!) 枚举全排列 ……

第三题:好像是个 DP?10 分可以爆搜? O(n ^ 3) 的划分 DP 可以 30 分?不管了,先回去想想第一题吧 …… 也许还有希望 ……

嗯 …… 后缀数组,先用 std::sort 写个暴力后缀数组再说 ……
好像求出 height 可以统计子串数?让我想想 …… height 表示排名相邻两个后缀的最长公共前缀长度 …… 这个好像可以线性递推?不管了,写个暴力吧 ……

于是我有了一个 O(n ^ 2 \log n + n ^ 2) 的后缀数组 ……

让我想想,每个后缀对答案的贡献是 ……

1.5h 过去了,终于把暴力后缀数组写完,暴力求 height 写完,统计子串数量写完 ……

手敲了一组大数据,答案和暴力结果一样,感觉推导的应该没问题 ……

O(n ^ 2) height 明显复杂度太高吧?让我想想怎么线性递推 ……
对于某个后缀的 height,当这个后缀与前一个后缀的首个字符相等时,结果为后一个字符所对应后缀的 height + 1,否则为 0 ……
"heheda" 作为例子手算了一下,感觉没问题 ……
恩好像没问题,就这样写吧 ……
实在不知道递推顺序,就记忆搜索吧 ……

嗯,让我想想后缀数组复杂度能不能降一降,写个倍增试试?

倍增的框架敲上了,想想怎么基数排序来着 …… 怎么基数排序来着 ……
将近半个小时过去了,还是没想到怎么基数排序 ……
算了吧,直接丢给 std::sort 做双关键字吧!

于是我的后缀数组变成了 O(n \log n \log n + n) ……

让我再试组数据 …… 啊啊啊啊啊怎么和暴力结果不一样啊!!!
后缀数组把倍增换成原来的暴力排序,结果还是不对 ……
难道是 height 求错了? 改成原来的平方暴力 ……
嗯,好像是对的 ……
maya我递推式推错了 …… 怎么办怎么办怎么办!

看了看时间已经十一点半多了 ……
算了吧,换成平方暴力!

后缀数组的复杂度定格为 O(n \log n \log n + n ^ 2) ……
瓶颈依然是 height 的平方 …… 药丸 ……

赶紧写第三题!
乘上一个整数表示方差?看来要维护两个信息啊 …… 和的平方与平方的和 …… 啥玩意 …… 还是记忆搜索吧 ……

写完自认为能有 30 分的 DP 之后已经 12:40 了 ……
赶紧测测样例,maya样例不过啊 ……
输出中间结果试试 …… maya除不开啊 ……
一定是我式子推错了吧 ……
赶紧换成 double 就算精度炸了说不定还有希望啊 ……
恩就这样吧 …… 样例总算过了 ……

12:50,赶紧检查一下前两题,文件输入输出写好 …… 关文件 …… 调试代码去掉 ……
maya第二题的表打错了啊啊啊赶紧重新打 ……

13:00 结束 …… 深感药丸 ……

听讲题 ……

Day1 T1 数位DP? T2 好像我的做法不是正解?正解没有二分 …… 怪不得跑这么慢 ……
T3 有点类似超哥线段树的东西?不懂啊 Orz

Day2 T1 后缀自动机裸题?后缀数组搞一搞就好? 唉后悔没学后缀数组了 ……
T2 叫什么错位排列?maya我就剩一点容斥就能推出 60 分做法了啊啊啊啊啊 ……
T3 斜率优化?好像我暴力的式子也推错了 …… 爆零啦 ……

成绩出来了 …… 90 分滚粗 …… 直接掉到 60 多名了 ……

果然 Day1 的 Flag 生效了?

下午坐火车走了,晚上回到了临沂 ……