NOI 真题模拟

$\text{NOI2022}$ 加油！

06.21 : NOI2016 Day 1

期望：$100+?+100=200+?$。
实际：$95+60+92=247$。

总结

$\mathtt{A}$

不能默写 SA，没有测极限，被卡常。

$\mathtt{B}$

一开始以为可以使用平面图欧拉定理来判断联通块个数。但是实际上可能比较困难：问题在于，在一般的计算中，所有的 $\text{face}$ 都是四元环。但是如果存在空腔，那么 $\text{face}$ 就比较难算了（可能是很大的环）。

[APIO2017]斑斓之地 能做的原因是黑色是联通的，所以只有在完全包含黑色的时候，才会出现一个空腔。

使用欧拉定理是尝试将网格图转变为单纯的数值，从而简化问题；但是另一种思路是建图（虽然可能丢失网格图的特殊性质，但是可能更容易使用图论工具），然后就直接是找到原图的割点了。

应该怎么想到呢？如果在想部分分的时候，能够把整张图的四联通连边都建立出来，应该就能想到了吧......

在考虑可能的位置时，很快就想到了拉出黑点边上的白点。但是在判断是否是 $0$ 的时候却没有想到可以拉出附近的白点/yun。

不会写割点.jpg

$\mathtt{C}$

在推的过程中，遇到一步：

找到所有 $j\in [1,m]$，满足存在一个 $p$ 使得 $j|(k^p-1)$。

最后结论是 $gcd(j,k)=1$ 即可。这就相当于存在一个 $p$ 使得 $k^p\equiv 1(\mathrm{mod}j)$。明显需要 $j,k$ 互质。

06.23 : NOI2016 Day 2

期望：$100+60+81=241$。
实际：$100+60+81=241$。

总结

$\mathtt{A}$

之前就做过的题。感觉和我的脑回路比较不同，我每次做这题第一步都要先枚举区间交点！！！

但是，注意到答案只和最长、最短区间的长度有关，所以暴力的话枚举两个区间的长度，然后判断是否存在合法的交点看起来更为合理。由于只要有一个交点就好了，所以可以线段树维护每个点被覆盖几次，然后双指针。

$\mathtt{B}$

比较可惜的题......考场上大概按顺序想到：

1. $1$ 每次都在集合中。
2. 一个点至多被用一次。
3. 次数够用的时候，从小到大依次选择每一个和 $1$ 操作是最优的。
4. 猜想 $>2$ 的集合至多只有 $1$ 个。

而且推出了变换的那个式子，如果观察每次集合大小 $c_i$ 的序列，大概可以发现一个数字最后的贡献形如 $c_i$ 的前缀乘积。因此一个越大的数字，越往后放越好，如果 $x>y$ 但 $y$ 选上了 $x$ 没有，把 $y$ 换成 $x$ 更优。

然后就能得到：肯定是对排序后的一个后缀操作，将这个后缀划分成若干区间依次合并。后来的 $\text{dp}$ 并不困难，但这里可能是比较少见的，将优化 $\text{dp}$ 看作最优化直线的斜率（感觉一般是截距？）。然后在维护凸壳的时候想错了弹出方向，然后就只能写暴力的 $\text{60pts}$ 了。

最后的正解比较神奇，但和我的猜想比较类似。$>2$ 的集合至多只有 $\log$ 个。之前模拟赛已经见过一次了，既然斜率优化之后都只能优化到 $\mathcal{O}(nkp)$，状态数都有 $\mathcal{O}(nk)$，所以肯定有神秘性质！感觉这时候分段题直接猜测段数不多就行了！！！

$\mathtt{C}$

哈哈，$\text{huhao}$ 之前讲过。但是我只记得他是咋做第 $3$ 个点的了，然后靠着这个优势在 $\text{2.5h}$ 里玩出了 $\text{81pts}$ 之多！！！感觉非常划算！！！

