NOIP2023

按惯例（似乎也没有）考前一周开始记。

没啥想发的牢骚，随便写点看看就行。

NOIp 完了会花比较久的时间补文化课，感觉也会写个日记。

11.11 Day -7

本来计划中是把之前的模拟赛拿出来重新想想的。

不过随机游走了一会回机房一看 qq 发现有 InfOJ NOIP 模拟。

感觉还是想找找感觉，还是打打比较好，一看怎么还要一个一个下题面和样例。

然后学校网速又不知道被哪个人给搞的巨慢无比，拿到题的时候已经八点五十多了。

开场一看 T1，欸这什么狗吧东西，好像不理解啊！！

看了 T2，T3，感觉困难，但 T3 有种熟悉的感觉，可以看一眼。

略微想一下感觉暂时不是很会，回去看 T1，看到这个 \(n < 64\) 脑海里突然回想起一句话：

有时候你看到 \(n \le 24\) 这样的数据范围，可以考虑是不是 \(O(n^6)\) dp 之类的东西，特别是某些 agc。

应该是 zjk 说的，但我找不到了。

只找到一个比较相近的聊天记录：

4182_543_731 2023/9/23 19:45:36
某些agc的"dp"题:

4182_543_731 2023/9/23 19:45:43
先推一车性质

Enonya 2023/9/23 19:45:52
我做过 n^13 的 atc dp 

4182_543_731 2023/9/23 19:46:00
结论:____________
这显然可以写成dp，所以

Enonya 2023/9/23 19:46:03
感觉不会有复杂度比这个逆天的。

4182_543_731 2023/9/23 19:46:06
Enonya  
    我做过 n^13 的 atc dp 
啥东西

4182_543_731 2023/9/23 19:46:09
我没做过。

4182_543_731 2023/9/23 19:46:13
只做过^6

然后稍微想了一下好像，额，随便枚举一下，随便设个状态，瞎转移一下就行了。

然后看 T2，感觉有点神秘，还是先做 T3 吧。

然后 T3 看到之后想了下暴力就是状压，之前好像见过一个 trick 可以把 \(msk\) 这一维度从 \(O(2^m)\) 变成 \(O(m)\) 的，然后想不起来咋回事。

思考了一下这个 trick 想表达的本质应该是不关心具体选哪些，换句话说就是只需要关心 \(|msk|\)，就又发现这显然有问题，比如某个节点 \(u\) 有两个子树，然后两个子树都是 \(x\) 种颜色，但是相互不同，于是肯定不能合并到 \(dp(u, x + 1)\) 之类的状态。

然后就不太懂了，过了一会好像理解了，憋出来一个 \(O(nm^2)\) 的唐氏做法。

大概就是合并子树然后枚举颜色重复了多少个，再转移。

然后就不会更优秀的做法了，本着开心的原则还是想把这个题弄懂，于是决定当成练习题做，找 kk 讨论了一会还是没啥头绪。

最后问了下 cftm 大神啊啊，发现我下意识以为这个状态是记不超过 \(i\) 种颜色，实际上题的限制是恰好。

去掉没有限制的部分，实际上是对于一个儿子 \(v\) 要从 \(m\) 种颜色里选恰好 \(f(v)\) 种，然后这样就是刚才上面说的问题，

然后就可以对这个进行二项式反演，或者说容斥，就考虑钦定有 \(k\) 种颜色不会被选，然后这个操作次数是 \(f(u) - \max\{f(v)\}\) 的。

大概就是一个 \(\log\) 的样子，然后感觉理解了就写了一下，submit。

吃饭之后发现好像这个做法复杂度也不对，操作次数还要乘上一个 \(deg\)，似乎是每个儿子都会做。

zhk 大神说这个和 UNR T1 差不多，把 \(f\) 相同的缩起来，就是根号的，感觉太有水平了呃呃，有点厉害啊啊。

T2 没想，感觉可能也不是很难，回家做一下得了，唉唉还有好多题没整理，无所谓，把手上的题弄清楚就行了。

哎麻了还想做一做棋盘游戏的来着，不过感觉也不是不行，csp 之后精神状态一直不太对，很久没花一两个小时一直推敲一个题了。

