Codeforces Global Round 26

Upsolved：A-G

A. Strange Splitting

考虑 $\min\ne\max$ 的情况，此时只需要 $\min/\max$ 出现次数最少的一种全给一个人即可。

按照题意模拟。

通过记录最小值和最大值进行 DP 转移。

转移过程中顺便记录方案数即可。

去掉末尾 $a$ ，所有合法串一定是最右边一个非 $a$ 位置结尾的后缀，暴力枚举复杂度是调和级数，Hash 判断即可。

不考虑根的特殊贡献，相邻两个点最多贡献一个，于是上界为最大独立集，容易构造。

换根 DP 即可。

长度为 $len$ 的区间值域限制为 $[-len\times m, len\times m]$ 。

值域限制包含可拆分，只用考虑相邻两个位置的限制：

考虑枚举开头一段 $PPPPPS$ 即可求出和，剩下直接 DP 判断。

直观理解答案离 $n$ 不会太远， $ans = n/n - 1$ 容易判断。

对于 $ans = n - 2$ ，可以实现整体向左循环移 $2$ 位，后 $n - 1$ 个数循环右移 $1$ 位，可以镜像。

$n$ 为奇数，可以实现整体向左循环移 $1$ 位，于是可以考虑逐步让 $1\sim i$ 连续，每次将 $i + 1$ 循环移到开头， $1\sim i$ 循环移到末尾。

$n$ 为偶数执行上述或者镜像操作一定能使 $1\sim n$ 连续，但不能保证 $1$ 循环移动到开头，这里是因为操作不改变逆序对奇偶性。

该情况如果不行则 $ans = n - 3$ ，可以把 $n$ 移动到末尾转换成 $n - 1$ 的奇数情况。