全部补完计划 Todo List

W1D1 (0804)

模拟赛。

T1

做

T2

观察发现斐波那契数列作为不定方程的系数，对其施以【二元一次不定方程解的数量获取】。

T3

我们二分一个答案，然后对于 $dis (1, x) + w + dis (y, n) \leq V$ （其中 $V$ 为二分值）的边保留，其余边删去，然后看剩下的图。

如果它不连通那么这个答案显然是合法的。

否则考虑图中的桥，如果任意一座桥满足起点和终点分居其两侧，且将其加上给定值之后能使得 $dis (1, x) + w + dis (y, n) > V$ ，就可以通过操作它以达成目标。

如果不存在那就不合法了。

T4

考虑将问题进行贪心，最后发现是一个双序列扩展模型。

W1D2 (0805)

T1

写

T2

关键观察：无序数对 $(a_{i}, b_{i})$ 构成的集合唯一。

证明与构造方法是从下往上匹配，使用 multiset。

那么我们令数对 $(x, x + 1)$ 的代表元为 $x$ ，该数对数量为 $c_{x}$ 。

这时构造一个序列相当于从每个数对中选择一个元素。设 $F_{i, j}$ 表示当前正在考虑 $(i, i + 1)$ ，其中有 $j$ 个该数对选择了 $i + 1$ 放进 A 中，对答案的贡献系数。那么，根据多重集的排列数，我们只需要计算逆元积之和，有转移方程：

F_{i, j} = \sum_{k = 0}^{c_{j - 1}} F_{i - 1, k} \times (k + c_{i} - j)^{- 1}

最后再乘上 $n!$ 即为答案。

注意离散化的时候要把数之间是否相邻也离散化出来。

T3

颜色段均摊在没有查询操作，或者查询和区间推平捆绑的时候，复杂度是对的，为 $O (m \log n)$ 。

题目中，计算一个序列的权最小值是简单的：只需要将其排序，然后取各连续段众数出现次数。

维护的话，可以维护一个值域线段树，单点维护出现次数，然后采用连续段线段树的方法维护。

修改的时候采用颜色段均摊枚举区间内元素并修改即可。

T4

发现 $x, y$ 两变量独立，那么问题就变成了：给定一个变量 $x = s$ ，对其执行恰好 $d$ 次 $+ 1$ 或 $- 1$ ，使得任意时刻 $1 \leq x \leq n$ 且最终 $x = t$ ，求方案数。

这可以转化为反射容斥模型：令起始点为 $(0, 0)$ ，将加操作看成 $x$ 坐标增加 $1$ ，减操作看成 $y$ 坐标增加 1，由于操作次数限制，所以令终点为 $(a, b)$ ，则 $a + b = d$ ，而我们又有 $s + a - b = t$ ，两者联立可求出终点坐标为 $(\frac{(d + t - s)}{2}, d - \frac{(d + t - s)}{2})$ 。

由于任意时刻 $0 < s + x - y < n + 1$ ，所以移动的时候不能碰到直线 $y = x + s$ 和 $y = s - n - 1$ 。

有了以上参数，套反射容斥模版即可。

反射容斥重学

周末补

W1D3 (0806)

同上

W1D4 (0807)

脏了 10 分

T1

从左往右模拟一遍题目的过程即可。

T2

每个点向上面第一个 D，左边第一个 R 一类的点连边然后跑搜索就行。

或者还有一种方法，就是倒着暴力扩展，每次遇到被相同方向扩展过的点就 break，每次扩展要从大往小和从小往大枚举各一遍。可以证明一个点只会被拜访 $O (1)$ 次，总复杂度 $O (n m)$ 。

T3

待会写

T4

首先，预处理出每个轮换的 size，每个元素在它所属轮换中的次序。

然后可以考虑分块。分块维护前缀连续段长度，后缀连续段长度，是否全段连续，对每个 $x \in [1, m]$ 段内包含 $x$ 的最大值。

然后考虑修改操作：直接将整块重构即可。注意在清零存【每个 $x \in [1, m]$ 段内包含 $x$ 的最大值】数组的时候要 $O (l e n)$ 不要写成 $O (m)$ 了。

考虑查询操作：散块暴力，然后查询每个单块内段长最大值。

考虑维护一个 cur 变量，表示当前处理的块间连续段的长度：左右散块直接求，中间的就观察其是否全块连续，然后根据之前求的前后缀长度维护。

当 cur 每次被重置时，我们就统计答案，检查这段区间是否能对答案贡献。

具体地，先检查左右端点所在轮换是否与 $x$ 所在轮换相同。然后观察区间长度，如果大于等于轮换大小那么 $x$ 一定出现过。

