NOI批量评测 - 记录详情

#	状态分数	耗时	内存占用

#1	Accepted 5	2ms	404 KiB
#2	Accepted 5	2ms	448 KiB
#3	Accepted 5	1ms	404 KiB
#4	Accepted 5	1ms	404 KiB
#5	Accepted 5	2ms	404 KiB
#6	Accepted 5	2ms	404 KiB
#7	Accepted 5	23ms	3.9 MiB
#8	Accepted 5	22ms	3.8 MiB
#9	Accepted 5	1ms	404 KiB
#10	Accepted 5	1ms	404 KiB
#11	Accepted 5	23ms	3.9 MiB
#12	Accepted 5	22ms	3.9 MiB
#13	Accepted 5	2ms	448 KiB
#14	Accepted 5	2ms	404 KiB
#15	Accepted 5	25ms	3.8 MiB
#16	Accepted 5	23ms	3.7 MiB
#17	Accepted 5	1ms	404 KiB
#18	Accepted 5	2ms	408 KiB
#19	Accepted 5	23ms	3.9 MiB
#20	Accepted 5	23ms	3.9 MiB

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;

int n;
char s[2][N],t[2][N];
bool v[N];

struct DSU{
    int fa[N],s0[N],s1[N],sz[N];
    void init(){
        for(int i=1;i<=n;i++)fa[i]=i,sz[i]=1;
    }
    int find(int x){
        return fa[x]==x?x:fa[x]=find(fa[x]);
    }
    bool check(int x){
        return sz[find(x)]==1;
    }
    void merge(int x,int y){
        x=find(x),y=find(y);
        if(x==y)return;
        fa[y]=x;
        s0[x]+=s0[y];
        s1[x]+=s1[y];
        sz[x]+=sz[y];
    }
}DSU[2];

void solve(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)v[i]=0;
    DSU[0].init(),DSU[1].init();
    scanf("%s%s%s%s",s[0]+1,s[1]+1,t[0]+1,t[1]+1);
    for(int i=1;i<=n;i++)DSU[0].s0[i]=s[0][i]=='0',DSU[0].s1[i]=s[0][i]=='1';
    for(int i=1;i<=n;i++)DSU[1].s0[i]=s[1][i]=='0',DSU[1].s1[i]=s[1][i]=='1';

    for(int i=2;i<=n;i++){
        if(t[0][i]=='1'&&t[0][i-1]=='1')DSU[0].merge(i-1,i);
        if(t[1][i]=='1'&&t[1][i-1]=='1')DSU[1].merge(i-1,i);
    }
    // for(int i=1;i<=n;i++)printf("%d ",DSU[0].check(i));puts("");
    // for(int i=1;i<=n;i++)printf("%d ",DSU[1].check(i));puts("");
    

    int ans=0;
    for(int i=1;i<=n;i++){
        if(v[i])continue;
        if(DSU[0].check(i)&&DSU[1].check(i)){
            if(s[0][i]==s[1][i])ans++;
        }
    }
    // printf("%d\n",ans);

    for(int i=1;i<=n;i++){
        if(v[i])continue;
        if(!DSU[0].check(i)&&DSU[1].check(i)){
            int x=DSU[0].find(i);
            if(DSU[0].s1[x]&&s[1][i]=='1'){
                ans++;
                DSU[0].s1[x]--;
                v[i]=1;
            }else if(DSU[0].s0[x]&&s[1][i]=='0'){
                ans++;
                DSU[0].s0[x]--;
                v[i]=1;
            }
        }else if(DSU[0].check(i)&&!DSU[1].check(i)){
            int y=DSU[1].find(i);
            if(s[0][i]=='1'&&DSU[1].s1[y]){
                ans++;
                DSU[1].s1[y]--;
                v[i]=1;
            }else if(s[0][i]=='0'&&DSU[1].s0[y]){
                ans++;
                DSU[1].s0[y]--;
                v[i]=1;
            }
        }
    }
    // printf("%d\n",ans);

    for(int i=1;i<=n;i++){
        if(v[i])continue;
        if(!DSU[0].check(i)&&!DSU[1].check(i)){
            int x=DSU[0].find(i),y=DSU[1].find(i);
            if(DSU[0].s0[x]&&DSU[1].s0[y]){
                ans++;
                DSU[0].s0[x]--,DSU[1].s0[y]--;
                v[i]=1;
            }else if(DSU[0].s1[x]&&DSU[1].s1[y]){
                ans++;
                DSU[0].s1[x]--,DSU[1].s1[y]--;
                v[i]=1;
            }
        }
    }
    printf("%d\n",ans);
}

int main(){
    freopen("edit.in","r",stdin);
    freopen("edit.out","w",stdout);
    int T;scanf("%d",&T);
    while(T--)solve();
    return 0;
}

递交者: 357
题目: NOIP2024A NOIP2024A
比赛: 【民间数据】NOIP2024 批量测试TT
语言: C++14(O2)
代码长度: 2.7 KiB
递交时间: 2024-12-1 11:55:32
评测时间: 2024-12-1 12:10:29

分数: 100
总耗时: 204ms
峰值时间: 25ms
峰值内存: 3.9 MiB

100 Accepted

代码

信息

100 Accepted

代码

信息

还没有账户？

登录