本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-19 15:19:48

记录

ABCD 切，E 不会，后来发现是结论题。（上紫了啊）

题解

A. Diverse Game

显然把每个数增加 $1$，$nm$ 变成 $1$，除 $n=m=1$ 外均有解。

B. Fun Game

首先发现只用一位去修改 $s_x$ 影响最小，所以先找到 $s$ 中第一个 $1$ 的位置 $p$。那么对于所有 $x>p$ 的 $s_x$ 都可以通过选以其为结尾的 $p$ 个字符来单点修改，最后 $s_p$ 也可以通过选前 $p$ 个来变成 $1$。所以当且仅当 $s$ 中与 $t$ 不同的位置均在第一个 $1$ 之后就合法，否则非法。

C. Hungry Games

考虑枚举 $l$，求出答案非零的 $r$ 数量。那么设 $f_i$ 表示以 $i$ 为 $l$ 时后面答案为 $0$ 的 $r$ 数量，则 $f_i=f_{nxt_i+1}+1$，其中 $nxt_i$ 表示从 $l$ 开始取到这一位正好大于 $x$，而取到上一位不大于。这个东西在前缀和上二分一下就行，对所有的 $n-i+1-f_i$ 求和即为答案。

D. Funny Game

倒着考虑，也就是从 $n-1$ 一直到 $1$。发现 $i\mid (a_u-a_v)$ 等价于 $a_u \equiv a_v\mod i$，而对 $i$ 取模的结果有 $i$ 种，此时有 $i+1$ 个连通块，根据抽屉原理一定能连出一条边。所以倒着考虑的时候暴力找到一对不连通的合法点连起来即可。

赛时对每一种余数分别平方找的，时间复杂度好像 $O(n^3)$，但跑得很快。其实如果对于每一组，若第一个与其他的都在同一连通块就可以跳出了，这样复杂度就是 $O(n^2)$ 的了，150ms 减到了 100ms。