否则就检查 $x$ 在轮换中的排名是否在左右端点排名之间就行。实现小技巧：由于轮换是一个轮换，所以当 $x$ 和右端点其中任意一个排名小于左端点的，要将排名小于左端点的排名临时加上轮换 size 以方便 check。

W1D5 (0808)

我怎么不会人均题？我怎么不会人均题？我怎么不会人均题？我怎么不会人均题？我怎么不会人均题？

T1

观察发现只有前面十个 bit 是有用的，并且 ban 掉的 bit 一定是一段后缀，直接枚举即可。

T2

容易写出来一个 dp，但是同一个集合不同摆放方案会算重。

考虑选出一个集合之后的最优摆法是左括号全摆前面，那么我们可以加一个 $0 / 1$ 维在状态里。设 $F_{i, j, 0 / 1}$ 为截至第 $i$ 个数总和为 $j$ ，是否要开始摆右括号。用脚转移即可。

但是我赛时没有脚，悲伤。

T3

考虑移动白色和移动黑色本质相同，不妨令 $2 k < n$ ，再以重心为根，这样子选择的那个块就一定是以重心为根的子树了，然后我们对 size=k 的节点的答案进行一个维护，用线段树维护即可。

T4

$k > 1$ 时答案即为每个连续段长度除以 $k + 1$ 向下取整。

然后分两种情况进行讨论一下，再套个淀粉质就行了。

W1D6 (0809)

W2D1 (0811)

W2D2 (0812)

W2D3 (0813)

W2D4 (0814)

人均 200+eps。

T1

直接做

T2

考虑正难则反，发现如果数列中的 min>0，那么第一次操作一定是插入 $[0, min {a_{i}} - 1]$ （可能并带着某些数）

不难发现其之后的都可以任意放，那么一次放很多个能构造出的序列一定是一次放一个能放出的子集。

所以我们每次操作都只放一个，使用组合数计算即可。另外，第一次操作也是只要插入那段区间数的全排列即可，不用并带。

T3

$k = 0, 1$ 可以矩阵树定理做，考虑枚举基环树的环。

$k = 2$ 好像也可以，等 JT 讲了之后学习一下。

T4

待补

W2D5 (0815)

喝到了奶茶。上去把我在题解区生产的 shift 讲了一下然后获得了泡面。

T1

网格图最小生成树，模拟即可

T2

直接转移

T3

熔池

T4

~~好像可以用假质数做法做？~~

W2D6 (0816)

W3D1 (0818)

T1

做

T2

考虑写出一个 dp 之后，是一个格路中的最短路问题。发现是尽量往右下走最优，又发现只有 $n$ 个点会影响，于是维护每条直线 $x - y = k$ 其上障碍的位置以及其答案，然后倒着 dp 即可。

T3

发现对于任意矩形，其四个顶点的 N 和 Z 的个数应该为偶数。

于是可以通过某个非 0 元素确定每个元素之间的异同关系，使用扩展域并查集维护即可。

T4

逮捕

W3D2 (0819)

T1

考虑对每个质数附一个权值，使用线性筛筛出每个数的质因子权值异或和。这样，两个数乘积为完全平方数当且仅当异或和为 0，然后直接做即可。

T2

拆贡献，计算每个权值在多少树上路径中出现。

对于一个权值 $w$ ，这其实特别好算，我们考虑每个路径只取一个代表元计算。

具体地，按照 dfn 考虑每个节点，这样子访问到一个点的时候它的儿子们没有被考虑到。

然后我们计算【从该子树内由外延伸的路径总数】，特别地，外部路径不能经过相同权值边。

为了实现这个我们需要求出【祖先中第一个同色边】，直接使用栈即可。特别地，如果没有，那相当于在整颗树上找经过该边的路径。

为了求出路径数量我们需要维护【每个点以该点权值的下剩余没有被计算的点】，也就是不额外经过同色边。由于节点 1 需要同时管理到所有颜色，所以需要特别处理一下。

以上东西特别好维护，只需要使用【数组】即可。

需要注意的是，以上说辞中，子树内的同色边是可以经过的。

可以证明以上方法不重不漏。

T3

考虑一个区间合法的必要条件是 $x_{r} - x_{l} \leq 2 v T (r - l)$ ，移项后考虑往两边扩展，这是一个经典的双序列扩展问题，直接做。

T4

考虑以二维坐标系上的点 $(x, y)$ 表示 $(x, y)$ 路径是否合法。

那么我们考虑同色点对的限制：

如果它们没有祖先关系，相当于 $x$ 子树中的点与 $y$ 子树中的点不能连。

否则，设 $y$ 为祖先， $z$ 为 $y$ 的儿子满足 $x$ 在 $z$ 子树内，相当于 $x$ 子树中的点不能连 $z$ 中的点的补集。

以 dfn 形式考虑，限制变成了若干矩形。

扫描线求矩形面积并即可。