https://atcoder.jp/contests/agc022/tasks
E - Median Replace
先考虑如何判断合法性。显然可以贪心的把 \(000\) 删去两个 \(0\)，然后删去剩下的相邻的 \(01\)，看最后是否剩下 \(1\)，第二步可以看作比较剩下的 \(0,1\) 个数
尝试构建成一个 DFA。使用栈维护前面剩下的 \(0,1\)，考虑转移：
- 添加 \(0\)：
- 栈顶为 \(0\)：如果栈顶有两个 \(0\) 那么
pop，否则push(0) - 栈顶为 \(1\)：直接
push(0)
- 栈顶为 \(0\)：如果栈顶有两个 \(0\) 那么
- 添加 \(1\)：
- 栈顶为 \(0\)：此时栈顶的这一段 \(0\) 不可能再形成 \(000\)，可以直接按 \(01\) 删除，即
pop - 栈顶为 \(1\)：直接
push(1)
- 栈顶为 \(0\)：此时栈顶的这一段 \(0\) 不可能再形成 \(000\)，可以直接按 \(01\) 删除，即
如果最后剩下的 \(1\) 比 \(0\) 多那么就合法。通过转移可以看出：任意时刻栈中从底到顶一定是一段 \(1\) 一段 \(0\)，且 \(0\) 的个数 \(<3\)
标签：01,栈顶,pop,剩下,000,push,AGC022 From： https://www.cnblogs.com/401rk8/p/16587000.html