考试LIST [2021.01]

$2021.01.03$ 日之前的总结数据丢失，随缘补。咕咕咕

2021.01.09

$\texttt{Location:HNOI2021}$

得分：$\texttt{200/300,Rank1}$。

[01.09]-错误

$\texttt{T3}$ 有想法但是没有写完，之后发现细节出现问题。

[01.09]-部分正解

$\texttt{T1}$

环十分不好做，考虑能否断环为链。

发现一定存在一个位置，使得无论如何安排顺序，都不会有点跨过这个位置。那么可以直接以这个位置作为断点来断环为链。

考虑找这样的位置，可以记录每一个位置会加入多少精灵，记录为 $c_x$，然后求前缀和，找：

$$\sum_{i=1}^x (c_i-1)$$

的最小值所在位置。这个位置 $x$ 与 $x+1$ 之间必然不会有精灵跨过，可以反证。

之后就是简单的链上贪心了，$\text{set}$ 即可。

$\texttt{T2}$

考虑一个操作会对最长上升子序列产生什么影响。

首先很显然，最后的答案不会劣于原序列的答案，因为如果每一个数字都往右边放就可以生成原序列。

发现对于从 $x$ 开始的，一个极长的上升子序列，无论如何操作都无法在后面增长了。因此考虑在左边加长，很显然的是，只要再找 $x$ 后面的下降子序列即可，令两者的长度分别为 $l_1,l_2$，那么最后可以构造一个 $l_1+l_2-1$ 的解，减 $1$ 是因为 $x$ 算了两边。

所以翻转序列然后直接做即可。

还有一种做法，考虑将原序列翻转，接在原序列的左边。

由于是上升子序列，所以不会有一个值被加入两遍，这就相当于模拟放在左边还是右边。直接跑就好了，需要注意的是方案数需要除 $2$，因为最中间的元素会被认为可以选择两个位置，实际上他们是一个位置。

$\texttt{T3}$

由于全都是整点且值域不大，所以考虑先将所有整点扣出来。

这个可以直接暴力枚举 $x$，然后求出所有与这个 $x$ 的交点，然后利用类似射线法的方式来判断节点是否在多边形内。

接着考虑如何判断一个位置是否合法。暴力做显然是 $\mathcal{O}(n^4)$ 的，无法通过。但是易于发现，判断的时候实际上是在做 $0,1$ 的与运算，所以可以 $\text{bitset}$ 优化，复杂度就变成 $\mathcal{O}(\dfrac{n^4}{\omega})$，剪剪枝就可以通过。

还有一种方法优化 $0,1$ 的与运算。可以把一个序列翻转然后做卷积，就做到了 $\mathcal{O}(n^3\log n)$。

2021.01.10

$\texttt{Location:HNOI2021}$

得分：$\texttt{230/300,Rank1}$。

[01.10]-错误

$\texttt{T3}$ 是可想的，但是没有仔细思考。

[01.10]-部分正解

$\texttt{T1}$

首先有简单的势能线段树做法，记录一个点是否变成 $0/-1$ 即可。但是由于有区间加法，所以复杂度不对。

考虑换一种设置势能的方法，令势能为区间内值 $\max-\min$。发现对于除以 $d$ 下取整，若 $\max-\left\lfloor\dfrac{\max}{d}\right\rfloor =\min-\left\lfloor\dfrac{\min}{d}\right\rfloor$，那么说明整个区间内的数字的变化量都相同。

这个直接把 $\max/\min$ 扔到分式里面，然后就类似数论分块了。

也就是说，当上述条件满足，我们就可以利用减法来代替下取整出发。发现一次操作之后，区间的势能变为 $\left\lfloor\dfrac{\max-\min}{d}\right\rfloor$ 级别，复杂度正确。

