题解：P11361 [NOIP2024] 编辑字符串

wbh20090611 · 2024-11-30 18:10:17 · 题解

主要思路

算法

• 贪心
• 前缀和

具体思路

• 以每个 0 作为端点分出区间。
• 在每个区间内做后缀和，相当于把区间内的所有数全部用交换堆到第一个数上，在一个一个放回来。
• 不难看出：在既可以放 1 也可以放 0 时，总贡献是一样的，因此，随便去一个即可。

代码实现

考场上写了 100 多行的代码，现在重新打过了：

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int T, n, cnt1[N][3], cnt2[N][3], a[3], b[3], ans;
char s1[N], s2[N], s3[N], s4[N];
int main()
{
    freopen("edit.in","r",stdin);
    freopen("edit.out","w",stdout);
    cin >> T;
    while(T--)
    {
        scanf("%d%s%s%s%s", &n, s1 + 1, s2 + 1, s3 + 1, s4 + 1);
        s3[0] = s4[0] = s3[n + 1] = s4[n + 1] = '0';
        // 记得清零 
        memset(cnt1, 0, sizeof cnt1);
        memset(cnt2, 0, sizeof cnt2);
        for (int i = 1; i <= n; i++) // 特判，要是左右都是零，自己自然也动不了 
        {
            if (s3[i - 1] == s3[i + 1] && s3[i - 1] == '0')
                s3[i] = '0';
            if (s4[i - 1] == s4[i + 1] && s4[i - 1] == '0')
                s4[i] = '0';
        }
        // 求每个连续 '1' 区间内的后缀和 
        for (int i = n; i > 0; i--)
        {
            if (s3[i] == '1')
                if (s3[i + 1] != '0')
                    cnt1[i][0] = cnt1[i + 1][0],
                    cnt1[i][1] = cnt1[i + 1][1],
                    cnt1[i][s1[i] - '0']++;
                else
                    cnt1[i][s1[i] - '0'] = 1;
            if (s4[i] == '1')
                if (s4[i + 1] != '0')
                    cnt2[i][0] = cnt2[i + 1][0],
                    cnt2[i][1] = cnt2[i + 1][1],
                    cnt2[i][s2[i] - '0']++;
                else
                    cnt2[i][s2[i] - '0'] = 1;
        } 
        a[0] = cnt1[1][0];
        a[1] = cnt1[1][1];
        b[1] = cnt2[1][1];
        b[0] = cnt2[1][0];
        ans = 0;
        // 使用计数器 a, b 记录后缀和 
        for (int i = 1; i <= n; i++)
        {
            if (s3[i] == '0' && s4[i] == '0') // 两个都是边界 
            {
                //直接把计数器 a, b 改成下一个点的后缀和 
                a[0] = cnt1[i + 1][0];
                a[1] = cnt1[i + 1][1];
                b[0] = cnt2[i + 1][0];
                b[1] = cnt2[i + 1][1];
                if (s1[i] == s2[i]) //相同就累计答案 
                    ans++;
            }
            else if (s3[i] == '0')
            {
                a[0] = cnt1[i + 1][0];
                a[1] = cnt1[i + 1][1];
                if (b[s1[i] - '0'] > 0)
                    b[s1[i] - '0']--, ans++;
            }
            else if (s4[i] == '0')
            {
                b[0] = cnt2[i + 1][0];
                b[1] = cnt2[i + 1][1];
                if (a[s2[i] - '0'] > 0)
                    a[s2[i] - '0']--, ans++;
            }
            else
            {
                if (a[0] > 0 && b[0] > 0)
                    ans++, a[0]--, b[0]--;
                else if (a[1] > 0 && b[1] > 0)
                    ans++, a[1]--, b[1]--;
            }
        }
        printf("%d\n", ans);
    }
    fclose(stdin);
    fclose(stdout);
    return 0; // 这是个好习惯，特别是到了比赛的时候 
}