但感觉今天上午想 T3 做法那会挺放松的，感觉可能因为这是自愿打的吧（话说 NOIp 不也是我自愿打的吗）

哎我想吃 lgd 了。

感觉 infoj 这次模拟赛质量很高啊啊。

晚上狂暴炫了三个人的份量，感觉有点吃过头了。

11.12 Day -6

在家打摆，昨天吃太多后劲没缓过来。

但是中午外婆复刻了一波 KFC 全家桶，感觉远远胜于 KFC。

不得不继续开炫了，还有她是怎么想到把鸡胸肉码上奥尔良味的料烤了之后再炒成鱼香的？？？太他妈好吃了卧槽，鱼香 Plus+++。

哎，豌豆尖煮到耙豌豆汤里，感觉还是吃不腻的。。。

可能又干了一坤人的份量，弄了下 CF 那边的事情，好像是要选 pretest 了。

调了半天。

晚上回学校出去吃饭的时候接到了噩耗，我们 CF 的 D 和洛谷上正在进行的比赛重了。

G，看来 NOIp 之前是真出不出来了……不过也算好事吧，所幸 lgd 有备用 D 题。

晚上把新 D 题交给在机房里的两个 tester LGM_Joanna_ 和 Earthmessager。

他们想了想都会了，我中间和教练商谈了一会没来的及好好想，有点急，好像要被吊打了。

回来想了一会发现好像，也不是很难，想出来了。

晚上意外发现了【】的另一面，感觉很 h。

哎呀芥末味薯片就是好吃，感觉下周要开始戒了。

11.13 Day -5

不太懂，模拟赛昏昏欲睡，被绿题吊打了。

下午想了一下感觉都是简单题，不过总结的时候发现 B C 两个题可以看作是对之前总结的两个模型的补充：一个是满足一定条件之后才能贡献，一个是多限制耦合的更多条件。

放一下题解：

---

B:

这题乍一看是之前总结的那个，代价形如 \((r, q)\)，其中 \(r\) 为限制，\(q\) 为满足限制之后的贡献的模型。

以这个样子估计要贪心或者拓扑排序都不太行，毕竟有环。

如果直接暴力的话，对于每个节点要走出去计算答案，但可以发现这个东西显然是可以继承的，或者说存在子问题。

（之后打暴力遇到这样的情况就想想能不能做一个类似 dp 的东西，赛时没想这个一是昏了，二是没能写下具体要求的东西，搞混了定义）

不妨设 \(dp(u)\) 表示 \(u\) 出发的最小初始钱数，转移形如枚举 \(u\) 的每一条出边 \(u\to v\)，\(dp(u) \gets \max\{r_{(u, v)}, f_{v} - p_{(u, v)}\}\)

显然有环不能转移，想想怎么消除后效性，一个很容易注意到（一开始就能注意到）的想法是，要想走下去，肯定是走到一个环上，然后经过 \(r\) 最大的边的时候还能够走下去。

先把没法到环的找出来，去掉他们和它们的相关边，此时这些点的答案就确定了，一个很自然的想法是，通过所有确定答案的点来更新未被更新的节点（此时是在反图上）。

你发现一个边更新之后就没用了，可以发现这是一个类似拓扑排序的过程。

然后你发现因为有环，这不太是能直接拓扑的样子，我们需要把某些环直接断开，这对应着在某个环上找到一些当前可以确定答案的节点。

具体来说，利用刚才找到的性质，如果某个边更新一个节点，且这是这个环上的最大值，可以直接用 \(r\) 更新这个节点，然后删去，正确性显然，我们只需要保证每次选尽量大的边（对边按 \(r\) 排序，然后依次考虑每条边即可），这样对于多个环重合的情况也能解得正确答案。

于是重复这样的过程就能可以了。

C:

没读懂题，感觉还是挺好玩的。

意思是构造一个图，每个边有一个权值对 \((x, y)\)，要求 \(x + y = W\)。

然后，需要满足 \(i \to j\) 的路径中最小 \(x\) 的最大值为 \(B_{i,j}\)，\(y\) 的为 \(C_{i, j}\)。

