关于此题的一个神奇做法

去年T1看错题目浪费近两个小时后成功成为废物AFOer，后来一直没看自己的代码，今天心血来潮翻出来看了一下觉得自己的做法很离谱……

大概就是一个应该是假掉的贪心，但是沿着这个贪心操作并反复交换重复操作最后是可以AC的，大概重复10遍就可以，时间还是很宽裕的

CPP

#include <bits/stdc++.h>
using namespace std;
int T,n;
string s1,s2,t1,t2;
int c[3][2];
void solve() {
	memset(c,0,sizeof(c));
	vector<pair<int,int>>op1,op2;
	int ans=0,reg=0;
	cin >> n >> s1 >> s2 >> t1 >> t2;
	int cnt=0,lst=-1;
	for (int i=0;i<n;i++) {
		if (t1[i]=='1') {
			cnt++;
			if (cnt==1) lst=i;
		}
		else {
			cnt=0;
			if (lst>=0&&i-1-lst+1>=2) op1.push_back(make_pair(lst,i-1));
			lst=-1;
		}
	}
	if (cnt>0&&lst>=0&&n-1-lst+1>=2) {
		op1.push_back(make_pair(lst,n-1));
	}
	/****************************/
	cnt=0,lst=-1;
	for (int i=0;i<n;i++) {
		if (t2[i]=='1') {
			cnt++;
			if (cnt==1) lst=i;
		}
		else {
			cnt=0;
			if (lst>=0&&i-1-lst+1>=2) op2.push_back(make_pair(lst,i-1));
			lst=-1;
		}
	}
	if (cnt>0&&lst>=0&&n-1-lst+1>=2) {
		op2.push_back(make_pair(lst,n-1));
	}
	for (auto now:op1){
		int l=now.first,r=now.second;
		int c0=0,c1=0;
		for (int i=l;i<=r;i++) {
			if (s1[i]=='0') c0++;
			else c1++;
		}
		for (int i=l;i<=r;i++) {
			if (s2[i]=='0') {
				if (c0>0) {
					c0--;
					s1[i]='0';
				}
				else {
					c1--;
					s1[i]='1';
				}
			}
			else {
				if (c1>0) {
					c1--;
					s1[i]='1';
				}
				else {
					c0--;
					s1[i]='0';
				}
			}
		}
	}
	for (auto now:op2){
		int l=now.first,r=now.second;
		int c0=0,c1=0;
		for (int i=l;i<=r;i++) {
			if (s2[i]=='0') c0++;
			else c1++;
		}
		for (int i=l;i<=r;i++) {
			if (s1[i]=='0') {
				if (c0>0) {
					c0--;
					s2[i]='0';
				}
				else {
					c1--;
					s2[i]='1';
				}
			}
			else {
				if (c1>0) {
					c1--;
					s2[i]='1';
				}
				else {
					c0--;
					s2[i]='0';
				}
			}
		}
	}
	for (int i=0;i<n;i++) {
		if (s1[i]==s2[i]) ans++;
	}
	double st=clock();
	int ccnt=0;
	while(true) {
		reg=max(reg,ans);
		ans=0;
		swap(s1,s2);
		swap(t1,t2);
		cnt=0,lst=-1;
		op1.clear(),op2.clear();
		for (int i=0;i<n;i++) {
			if (t2[i]=='1') {
				cnt++;
				if (cnt==1) lst=i;
			}
			else {
				cnt=0;
				if (lst>=0&&i-1-lst+1>=2) op2.push_back(make_pair(lst,i-1));
				lst=-1;
			}
		}
		if (cnt>0&&lst>=0&&n-1-lst+1>=2) {
			op2.push_back(make_pair(lst,n-1));
		}
		for (auto now:op1){
			int l=now.first,r=now.second;
			int c0=0,c1=0;
			for (int i=l;i<=r;i++) {
				if (s1[i]=='0') c0++;
				else c1++;
			}
			for (int i=l;i<=r;i++) {
				if (s2[i]=='0') {
					if (c0>0) {
						c0--;
						s1[i]='0';
					}
					else {
						c1--;
						s1[i]='1';
					}
				}
				else {
					if (c1>0) {
						c1--;
						s1[i]='1';
					}
					else {
						c0--;
						s1[i]='0';
					}
				}
			}
		}
		for (auto now:op2){
			int l=now.first,r=now.second;
			//cout << l << ' ' << r << endl;
			int c0=0,c1=0;
			for (int i=l;i<=r;i++) {
				if (s2[i]=='0') c0++;
				else c1++;
			}
			for (int i=l;i<=r;i++) {
				if (s1[i]=='0') {
					if (c0>0) {
						c0--;
						s2[i]='0';
					}
					else {
						c1--;
						s2[i]='1';
					}
				}
				else {
					if (c1>0) {
						c1--;
						s2[i]='1';
					}
					else {
						c0--;
						s2[i]='0';
					}
				}
			}
		}
		for (int i=0;i<n;i++) {
			if (s1[i]==s2[i]) ans++;
		} 
//		double ed=clock();
//		if (ed-st>=100.0) break;
		if (++ccnt>=10) break;
	}
	cout << max(reg,ans) << endl;
}
int main() {
	cin >> T;
	while(T--) {
		solve();
	} 
	return 0;
}

关于此题的一个神奇做法

讨论操作

回复

相关推荐

关于此题的一个神奇做法