如何在不动脑的情况下解决此题

abcdeffa · 2025-10-31 14:41:04 · 题解

尝试进行一种直观的 dp。把 2 改为 0/1，则若长度为 i 的前缀消剩下了长度 j，那么一定是长度为 j 的 01 交替串，并且如果知道最后一位是什么数字，就可以知道当前消剩下的串的结构。

并且，可能剩下的可行长度一定是一个区间。于是考虑设 f_{i, c} / g_{i, c} 表示长度为 i 的前缀，最后一位是数字 c，前缀串能消出来的 01 交替串的最大 / 最小长度。

这样就并不需要想到翻转偶数位、讨论奇偶性之类的 trick，很可惜十余篇题解几乎都在复读官解，并未想到 dp 的可行性。

时间复杂度 O(\sum n)，参考实现如下。

#include<bits/stdc++.h>
using namespace std;
constexpr int N = 2e5 + 5;
int T, num[N], f[N][2], g[N][2];
string S;
int main() {
    cin >> T;
    for (; T--;) {
        vector <int> a;
        cin >> S;
        for (int i = 0; S[i]; ++i) {
            num[i] = S[i] - '0';
            if (a.empty())
                a.push_back(num[i]);
            else if (num[i] <= 1 && num[i] == a.back())
                a.pop_back();
            else a.push_back(num[i]);
        }
        int n = a.size() - 1;
        if (a.empty()) {
            cout << "0\n";
            continue;
        }
        for (int i = 0; i <= n; ++i)
            f[i][0] = f[i][1] = g[i][0] = g[i][1] = -1;
        if (a[0] == 0 || a[0] == 2) f[0][0] = g[0][0] = 1;
        if (a[0] == 1 || a[0] == 2) f[0][1] = g[0][1] = 1;
        for (int i = 1; i <= n; ++i) {
            if (a[i] == 0) {
                if (~f[i - 1][1])
                    f[i][0] = f[i - 1][1] + 1;
                else if (g[i - 1][0] == 0)
                    f[i][0] = 1;
                else f[i][0] = -1;

                if (g[i - 1][0] == 0)
                    g[i][0] = 1;
                else if (~g[i - 1][1])
                    g[i][0] = g[i - 1][1] + 1;
                else g[i][0] = -1;

                if (f[i - 1][0] >= 1)
                    f[i][1] = f[i - 1][0] - 1;
                else f[i][1] = -1;

                if (g[i - 1][0] >= 1)
                    g[i][1] = g[i - 1][0] - 1;
                else if (f[i - 1][0] >= 1)
                    g[i][1] = f[i - 1][0] & 1 ^ 1;
                else g[i][1] = -1;
            }
            if (a[i] == 1) {
                if (f[i - 1][1] >= 1)
                    f[i][0] = f[i - 1][1] - 1;
                else f[i][0] = -1;

                if (g[i - 1][1] >= 1)
                    g[i][0] = g[i - 1][1] - 1;
                else if (f[i - 1][1] >= 1)
                    g[i][0] = f[i - 1][1] & 1 ^ 1;
                else g[i][0] = -1;

                if (~f[i - 1][0])
                    f[i][1] = f[i - 1][0] + 1;
                else if (g[i - 1][1] == 0)
                    f[i][1] = 1;
                else f[i][1] = -1;

                if (g[i - 1][1] == 0)
                    g[i][1] = 1;
                else if (~g[i - 1][0])
                    g[i][1] = g[i - 1][0] + 1;
                else g[i][1] = -1;
            }
            if (a[i] == 2) {
                if (~f[i - 1][1])
                    f[i][0] = f[i - 1][1] + 1;
                else if (g[i - 1][0] == 0)
                    f[i][0] = 1;
                else f[i][0] = -1;

                if (g[i - 1][0] == 0)
                    g[i][0] = 1;
                else if (~g[i - 1][1])
                    g[i][0] = g[i - 1][1] + 1;
                else g[i][0] = -1;

                if (~f[i - 1][0])
                    f[i][1] = f[i - 1][0] + 1;
                else if (g[i - 1][1] == 0)
                    f[i][1] = 1;
                else f[i][1] = -1;

                if (g[i - 1][1] == 0)
                    g[i][1] = 1;
                else if (~g[i - 1][0])
                    g[i][1] = g[i - 1][0] + 1;
                else g[i][1] = -1;

                if (g[i - 1][1] >= 1)
                    g[i][0] = min(g[i - 1][1] - 1, ~g[i][0] ? g[i][0] : inf);
                else if (f[i - 1][1] >= 1)
                    g[i][0] = min(f[i - 1][1] & 1 ^ 1, ~g[i][0] ? g[i][0] : inf);

                if (g[i - 1][0] >= 1)
                    g[i][1] = min(g[i - 1][0] - 1, ~g[i][1] ? g[i][1] : inf);
                else if (f[i - 1][0] >= 1)
                    g[i][1] = min(f[i - 1][0] & 1 ^ 1, ~g[i][1] ? g[i][1] : inf);
            }
        }
        cout << min(~g[n][0] ? g[n][0] : inf, ~g[n][1] ? g[n][1] : inf) << endl;
    }
}