这个，如果还记得 Kruskal 重构树的话就可以知道，对于一个 \(B\) 来说这样的图其实就是关于 \(x\) 的最大生成树。

但是这里有 \(C\) 的限制，注意到 \(x + y = W\) 所以我们可以把 \(C_{i, j}\) 的限制变为最大 \(W - x\) 的最小值，这就是最小生成树。

两边跑出来之后需要验证一下对不对，因为直接交起来可能会有矛盾，这个就用 Floyd 跑一下就好了。

然后记得去个重，这个题能直接并起来是因为，虽然生成树有多个，但是它们的作用等价，所以两边都可以看作严格的唯一情况，所以只要并起来有问题就是无解。

这对于多限制的题目算是一个补充了。

---

回去看了下 InfOJ 模拟赛 T3，想明白了一点小细节，大概就是分析到 \(O(n \sqrt n)\) 的部分，这个是看了下 UR26 的 T1 题解看懂的。

题解放送：

---

感觉是经典题目，之前见过类似的 Trick 不过没总结，可能那个题都直接没做。

考虑暴力的想法就是，直接设 \(dp(u, msk)\) 表示考虑 \(u\) 子树当中，选出颜色状态为 \(msk\) 的方案数。

首先这显然没法有很好的复杂度，考虑优化。（其次这个不能很好的表示恰好的限制。）

这种 \(O(2^m) \to O(m)\) 的过程基本都是考虑，我们可以不关心具体选了哪些，只关心选了的个数也就是 \(|msk|\)。

但是这样还是没法转移，因为你发现我们可能会算重，比如有两个子树，限制分别为 \(4, 5\)，然后合并到 \(u\)，你发现 \(u\) 子树内可能的颜色个数（不考虑 \(u\) 的限制的存在），应该是 \([\max\{f_{v}\},\min((\sum f_{v}) + 1, m)]\)。

一个比较笨的想法是直接类似树形背包把子树状态合并上来，合并的时候枚举算重多少个，但是这复杂度太高了我们不能接受，所以怎么办呢？

就，套路的考虑容斥，钦定出现 \(i\) 种颜色，假设 \(dp(u)\) 表示 \(u\) 子树内恰好有 \(f_{u}\) 种颜色的方案数。

\[ dp(u) = \sum\limits_{i = 0}^{f_{u}} (-1)^{f_{u} - i}\prod\limits_{v \in \text{son}(u)}^{}dp(v)\dbinom{i}{f_{v}} \]

复杂度 \(O(nm)\)。

考虑优化，注意到 \(i\) 有一部分是不会做贡献的，因为组合数的存在，所以我们直接从 \(f\) 最大的儿子开始枚举，这个可以看作重儿子，于是这形如轻儿子之和。

但是这还不太对，会有相同的 \(f\) 存在，我们需要合并，然后可以快速幂计算代价，这样复杂度就是 \(O(n\sqrt n)\) 的，可以看 UR #26 石子合并的题解。

对于 \(f_{i} = -1\) 的情况，我们把他的子节点全部合并到他的父节点下就可以了。

---

感觉还是挺有意思的。

突然发现其实还是会不少东西的。

不过好像不用刻意放大差距，也别太懊悔了？

11.14 Day -4

好像是头一次 NOIp 模拟赛能会 300pts。

但是哈哈了：

感觉没干什么事情几乎，下午去打球的时候遇到几个萌新来拼场，后面遇到砸场的好像还护下来了。

感觉，已经不会过人了，只能晃飞萌新的 Crossover 算什么啊，是不是个子太高重心下不去。

但感觉其实是基本功已经忘完了，之后是不是该加训了。

11.15 Day -3

感觉今天一整天几乎丧失了做题欲望，本来打算的是要复习一下之前的题，但是完全没法静下来想题。

上午前两个小时在和 EarthMessager 研究 Terminal Color 的一个小问题，最终还是找到了解决方案：link

下午浑浑噩噩的，打不起精神，出去吃了个饭回来还是这个样子，lgd 说提不起劲大概可以写写代码，也不错啊。

周五之前应该把 JOISC2016 弄完，有些贪心的小模型，比如构造答案下界什么的也许需要整理一下，然后还有最近模拟赛的 trick 整理。

