NOI批量评测 - 记录详情

#	状态分数	耗时	内存占用

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

#include <bits/stdc++.h>

using namespace std;
char s1[100002],s2[100002],t1[100002],t2[100002];
/*
vector<pair<int,int> > tab1;//index,sum
vector<pair<int,int> > tab2;*/

int ca1[100002],ca0[100002],cb1[100002],cb0[100002],inda[100002],indb[100002];

void clear() {
	memset(ca1,0,sizeof(ca1));
	memset(ca0,0,sizeof(ca1));
	memset(cb1,0,sizeof(ca1));
	memset(cb0,0,sizeof(ca1));
	memset(inda,0,sizeof(ca1));
	memset(indb,0,sizeof(ca1));
}

void solve() {
	int n,i;
	int sa1,sa0,sb1,sb0;
	int use1,use0;
	int pa=0,pb=0;
	int ans = 0;
	int suba=0,subb=0;
	int L;
	cin>>n;
	cin>>s1;
	cin>>s2;
	cin>>t1;
	cin>>t2;
	sa1=sa0=sb1=sb0=0;
	
	
	for(i=0;i<n;i++) {
		
		if(t1[i] == '0') {
			ca1[suba] = sa1;
			ca0[suba] = sa0;
			inda[suba] = i;
			suba++;
			sa1=sa0=0;
		}
		else {
			if(s1[i] == '1') sa1++;
			else sa0++;
		}
		if(t2[i] == '0') {
			cb1[subb] = sb1;
			cb0[subb] = sb0;
			indb[subb] = i;
			subb++;
			sb1=sb0=0;
		}
		else {
			if(s2[i] == '1') sb1++;
			else sb0++;
		}
		///printf("%d  %d %d  \n",suba,sa1,sa0);
		if(i == n-1) {
			ca1[suba] = sa1;
			ca0[suba] = sa0;
			inda[suba] = n;
			s1[n] = '0';
			suba++;
			
			cb1[subb] = sb1;
			cb0[subb] = sb0;
			indb[subb] = n;
			s2[n] = '1';
			subb++;
		}
		
		
	}
	while(pa < suba || pb < subb) {
		if(inda[pa] < indb[pb]) {
			
				
			L = ca1[pa] + ca0[pa]+1;
			use1 = ca1[pa] + s1[inda[pa]] - '0';
			use0 = L - use1;
			
			ans += min(use1,cb1[pb]) + min(use0,cb0[pb]);
			//cout<<min(use1,cb1[pb]) + min(use0,cb0[pb])<<endl;
			if(use1 > cb1[pb]) {
				//cb0[pb] -= use1 - cb1[pb];
				cb0[pb] -= L - cb1[pb];
				cb1[pb] = 0;
			} else if(use0 > cb0[pb]) {
				cb1[pb] -= L - cb0[pb];
				cb0[pb] = 0;
			} else {
				cb1[pb] -= use1;
				cb0[pb] -= use0;
			}
			pa++;
		} else if(inda[pa] > indb[pb]) {
			L = cb1[pb] + cb0[pb]+1;
			use1 = cb1[pb] + s2[indb[pb]] - '0';
			use0 = L - use1;
			
			ans += min(use1,ca1[pa]) + min(use0,ca0[pa]);
			//cout<<min(use1,cb1[pb]) + min(use0,cb0[pb])<<endl;
			if(use1 > ca1[pa]) {
				ca0[pa] -= L - ca1[pa];
				ca1[pa] = 0;
			} else if(use0 > ca0[pa]) {
				ca1[pa] -= L - ca0[pa];
				ca0[pa] = 0;
			} else {
				ca1[pa] -= use1;
				ca0[pa] -= use0;
			}
			pb++;
		} else {
			L = cb1[pb] + cb0[pb];
			use1 = cb1[pb];
			use0 = L - use1;
			
			ans += min(use1,ca1[pa]) + min(use0,ca0[pa]);
			//cout<<min(use1,ca1[pa]) + min(use0,ca0[pa])<<endl;
			if(s1[inda[pa]] == s2[indb[pb]]) ans++;
			if(inda[pa] == n) break;
			pa++;
			pb++;
			
			
		}
	}
	cout<<ans<<endl;
}

int main() {
	freopen("edit.in","r",stdin);
	freopen("edit.out","w",stdout);
	int T;
	
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>T;
	while(T--) {
		//if(T==6) break;
		//clear();
		solve(); 
	} 
	fclose(stdin);
	fclose(stdout);
	return 0;
}

递交者: TJ-0086
题目: NOIP2024AGF NOIP2024AGF
比赛: 【官方数据 TJ】 NOIP2024 批量测试
语言: C++14(O2)
代码长度: 2.8 KiB
递交时间: 2024-12-6 16:41:59
评测时间: 2024-12-6 16:46:23

分数: 100
总耗时: 94ms
峰值时间: 12ms
峰值内存: 1.8 MiB

100 Accepted

代码

信息

100 Accepted

代码

信息

还没有账户？

登录