CF1467 题解

这么水的比赛 lxr 咋都没阿克啊。

A

这道题不会做/kel

直接输出 \(98901234567890123456789012345678901234\cdots\)。

B

直接枚举修改的位置和修改成的值与两边的相对大小关系即可。

C

这题还算有点意思，想了我好长时间。

最终的值显然可以表示成每个数乘上一个 \(\pm1\) 的贡献。

首先所有的数的贡献系数都是 \(1\) 是不可能的。我们考虑分两种情况决策：

1. 两个 bag 的贡献系数都是 \(1\)。这时候显然这两个 bag 之间不能发生操作，因为一旦这样的话那么它们中至少存在一对数的贡献系数互异，就不可能都是 \(1\) 了。于是只允许将非 \(1\) 的那个作为港口进行贸易往来。那这就很清晰了，那就是个二分图，显然转移一次阵营那么贡献系数就取个相反数。于是不难得到最终是要在 \(1\) bag 结束的。那显然只可能是非 \(1\) 的贡献系数全是 \(-1\)，其他全是 \(1\)，方案显然存在；
2. 至多一个 bag 的贡献系数都是 \(1\)。那么不难构造出一个对两个非 \(1\) bag 分别取最小值进行 \(-1\)，其他所有值都是 \(1\) 的方案。就是可以在 \(1\) bag 里留一个，除了这个和两个 \(-1\) 其他所有值显然都可以被不在同一个 bag 里的 \(-1\) 给吸收光。最后留的减去两个 \(-1\) 即可。

最后取个 \(\min\)。

D

我们考虑计算出每个位置对答案的贡献系数。那么显然修改啥的有手就行了。

我们考虑让第 \(0\sim m\) 的每一步都对每个位置的贡献做出贡献。这是 \(\mathrm O(nm)\) 的。那么贡献值显然就是在该步穿过该位置的 good path 数量。

这个可以乘法原理分解一下，分成左边一部分和右边一部分，就是求长度为若干的以该位置结尾 / 开头的 good path 数量。这是个很显然的 \(\mathrm O(nm)\) DP，每一步就往前一步的该位置 \(\pm1\) 转移即可。然后左边和右边是镜像的，只需要 DP 一遍即可。

E

没啥难度的套路题一道。

注意到对于任意一个点，它满足条件当且仅当，若以它为根的话，那么没有颜色相同的祖先后代对。

那么很自然的想到换根，实时维护当前颜色相同的祖先后代对个数（注意要开 ll）。

首先求出初始值。我们考虑换一次根这个值会有什么变化。

考虑所有点对。如果点对在老根和新根的子树中的同一个的话，那关系显然不变。然后如果是不同的，并且两个都不是老根或新根，那显然也不变。于是只需要考虑新根子树对老根的贡献和老根子树对新根的贡献即可。这个只需要一开始离散化一下，装个桶，然后在 dfs 序上二分即可。

复杂度线对。有时候研究线性做法也是没啥意义的。

CF1467 题解

原文：https://www.cnblogs.com/ycx-akioi/p/sol-cf1467.html