再考虑一个加法操作，根据线段树经典结论，一个区间最多被划分出 $\mathcal{O}(\log n)$ 个线段树上的段，而中间被完全覆盖的部分的势能是不变的——每一个值都加上相同的值。唯一势能改变的只有两边 $\mathcal{O}(\log n)$ 级别个区间，所以势能增加同样正确。

因此时间复杂度 $\mathcal{O}(n\log^2 n)$。

$\texttt{T2}$

手玩发现，如果没有全黑行，那么一定不能使得整个矩形变黑。同时，只要出现全黑行，就立马可以把矩形变成全黑。

发现只要存在一个黑点，就可以构造出一个全黑行。因此无解当且仅当矩形全白。

不妨枚举哪一行是全黑行，若第 $x$ 行变为全黑行，但是原本他并不是全黑行，那么需要从第 $x$ 列中，某一个黑点所在的行来染黑他。

若第 $x$ 列不存在这样一个黑点，则需要再加一步让第 $x$ 列存在黑点——在矩形有解的前提下，这显然是必然可以做到的。

$\texttt{T3}$

建立 $\text{SuffixAutomaton}$，观察数据范围发现 $\sum w\le 10^5$，实际上就是 $k\times q\le 10^5$。

发现是乘积的限制，所以考虑根号分治。

$\text{trick:}$ 当数据范围形如 $a\times b\le ...$，那么可以考虑对 $a,b$ 根号分治。

对于 $k\le \sqrt{m}$ 的情形：

发现字符串并不长，所以考虑直接暴力找每一个子串的出现次数，乘上每一个子串被查询了多少次即可。

暴力枚举左右端点，$\sum k^2\le m\sqrt{m}$，在 $\text{SuffixAutomaton}$ 上沿着匹配边直接走，然后二分来找每一个子串被查询了多少次即可。

对于 $q\le \sqrt{m}$ 的情形：

询问很少，所以考虑每次询问暴力 $\mathcal{O}(m)$ 枚举子串，然后在 $\text{parent tree}$ 上倍增找到这个子串的出现位置，累加即可。

时间复杂度 $\mathcal{O}(m\sqrt{m}\log n)$，实际上可以通过。

2021.01.16

$\texttt{Location:HNOI2021}$

得分：$\texttt{190/300,Rank1}$。

[01.16]-错误

$\texttt{T1}$ 的点数计算错误导致数组越界。

[01.16]-部分正解

$\texttt{T1}$

建立 $\text{SuffixAutomaton}$，发现一次查询就是一些节点在 $\text{parent tree}$ 上两两 $\text{LCA}$ 节点的 $\text{len}$ 的 $\max$。

考虑离线下来做，在一个点处计算以其为 $\text{LCA}$ 的点对。对于一个点对 $(x,y)\ (x<y)$，那么其对区间 $[L,R]$ 有贡献当且仅当 $L\le x<y\le R$，这实际上是二维数点问题。

那么考虑将点对加入二维平面，但是由于点对个数可能有 $n^2$ 级别个，所以需要对点对数进行优化。

贪心地想，发现对于固定的一个点 $x$ 与点权 $\text{val}$，显然 $y-x$ 越小越优，所以每次 $\text{set}$ 启发式合并，加入一个新点的时候在 $\text{set}$ 内找其前驱、后缀，然后加入这两个点即可。

$\texttt{T2}$

这是重心的一个性质，考虑将重心先提到根上，那么显然重心答案为 $0$。

考虑一个节点的答案，发现当其为根时，只有重心所在的子树有可能会“超重”，同时，我们显然贪心地断掉重心的孩子连到根上。贪心地想，肯定优先加重心的 $\text{siz}$ 更大的儿子。

那么可以把重心的儿子排序，然后每次二分找需要断开哪些儿子。

实际上，断开的儿子的个数的变化是很小的，只有可能是断开一些儿子之后，包括重心的子树仍然"超重"才有可能再多断一个儿子。因此只需要每次判断一下是否需要多断开一个即可。

时间复杂度 $\mathcal{O}(n)$。