周五是复习板子和看看以前做过的题，如果可以的话做一下喵了个喵吧。

7：20 要去教室签到啊啊啊啊，不要忘了，感觉芙莉莲的 op 很好听。

晚上和 lgd 稍微讨论了一下好像就会了，没那么自闭了。

11.16 Day -2

好吧，上午又忘记去班上签到了。

我不知道模拟赛啥难度啊，但是我想了半天不会 T1 给我干破防了。

T2 也没想明白，只能 submit 了，加上我其实本来也不咋想打。

但可能，也不是坏事，还没考完的这会就可以无打扰的好好想一想要做的准备，之前让我比较难受的一些细节问题。

从环境上来说，应该适应一下 Vim 8.0，并且大括号补全之后它和 9.0 不太一样，似乎不太会自动缩进，可能需要调整下 vimrc，不然到时候考场打 tab 又难受，打断思路也是一个（update: 找到原因了，是 cindent 的问题）

然后还有就是配色，之前用的 zellner 看着有点亮了，现在换成 desert。

如果七中高新那个键盘实在拿不上来，那就往后坐一点，不要对于键盘想这想那。

然后是时间把控和开场心态，开场应该是不让动键鼠的，写 vimrc 大概需要花我 1~2 min，然后打好 template.cpp 需要 2min，记得 map 一下快捷键，解压文件的话记得保留压缩包。

这 5min 左右的时间不需要太着急，别人开写了也不要管，刚开始这一会心态稳不住可能会浪费之后的时间。

策略是先打 T1，T1 打完了把三个题暴力打了，看一下哪一个比较可做，然后多冲一点性质。

也可能存在卡 T1 的情况，不排除这样的可能，虽然要相信 T1 是简单的，但是不能说在卡题的时候因为“这是简单题，做不出来就完了”的想法紧张。

总会有人挂分，实在不行先把一部分拿了也好，可能做好一切要拿 NOIP 2= 的准备，做题的时候能稍微自如一点，也能更享受比赛一些。

T1 卡题有可能是因为题读错了，理解错了题意，所以 T1 做的时候应该把详细的步骤写下来，多开一个 vim 窗口用来写 md，最好不要 split，有点影响观感。

不要以做出 T1 为目标，如果很快做出了 T1 也不要慌，觉得题简单别人肯定都拿了，显然总会有卡 T1 的人存在，只是看不到罢了。

从预估来看 T1 可能是一个小模拟/贪心/dp，可能第一眼看着会比较显然，但别着急做，多分析一下特殊情况，卡一下答案的下界和上界。

而且如果真分析出了有问题的特殊情况是好事，越早越好，就算发现做法有问题了也别急，应该先考虑一下这个问题可不可能出现，考虑的时候有没有漏了什么限制。

然后耐心的复盘一下，到底是哪里出现了问题？修正问题的时候可能需要抛弃之前的一些想法，但具体在哪里抛弃也是一个未知的东西，所以从头开始梳理。

但梳理的时候很容易直接按着之前的想法又一次回来，然后什么收获都没有，分析的话仍然是考虑构造上下界，考虑极端情况（链、菊花、相同颜色全部放一起）。

再具体的就要依赖总结的模型了，至于做出 T1 之后，对于后面的题应该怎么办，先尝试划分难度，然后把它当成新的 T1 做就行。

再有就是考前应该做的事情，首先是应该把自己做过的模拟赛题至少先全部看一遍，不会做的要搞明白，然后总结好各种模型，尤其对于基本的贪心啊，dp 啊什么，很多时候会做为转化的第一步，总结一些通用的想法，也会对考试时有所启发。

只要清楚的知道，考前所做的事情基本是很好的做到了的，考试的时候慌张就会少那么一分。

还有，应该调整一下作息，多睡一会，保证八点半的时候基本是清醒的，中间也不会犯困。说到这里，感觉坐姿其实对考场发困有很大的影响，如果埋的太下去很容易就困了。

如果和物体的交互多，一般也不会特别困，然后因为要到中午，水肯定要带，在考场外可能去买个三明治什么的放旁边。

---

下午还是挺摆的，感觉在机房里静不下来（都在 AC Saber 打板子）。

