【做题记录】NOI 题选做 / 部分扯淡
honglan0301
·
·
个人记录
距 NOI 2024 还有 30 天。
以前是听传奇故事的吃瓜群众，现在终于快到了自己亲自写故事的时候，难免有些感慨。
从现实走进故事总是如同在平面上观察投影，突出一个管中窥天。于主人公而言的全部世界，终究也只能成为一眼就能望尽的“事实”，而那些一个人的回忆再不会有了。
不过也有时候，比如现在，我觉得这种收束是优雅的。留在这里的可以是“匿名用户”，可以是“honglan0301”，但最好不要是我。所谓“至人无己，神人无功，圣人无名”何尝不是一种美妙的妥协，没有人能活在各种事迹里。
话说回来，到目前为止，我自己 NOI2006\~NOI2023 还有 78 道题没有做，希望一个月后这个数字能变得更小一些。
NOI 2006
？这场怎么只有五个题？这些东西也能叫题？？？？？
1. P4252 [NOI2006] 聪明的导游 √
无向图找最长简单路径，还是提交答案。
显然这个没法做，我们直接上乱搞。
考虑多次重复执行 ucup3 stage1 G 的 随机扩展算法，由于这题并不保证图随机，当多次卡在一个点附近时我们需要按一定概率调整路径/回溯。这样能够通过测试点 1\~6,9\~10，并在 #3 吊打 std，但在 7~8 两个存在哈密顿路径的图上表现不太好。
然后我尝试进行调参，跑十分钟通过了 #8。
然后考虑到找哈密顿路径还有一种“邓老师调整法”，我根据数据特点稍微魔改了一部分，挂了三小时后终于跑出了 #7 的答案。
我现在还不太懂题解为啥跑得那么快，调整不是应该严格强于搜 dfs 树吗？我按度数加权之后为什么反而效率慢了很多，晕。
2. P2703 [NOI2006] 千年虫 ×
说实话我看不懂这题在说什么。有空再补。
3. P4204 [NOI2006] 神奇口袋 √
感性理解一下，随机抽几个球并不会改变下一次抽到某个球的概率，这从归纳的角度也很好证明。
那么当然，钦定某次选一个球+再随机抽几个球 与 钦定某次选一个球 也没有区别，于是只需求 \prod\limits_{i=1}^n (a_{y_i}+d\sum\limits_{j<i} [y_j=y_i])/(\sum a+d(i-1))，使用低精乘高精的模拟即可。
时间复杂度 O(n^2d)。
这个结论确实还是很酷的。
4. P4297 [NOI2006] 网络收费 √
最像题的一道题。
首先观察到 付费系数 k 可以由 O(n^2) 个点对贡献拆成 O(n\log n) 个直上直下的贡献，即我们只关心每个点与其每个祖先子树内部的众数是否相同。
然后就可以简单 dp，为了方便算贡献，我们需要钦定每个祖先子树的众数分别是什么，记 f_{i,j,S} 表示 i 子树，cnt_1=j，dep_i 个祖先的子树众数（状压）为 S 的最小代价，那么有简单转移：
f_{i,j,S}=\min \{f_{ls_i,j',2S+[j>sz_i/2]}+ f_{rs_i,j-j',2S+[j>sz_i/2]}\}
状态数量是 \sum 2^i2^i2^{n-i}=O(2^{2n})。
转移的总复杂度 \sum 2^i2^i2^{n-i}2^{n-i}=O(2^{2n}n)，可以通过。
5. P4174 [NOI2006] 最大获利 √
【模板】最小割。
NOI 2007
1. P2099 [NOI2007] 调兵遣将 ×
毒瘤提答，不能要了。
2. P2892 [NOI2007] 追捕盗贼 ×
毒瘤提答，但我可以（点分+搜重链）骗分。
3. P2047 [NOI2007] 社交网络 √
弱智题，也不讲了。
4. P4027 [NOI2007] 货币兑换 (√)
开小号做题有个好处是，当你不会做以前过掉的题时，你会非常开心破防。
我猜测买卖都只会选择 100\%，这确实很有道理，但是我想半天不会证，好奇我以前怎么想的？
然后就是斜率优化 dp，可以使用万能工具李超树。
5. P4130 [NOI2007] 项链工厂 √
暴力上 fhq，区间翻转+区间推平+swap/shift+维护可合并信息都是板子。
但我每次写平衡树都要调很久。比如你知道吗，merge(rs(p),q)/merge(p,ls(q)) 里面的顺序不能写反；不能对 0 节点进行赋值；当你合并首尾时要判它们是否已经在同一段里。
6. P2109 [NOI2007] 生成树计数 √
放到现在非常套路了。
实现时要注意，连通块必须是树，且转移必须合法（即 $i-k$ 不能被孤立）。
## NOI 2008
-最近心态很浮躁啊，对接下来的一个月还是恐惧大过期待。
-找到一个很好听的钢琴版 Get Over，是八年前发在 youtube 上的，那个博主前后发过三个版本，但貌似第一版最有味道。试图单曲循环找一些纯粹的感觉，不过没有成功。试图复健钢琴，笨得快把自己气笑了，遂开摆。
### 1. P5699 [NOI2008] 赛程安排 ×
又是提答。本来以为没那么毒瘤，但 #8\~#10 毛都跑不出来，弃疗。
### 2. P3980 [NOI2008] 志愿者招募 (√)
【模板】上下界费用流
### 3. P4201 [NOI2008] 设计路线 √
经典树形 DP。
记公路边权为 $1$，铁路边权为 $0$。则 dp 时只需记录当前节点 $i$ 在子树里挂了 $j\in\{0,1,2\}$ 条铁路链，子树内最大深度 $p\in [0,\log n]$ 的方案数。
前缀和优化后时间复杂度 $O(n\log n)$，我懒了，写的纯暴力 $O(n\log^2 n)$。
### 4. P1477 [NOI2008] 假面舞会 √
一条信息可以类似差分约束地看作在模意义下有 $(u,v,1)$ 和 $(v,u,-1)$ 两条边。那么显然地，种类数需要是环长 $\gcd$ 的约数，求环长 $\gcd$ 是经典问题，在我 [去年的博客里](https://www.luogu.com.cn/article/jniq2cmy) 有写到。
注意要特判 $\gcd=0$ 的情况，此时由于要求每类不能为空，需要求出每个连通分量的最长（长度绝对值最大）路径。由于此时 $dep_u+w-dep_v=0$ 恒成立，可以一遍 dfs 解决（$\max \{dep\}-\min\{dep\}$）。
### 5. P4202 [NOI2008] 奥运物流 √
首先显然整张图是一棵内向基环树。
先对确定形态的图算答案。位于环外的节点可以简单考虑，把它们的 $c_i$ 按照 $k^{dep_i}$ 的比例加到 $c_{root_i}$ 上；然后剩下一个环，不妨假设节点依次为 $1\sim n$，那么你在 $1$ 节点处对其断环成链，得到要求 $R_1=c_1+\sum\limits_{0<i<len} c_{len-i}k^i+R_1k^{len}$，即 $R_1=\sum c_{len-i}k^i/(1-k^{len})$。
那么显然地，每次操作都是选一个节点挂到 $1$ 上面（否则调整后严格更优）。
那么枚举环长，然后断开 $(1,s_1)$ 做树上 DP 即可。你只需要钦定每个节点的深度和其子树内使用的操作次数，总时间复杂度 $O(len\times n^4)=O(n^5)$，可以通过。
### 6. P4203 [NOI2008] 糖果雨 √
好像很简单，是我理解错了吗。
注意到每朵云的运动周期都相等，那么可以把插入映射到 $T=0$ 上，然后它的贡献应该分成 $O(1)$ 段，是好处理的。
然后应该就是拼两个三维~~数颜色~~数点（\*数据保证任何时刻不会出现两片颜色相同的云朵，oonp，被这个卡了一百年），但我发现自己不会写 cdq 分治，先鸽了。
学习了 cdq 套 cdq，我的做法有点麻烦，要跑两次 6e5 个点的三维数点，又卡了一百年常才过。总计耗时两百年。
## NOI 2009
-年初有个很想写的书评，一直鸽到现在。
-刚才尝试回忆我当时有什么感想，发现不太记得了，于是重新编了一些，但又没写完啊啊啊。
### 1. P1963 [NOI2009] 变换序列 √
时代在变化.jpg
去年省选 D2T2 我想了一整场的网络流，然后只有四十多分，然后我在这里看到了 $O(n^2)$ 能过的基环树题。。
显然是“每个左部点匹配 1 或 2 个右部点”的二分图匹配最优化，对这两个点连边（或者对一个点连自环），如果图不是基环树森林必然无解，否则树边的定向已被确定，环边有两种定向方式，枚举一下即可。
### 2. P1864 [NOI2009] 二叉查找树 √
时代在变化.jpg
这是 PKUWC 套路超级弱化版吗。
进行一点离散化，显然只有 $\bigcup [val_i-n,val_i]$ 这 $O(n^2)$ 个数有用，然后对笛卡尔树形态进行区间 DP，时间复杂度 $O(n^5)$，我觉得能过。
### 3. P1758 [NOI2009] 管道取珠 √
关于平方的计数有常见套路，变成计数“选两个操作序列，使得输出相同”的方案数，有简单 $O((n+m)nm)$ DP。
### 4. P1756 [NOI2009] 描边 ×
计算几何提答，honglan0301 不假思索地投降了。
### 5. P1912 [NOI2009] 诗人小G ×
实话讲我忘记决策单调性怎么优化了，于是重学了一遍二分队列。
### 6. P2805 [NOI2009] 植物大战僵尸 √
先把环全删掉，然后变成了【模板】最大权闭合子图。
## NOI 2010
这场没有训练价值啊，提答+插头 dp+四个做过的题。
## NOI 2011
-最近训练了高一生物&地理，感觉我要拿下学考了！！1
-和教练说了高二不再打 OI，很感谢可亲可敬的叶师傅没有劝我！以及再次找 wzp 校长谈了转班的事，这次得到的回复是打完 NOI 之后会考虑处理，我先感恩一下！大概很快就能从 zp 润走啦[欢呼][欢呼][欢呼][欢呼][欢呼]
### 1. P2052 [NOI2011] 道路修建 √
NOI 出黄题是几个意思。在搞笑吗。
### 2. P2414 [NOI2011] 阿狸的打字机 √
非常模板的 ACAM 题。离线到 fail 树上随便搞搞。
### 3. P1973 [NOI2011] NOI 嘉年华 √
做起来有点像 AGC012E。
首先不难发现一个合法的方案其实只要求你对时间轴做划分，两边的“活动数量”分别是编号为奇数/偶数的段的权值和。同样不难发现“钦定第 $i$ 个活动必选”意味着在 $(s_i,t_i)$ 之间没有断点。
那么不难对前后缀分别做 dp，然后枚举完全包含 $[s_i,t_i]$ 的那个区间，这样复杂度是 $O(n^4)$，然而我写完直接就过了。。。
想优化也非常简单。注意到枚举中间区间的贡献类似于 $h_{i,j}=\max\{f_{i,k_1}+f_{j,k_2}+val(i,j),k_1+k_2\}$，当 $i$ 与 $k_1$ 固定时，$k_2$ 必定随 $j$ 的增大而单调不降，双指针即可做到 $O(n^3)$。
### 4. P2020 [NOI2011] 兔农 ×
暴力有 75pts，但感觉正解有点难的，看了题解。
容易发现你只关心 $[(f_{i-2}+f_{i-1})\bmod k=1]$ 这个 01 序列的情况。
由于模意义下斐波那契数列的循环节在 $O(mod)$ 级别，我首先猜测在 $O(k)$ 的范围内一定会出现循环节，但是不对。
这时题解告诉我，你需要注意到可以给序列在每个 $[(f_{i-2}+f_{i-1})\bmod k=1]$ 处分段，那么每段都形如 $x,x,2x,3x,5x,\dots$，这时再套斐波那契循环节的结论即可求出断点——序列要么在某段内部无限循环，要么有一个 $O(k)$ 段的循环节。
那么最后求 $f_{n}\bmod p$ 用矩阵快速幂即可，复杂度在 $O(k\log n)$ 级别。
### 5. P1995 [NOI2011] 智能车比赛 √
以为是 nb 计算几何，实际上是弱智题。
你发现他基本完全等价于联考搬过的【P2452 [SDOI2005] 屠龙传说-屠龙枪卷】，那么做完了。
具体地，在那题里你显然能发现只有内外公切线/点到圆的切线/点到点的线段/圆弧有用；本题里你也一样能发现只有“相邻两矩形重叠在一起的边”的端点有用，并且要好写得多，只需要判每条线段是否被矩形框包含，枚举横坐标后即限制斜率在某区间内，能够简单维护。
起点/终点处可能有直上直下的线段，需要做特判。
### 6. P1971 [NOI2011] 兔兔与蛋蛋游戏 √
你发现网格图（二分图）上只有偶环，因此空格不会重复到达任意一个位置。
于是你不考虑必然无法被到达的格子（黑白染色），问题变为在剩余二分图上做“二分图博弈”。某次 ucup 上 xsap 教过我结论是“当且仅当初始位置是最大匹配必经点时，先手必胜”，那么跑 $k$ 次网络流即可。
本来以为需要利用相邻两次局面差距不大的特点跑退流，但是直接写 $O(k(nm)^{3/2})$ 就过了。
## NOI 2012~2016
要做不完了，暂时先跳过
## NOI 2017
做锤子。
开 始 做 梦。