CSP-S2019 退役记

退役了。

Day 0

去秋游了，走了三万多步，人没了（退役 flag x 1）。

回来就颓颓颓颓（退役 flag x 2）。

Day 1

11 点睡觉的，1 点多被爆肝的室友吵醒，醒了大半个小时才睡着（退役 flag x 3），6 点多就得起床了。

考场是某校名中带有学车二字的学校的负一层教室（地下停车场），只提供睿智的移动厕所，厕所不能冲水（退役 flag x 4）。

考场座位对面就有一个显示屏，随时可以看到时间，觉得很爽（退役 flag x 5）。

开考，直接把第一题走了。

第二题调了很久智障错误（退役 flag x 6），比如什么左括号的点没算贡献、没做前缀和……

我想 AK（退役 flag x 7）。

第三题一开始去想一个拆子问题的算法了（退役 flag x 8），大概是 $1$ 一定会走到另外的编号最小点，于是对于这条链挂出的若干子树搞一搞，一开始还以为是对的，成功自闭。

后来想到正解方向，只是模糊觉得限制都是一条边要在另一条边之前做，于是全局暴力维护一个顺序关系（优化以后再说）（退役 flag x 9），后来发现无法解决的是一条边必须紧接着一条边选的情况，成功自闭。

还有一个小时就冲上去写暴力了，十分不冷静，写了一个假的链，然后不会做菊花，最后就是把阶乘和链和假的算法结合了一下。后来很开心地发现链挂了，然后意识到我的假算法对于链的情况应该是对的？获得了 10pts 的好成绩。

出来发现大家都 AK 了，滚回学校继续颓（退役 flag x 10）。

Day 2

换了个寝室住，但是也没睡好（退役 flag x 11）。

我想 AK（退役 flag x 12）。

开考前在正常的厕所外面排了一会儿队，然后意识到好像不想上厕所。

开考，看到一个 $998244353$，直接把 dp 走了。

看到第二题慌的一批，有点点斜率优化的感觉（？）（退役 flag x 13）。先猜了一个段数相同情况下每一段尽量往右延伸的结论，然后再猜了一个段数越多越优的结论，乱写一通从前往后贪心，发现写不来，于是不会做（退役 flag x 14）。

想扔了看第三题（退役 flag x 15），但是模糊意识到反过来做最后一段尽量短，然后写了一个二分，过不去大样例（退役 flag x 16）。冷静了一下，写了个暴力，发现右端点确定时段长不能二分。

再冷静了一下，发现左端点确定时段长可以二分（注定了想不到单调队列优化（退役 flag x 17）），写了个 88pts 跑路了。

第三题一开始想对于每条边求出具体两边中心的，搞了一会儿还是不会做。突然想到对每个点算贡献，随便推了一下发现好像是可以维护的，就把线段树合并走了（退役 flag x 18），到根的链单独拿个树状数组维护。大概 1h 后过了大样例，还有 20min，觉得自己好强（退役 flag x 19）。极限数据本机跑了 3.5s 不想卡，改了个用 getchar() 的读入优化没有任何变化，怕写挂就改回去了（退役 flag x 20）。

出来发现大家都 AK 了，滚回学校继续颓（退役 flag x 21）。

学会了德扑，赌了两局都破产了（退役 flag x 22），还重学了 UNO。

100+100+10+100+88+(100-?)，大家再见。