NOI 补题

Sol1 · 2022-06-10 23:04:27 · 个人记录

NOI2016 589/600

优秀的拆分 100/100

忘了。

好像是 SA 然后枚举长度然后撒关键点然后分类讨论，复杂度带个调和级数。

哪天太摸了就来具体补一下。

网格 100/100 [4 Attempt: 44 - 84 - 92 - 100]

答案不超过 2（隔离一个角），然后自然就是大力分类讨论。

如果少于两个白点，或者两个连通白点，输出 -1。

如果不连通，输出 0。当然不能直接判。考虑到既然两个不同的白连通块一定被一个黑点隔开，把黑点的八连通白点拿出来四连通 BFS，如果一个黑八连通块有两个以上八连通的白四连通块就说明不连通。

~~怎么感觉写成绕口令了。~~

如果有割点，输出 1。显然一个不和任何黑点八连通的白点不可能是割点，于是为了保证连通性是对的，把每一个黑点开出去两圈，然后只考虑一圈范围内的割点就可以了。

剩下的输出 2 就行了。

44 -> 84 是没判一行/一列。

84 -> 92 是修了一个 xy 打反。

92 -> 100 是数组开小了。

循环之美 100/100

一大堆式子。好像之前写过一个题解。

区间 100/100

长度排序双指针，搞个线段树维护区间加区间最大值即可。

正确性显然。

国王饮水记 100/100 [2 Attempt: 95 - 100]

nb 题，过几天来补上题解。

旷野大计算 89/100

有点忘了，明天复习一下就补上。

NOI2017 500/600

整数 100/100

线段树维护压位高精。挺 trivial 的，就不写了。

有时间再写一遍这题。

蚯蚓排队 100/100

写个 hash 表，然后暴力即可，非常愚蠢。

泳池 100/100

冲个笛卡尔树 dp 板子可以得 70。

然后考虑到一定是一堆很短的白块用黑块分开，于是可以再套一个 dp，而外面的这个 dp 可以常系数齐次线性递推优化一下。

游戏 100/100

爆搜 x 换成 a 还是 b 就可以覆盖所有情况，然后每一个图只有两种选择，跑 2sat 即可，O(n2^d)。

蔬菜 100/100

好像写过一个题解。

分身术 0/100

算几

NOI2018 500/600

归程 100/100

既然是先从 v 随便走，到一个点 u，然后再最小化 u 到 1 的距离，那自然就是从 1 跑个 dij 到所有点，然后就要用车走到最短路最小的点。

这样就可以转化为一个动态连通性问题，倒着涨水就行。怎么还有个强制在线，感恩出题人不卡空间，写个可持久化并查集就 ok 了。

冒泡排序 100/100

最近写过一个题解。

你的名字 100/100

首先把所有字符串接起来建个 SA。

然后对于一个询问，在 T 上扫一遍 SA 上面对应的点，要求出它与它后面的在 [l,r] 之间的 S 点，以及下一个 T 点的最长的 LCP。

注意到这个形式上非常像 height，于是可以套用 height 的求法转化成线性次 check 一个长度是否可行。这个直接拿个主席树维护即可。

复杂度 O(n\log n)。

这个题感觉最难的地方在于观察到求答案的过程类似于求 height。在考场上可以考虑一下手头的模型是否与某些经典模型类似。

屠龙勇士 100/100

EXCRT 板子。

noi 之前记得复习一下。

情报中心 100/100

nb 起来了。。

观察到这个题给了个 S_1 和 S_2，不妨从这两个开始想起。

首先考虑 S_1。LCA 不相同的时候两条路径的交必定是一条祖先到孩子的链。

下部点一定是两个路径各一个端点的 LCA，提示线段树合并；上部点一定是一个路径的 LCA，提示树上差分。

于是考虑把路径树上差分之后线段树合并维护。由于合并点确定后交的长度受更深的 LCA 的限制，所以把一条路径记在线段树上的位置设为其 LCA 的编号，然后就是统计偏序对的权值之和最大值，这个可以利用线段树的分治结构自然维护。

这样 S_1 做完了。

考虑 S_2。尝试直接套用虚树边权和等于叶子环距离除以 2。

得到 P_1 和 P_2 的并的边权和是（P_1 的长度 + P_2 的长度 + 两条路径的交的两个端点下面的两个点的距离）除以 2。

枚举一侧的交的端点，然后除了另一侧距离全都可以拆成独立量。于是把独立量挂到那边的两个点上求直径就可以了。可以使用经典的动态维护点集直径。

把这两个做法拼起来，S_2 部分把相同 LCA 的所有点拉个虚树，就 1log 了。

~~然后我就写了 10KB。~~

有时间的话把这题也写一遍。

多边形 0/100

450 行

不过为啥我不怕上一题 350 行怕这题 450 行，如果实在闲的没事可以试着补一下。