感觉提交答案题就是时间换分数，如果做到一定程度感觉瓶颈了，就赶紧去别的题吧（当然是在保证拿到所有弱智分之后）

06.28 : NOI2017 Day 1

期望：$100+100+100=300$。
实际：$100+100+100=300$。

总结

笑拉了，要是 $\text{Day 1}$ 真这个分，那年 $\text{Day 2}$ 只要 $38$ 分就可以进队！睡觉都能进！！！

$\mathtt{A}$

本场最难题

明显是拿个什么东西模拟进位。一开始的想法是开那么多个 $\text{bit}$ 然后大力维护，这样复杂度里有个 $30$，不太好。但是他都告诉你是 $30$ 了，一看就要压位！然后就每位保存 $2^{30}$ 就行了。

很长一段时间明明脑子里想着线段树，但是一直在考虑加法的过程中均摊（甚至没意识到有减法！）。想了一年才发现如果只有加法那甚至不用线段树。但是如果有减法的话，二分找可以进位/借位的地方就比较明显了。

$\mathtt{B}$

不知道为啥这种垃圾题会出现在 NOI！

感觉就算没算出来复杂度，写个没有脑子的暴力也能直接过啊！

显然每次接上两段的时候，把经过端点的长度不超过 $k$ 的大力更新到哈希表上就行了！断开直接删掉就行了。这样看起来是 $\mathcal{O}(n{k}^2)$ 的，但是你看那个 $c\le {10}^3$ 非常迷惑啊！为什么会有这样一个条件呢！

尝试考虑一下以某一个点开头的区间个数，你发现只有 $k$ 个啊！所以你至多只会更新 $\mathcal{O}(nk)$ 次啊！然后你只要定义一个点的势能是，这个点到末尾的距离，和 $50$ 取 $min$ 就行了。每次断开只会增加 $k^2$ 级别的势能，然后就能过了！

$\mathtt{C}$

比想象的要简单一点！

$\text{dp}$ 最重要的就是转移的阶段。

首先恰好为 $k$ 不太好算，转变成“最大面积 $\le k$”减去“最大面积 $\le k-1$”，这样就只要保证每个矩形大小都 $\le k$ 了。

一开始以为只要对最低一层的情况 $\text{dp}$，一个矩形里不能都没有障碍就行了。没想到可能存在一个障碍在中间，两边很高都没有障碍然后爆掉。

然后就在想，如果给定一张图，怎么算最大矩形面积。想法是直接对每列最低的障碍，建笛卡尔树一样的东西。那对递归进两边的时候，相当于递归进两个子问题，然后给两个子问题下面加一行。所以一个子问题状态可以看作 $(l,h)$ 表示现在底边长度是 $l$，下面垫了 $h$ 层。

然后先设 $\text{dp}(i,h)$ 表示底边长 $i$，下面垫了 $h$ 层，合法的概率。转移直接枚举底层最靠右的障碍在哪里。这样看起来是 $\mathcal{O}(n^{2}k)$ 的。但是因为 $i\times h\le k$ 所以有一个调和级数，大概是 $\mathcal{O}(nk\ln k)$。

然后 $n$ 很大的时候，最底层两个障碍之间不可能超过 $k$，所以可以直接调用 $\text{dp}(i,1)$ 来做 $\mathcal{O}(nk)$ 的另一个 $\text{dp}$。是常系数齐次线性递推，写个暴力就是 $\mathcal{O}(k^2\log k)$ 了，然后就过了！

07.01 : NOI2017 Day 2

期望：$100+88+20=208$。
实际：$100+80+20=200$。

总结

挂了整整 $8$ 分！！！

$\mathtt{A}$

是之前讲课就讲过的题。$\mathcal{O}(3^d(n+m))$ 是没有任何难度的，这直接就已经有 $\text{90pts}$ 了。关键的观察在于，不必直接钦定 x 的取值，而是可以给他分配成 a，b 或 c 然后一起跑 $\text{2-SAT}$，这样只需要枚举他是 a 还是 b，就可以覆盖这个位置的三种取值了，非常神奇！

