CF1535C
LinkZelda
·
·
题解
$1\leq t\leq 10^4,1 \leq\left\vert s\right\vert\leq2\times10^5,\sum \left\vert s\right\vert\leq2\times10^5$。
- **题解**：
考虑 `dp`，定义 $dp_{i,1/0}$ 表示第 $i$ 位为 $1/0$ ，以 $i$ 为结尾的极长不稳定子段长。
当 $s_i=$`1`，有 $dp_{i,1}=dp_{i-1,0}+1$。
当 $s_i=$`0`，有 $dp_{i,0}=dp_{i-1,1}+1$。
当 $s_i=$`?`，有 $dp_{i,1}=dp_{i-1,0}+1$，$dp_{i,0}=dp_{i-1,1}+1$。
然后我们扫一次 `dp` 数组，把每一个 $\max(dp_{i,1},dp_{i,0})$ 加起来就是答案了。时间复杂度为 $O(\left\vert s\right\vert)$。
- [代码](https://www.luogu.com.cn/paste/dotr7r10)