联合省选 2022 没翻车记
联合省选 $2021$ 考场上，本人因为没有理解 $\text{ranklist}$ 一题的题意，导致至少失去了 $\mathcal{O}(n!)$ 的 $60\text{pts}$；$\text{dominator}$ 甚至因为心态崩掉，出现了爆零的情况，最后连公示都没上。
因此，对今年的省选，我其实是有很大期待的，我也想在省选公示上看到自己的名字，也想证明“看起来没有想象的难”。
高二赛季的 $\text{round 2}$，希望能实现愿望。
Day -Unknown
考完 $\text{WC}$ 后发现我这个赛季每场考试都是 $\text{HN-02}$，但是 $\text{HN-01}$ 一直在变（
虽然每次都觉得可惜，但是目前来看大考成绩还是较为稳定的，这是好的。
稍微计算了一下 $\text{NOIP}$ 的标准分，发现好像高达 $290+$，如果按照往年队线 $600/700$ 标准分，感觉省选只要考到 $0.6\ \text{z}\red{\text{xy}}$ 就行，所以心态稳健（
但是模拟赛被各种学校的超人疯狂爆锤。联考集团排名甚至进不了前 20 /kx。
Day -?
$\text{THUPC}$ 初赛，取了个队名叫 $\text{Surfing Online, Know All Things}$，中文叫“上网冲浪，什么都知道！”
灵感来源于不愿透露姓名的 $\text{i}\red{\text{odwad}}$ 的虎狼之词。
最后我实现了 $\text{ADEJ}$，贡献了 $13/23$ 个罚时 /kx。不过最后过了 $9$ 题，$\text{rank 30}$，应该是能进了。
又一次问了 $\text{i}\red{\text{odwad}}$ 伯努利数自然数等幂和相关的东西，本来准备写学习笔记，结果 $\text{i}\red{\text{odwad}}$ 说去年 $\text{m}\red{\text{entos}}$ 在同样的时间问过他同样的问题，写了个学习笔记，最后省选寄了（x）然后我就没写了
Day -20
是 $\text{NOI Online}$ 的日子。起床吃完早餐准备去学校，突然接到通知说今天不去了/xia，然后立马得知我校有老师确诊了/px。麻了，那我怎么省选啊/fn。
然后在家打 $\text{NOI Online}$，感觉开考之后脑子宕机了，很长时间没有任何靠谱的想法......于是最后只过了 $\text{T1, T2}$，$\text{T3}$ 补了个暴力。不过最后 T1 还 WA 了 20 分，不知道发生什么事了
然后得知 $\text{z}\red{\text{xy}}$ $\text{AK}$ 了，感觉有点厉害。
最后发成绩发现 $\text{Q}\red{\text{iuly}}$ 也 $\text{AK}$ 了，但是我甚至没上省队线/kx，感觉稍微有点麻烦（
Day -19 ~ -1
尝试 $\text{vp SDOI2018}$，发现上那年 $\text{SD}$ 队线有点难（
考前最后两场模拟赛，一场 $30/300$，一场 $230/300$，感觉波动有点大。不过 $\text{z}\red{\text{xy}}$ 感觉稳的飞起，加上省选 $70\%$ 的占比，感觉他翻盘没啥难度。
一直不能回学校，在家里其实还是没那味，感觉自己状态比较一般。后来得知我们还真参加联合省选，正好在我们解封之后 $\mathcal{O}(1)$ 天......
不过 $\text{l}\red{\text{k}}$ 和我分析了一下，感觉进省队并不难，一定程度缓解了焦虑。
每天都再说不能搞颓了再搞颓要寄了，但是还是忍不住搞颓的强烈欲望，3 周里我甚至看完了两部电视剧，同时追了一部综艺
Day 0
上午线上举办了动员大会，把四个集训队学长抓过来分享经验了，感觉大家讲的还是挺有用的。
有学长说：“你觉得省选会送你 $\text{50}$ 分他就真的送了你 $\text{50}$ 分，然后我就混进了 $\text{A}$ 队”，“我就是混子，我是混进集训队的”。在为大家放松心态方面很有用
然后廖哥分析了高一要多少分就能进队，发现好像他们要进队乃至 $\text{A}$ 队也并不困难，我的优势比我想象的要小多了，顿时就紧张了。
本来准备写板子的，但是颓意涌动，然后各种搞颓，到晚上才正儿八经写了几个板子。整个人非常非常紧张，我真的不敢想象如果进不了省队会怎么样......
收到了 $\text{Q}\red{\text{iuly}}$ 的加油，很感动/qq。
Day 1
早上按时到了，屈哥看起来被门卫拦住了（
走到考场楼的门口遇到了大部队，廖哥对我说：“那 $\text{cxy}$ 你只能 $\text{HN-03}$ 了，因为你来太晚了（”，我看着旁边的 $\text{z}\red{\text{xy}}$ 和 $\text{Z}\red{\text{cus}}$ 就知道他奶的都是谁了（x）
然后看到了 $\text{Q}\red{\text{iuly}}$ 和 $\text{z}\red{\text{hy12138}}$，大概率认出了 $\text{A}\red{\text{chtoria}}$，然后就进考场了。考完才知道右边是 $\text{E}\red{\text{ason\_AC}}$/bx/bx/bx，再右边是 $\text{Z}\red{\text{cus}}$。
把时间调早 $\text{5 min}$，配好 $\text{vimrc}$ 就开考了。
以为自己真的能像之前一直想象的那样气定神闲，但坐到考场上还是很紧张。
打开 $\text{pdf}$，看到 $\text{preprocessor}$ 的中文名就觉得大事不妙，发现还真 tm 是模拟，再看一眼样例，发现最大的样例 $n=8$，血压直接拉满。$\text{tree}$ 是计数，$\text{community}$ 看起来比较神秘，感觉很网络流。
仔细看了下 $\text{preprocessor}$ 觉得直接 map<string, string> 就能过，然后就先扔在那里去做 $\text{tree}$。
我猜测 $\text{tree}$ 应该还是一道送分题，毕竟今年不分 $\text{AB}$ 卷，还是比较有信心做出来的。
第一眼就看出来，首先是一个容斥，然后一条链的第一问是一个 $\mathcal{O}(n)$ 次多项式，那第二问也是。
然后以为暴力枚举两个点，然后暴力维护多项式就是 $\mathcal{O}(n^3)$，随便自然数等幂和一下貌似就行。
决定先搞定前两题，仔细编 $\text{tree}$ 的时候发现做法是 $\mathcal{O}(n^4)$，然后意识到可以枚举最小值，但是改成插值也没有优化。不过思考了一段时间之后发现枚举链可以改成换根 $\text{dp}$，这样就是 $\mathcal{O}(n^3)$ 了。
准备使用伯努利数来推自然数等幂和，我也不知道出于什么原因搁那推了 $>\text{30 min}$ 推不对/px，这种时候不知道为什么不立刻改成拉格朗日插值插系数，毕竟后面也要用。
此时觉得不行，先去把 $\text{preprocessor}$ 写了，发现 $\text{10 min}$ 就搞定了，造了几个数据都没啥大问题的样子 虽然心里还是虚得很，于是就接着回来 $\text{tree}$。
过了一年终于意识到推不出也无所谓，插出来就好了/qd。首先把插值部分全写好了，然后开始写换根 $\text{dp}$。
写好第一遍 $\text{DFS}$ 后发现第二问答案和我想象的不一样，回去看题发现第二问是“权值和的和”，而不是“权值乘积的和”。这时已经 $11:00$ 了，整个人顿时就僵住了，真的有了退役离我一步之遥的感受，为什么省选看错题啊......
不过幸好心态没完全崩掉，没过多久就发现这也是多项式了，把 $\text{dp}$ 改改就能一样做了。
写完大概到 $11:20$，直接过了三个样例，然后发现没有一个样例需要插值/qd，出题人你给个大样例会【数据删除】吗？？？
然后立马改出了一个暴力枚举最小值的 $\text{dp}$，拍上了。测测极限发现 $\text{8s}$，血压拉满。发现有一个地方我一直在快速幂算逆元，改成线性求逆元就 $\text{3s}$ 了，卡了一会卡进 $\text{2.5s}$，觉得考场 $\text{i3}$ 评测 $\text{i7}$ 应该问题不大，于是赶紧去 $\text{rush}$ $\text{community}$ 的暴力。
本来想贪一下多拿一点分的，然后就隐隐约约推出了网络流相关的一些东西，感觉时间也不太够了，于是写了 $\text{8pts}$ 就跑了。
接下来就在给 $\text{tree}$ 卡常，卡到后面觉得没啥可卡的了，并坚信他能过，检查检查文件就下考了。
出来估分是 $100+100+8=208$，感觉如果 $\text{tree}$ 确实是这个做法，那这个分应该不会非常低。听说同学们几乎都会 $\text{tree}$ 不过好像没几个人写出来了，$\text{z}\red{\text{xy}}$ 是 $170$ 分，突然感觉自己有了 $\text{30pts}$ 优势（x）
$\text{Z}\red{\text{cus}}$ 写了 $\text{7k}$ 最后调不出来改了暴力，$\text{i}\red{\text{odwad}}$ 考得也不太好......和 $\text{Q}\red{\text{iuly}}$ 对比了一下 $\text{tree}$ 发现我比他少个 $\log$，感觉应该还可以。
Day 1.5
回家之后吃了个饭，和父母聊了一会，觉得应该问题不大，明天稳点就行。然后就开始搞颓，搞了好一会听说 $\text{preprocessor}$ 出民间数据了，我拿到自己代码去测了一发，发现只有 $\text{20pts}$，不知道为啥心里没啥波动 可能是觉得就算我只有 20 分也问题不太大？
后来才知道是数据锅了，然后就过了，心态稳健。接着听说 $\text{z}\red{\text{xy}}$ $\text{preprocessor}$ 挂了，有可能被卡到 $\text{40pts}$，感觉有点恐怖。
然后突然记起来应该去自己电脑上测一下 $\text{tree}$，发现我 $\text{i9}$ 的电脑跑不进 $\text{2s}$！！！极限在 $\text{1.7s}$ 到 $\text{2.3s}$ 之间浮动，感觉寄了......可能只剩 $168$ 了，优势没了/px。
几个集训队学长来问我怎么样，我只能说“本来可以更高”（
晚上和 $\text{Z}\red{\text{cus}}$ 聊天，他也挂了分，和我说希望 $\text{Surfing Online, Know All Things}$ 能满编去打 $\text{THUPC}$，我说一定行。
晚上躺在床上，还是非常紧张，想着曾经几次 $\text{Day 2}$ 翻车的经历，真的没把握 $100\%$ 进队/px。
Day 2
早上准备出门之前心跳加速，深呼吸了很久才好一点......
到考场的时候大家都已经上去了，很快就进了考场。打开 down.zip 发现所有样例加起来不到 $250$ 字节/qd，我真的是无大语......
开考发现 $\text{card}$ 一看就很套路，$\text{bracket}$ 肯定要改成树来做，$\text{mis}$ 第一眼没有明确的想法。
回去 $\text{card}$，感觉根号分治之后随便搞搞的套路题，一开始以为最后复杂度里是 $2^{\omega(V)}$。本来以为需要 $\text{FMT}$，后来发现其实是容斥 $14$ 个小质数，复杂度是 $\mathcal{O}(2^{14}\sum c)$，算出来跑不过。
编了很久编不出一个更好的做法，有点小着急，脑子里“不会又 $\text{Day 2}$ 翻车吧”的想法挥之不去。听说这时我的叹气 $\text{z}\red{\text{xy}}$ 都能听到（
上个厕所回来决定还是先写吧，大不了 $85$ 也可以接受。写出来发现确实跑不过，甚至 $85$ 都有点难（。卡了一会感觉能过 $85$ 了，然后就先去 $\text{bracket}$。
转化了一下发现就是把一个点接到兄弟上，然后这个点的儿子也接到兄弟上。最后是要变成一条链，然后立马会了 $x=1,y=1$ 和 $x=0,y=1$。一开始我以为 $x=1,y=0$ 和 $x=0,y=1$ 是等价的，以为自己这么快就切了。
代码很好写，实现完之后发现过了后来下发的大样例，忍不住小声说了一句 $\text{Yes}$，据 $\text{Z}\red{\text{cus}}$ 说听的很清楚（
然后回去卡 $\text{card}$，通过一些奇怪的方法在本机卡到 $\text{1.2s}$，此时意识到 $x=1,y=0$ 并没有那么简单。于是拍上 $\text{card}$ 之后回去继续想 $\text{bracket}$。
编了很久感觉编不出来，于是开始乱搞（，花了巨大长时间写了个暴力，然后发现猜的贪心都过不了拍......
去赶了个 $\text{mis}$ 的 $\mathcal{O}(n!)$ 回来继续想。最后决定每层删最小值 / 次小值，感觉做不出来了于是每次按一定概率随机删（，能过 $n=9$ 的拍，感觉可能还可以，可能能过 $48$。
然后就下考了，估分是 $85+48+12=145$。出来听说 $\text{z}\red{\text{xy}}$ 过了 $\text{bracket}$，估计有 $200+$，肯定翻盘了。
非常佩服他，要是我 $\text{NOIP}$ 和 $\text{Day 1}$ 这样我绝对会寄，感觉十分大心脏。
但是其他同学看起来考得并不好......有点难过，下午的团建也没有去......
Day 2.5
下午和 $\text{i}\red{\text{odwad}}$ 打了一把 $\text{APEX}$，然后看了 省选前忍着没看的综艺。晚上底特律变人，感觉这个游戏真的很令人震撼 推荐给看到这里的各位
然后听说第二天要 $\text{whk}$，破大防。
$\text{l}\red{\text{k}}$，$\text{h}\red{\text{uhao}}$，$\text{s}\red{\text{kydogli}}$ 都来问情况，听他们说我感觉比较稳（x）
很晚的时候教练让我在小图灵上测一下几个同学，发现 $\text{Z}\red{\text{cus}}$ 和 $\text{i}\red{\text{odwad}}$ $\text{Day 2}$ 都挂惨了，可能进不了了......真的好难过/kk。
$\text{Z}\red{\text{cus}}$ 的 $\text{card}$ 爆零了，但是我能过的代码能和他拍上，研究了很久发现是他没有去重，希望最终数据没有重复元素吧拜托了！！！
$\text{b}\red{\text{igmurmur}}$ 有 $244$ 分，可能可以翻一点他 $\text{NOIP}$ 的劣势，能买到 $\text{C}$ 也行啊/ll/ll/ll。
我在小图灵上拿到了 $100+70+8+100+68+12=358$，感觉挺能接受的。听说 $\text{Q}\red{\text{iuly}}$ $\text{card}$ 也因为没去重而挂了很多分，希望没有重复元素。
Day 3
文化课精彩纷呈。
语文课讲古诗我竟然觉得很有意思？？？然后数学课上二项式定理坐大牢。下午物理课听天书，但是英语和生物还能听懂。
然后晚上听说第二天就回机房了/jy，于是鸽了所有文化作业，又玩了一晚上底特律变人。
Day 4
回机房了。还有 $\text{z}\red{\text{xy}}$ 和 $\text{D}\red{\text{eltax}}$，应该是比较稳的几个。
但是一整天都没搞学，一直在各种估计省队线、省队组成......希望我校能再进一个吧/kk。
一开始以为初三 $\text{lcm}$ 要进了，他 $\text{mis}$ 有多项式时间做法，感觉很有实力。
然后晚上 $6:00$ 数据就出来了！在几台电脑上测了一下，发现分数在 $322$ 到 $332$ 之间浮动，$\text{z}\red{\text{xy}}$ 稳定 $378$。
掐指一算发现如果我的省选分是 $332$，那标准分可以险胜 $\text{z}\red{\text{xy}}$ $1.5$（（，感觉有点刺激（bushi
晚上去剪了个头发，在外面吃了饭，回到机房成绩已经出来了。我是 $100+60+8+100+52+12=332$，是我想要的 NOIP 分数，那应该是没啥问题了。
但是 $\text{b}\red{\text{igmurmur}}$ 少了分，$\text{lcm}$ 可能也进不了了。不过 $\text{card}$ 没有重复元素！$\text{Z}\red{\text{cus}}$ 有机会了！
然后听说 $\text{Q}\red{\text{iuly}}$ 比我高 $4$ 分，下次再战！
然后就是等公示了。