Day 924844031

退役前最后一场模拟赛。

T2 用 $\mathcal O(\frac{n^4}{16 \omega})$ 冲过了 $n = 2000$，很震撼。大概是要求一个带特殊性质的 01 矩阵的秩被我用线性基 bitset::_Find_first() 启发式硬搞过了。

希望省选的 RP 不要因此消失。

Day 924844032

没去学校。感觉 3 月份状态明显不如 2 月，具体表现为模拟赛前 10 的次数少了一半，于是在家不做题，尝试调整状态。不过上午还是把某场已经咕了半个月的 CF 题补掉了，写了一堆很智障的错误，果然状态不佳啊。

中午点 KFC，大概是退役前最后一个疯狂星期四了。

下午美美地睡了一觉。醒来以后有被新闻震撼到。

12 人中还得减去一个女队。除去集训队和高三，发现自己 NOIP 省内排名 rk12，校内排名 rk5。这下队线外 rk1 和校线外 rk1 全占，提前退役了。

奶一波 JS 省队，nfls $\frac{1}{3}$，jzhx $\frac{1}{3}$，剩下的 cz, xs 和 tx 各期望 1 个，女队大概率 rhx。而我稳坐队线 & 校线外 rk1，哈哈！:smiley: :thumbsup:

所幸分差不大，仍有翻盘的可能。但愿如此吧，队线外的人大都这么想。

明天干啥呢？去学校用比赛的系统敲敲不太熟的板子吧。或许可以去看一看总结，回顾回顾自己模拟赛成为 :clown_face: 的经历。/cf

江苏荣光不再了。

Day 924844033 $\equiv$ 0

为什么拿 924844033 作为模数呢？因为它的原根是 5 而不是 3 啦！

敲了一些各种板子，一直敲到下午试机。试机写了 NTT 和 SAM，奶一口都没用。还写个线段树用来测对拍，纯属无聊。晚上翻一翻模拟赛的记录，并把某些不太常用但感觉挺重要的算法看了看。

晚上比较早就睡了。明天 RP++！

Day 1

7 点的闹钟，硬是拖到了 7:10 才起床。

8 点左右到了学校，在走廊外的窗口吹了一会儿风。

8:30 发 pdf 密码，三个传统题。T1 感觉直接跑个 bfs 啥的就行了，签到题吧，但还是耐着性子读完了 T2 和 T3 的题面。T2 看着像 tarjan，T3 似乎是用什么数据结构维护贪心，有 15 个大样例，看起来不像是 yyl 组的题。

决定先签到，发现建图是 $\mathcal O(nm)$ 的，思考了几秒钟发现直接差分求一下并再乱搞搞就行了，10 分钟以内过了大样例。肉眼检查检查感觉没啥问题，丢掉去看 T2。

大小 $\in \{1,2\}$ 的划分似乎是好处理的，而 $\{i,i+1\}(i > 1)$ 的划分就必然是从割点处分开。感觉做一遍 tarjan 然后枚举方点算一下就行了？于是开始码，期待着 1.5h 做完 T2 然后留下 3h 刚 T3。没多久过了小样例，测了样例 2 发现输出是 2，然而答案是 3。检查了一下代码感觉没写错的样子？于是在草稿纸上画了 20 个点的图（并意外地发现数据中有重边，虽然不影响 tarjan），这才意识到一个可行的划分不一定要从一个方点割开，于是算法整个假掉了。

接下来的半小时，我尝试修改 T2 假掉的算法，但没有任何进展。大约 10 点决定暂时放下 T2，去给 T3 打一个暴力。胡了一个子树向父亲合并的贪心，用堆启发式合并维护，看了眼部分分的表发现有高贵的 48 分！那还不赶紧写掉？于是在 10:30 之前，通过了第 $\{x \mid x \le 8 \lor x = 11\}$ 个大样例，$\mathcal O(nm \log^2 n)$ 开了 O2 跑的飞快。

继续瞪了眼 T3 的部分分表，发现唯一可做的似乎是性质 C，用树剖维护下 $\min / +$ 矩阵就好了，但是只有 6 分，谁写？性质 B 的链没有想到什么复杂度正确的做法，性质 A 可能得维护每个元素在堆中存活的深度，感觉巨大难写，还是回去想 T2 更实惠。

想着先拿个 $k=0$ 的 40 分吧，但只有大样例 2 是 $k=0$ 且答案是个 $\mathcal O(1)$，于是写了个 $\mathcal O(3^nn)$ 的暴力用来对拍。$k=0$ 直接枚举因数然后在圆方树上跑个 dp，$\mathcal O(n \sqrt n)$，写起来很痛苦。之后的一小时基本处于写了拍，拍了挂，挂了调，调了再挂的死循环中。中间某一个版本拍到了 100 多个点，正准备开香槟然后挂了。好在 11:30 之前过了拍，至少感觉分差不至于大到离谱了。