$\mathtt{B}$

因为在考前被灌输了无数次“这是个模拟费用流”的思想，所以这题的难度直接减半 前一半是想到网络流。中途题意理解出现了问题，搞定题意之后，很快就想到了 $n$ 个点 $nk$ 条边的费用流建模，这就已经 $\text{60pts}$ 了。

优化到 $\text{80}$ 可以直接从后往前贪心匹配，容易证明不会退流。还有一个 $\text{8pts}$ 是直接从前往后贪心，但是前面的部分正好挂了 $\text{8pts}$ 所以最后还是只有 $\text{80pts}$！！！

$\mathtt{C}$

8。

07.10 : NOI2018 Day 1

期望：$100+56+100=256$。
实际：$100+56+100=256$。

$\mathtt{A}$

简单的 $\text{kruskal}$ 重构树入门题。记得不要写 SPFA 求最短路

$\mathtt{B}$

比较可惜的题。

首先打表猜结论。首先看到 3 2 1 是不合法的，容易得知任意存在三个下标 $a<b<c$，满足 $p_a>p_b>p_c$ 的排列都不合法。然后大胆猜测这是充要条件！

然后这就是不存在一个长度为三的下降子序列。根据 $\text{dilworth}$ 定理得到排列可以拆成两个上升子序列。

考场上直接模拟 $\mathcal{O}(n\log n)$ 求最长上升子序列的算法，设 $\text{dp}(i,a,b)$ 表示只考虑前 $i$ 个位置，值域为 $[1,n]$，两个上升子序列的结尾分别是 $a,b$ 的方案数。然后枚举最新的能放在哪里，能放第一个就放第一个。

容易发现 $a=i$ 恒成立，所以就变成二维状态了。观察转移，容易转化为格路计数问题。

可惜这个定义方式貌似难以支持此题所需要的限制，因为带有标号分配，所以字典序大小难以控制。

如果重新观察最长上升子序列的求法，注意到如果一个数是前缀最大值，那么一定被放在第一个序列；否则，他一定是“还没放好的最小元素”，否则后面这个元素就再也放不了了。于是可以设 $\text{dp}(i,j)$ 表示前 $i$ 个数，$max=j$ 的方案数。同样容易转化为格路计数问题。

与上面不同的是，这样设置后不涉及标号分配，容易满足字典序要求。于是，只需要枚举 $p,q$ 的最长公共前缀，然后在第一个不同的地方放一个前缀最大值。这个事情的方案数同样可以看作从一个点走到 $(n,n)$，不超过 $y=x$ 的方案数。

当然，如果 $q$ 的一个前缀已经不合法了，就需要提前结束。时间复杂度 $\mathcal{O}(n)$。

$\mathtt{C}$

感觉并不算特别困难。

建立 $S$ 的 $\text{SAM}$ 之后，想法肯定是枚举 $T$ 中子串的右端点，看左端点的合法情况。首先容斥成 “$T$ 中本质不同子串” $-$ “$S_{l...r}$ 和 $T$ 的公共本质不同子串”。

然后对于一个枚举的 $T$ 中右端点，肯定是维护 $\text{endpos}$ 集合看和 $S_{l...r}$ 的最长公共子串长度，这个可以通过二分 $+$ 线段树做到单次 $\mathcal{O}({\log }^{2}n)$。

然后就得到了一个 $\mathcal{O}(n{\log }^{2}n)$ 级别的做法，貌似可以拿到 $\text{68pts}$。

根据一般经验得知二分套线段树总是不优的 考虑优化掉二分的 $\log$。注意到如果对于一个右端点 $r$，$l$ 是最远的合法左端点，那么对于 $r+1$，合法左端点也不会在 $l$ 之前。意味着可以双指针，然后就少一个 $\log$ 了。

