NOIP2024 油鸡

剩流：炸

2024/11/9

上午无聊没事干，写了点 tarjan。下午去八中试机，没想到八中机子一坨屎， 3 \times 10^8 次模运算要 1.7s。晚上吃的火锅。

晚上睡不着，浑身发烫，寄。

2024/11/10

早上状态不好，来到考场还是迷迷糊糊的。

8:27左右发了密码，发现竟真有之前一个帖子说的树上问题。T1 是一个贪心，把连续段维护 0/1 的个数，一位一位贪就行。8:50 过掉大样例。

T2 看完之后胡了一个 O(n) 的 dp，发现能用矩乘优化。

写了之后发现假了，这时已经浪费了 40 分钟。心态有点小崩，去看了看后面 2 题，T3 不想看，T4 链会一个整体二分。好像都不太好写，又回去看 T2。改了 T2 的方程式，然后各种调，终于过了大样例，此时 11:10。

虽然时间不多了，但是好歹 T2 搞出来了。T3 读了读题，能拿 40 分，便打了。11:40 左右过了链和菊花，k=1 只测了小样例，，没看到样例3也是 k=1 的，烂烂烂。

留了1小时给 T4，显然不够。发现把链的推广一下，用主席树维护深度大于某个值的来自相同子树的点的连续段。最后二分答案看区间最长值相同的连续段是否大于等于 k。是常数很大的 O(q \log^2n)。

写花了 30 分钟，调样例又花了 20 分钟。一测样例2，WAWAWA，天塌了。测了下样例3，发现链的过了。这时候我完全后悔了，不如直接拼暴力，都有 64 分。但是没办法，最后 10 分钟我想应该也调不出来了，只好拼了个平方的暴力，12:57 过完样例2，检查了下 freopen 就交了。

考完整个人都是蒙的，分不高还容易挂，主要是 T2 写太久和冲 T4 导致的。

最后 100+100+40+48=288，最低会挂到 240。

回家吃了饭还要来学校报分，同学们的分数参差不齐，有不到 200 的，有 300 多的。考都考完了，和同学去万象城玩游戏了。

upd:100+100+40+36=276，T4 \log ^2 的链没过，哭哭哭。