CVBB ACM Team

签到题。

签到题。

签到题。

不 WA 就是签到题。

题目大意：给一个 $n\times n$ 的网格，要求你给每个点一个权，使得从左上角仅往右往下的所有 ${2n-2\choose n-1}$ 条路径的权值和各不相同。权 $\le10^{15}$。

题解：考虑所有 $x+y=k$ 的点（在一条副对角线上），给所有可能的路径连续编号，那么位于 $(x,y)$ 的点应当占用 ${x+y\choose x}$ 个连续编号，从右上往左下依次从 $0$ 开始编号。由于 $(x,y)$ 的路径数量必然等于 $(x-1,y)$ 的路径数量加上 $(x,y-1)$ 的路径数量，而且 $(x-1,y)$ 和 $(x,y-1)$ 的编号连续，因而我们比较 $(x-1,y)$ 与 $(x,y-1)$ 拼起来的编号区间与 $(x,y)$ 的编号区间，给 $(x,y)$ 一个合适的权值即可。

题目大意：给一个长为 $n$，单调增的正整数序列 $h$。每次操作时，若 $h_{i}\le h_{i+1}-2$，那么把 $h_{i}$ 加一，$h_{i+1}$ 减一，所有位置同时操作。直到不存在 $h_{i}\le h_{i+1}-2$ 时停止。问最终的序列。

题解：首先证明操作一定终止。考虑 $h_{1},h_{2}-h_{1},\cdots,h_{n}-h_{n-1}$，可见一次操作是将相邻三项分别 $+1,-2,+1$。那么该差分序列的字典序是单调增的。

其次需要证明不论使用何种顺序操作，都会得到相同的最终序列。若序列已经是最终序列，那么显然。否则假设有两种不同的操作序列。那么当前序列一定有一个位置 $\alpha$ 可操作。注意到每次操作都不会使得别的位置不可操作（至多使不可操作变得可操作）那么两个序列都必然在某一位置出现 $\alpha$。基于相同的原因，我们把两个序列的 $\alpha$ 都移到开头不会影响序列的合法性，且不影响最终结果。那么归纳即可。

考虑这样的移动策略，从 $1$ 到 $n$ 依次遍历每个 $i$，每当 $h_{i}>=h_{i-1}+2$ 时，就从 $i-1$ 一直操作到 $1$，当然如果有某个 $h_{j}=h_{j+1}$ 操作会停止。注意这样可以保证 $1\sim i$ 中每对相邻元素相差至多 $1$，因而可以得到最终序列。

我们来证明操作的过程中，相邻相等的元素至多有一对。假设当前没有相邻相等的元素，那么可能导致 $h_{1}=h_{2}$，即操作后至多有一对相邻。假设当前有一对相邻相等的元素，设最右的是 $h_{j}=h_{j+1}$，那么操作完后 $h_{j}<h_{j+1}$，但是 $h_{j+1}$ 可能等于 $h_{j+2}$。那么相邻相等的对数也不会增加。

可以发现满足上述条件的序列是唯一的。

题目大意：给出 $01$ 串 $s,t$，长度 $k\le20$，给出 $m$ 个操作，每次交换 $a_{i},b_{i}$ 的字符。现在对 $s$ 应用一段区间中的操作，求 $s,t$ 最多能有几个相同的位，并求方案。

题解：设区间为 $[l,r]$，那么不妨对 $s,t$ 再共同运用 $[r+1,m]$ 中的操作，不影响最终结果。因此，题目可以修改为，对 $s,t$ 分别应用一段后缀的操作，最多相同的位。当然仍需满足 $s$ 的操作后缀长度比 $t$ 的操作后缀长度大至少 $m$ 的要求。

其次注意到，由于操作不改变 $01$ 数量，因此相同的 $1$ 数量确定后，相同的 $0$ 数量也确定，且它们成正相关。那么我们的优化目标就可改为使得相同的 $1$ 的数量最多。考虑枚举有哪些位 $1$ 相同，求出 $s$ 最少什么时候有这些位，$t$ 最晚什么时候有这些位，再 check 差是否 $\ge m$ 即可。使用 FMT 加速。

题目大意：一种扑克，有 $n$ 张普通牌 $1\sim n$ 和 $m$ 张王。游戏有若干轮，每轮随机把所有牌打乱，然后从上到下抽牌，抽到王停止。把所有普通牌记录下来，然后开始新的一轮。若已经记录了所有普通牌，游戏结束。抽一张牌需要 $1s$，其它操作不需要时间。求游戏结束的期望时间。

题解：若需要求游戏结束的期望轮次，就是简单的 Endless Spin。可以感受到每轮的期望时间是独立的，因此二者乘一下即可。

题目大意：有一个 $n\times m$ 的网格，$(i,j)$ 的点权为 $a_{i}+b_{j}$。给定一个 $x$，$\ge x$ 的点称为好点，$<x$ 的点称为坏点，所有四连通的好点和坏点分别连边。好点的价值定义为好连通块的数量加不包含边界的好连通块数量，坏点同理。定义整个图的价值为好价值减坏价值。对每个 $x$ 求图的价值。

题解：需要观察到一些性质：好图和坏图都是平面图。一个不包含边界的好连通块，必然被一个坏面包含，一个坏面要么不包含好连通块（是个 $2\times2$ 的网格），要么必然包含恰好一个好连通块。反之亦然。

考虑欧拉公式。$V_{1}+F_{1}=E_{1}+C_{1}$，$V_{2}+F_{2}=E_{2}+C_{2}$。设 $Q_{1},Q_{2}$ 表示 $2\times2$ 平面的数量，那么答案为 $C_{1}+F_{2}-Q_{2}-C_{2}-F_{1}+Q_{1}$。两式相减得 $V_{1}+F_{1}-V_{2}-F_{2}=E_{1}+C_{1}-E_{2}-C_{2}$。因此答案为 $V_{1}-V_{2}-E_{1}+E_{2}+Q_{1}-Q_{2}$。

$V$ 较为好求，FFT 即可。关于边数，不妨考虑横边及好点，那么 $a_{i}+b_{j}\ge x\land a_{i}+b_{j+1}\ge x$。即 $a_{i}+\min(b_{j},b_{j+1})\ge x$，那么还是可以使用 FFT 解决。竖边及坏点同理。$2\times 2$ 平面也同理。