CSP2020 懵逼记

咕了一个周，今天突然良心发现来更新了。 # Day -? 国庆假期前收到了两大张月考复习指南和成堆的卷子，然而还是在 $\rm OI$ 的路上一去不返了…… # Day -26 初赛，没有计数题差评。 在回来的大巴上发现自己白给了好多分。 # Day -24~-22 高一第一次校内大考。 啥都没复习，只有 $\rm Day\ -\!25$ 在拼命干活。几乎把所有生物笔记抄了一遍。 通过奇妙的方式预知到自己会挂三科。 考试节奏比初中慢得多，九科考三天，似乎还比较休闲。 出分之后发现挂了数学，英语和地理。 数学填空把负号和分数线写到一块去了qwq 总体上讲，三大科比较渣，六小科还挺稳(挺勉强的)，所以还算没有跌，但估计后面的考试就吃力了。 # Day -16~0 收拾收拾东西，停课。 主要是做杂题，来者不拒，但是似乎和 $\rm CSP$ 关系不大? 奉行批量口胡少量写的原则，博客文章总量大膨胀。 好不容易打了场七点的 $\rm CF$ ，又掉分了，还被隔壁同场 $\rm Div2$ 的同学吊打。脑子还得做些除锈工作，手速也着实不行。 发现看不懂 $\rm EI$ 的题解，于是上 $\rm B$站 自学了一把抽代，产生 $\rm 10Kb$ 抄抄写写的文字垃圾。 中间抽空学了把 $\rm KDT$ ，感觉挺易懂的，不知道之前为啥没学。 杂题屠多了感觉手速略有恢复。 写的大多是数据结构，计数(尤其是多项式)没怎么敢碰，但还是忍不住口胡了几题。 最后几天搞了几道思维题和 $\rm DP$，希望考场上别再降智了。 中间还穿插了一些模拟赛，偶尔卡题，打得都不咋地。最后一把 $\rm AK$ 感觉把 $\rm rp$ 都赔进去了。 $\rm Day0$ 晚上围观同学们打牛客，胡了一道简单数论。 # Day 1 早上仍然在胡题，发现 $2008$ 年联赛题不会做。 早早到达考场，发现无法提早进入，于是一车人在门口等待。 广大附门口的 **I ❤ GF** 显示了该校优良的计数传统(大雾)。 一路上都没有看到认识的外校同学。 后来才知道 $\rm ntf$ 十二点的时候找过我，可惜没带手机的我正在大巴上睡觉…… ------------ 感觉等了一个世纪才开考。 以下括号内时间均指距离开考的用时。 看了看 $\rm T1$ : 估计出题人____不保。 由于曾经在奇怪的天文杂志上看到过历法有多乱，干脆把 $T1$ 跳了，这样发挥应该稳定一点。 看了看 $\rm T2$ : 一眼秒了，感觉比 $\rm T1$ 简单好多啊，为啥丢这个位置……(flag) $k\leq 64$ 又是想干啥……这跟题目本身关系不大好吧。 看了看 $\rm T3,T4$ : 有点玄妙，秒不出来。 ( $\rm 10min$ ) 先以冲 $\rm Div1A$ 的模式写了 $T2$ ，很快就搞完了。 ( $\rm 25min$ ) 接着开始看 $T3$ ，自动把问题一般化成了一次函数的复合，然后在草稿纸上化了半天啥也没搞出来。 ( $\rm 40min$ ) 突然察觉自己把问题搞复杂了，于是考虑每个加法标记的贡献，发现是操作序列的后缀乘积，那么搞正反两次拓扑就没了。 大概在草稿纸上画了画细节，觉得挺可靠，就写这个了。 - 这里要给自己记一句 : 虽然从应用层面来看，系统,精确而完备的理论往往让使用者感到踏实和满意，但是在开拓的思维过程中，不可避免地需要跋涉于未完备和混沌的泥潭。 我们固然要追求完备的理论，以在某种程度上脱离对灵感的依赖。但对开拓者必经之泥潭的有意无意的逃避，却会扼杀灵感本身。 这类谬误，在之前的所有比赛策略，学习进程，进退抉择中都投下了些许影子…… 在本场 $\rm CSP2020$ 中则表现为 : 上来就给问题一般化，讨厌启发式解法的思维。这是不可取的。 ( $\rm 55min$ ) 由于思路不清楚，写了 $\rm 30min+$ (中途改了好几个地方)才过小样例，大样例有百来个数对不上，猜测是加法标记的贡献算错了。 觉得静态查错成本太高，于是写了个暴力，然后手造了若干组对拍，没发现任何错误。这又花费了一定时间。 最后还是选择了动态查错，输出了一下每个加法标记的贡献，发现错误的位置贡献居然是 $0$ ,根本没计算? 后来才发现是拓补排序的入度算错了，改完就飞过大样例，觉得挺稳。 - 这个故事告诉我们 : 静态查错，动态查错，对拍之间本无强弱之分。灵活应对才是节省时间的上策。 ( $\rm 1h40min$ ) 比赛快要过半了，才搞出 $T2/T3$ ，还有一个大模拟 $T1$ 和不可捉摸的 $T4$ 没开，有点慌。 回头搞 $T1$ ，仔细看了看题面，发现没有想象中复杂。 不止从何写起，决定仔细思考做法再动手。 首先实现一个从儒略日到年份的映射，然后根据单调性二分一下就可以得到答案了。 二分月份和日期有点烦，不如枚举，那就只用二分年份了。 公元前容易用负数实现兼容。 ( $\rm 1h50min$ ) 先写了个儒略历版本，细节比较少，很快就写完了，过了第一个样例。 接下来就是判消失日，凑闰年等等…… 跑了下大样例发现不过，错了几十个，一番调试后发现是边界问题，改完就过了。 ( $\rm 2h20min$ ) 还剩下 $T4$ ，回想起 $\rm CSP2019\ D1T3$ ，有点慌了。 大概思考了一下，发现让每条蛇都选择吃，如果自己选择吃会导致自己被吃，则反悔即可。 于是就是要每次抽出最大最小值然后相减加入回去。 发现 $O(Tn\log n)$ 算法非常好写，于是先搞了一发线段树当堆。 写完调了两下就过了小样例，然后一发过了大样例。 ( $\rm 2h50min$ ) 沉思片刻后发现和蚯蚓有点像，但还是不会线性做法。 前面几题都没检查，估摸着自己没有 $\rm AK$ 的实力，决定见好就收。 写了个类似 $\rm zkw$ 的东西试图卡常，写了三个版本(说好的见好就收呢……)，发现压成一个 `ll` 最快。 最后的成果是本机极限数据 $\texttt{4s}$ ，开 $\rm O2$ 要 $\texttt{1.5s}$，觉得没救。 ( $\rm 3h25min$ ) 回头看了看比较担心的 $T2$ ，没发现什么，天真地以为 `ull` 就能保平安。 最后看了看 $T1$ ，测了几下消失日附近，发现挂了，赶紧改了改。 ( $\rm 3h45min$ ) 最后 $\rm 15min$ 无所事事，检查了下文件，重新跑完所有样例，什么都没有发现。 感觉检查挺充分的，心里比较踏实。(flag) 期望得分 $100+100+100+70=370$ ，感觉这个分挺大众的，不过卡 $T3$ 也是有可能的? 晚上跑到 `oitiku` 测了测，发现 $T2$ 有 $2^{64}$ ，变成了 $365$。 # Day 2 早上到 $\rm luogu$ 测了测，发现 $T4$ 挂了。 我三种写法拍了半天怎么可能挂……于是把 `main()` 看了一遍，发现是读入写错了。 果然还是挂分了，希望排名不要太难看吧。 # Day 3+ 在学校拼命补作业。 出分了， $100+95+100+45=340$ ，省内 $\rm rk10$ ，还算凑合。