$\texttt{T3}$

置换是环，手玩发现奇环显然无解，因为一个环上选的边与不选的边是交替出现的。

发现一个环只有两种选择方案，那么最简单的想法就是暴力搜索每一个环的选择方案，最后判断构造的是否是合法的括号序列。但是环的个数最多有 $\dfrac{n}{2}$ 个，所以最劣复杂度是 $\mathcal{O}(2^{\frac{n}{2}})$。

但是，根据括号序列的性质，我们发现对于长度为 $2$ 的环，一定是编号更小的位置放左括号更优。所以直接预处理一下二元环，然后环就最多只有 $\dfrac{n}{4}$ 了，时间复杂度 $\mathcal{O}(2^{\frac{n}{4}})$，可以通过。

2021.01.17

$\texttt{Location:HNOI2021}$

得分：$\texttt{100/300,Rank2}$。

[01.17]-错误

$\texttt{T1}$ 考虑顺序出现错误导致 $\text{90pts}$。
$\texttt{T2}$ 爆搜可以 $\text{80pts}$ 却没打......
$\texttt{T3}$ 板子题却写挂了......

[01.17]-部分正解

$\texttt{T1}$

以下令有水的限制为黑点，无水的限制为白点。

首先手玩 $n=1$ 的情况，发现有水的高度显然是单调的，所以可以暴力枚举水的高度，记录下方的黑点个数即可。

拓展到普遍的情形，发现如果水的高度超过两个相邻水箱的边，再向上，两个水箱就没有区别了，所以可以并查集合并。

那么每次遇到一个节点，若是黑点，那么令黑点个数加一，更新答案；若是白点，那么可以考虑先更新让水停在当前位置，答案加一，也可以选择淹掉这个点，两者取更优的解即可。这些信息也是可以在并查集时合并的。

需要注意的是，在同一高度上需要先考虑白点再考虑黑点。因为若先考虑黑点，就会让黑点的计数器被累加，再考虑到白点的时候答案就会偏大。

或者直接按照隔板的高度划分成树形结构，然后树形 $\text{dp}$。

$\texttt{T2}$

网格图，黑白染色之后连边是二分图。

先找出一个二分图的最大匹配。若落在一个点上，他不在最大匹配中，那么 $\text{Bob}$ 只能走非匹配边，且会到一个匹配点（否则就会出现增广路），接着 $\text{Alice}$ 只要一直走匹配边即可，而 $\text{Bob}$ 又只能走非匹配边走到一个匹配点（否则会出现增广路），一直这样下去 $\text{Alice}$ 必胜。

而一张图可以有多种最大匹配，只要一个点在一种匹配中不在最大匹配中，那么这个点就是必胜的。因为这样的话必然会走到匹配点，然后进入上述过程。

因此只需要找二分图的非关键点即可。

可以首先跑一边二分图最大匹配，对于每一个不在最大匹配中的点，考虑寻找增广路，若点 $x$ 能够找到增广路 $x->y->z$，那么说明 $z$ 也是非关键点，因为可以将 $(y,z)$ 改为 $(x,y)$。

$\texttt{T3}$

李超线段树板子。

$\text{OI wiki}$

2021.01.29

$\texttt{Location:HNOI2021}$

得分：$\texttt{105/300,Rank1}$。

[01.29]-错误

$\texttt{T1}$ 做法差不多了，但是少了一步导致挂分。
$\texttt{T2}$ 是才在论文中看过的内容，却没能想到。

[01.29]-部分正解

$\texttt{T1}$

考虑一下最短路实际上是什么。应该是一对合法点的，所有对应点的最短路的 $\max$。

同时，要求这些对应点的最短路长度的奇偶性应该相同，这样就可以让一些点在一条边上反复横跳。

因此跑一遍 $\text{BFS}$ ，求出每一个点的，长度为奇数/偶数的最短路，然后分奇偶两种，组合计算即可。