所以七点多的时候拿了东西，配好了临时环境去久违的地方做喵了个喵，算是了结当年的痛吧。

那台机子还是 Win11，就当熟悉环境了。

想了一会，前面还是比较好的践行了上面说的东西。确实有果断放弃思路了。

最后想不出来观察了数据范围，最后就有了想法，明天来补一个题解。

JOISC 就先放下吧，明天当务之急是复习。

继续和 lgd 聊一些共同遇到的问题，感觉怎么，lgd 也很在意 noip 的那个“结果”啊（虽然是不是大部分人都这样来着）。

感觉要思考的问题，其实很明了，最主要是咋去解决它，这大概就是前几天鲜花写的内容了。

就其实，卡住的时候真的，因为陷于一个不知道自己能不能做出来的状态，难免会怀疑，会焦虑。

但等到时候复盘，别人说做法的时候，又会觉得这很简单，这其实也可以归结为高估自己水平吧。

哎呀我在写什么呢，好像也不知道自己在写什么了，先这样吧，感觉可以把一些聊天中提到的问题提出来。

11.17 Day -1

咦？怎么就最后一天了，好像对我来说没有什么感觉。

可能就是有点困，所以我选择在办公室睡到了九点钟。

昨晚聊了很多，不过其实最后得出的结论和讨论前一模一样，草。

但是【】怎么又来【】这种东西，快给我整受不了了。

感觉今天反而很快乐，坐在机房格外舒服，因为少见的坐直了吧。

也不一定，可能就是我本人心情比较好，但是我想躺在温柔的大姐姐腿上睡觉呜呜。

以上是本人今天上午九点半以前的状态，从表情到动作几乎完全一致。

不懂啊，怎么感觉自己的心态好像突然就变成那种，平静，享受每一天的感觉了。

咋回事呢，我记得我考前一天都是苦大仇深的，怕这个怕那个的，今天这种感觉不这么强烈了，几乎可以说是聊胜于无。

但是我现在都还没开始复习啊（）

还是做点事情，放一下喵了个喵题解，因为找不到合适的地方放了。

题解：

手玩几个样例，觉得最重要的一点是考虑两个被消除的元素之前有什么关系。

一开始是想的它们对中间夹着的部分会有什么影响，发现这个限制太宽泛了。

但是注意到这个 \(k = (2n - 2), (2n - 1)\)。

这似乎是在提示我们什么，先考虑 \(2n - 2\)，实际上启发我们可以每个堆里面放两个，然后这样空出来的一个堆就有用了。

对于新加入的一个牌 \(x\)，记录一下这个种类的元素上一次出现的位置，如果在顶部就直接拉过去删掉，不然就用空出来的堆删掉。

然后考虑 \(2n - 1\) 怎么做，这样的话极端情况是，\(n - 1\) 个堆里面都有两种不同卡牌，然后又来一个新的种类。

假设这个新来的为 \(new\)，我们考虑一下这个 \(new\) 应该怎么放。

一种想法是考察下一次出现时间，因为我们有可能要让 \(new\) 占用这个空出来的堆一会。

考虑所有 \(n - 1\) 个堆当中，栈底下一次出现最早的元素 \(e\)，如果 \(new\) 下一次出现比 \(e\) 早，那就把 \(new\) 放到空堆里就行（虽然现在不是空的了，但我们还是称它为空堆），因为其他的，在栈顶就能解决，栈底的话这样 \(new\) 也不会因为占用空堆给操作带来什么影响。

考虑 \(new\) 的下一次出现晚于 \(e\) 的情况，此时应该把 \(new\) 放到这个堆上面，因为 \(e\) 会被更早的消除，所以这个堆会变回两个卡牌的情况。

但是呢，这要求 \(e\) 所在堆的栈顶 \(t\) 下一次出现时间不早于 \(e\)，不然 \(v\) 就消不掉了。

如果不是的话，我们考虑怎么办，此时其实 \(e,t\) 所在的堆可以被当作空堆的作用看待，于是我们把 \(new\) 放进原先的空堆，标记 \(e,t\) 所在的堆为新的空堆就行了！！

唉唉，355 天过去了，有种直面恐惧亲手了结它的快乐。

