2021 年 8 月水题选做

决定重新开坑这个系列。

然而马上就初三了估计只有 8 月份的了。

8/11

$\color{green}{\text{AT4512}}$

好神仙的构造题…

首先有一种 naive 解是第 $i$ 行全都填 $i$。

但是这样只能做 $k\le 500$ 的情况。

考虑换一种新解。

$$\begin{matrix} 1&2&3&4&5\\ 2&3&4&5&1\\ 3&4&5&1&2\\ 4&5&1&2&3\\ 5&1&2&3&4\\ \end{matrix}$$

看起来还是只能做 $k\le 500$ 的情况。但是这个解法可以拓展。

观察到对于每一个数，其周围一定是两个 $a$ 和两个 $b$，而且这两个 $a$ 的行奇偶性一定不一样，这两个 $b$ 的行奇偶性也不一样。

那么就可以把这种解的其中一个数的奇数行的位置都换成一个新数。

换任意个数都可以。

例如

$$\begin{matrix} 6&7&8&9&10\\ 2&3&4&5&1\\ 8&9&10&6&7\\ 4&5&1&2&3\\ 10&6&7&8&9\\ \end{matrix}$$

这样的话就可以做 $k\le 1000$ 的情况了。

$\color{green}{\text{CF1364D}}$

首先考虑一棵树的情况。显然树上不存在环，然后我们可以将树按照深度奇偶性染色，每一种颜色的构成一个独立集。从大的里面选 $\left\lceil\frac{k}{2}\right\rceil$ 个就可以了。

变成了一个图，我们可以类似地先搜出一个生成树。如果存在一条非树边连接的两个点深度之差 $<k$ 的话那么显然可以找出一个大小不超过 $k$ 的环。

否则，在树上有非树边连接的两点之间在树上的距离一定是 $\ge k$ 的。那么我们从任意一个深度 $>k$ 的点出发，往上跳，隔一个选一个，选出一个大小为 $\left\lceil\frac{k}{2}\right\rceil$ 的独立集即可。这样可以保证选出的点中一定没有非树边连接。

8/13

$\color{green}{\text{P1935}}$

发现这道题是与周围类型不同的时候有额外收益。如果是相同的话那就很好办，不同怎么做呢？

将格子黑白染色，黑格子反着连边，这样就可以转化为相同了。

8/14

$\color{green}{\text{P3195}}$

决策单调性优化 dp 的经典板子题，二分+队列维护即可。

8/15

$\color{green}{\text{P3809}}$

终于学会 SA 了。。。

之前一直不懂板子的代码，现在算是搞懂了（但是难背死了）。

$\color{green}{\text{P2408}}$

SA 最简单的应用之一。使用 height 数组直接求解即可。

$\color{green}{\text{P4555}}$

manacher 的简单应用。对于每个 # 存一下它向左的最长回文串和向右的最长回文串。

具体来说，先用 manacher 处理出每个 # 能扩展的最长的极大回文子串，然后扫一遍更新即可。

8/16

$\color{green}{\text{P5495}}$

莫反前置知识。从枚举约数优化到枚举素数，然后做高维前缀和。

8/17

今天是虵滴生日

$\color{green}{\text{P3803}}$

学了一发 FFT。

$\color{green}{\text{P3701}}$

由于某些原因，在今天（8.17，蛏蜒节）写这道题。

这道题显然是一道最大流，考虑如何建图。

观察到寿命即为一个人可以用的次数，于是我们从 s 向 byx 的人连他们寿命的边，注意长者需要 +1s，于是需要把膜法师的人数续进命里。类似地从诗乃的人向 t 连类似的边。

然后考虑两边人之间比赛的连边情况，可以枚举一波然后如果 byx 的这个人可以赢诗乃的这个人，从 byx 的人向诗乃的人连 1 边，表示这个人可以用 1 个寿命获得一个赢的次数。

然后跑最大流就完了。注意只有 $m$ 场比赛，所以要特判一下答案 $>m$ 的情况。

代码：戳我