但这还不够，因为这中间可能存在相同的子串被重复计算。“$T$ 中本质不同子串” 可以直接先对 $T$ 也建立 $\text{SAM}$ 算出，后面的部分实质上是在 $S$ 的 $\text{parent tree}$ 上一个包含根的联通块。可以通过类似建立虚树的方法计算。

（后来发现为什么要在 $S$ 的 $\text{SAM}$ 上计数，在 $T$ 上计数直接遍历复杂度就是对的）

可能可以通过离线之类的方法把线段树合并维护 $\text{endpos}$ 扬了，但是上述做法已经足够了，复杂度 $\mathcal{O}(n\log n)$。

08.05 : NOI2018 Day 2

期望：$100+45+50=195$。
实际：$45+45+50=140$。

鸽了快一个月

$\mathtt{A}$

大概是要解决 $v_{i}x\equiv a_i(\mathrm{mod}{p}_i)$ 的方程组。考场上的写法是尝试合并之前的 $x^{\prime }+kM$ 和 $v_{i}x\equiv a_i(\mathrm{mod}{p}_i)$：

X = 0, M = 1;
for(int i = 1, d, c1, c2, x1, x2, g; i <= n; ++i) {
    d = (a[i] - v[i] * (X % p[i]) % p[i] + p[i]) % p[i];
    c1 = v[i] * (M % p[i]) % p[i], c2 = p[i];
    ExGcd(c1, c2, g, x1, x2);
    if(d % g) return puts("-1"), void();
    x1 = x1 * (d / g) % p[i];
    X = X + x1 * M;
    M = M / __gcd(p[i], M) * p[i];
    X = (X % M + M) % M;
}

关键的问题是 M = M / __gcd(p[i], M) * p[i];，这是默认所有方程都是 $x\equiv a_i(\mathrm{mod}{p}_i)$ 的情况下的做法。而此处 $x$ 前还有系数，可能需要一些更复杂的处理。

比较稳妥的方式是将其转化为 $x$ 前系数为 $1$。我们首先对 $v_{i}x\equiv a_i(\mathrm{mod}{p}_i)$ 解出一个 $x^{\prime }+k{M}^{\prime }$ 的形式，然后再使用一次 $\text{ExGcd}$ 合并两个 $x$ 系数为 $1$ 的同余方程。

$\mathtt{B}$

cmd 的做法非常杨戬！！！

$\mathtt{C}$

$8$。

08.17 : NOI2019 Day 1

期望：$100+50+64=214$。
实际：$100+50+44=194$。

极限模拟

$\mathtt{A}$

以边为阶段转移，在每个点上挂一个队列表示以这个点作为结尾的边的凸壳。求答案的时候可以直接在凸壳上二分最接近要求斜率的点，也可以这样指针扫过去：

因为查询的斜率单调不降，所以用一个“单调队列”将斜率不再可能合法的点全弹出。直接用凸壳切线截距最小来理解看起来有点怪，主要是因为这会使得单调队列里留下一些“实际上不在全局凸壳上的点”，或者说会缺少当前区间凸壳的一些点。但是由于询问点单调，所以可以说明这些缺失的点不会对答案产生任何影响。

但是你如果用一些更不“本质”的角度去想，看起来会有道理一些：当直线的切点切换的时候，前面的点就再也没用了，所以可以直接删掉。

反正我是不知道哪里觉得有点怪

$\mathtt{B}$

没做出来，比较可惜。

首先考虑最大值，如果有多个，先看最靠右的那个。这个点的位置应该“几乎在序列中点”，因为他向左向右都可以移动到端点。然后两侧就是两个子问题，注意左边的子问题中仍然可以填，和最大值相等的元素（因为这样的位置向右也跨不过当前这个点），即：

$$\text{dp}(l,r,k)=\sum _o\text{sum}(l,o-1,k)\times \text{sum}(o+1,r,k-1)$$

$\text{sum}$ 是前缀和。容易猜到要用的区间不多，所以只转移要用的区间就可以得到 $\text{50pts}$。