晚上在家简单收拾了一下，调了下 vim 配置，默写了两遍 _vimrc。

然后打板子，感觉就 Tarjan，欧拉回路，虚树，圆方树，树剖，fhq，数学相关，树分治。

Tarjan SCC 倒是没啥，主要是点双和边双。

边双要稍微简单一点，判定条件是 \(dfn(u) < low[v]\)（并且是在 !dfn[v] 里面更新），那么 \((u, v)\) 就是桥边。

然后更新 low, low dfn 的时候需要考虑到进来的那条边的影响，所以需要满足 (i ^ 1) != in_edge。

然后点双要麻烦一点，判定条件是 \(\le\)，也是在里面更新，但是不需要记录 instack 了。

但是根节点需要满足两次判定条件，弹栈的时候只能弹到 v, u 记得要放进去。

孤立点（为根且 deg = 0）也需要额外判断，但是不管是不是割点，满足了条件就要弹栈。

void tarjan(int u) {
    s.push(u);
    dfn[u] = low[u] = ++tim;

    if(u == root && head[u] == -1) {
        vdcc[++cnt].push_back(u); return;
    }

    int flag = 0;
    for(int i = head[u]; ~i; i = e[i].Next) {
        int v = e[i].ver;
        if(!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
            if(dfn[u] <= low[v]) {
                ++flag;
                if(u == root || flag >= 2) {
                    cut[u] = true;
                }
                int x; ++cnt;
                do {
                    x = s.top(), s.pop();
                    vdcc[cnt].push_back(x), c[x] = cnt; 
                } while(x != v);
                vdcc[cnt].push_back(u);
            }
        }
        else low[u] = min(low[u], dfn[v]);
    }
}

圆方树也是这个板子，但是不需要割点，自然也不需要特判，直接加边就行。

树剖的话就记得先 dfs 重儿子维持重链性质，操作一般是通过 dfn 性质和跳重链整体处理就行。

轻儿子将会作为重链的顶端，树根也是重链顶端。

if(hson[u] == -1) return;
dfs2(hson[u], tp);

for(int i = head[u]; ~i; i = e[i].Next) {
    int v = e[i].ver;
    if(v == fat[u] || v == hson[u]) continue;
    dfs2(v, v);
}

线性筛是标记最小质因子 \(pri(j)\) 来着，乘法逆元是 inv[i] = (mod - mod / i) * inv[mod % i]。

void sieve(int n) {
    for(int i = 2; i <= n; ++i) {
        if(!vis[i]) {
            vis[i] = i;
            pri[++m] = i;
        }
        for(int j = 1; j <= m; ++j) {
            if(pri[j] > vis[i] || i * pri[j] > n) break;
            vis[i * pri[j]] = pri[j];
        }
    }
}

虚树懒得背板子就记得把关键点拿出来排序，两两求 LCA 就行。

感觉平衡树不太想看了，树分治主要是注意处理跨越的贡献的时候不要越界。

KMP 是每次尝试匹配 \(s(i), s(j + 1)\)，不匹配就跳 Next。

直到匹配，然后记录 Next(i)：

nxt[1] = 0;
for(int i = 2, j = 0; i <= n; ++i) {
    while(j > 0 && s[i] != s[j + 1]) j = nxt[j];
    if(s[i] == s[j + 1]) j += 1;
    nxt[i] = j;
}

nxt 记录的是 LBorder。

睡了，明天最重要的是复盘一下策略和 tricks，具体题目本身过一下就行。

欧拉回路早上再看吧。

11.18 Day 0

考完过后和 lgd 聊了一会。

睡了一觉起来，发现自己似乎不再是 OIer 了。

最终因为考场心态挂掉，从各种角度上来说其实挺不甘心的。

明明考前思考了那么多，几乎是做好了一切的准备。

但是，已经这样了，能改变什么呢，csp 和 noip 两套相对简单的题目都没能抓住机会。

也不能怨谁怪谁了，五年的 OI 以这样的方式结束，感觉及其荒唐。

好吧，认命了，我以为打好暴力就行了，唉，谁知道出成这个难度呢，技不如人，甘拜下风。

高考再见了！

---

最后更新: November 19, 2023