需要注意的是，对于一些点对，如果既有奇数最短路，又有偶数最短路，那么会算重。实际上我们应该去两者的 $\min$。只需要减去 $\max$ 即可，所以再把一个点的奇数最短路、偶数最短路取 $\max$ 再做一遍上面的东西即可。

时间复杂度 $\mathcal{O}(n\log n)$。

$\texttt{T2}$

题解 [USACO21JAN] Minimum Cost Paths P

$\texttt{T3}$

考虑平面图上的欧拉定理 $V+F-E=C+1$，其中 $V$ 是点数，$F$ 是面数，$E$ 是边数，$C$ 是联通块个数。

例如

AAB
BBA
BBB

把一个点的四个角看做有点，然后对于相邻的，不同的位置，两个点连边，那么可以得到这样的图：

._._._.
|   | |
._._._.
|   | |
. . ._.
|     |
._._._.

点和边都是很好算的，关键是联通块个数。可能存在一些联通块，一部分在子矩形但并不完全包含。

因此可以考虑对每一个联通块设置一个特殊点，代表这个联通块。先将子矩形中存在的特殊点给取出来，然后再考虑如何减去不被完全包含的。

容易发现，如果一个联通块的特殊点被包含，但整个联通块不被完全包含，那么一定存在一个点在子矩阵的边界上。因此，遍历一遍矩形的周长，然后减去在周长上的矩形即可。

时间复杂度 $\mathcal{O}(n\times m+q\times (n+m))$。

2021.01.31

$\texttt{Location:HNOI2021}$

得分：$\texttt{190/300,Rank1}$。

[01.31]-错误

$\texttt{T1}$ 数组开小了......
$\texttt{T3}$ 可做却没开。

[01.31]-部分正解

$\texttt{T1}$

主席树板子，从父亲继承即可。

$\texttt{T2}$

根据观察数据范围，发现 $n$ 恒为质数。这也太毒了吧......

把柿子写成：

$$c_i=\sum_{j=0}^{n-1} \sum_{k=0}^3 a_{j,k} [b_{i\times j\bmod\ n}=k]$$

交换和式：

$$c_i=\sum_{k=0}^3 \sum_{j=0}^{n-1} a_{j,k} [b_{i\times j\bmod\ n}=k]$$

看起来像一个卷积，但是 $i\times j$ 很烦，所以运用离散对数变成加法，注意先把 $0$ 特殊处理。

$$c_{i}=a_{0,b_0}+\sum_{k=0}^3 \sum_{j=1}^{n-1} a_{\log j, k} [b_{\log i+\log j\bmod\ (n-1)}=k]$$

发现后面类似一个卷积，把 $k$ 看做定值，然后将 $a,b$ 代表的函数中的一个翻转就可以做卷积了。

需要注意的是，由于后面有一个取模，所以需要推推柿子看取卷积中哪些位置。同时，因为所有数字在 $[0,1024)$，所以最后的答案都是没有模的，不管 $\text{NTT}$ 途中有没有模。所以可以直接 $\text{NTT}$ 而不用 $\text{FFT}$。

时间复杂度 $\mathcal{O}(kn\log n)$。

$\texttt{T3}$

发现方程就是假的，因为根本不需要你求方程的真实解。

不妨直接考虑下面判定答案的柿子：

$$\text{ans} = \sum_{i=1}^m \Big(\Big(\sum_{j=1}^n a_{i,j}\times x_j\Big)-b_i\Big)^2$$

可以看做一个关于 $\{x_i\}$ 的多元函数，在最小值点上，当且仅当每一维的偏导都为 $0$。

$x_k$ 这一维的偏导为：

$$\sum_{i=1}^m 2a_{i,k}\Big(\Big(\sum_{j=1}^n a_{i,j}\times x_j\Big)-b_i\Big)=0$$

直接搞出系数，然后高斯消元。

别问为什么 $\mathcal{O}(n^3)$ 能过，出题人说能过就能过。