thisislike_fan

发布于 04-18 21:30 陕西

+ 关注

题解

A：

签到题，注意到样例给了 $n = 1, 3, 4$ 的答案，填上 $n = 2$ 的答案直接输出即可，也可以写全排列。

B:

鸽巢原理容易得到满足题面条件的 $|E|$ 至少为 $m - 1$ ，以下给出一组构造：

选定任意一个在 $V$ 中出现过的点 $rt$ ，令树的根为 $rt$ 。

此时对于每个在 $V$ 中出现过的点 $u$ ，若 $u \neq rt$ ，删掉 $(parent_u, u)$ 这条边，其中 $parent_u$ 为 $u$ 在树上的父节点。

C：

考虑期望的线性性，观察每次修改对 $a_i$ 期望值的增量，容易得到每次修改具有 $x$ 的固定增量以及 $a_i \operatorname{and} m$ 的不固定增量，又有对于任意 $a_i \operatorname{and} m = v$ ，显然 $v$ 的取值只与 $a_i$ 的低 $\lfloor\log_2(m)\rfloor + 1$ 位有关，考虑建一个有 $2^{\lfloor\log_2(m)\rfloor + 1}$ 个点且编号从 $0$ 开始的图，从每个图上点 $u$ 向 $u + (u \operatorname{and} m) + k$ 的低 $\lfloor\log_2(m)\rfloor + 1$ 位连有向边后，定义 $dp[i][j]$ 为从每个 $a_i$ 对应的起始状态开始操作 $i$ 次且到达点 $j$ 的概率之和，对于每个 $a_i$ 将 $a_i$ 的低 $\lfloor\log_2(m)\rfloor + 1$ 位加入 $dp[0]$ 数组作为起始状态后，又因为 $m\cdot k \leq 10^8$ ，直接进行动态规划即可得到每次操作对答案贡献的增量。

D:

注意到一个排列 $P$ 的前后缀 $mex$ 与 $Q$ 的前缀 $max$ 与前缀 $min$ 构成双射，其中 $Q[P[i]] = i$ 。

设我们当前构造的答案为 $P'$ 。

考虑在求出 $P$ 对应的 $Q$ 后，按下标 $i$ 从小到大扫描：

若当前 $Q[i]$ 大于上一个前缀的最大值或 $Q[i]$ 小于上一个前缀的最小值，显然一定有 $P'[Q[i]] = i$ ，同时从可用的下标集合 $T$ 内删除 $Q[i]$ 。

然后按下标 $i$ 从小到大再进行一次扫描：

若当前 $Q[i]$ 在上一个前缀的最小值到上一个前缀的最大值区间内， $Q[i]$ 对应的在 $P'$ 内对应的下标可以从 $T$ 中值在上一个前缀的最小值到上一个前缀的最大值这个区间内的元素内任意选择，转换一下就是每个出现在 $T$ 内的下标 $idx$ 需要与一个大于等于 $left_{idx}$ 的值匹配，其中 $left_{idx}$ 为长度最小的前缀最小到前缀最大这个区间包含 $idx$ 的前缀的长度。

考虑按字典序进行贪心，显然就是找到一个最大的下标 $i$ ，保证把 $a_i$ 修改为比 $k (k > a[i])$ 之后可以构造一组匹配，令 $a_i =$ 满足条件的最小的 $k$ 后按顺序从小到大匹配后面的 $a_j$ 即可。

是否可以构造匹配可以考虑建一个整数数组 $cnt$ ，初始元素全为 $-1$ ，对于所有 $idx$ ，令 $cnt[left_{idx}] = cnt[left_{idx}] + 1$ ，则解存在当且仅当数组 $cnt$ 所有前缀和大于等于 $0$ ，使用数据结构优化。

E:

此时有 $1 \leq k \leq 10^6$ ，直接 $dp$ 看上去不太现实，但注意到当图上每个节点存在且只存在一条出边时，这个图为一个内向基环树，考虑从点 $u$ 到点 $v$ 的贡献 $diff$ ，显然有 $diff = (dp[0][u] \cdot \sum_{i=dist(u, v)}^{k}\binom{k}{i}) \cdot (2^k)^{-1}$ ，其中 $dist(u, v)$ 为 $u$ 和 $v$ 在树上的距离，当 $v$ 在环上时，此时 $dist(u, v)$ 可能有多个取值，显然都需要加上。

考虑计算在环上的点 $u$ 对所有环上点 $v$ 的贡献，容易发现图上不同环长只有 $2\sqrt{m}$ 种，这启示我们对于每个不同环长，预处理一个贡献数组 $f[i][j]$ 表示长度为 $i$ 的环上从 $0$ 号点向前移动到 $j$ 号点的方案数，即 $\sum_{t=j}^{k}\sum_{c=t}^{k}\binom{k}{c}[t \equiv j\ (mod\ i)]$ ，注意力比较强的话还可以发现环长只能是 $2$ 的整数次幂。

此时直接按照贡献数组对答案累加，同时对于树上节点，设它与环上节点的最小距离为 $c$ ，满足距离最小的环上节点为 $v$ ，那么容易发现把它的贡献直接挂在 $v$ 在环上前驱的第 $c$ 个节点上后减去本应到树上节点的错误贡献即可。

F:

考虑枚举 $g$ ，对每个 $g$ ，建一个有 $m = \lfloor\frac{\max_{i=1}^{n} a_i}{g}\rfloor$ 个点的图 $G$ ，其中点 $u$ 向点 $v$ 连无向边当且仅当 $\operatorname{gcd}(u, v) = 1$ 即 $u, v$ 互质且数组 $a$ 中同时存在 $u \cdot g, v \cdot g$ 。

考虑经典问题，即给数组 $a$ ，保证元素不重，找到 $a$ 中一对互质的 $(a[i], a[j])$ 保证 $i \neq j$ ，容易发现对每个 $a_i$ ，计算是否存在至少一个 $a_j$ 与 $a_i$ 互质可以使用莫比乌斯反演在 $m\cdot\log(m)$ 复杂度内实现，同时当找到一个 $a_i$ 存在至少一个 $a_j$ 时，我们只需要暴力扫描整个数组便可以确定一对 $(a_i, a_j)$ ，此时对于计算所有 $g$ ，设 $k = max_{i=1}^{n} a_i$ ，则总复杂度为 $k\log^2 k$ ，同时找到的 $(a[i], a[j])$ 显然为上面图 $G$ 上的一条边。

考虑计算当前 $g$ ，首先按照上面算法扫描得到 $4$ 条不同的边，特别地，当扫描不到 $4$ 条边时，直接暴力计算即可。

接下来计算图 $G$ 上边数大于等于 $4$ 的情况，取出上面 $4$ 条边中的任意 $3$ 条，暴力计算查看是否可以得到解，如果可以得到直接输出答案。

否则，这三条边的形态只能是三元环或菊花树：

对于三元环，加入剩下的一条边即可构造一组解，因此在实现上，可以直接暴力计算全部的 $4$ 条边。

对于菊花树，我们删去这棵树的中心点，此时如果再扫描到一条边，也可以构造出一组解，否则显然有所有点只对中心点有边，显然不存在解，输出 $-1$ 。

G:

考虑后缀数组，令 $t = s + \operatorname{reverse}(s)$ ，显然有翻转 $(l, r)$ 符合题目条件当且仅当 $rk_l \le rk_{2n-r+1}$ 且 $l + lcp(l, 2n - r + 1) \leq r$ ，考虑从小到大扫描 $sa_i$ ，显然有经典结论 $lcp(sa_i, sa_j) = \min_{x=i+1}^{j} ht_x$ ，考虑单调栈维护 $lcp$ 相等的段，发现同一个段内如果出现多个 $l$ ，显然取最小的 $l$ 最优，数据结构维护即可。