又花了半小时想 T2 的树，但是啥思路都没有。12:00 又回头看了眼 T3，在 T2 的 $n \le 20$ 和 T3 的性质 C 中果断选择了 T2。去洗了把脸以后准备莽个 $\mathcal O(n^3)$，但为什么不去给暴力剪剪枝呢？于是把枚举子集改为了「枚举合法的子集」，随机数据下跑过 20 简简单单。这下不挂分勉强上 200 了，但不知道会不会有一车人过了 T2。

最后半小时，感觉也没啥别的分能写了，尝试冲 T3 的性质 C 但未果。最后 5 分钟果断弃掉性质 C 去检查了文件名以及 10 分钟写出来的 T1 了，求稳不比那 6 分重要？

估分 $100 + 55 + 48 = 203$，希望不要挂。还没我的 APIO2022 高。

出来一问，ymx AK 了，很猛。csy 没 AK，很震撼，但仍有极高的分数。高二有两个 223，并已知 wjz 过了 T2。看来还是被碾压了。

无所谓，Day 2 还能翻盘/被翻盘。

Day 2

晚上睡的不太好，6:30 左右就醒了。试机的时候感觉有点困，但不太敢睡，担心趴一会儿会导致整场精神都不太好。

8:30 准时开题，T1 数据范围只有 10，一脸的直接 $\mathcal O((nm)^3)$ 判胜负态。T2 感觉可以从集合大小 $\le 2$ 入手，但一眼看不出什么想法。T3 很复杂的计数，一脸的不可做，大抵是防 AK 用的吧。

那就先写 T1 吧。写起来有一车细节，感觉不比什么大模拟好写，总之很痛苦。大约 9:10 写完了判胜负，求步数还没写，但 9:20 才把判胜负调对。接下来打算写个 dfs 用来算步数，但是输出一直不对，想了半天才发现 dfs 会产生环。那就不 dfs 了，想到可以直接在 bfs 里面统计步数吧，这似乎恰好是对的。于是浪费了半小时后，10 点整过了大样例，码长 7K+，近 200 行。

没心思检查 T1 了，洗把脸准备先丢一边看 T2。发现部分分给的很多，于是对着表格开始想。性质 A 直接判 -1，跑个 dinic 二分图匹配。性质 B 中 Bob 只有两种可能的方案，那 Alice 让 $X$ 最小的那种尽量大就行了。性质 C 把二分图匹配换成带权匹配，dinic 费用流硬上。性质 D 不会做，先放着。加上指数的暴力已经有 52 了。但是怎么会有人能忍住不写退火的？于是 $n,m \le 200$ 的随机数据也能跑过去了。这样就有至少 60 了，那么开始写。预估 12 点之前必须写完，然而 11:30 就完工了，共计 341 行，8K+。

接下来的举动让我大受震撼。写完 T3 人人都会的 10 分后，我浪费了宝贵的 30 分钟在思考 T3 一脸不可做的各种部分分上，然而一分都没有得到。大约 12:15，我回来思考 T2 的性质 D。其实看完 T2 不久我便有一个在 $S \cap T$ 的点之间连边转图论的想法了，但并没有仔细思考下去。在思考性质 D 的过程中，我意识到合法的情况应该是一个基环树森林，这样正解就呼之欲出。然而此时已经 12:30，基环树上的各类情况看起来较为复杂，我并无足够的自信能在比赛的最后半小时中思考完并码出来。同时性质 D 也并非该转化的某个比较好写的分支，如果贸然开冲可能会使得这半小时的努力化为乌有。因此我选择检查码量巨长的 T1 和 T2，不过一直到比赛结束也没有瞪出来什么细节上的错误，应该问题不大。

总之被翻掉了，且高二学长人均 210。预计不超过 100+60+10=170，JS 前 11 不知道还有没有。校线？做梦去吧。

无所谓，C 类会出手。

Day 懒得算

出分。day1 没挂分，day2 T2 变成了 48，似乎是错误估计了 flow 的效率以及退火退的不够好。

总分 $100+55+48+100+48+10=361$，加上 NOIP 算是苟进了 JS 前 11。据说我这个分还能有 ZJ 队线？我不好说。

似乎挺多人 day2 T1 挂成了 20 以下，为他们默哀。

Day 还是懒得算

高贵的「1/3 受限」。