社区讨论

NOIP2024T1求助,玄关

P11361[NOIP2024] 编辑字符串参与者 3已保存回复 8

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
8 条
当前快照
1 份
快照标识符
@mhj1rz2t
此快照首次捕获于
2025/11/03 19:19
4 个月前
此快照最后确认于
2025/11/03 19:19
4 个月前
查看原帖
思路大概就是先分段,彼此可以交换的在一起,固定的单独成段,然后去贪心的匹配
可能是匹配的思路有问题,大样例过不去,能不能帮忙看看是哪里有问题,谢谢了
CPP
#include<bits/stdc++.h>
using namespace std;
int ttt, len;
string a, b, c, d;
int jsb[100010][3], jsa[100010][3];
int xb1[100010], xb2[100010];
int main()
{
    scanf("%d", &ttt);
    while(ttt--)
    {
        scanf("%d", &len);
        cin >> a >> b >> c >> d;
        int cntb = 0, cnta = 0;
        for(int i = 0; i < len; i++) 
        {
            jsb[i][0] = jsb[i][1] = 0;
            xb1[i] = xb2[i] = 0;
        }
        for(int i = 0; i < len; i++)
        {
            if((c[i] == '1') && ((i == 0) || ((i != 0) && (c[i-1] != '1')))) if((((i+1) < len) && (c[i+1] != '1')) || ((i+1) == len)) c[i] = '0'; 
            if((i != 0) && (c[i] == c[i-1]) && (c[i] == '1'))  jsa[cnta][a[i]-'0']++;
            else jsa[++cnta][a[i]-'0']++;
            xb1[i] = cnta;
        }
        for(int i = 0; i < len; i++)
        {
            if((d[i] == '1') && ((i == 0) || ((i != 0) && (c[i-1] != '1')))) if((((i+1) < len) && (d[i+1] != '1')) || ((i+1) == len)) d[i] = '0'; 
            if((i!= 0) && (d[i] == '1') && (d[i] == d[i-1]))  jsb[cntb][b[i]-'0']++;
            else jsb[++cntb][b[i]-'0']++;
            xb2[i] = cntb; 
        }
        int ans = 0;
        for(int i = 0; i < len; i++)
        {
            if(jsa[xb1[i]][1]) 
            {
                if(jsb[xb2[i]][1])
                {
                    ans++;
                    jsb[xb2[i]][1]--;
                    jsa[xb1[i]][1]--;
                }
            }
            else if(jsa[xb1[i]][0])
            {
                if(jsb[xb2[i]][0]) 
                {
                    ans++;
                    jsa[xb1[i]][0]--;
                    jsb[xb2[i]][0]--;
                }
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

回复

8 条回复,欢迎继续交流。

正在加载回复...