NOI批量评测 - 记录详情

#	状态分数	耗时	内存占用

#1	Accepted 5	1ms	404 KiB
#2	Accepted 5	1ms	404 KiB
#3	Accepted 5	1ms	404 KiB
#4	Accepted 5	1ms	448 KiB
#5	Accepted 5	1ms	404 KiB
#6	Accepted 5	1ms	404 KiB
#7	Accepted 5	8ms	1.8 MiB
#8	Accepted 5	10ms	1.7 MiB
#9	Accepted 5	1ms	404 KiB
#10	Accepted 5	1ms	416 KiB
#11	Accepted 5	9ms	3 MiB
#12	Accepted 5	8ms	1.7 MiB
#13	Accepted 5	1ms	404 KiB
#14	Accepted 5	1ms	404 KiB
#15	Accepted 5	7ms	1.3 MiB
#16	Accepted 5	6ms	1 MiB
#17	Accepted 5	1ms	448 KiB
#18	Accepted 5	1ms	404 KiB
#19	Accepted 5	11ms	3.1 MiB
#20	Accepted 5	10ms	2.2 MiB

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
string s1,s2,t1,t2;
const int N=1e5;
int d1[N+5],d2[N+5];
int ccf1[N+5],ccf2[N+5];
void solve(){
    cin>>n>>s1>>s2>>t1>>t2;
    s1=' '+s1;
    s2=' '+s2;
    t1=' '+t1;
    t2=' '+t2;
    int cnt1=0,cnt2=0,len1=0,len2=0,num1=0,num2=0;
    for(int i=1;i<=n;i++){
        if(t1[i]=='0'){
            if(len1){
                d1[++cnt1]=len1;
                ccf1[cnt1]=num1;
            }
            d1[++cnt1]=1;
            ccf1[cnt1]=(s1[i]-'0');
            len1=num1=0;
        }
        else{
            num1+=(s1[i]-'0');
            len1++;
        }
        if(t2[i]=='0'){
            if(len2){
                d2[++cnt2]=len2;
                ccf2[cnt2]=num2;
            }
            d2[++cnt2]=1;
            ccf2[cnt2]=(s2[i]-'0');
            len2=num2=0;
        }
        else{
            num2+=(s2[i]-'0');
            len2++;
        }
    }
    if(len1){
        d1[++cnt1]=len1;
        ccf1[cnt1]=num1;
    }
    if(len2){
        d2[++cnt2]=len2;
        ccf2[cnt2]=num2;
    }
    int l=1,r=1;
    int ans=0;
    while(l<=cnt1&&r<=cnt2){
        if(d1[l]>=d2[r]){
            d1[l]-=d2[r];
            if(ccf1[l]>=ccf2[r]){
                ans+=max(0ll,ccf1[l]-ccf2[r]-d1[l]);
                ccf1[l]=min(ccf1[l]-ccf2[r],d1[l]);
            }
            else{
                ans+=ccf2[r]-ccf1[l];
                ccf1[l]=0;
            }
            r++;
        }
        if(d1[l]<=d2[r]){
            d2[r]-=d1[l];
            if(ccf2[r]>=ccf1[l]){
                ans+=max(0ll,ccf2[r]-ccf1[l]-d2[r]);
                ccf2[r]=min(ccf2[r]-ccf1[l],d2[r]);
            }
            else{
                ans+=ccf1[l]-ccf2[r];
                ccf2[r]=0;
            }
            l++;
        }
    }
    cout<<n-ans<<"\n";
}
signed main(){
    freopen("edit.in","r",stdin);
    freopen("edit.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}
/*
呜呜呜，T1 不会做。

AFO 了。
    for(int i=1;i<=cnt1;i++){
        cout<<d1[i]<<" "<<ccf1[i]<<"\n";
    }
1
10
0110111100
1111111100
1110000100
0110111011
*/

递交者: HN-0282
题目: NOIP2024AGF NOIP2024AGF
比赛: 【官方数据 HN】 NOIP2024 批量测试
语言: C++14(O2)
代码长度: 2.1 KiB
递交时间: 2024-12-6 17:25:45
评测时间: 2024-12-6 17:26:05

分数: 100
总耗时: 85ms
峰值时间: 11ms
峰值内存: 3.1 MiB

100 Accepted

代码

信息

100 Accepted

代码

信息

还没有账户？

登录