考虑 $A_i=1,B_i={10}^9$ 的部分分。对于 $l=r$，$\text{dp}(l,r,k)=1$，是关于 $k$ 的 $0$ 次多项式，其前缀和是关于 $k$ 的 $1$ 次多项式。

再看上面的转移，就会发现 $\text{dp}(l,r,k)$ 是关于 $k$ 的 $\mathcal{O}(r-l)$ 次多项式。因此可以插值！

然后推到 $A,B$ 有限制的情况，那么明显可以按照给出的 $A,B$ 将值域分段，每段的答案是多项式。

$\mathtt{C}$

一开始编的费用流模型依靠一个结论，但是那个结论假了！！！后面写的费用流甚至跑不过 $\text{64pts}$！！！身败名裂。

首先，可以看作是将 $a,b$ 做带权匹配，需要有至少 $L$ 组下标一致的位置匹配。至少 $L$ 组要匹配，相当于至多 $K-L$ 组不匹配。然后就可以列出费用流建模。

根据 cmd 的方法，只需要对特殊的费用流图，一一枚举增广路，并分析其现实意义，就可以得到若干种贪心转移。最后大概需要 $5$ 个堆。

08.18 : NOI2019 Day 2

期望：$100+100+68=268$。
实际：$100+100+64=264$。

考虑到凑不出 $5$ 个小时了，所以就各种凑，拼出了 $5$ 个小时！！！！

极限翻盘！！！！！！

$\mathtt{A}$

一个做法是直接数据结构优化建图，但是空间开不太下。直接的解决方案是，不把这些边建出来，每次都暴力在数据结构上松弛。

另外一个跑的飞快的做法是，按弹跳装置做点，然后跑点权 $\text{dijkstra}$，一个点第一次被遍历到就是最优的，可以均摊。这个做法所有点的时间总和比前一种做法一个点还快

$\mathtt{B}$

考前听说了这题是找规律题，然后就快速通过了！！！！

先写一个暴力，尝试看看样例每一项是多少。把取模的数字改回小数，观察发现 $\text{type}=1$ 的时候答案是等差数列！！！！那么经过每一步，答案都是等差数列，可以每次暴力求出 $2$ 个点值然后插出来。

合理猜测 $\text{type}=2$ 就是 $2$ 次多项式！！！！然后就过了！！！

$\mathtt{C}$

好像编的就是正解，但是不会处理单点，加上一些常数问题导致只有 $\text{64pts}$。

查询次数 ${\displaystyle \frac{n^2}{2}}$：每次修改一个点，暴力查找前面的每一个元素，有哪些发生了变化。需要维护每个点的真实值。不过实际上只需要维护当前操作位置前面的实际值，所以可以一步一步确定。

$\text{A}$ 部分：考虑编号在某一个点之前的点中，有没有和当前点有边的。由于只有一个点，所以可以直接整体二分。同样需要维护每个点的真实值变化，在这个部分分中，每个点的变化就是恰好翻转。

$\text{B}$ 部分：发现和 $\text{A}$ 没啥区别，只要注意只在当前点前面二分就行（这样就只有一个点和当前点相连了）。但是每个点的变化不是简单的翻转了，所以可以一开始模拟一次，操作了所有元素后每个点是否翻转，然后每完整操作一轮就模拟一次。

$\text{CD}$ 部分：感觉我没得到什么特殊解法，看起来做法就是正解。大概是，你考虑上面这个做法，要求是编号在我之前的恰好有一个和我相连。稍微分析一下会发现，其实只要前面与我相连的是奇数个也行。所以就 random_shuffle 一下，每次想必会找到很多的边！！！然后就可以用 check 来判断与一个点相连的边是不是都被标记了，及时把这样的点删掉就行。

但是我不太会处理单点，他们会让这个过程无法结束，且会增大操作常数。所以我的做法中一开始需要 $n$ 次 check 来先删掉所有单点。后面修完了再回来补！！！