NOI批量评测 - 记录详情

#	状态分数	耗时	内存占用

#1	Accepted 5	2ms	404 KiB
#2	Accepted 5	2ms	448 KiB
#3	Accepted 5	1ms	408 KiB
#4	Accepted 5	1ms	420 KiB
#5	Accepted 5	2ms	404 KiB
#6	Accepted 5	3ms	444 KiB
#7	Accepted 5	88ms	7 MiB
#8	Accepted 5	85ms	6.8 MiB
#9	Accepted 5	3ms	408 KiB
#10	Accepted 5	3ms	404 KiB
#11	Accepted 5	86ms	7.2 MiB
#12	Accepted 5	87ms	7 MiB
#13	Accepted 5	3ms	404 KiB
#14	Accepted 5	3ms	404 KiB
#15	Accepted 5	93ms	7.7 MiB
#16	Accepted 5	87ms	7.3 MiB
#17	Accepted 5	3ms	484 KiB
#18	Accepted 5	3ms	532 KiB
#19	Accepted 5	89ms	7.1 MiB
#20	Accepted 5	88ms	7 MiB

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll rd(){
    ll re=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){
        re=re*10+ch-'0';
        ch=getchar();
    }
    return re*f;
}
const int N = 1e5+5;

int T;
int n;
string s1,s2;
int t1[N],t2[N];
int cnt[3][N][5];
int ans;
int f[N][3];
int find(int x,int qwe){return f[x][qwe]==x?x:f[x][qwe]=find(f[x][qwe],qwe);}
void merge(int x,int y,int qwe){
    int fx=find(x,qwe),fy=find(y,qwe);
    if(fx==fy) return ;
    cnt[qwe][fx][0]+=cnt[qwe][fy][0];
    cnt[qwe][fx][1]+=cnt[qwe][fy][1];
    cnt[qwe][fy][0]=cnt[qwe][fy][1]=0;
    f[fy][qwe]=fx;
}

int main(){
    freopen("edit.in","r",stdin);
    freopen("edit.out","w",stdout);
    
    T=rd();
    while(T--){
        n=rd();ans=0;
        cin>>s1>>s2;s1=' '+s1,s2=' '+s2;
        for(int i=1;i<=n;i++){
            cnt[1][i][0]=cnt[1][i][1]=0;f[i][1]=f[i][2]=i;
            cnt[2][i][0]=cnt[2][i][1]=0;
            cnt[1][i][s1[i]-'0']++;
            cnt[2][i][s2[i]-'0']++;
        }
        for(int i=1;i<=n;i++){
            char x;cin>>x;
            t1[i]=0;
            if(x=='1') t1[i]=1;
        }
        for(int i=1;i<=n;i++){
            char x;cin>>x;
            t2[i]=0;
            if(x=='1') t2[i]=1;
        }
        // for(int i=1;i<=n;i++) cout<<cnt[1][i][1];
        // for(int i=1;i<=n;i++) cout<<cnt[2][i][1];
        // for(int i=1;i<=n;i++) cout<<s1[i];
        // cout<<'\n';
        // for(int i=1;i<=n;i++) cout<<s2[i];
        // cout<<'\n';
        // for(int i=1;i<=n;i++) cout<<t1[i];
        // cout<<'\n';
        // for(int i=1;i<=n;i++) cout<<t2[i];
        // cout<<'\n';
        for(int i=2;i<=n;i++){
            if(t1[i]==1&&t1[i-1]==1) merge(i,i-1,1);
            if(t2[i]==1&&t2[i-1]==1) merge(i,i-1,2);
        }
        // for(int i=1;i<=n;i++){
        //     cout<<find(i,1)<<' '<<cnt[1][find(i,1)][1]<<'\n';
        //     cout<<find(i,2)<<' '<<cnt[2][find(i,2)][1]<<'\n';
        // }
        for(int i=1;i<=n;i++){
            int f1=find(i,1),f2=find(i,2);
            if(cnt[1][f1][1]&&cnt[2][f2][1]){
                cnt[1][f1][1]--,cnt[2][f2][1]--;ans++;
                continue;
            }
            if(cnt[1][f1][0]&&cnt[2][f2][0]){
                cnt[1][f1][0]--,cnt[2][f2][0]--;ans++;
                continue;
            }
            if(cnt[1][f1][0]){
                cnt[1][f1][0]--,cnt[2][f2][1]--;
                continue;
            }
            cnt[1][f1][1]--,cnt[2][f2][0]--;
        }
        
        printf("%d\n",ans);
    }
    
    return 0;
}
/*
1s
512Mib

1
6
011101
111010
111010
101101
4
*/

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

分数: 100
总耗时: 730ms
峰值时间: 93ms
峰值内存: 7.7 MiB

100 Accepted

代码

信息

100 Accepted

代码

信息

还没有账户？

登录