自动搬运

查看原文

来自洛谷，原作者为

	panyf **

搬运于2025-08-24 22:36:48，当前版本为作者最后更新于2022-03-11 14:53:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑从前到后 dp。当前 dp 了长度为 $i$ 的前缀，记 $f_{u_1,u_2,u_3,v_0,v_1,v_2,v_3}$ 表示第 $i-2$ 位为 $u_1$，第 $i-1$ 位为 $u_2$，第 $i$ 位为 $u_3$,长度为 $i-3$ 的前缀能否匹配（$v_0=1$ 表示能匹配，$v_0=0$ 表示不能），$i-2$ 能否匹配，$i-1$ 能否匹配，$i$ 能否匹配。转移时枚举第 $i+1$ 位的值，判断 $[i-2,i+1],[i,i+1],[i+1,i+1]$ 这三个区间能否匹配。时间复杂度 $O(n)$。

算一下这个做法的常数，状态数 $2^4\times 9^3$，转移数 $9$。显然 TLE。

考虑优化。首先容易发现若 $v_0=0$，那么 $u_1$ 就没用了，就不用记录了。若 $v_0=v_1=0$，那么 $u_2$ 也就没用了。若 $v_0=v_1=v_2=0$，那么 $u_3$ 也就没用了，若 $v_0=v_1=v_2=v_3=0$，那么这个状态不合法。但是 $v_0=1$ 的时候还是要记 $u_1,u_2,u_3$，状态数只减少了不到一半。

若 $v_0=1$，但是 $u_1,u_2,u_3$ 再加上任何一个数，都不能和 $[i-2,i+1]$ 匹配上，那么可以把 $v_0$ 改成 $0$。或者如果 $[i-2,i+1]$ 的数不在一个正方形内，也可以把 $v_0$ 改成 $0$。同理 $v_1,v_2$ 也可以这样做。

加上这两个优化以后，再分析一下状态数。若 $v_0=1$，那么 $u_1,u_2,u_3$ 一定是从数字串的区间 $[i-2,i+1]$ 中选出三个数，有 $24$ 种方案，并且 $v_1$ 一定等于 $0$（因为），$v_2,v_3$ 不确定，有 $4\times 24=96$ 种方案。若 $v_0=0,v_1=1$，则 $u_2,u_3$ 一定是 $[i-1,i+2]$ 中选出的两个数，有 $12$ 种方案，$v_2,v_3$ 不确定，有 $4\times 12=48$ 种方案。若 $v_0=v_1=0,v_2=1$，有 $2\times 4=8$ 种方案。若 $v_0=v_1=v_2=0,v_3=1$，有 $1$ 种方案。总状态数就是 $96+48+8+1=153$。实际上跑不满，按照官方题解的说法数据中状态不超过 $50$。可以写一个哈希表压缩状态。

$10\times 100000\times 153\times 9\approx 1.4\times 10^9$，然后时限 $4s$，就过了。