C. Complementary XOR CodeTON Round 3 (Div. 1 + Div. 2, Rated, Prizes)

传送门

 

 题目意思：给你两个01字符串ab，你可以选择一个范围l,r，使 a字符串的l<=i<=r" role="presentation">l<=i<=r$l<=i<=r$ 都变成1-a[i]（0变1，1变0），而b使除了l,r（包含）的范围外，都变成1-b[i].问你能不能通过最多n+5次操作，使a和b都全为0？

思路：从全部都是0开始模拟，我们发现， 只要进行奇数次操作，ab的每一位一定不一样；如果进行偶数次操作，那么ab每一位一定一样。那么对于ab，只有全是相反的或者全部相同才可以使ab全部为0，否则就不可以。

那么从a看，我使a全部变成0，那么b要么是0，要么是1。如果是0的话，直接输出对应的操作就好了。如果都是1，可以再多三次操作。

[1n112n]" role="presentation">⎡⎣⎢112n1n⎤⎦⎥$\left[\begin{array}{ccc}1& & n\\ 1& & 1\\ 2& & n\end{array}\right]$使b全部为0，那么最多的次数也不会超过n+3。

然后怎么看是否全为1，就可以在每次操作后用差分保存第一位的状态（b在操作后要么全为1，要么全为0）

      c[1]+=1,c[i]-=1,c[i+1]+=1;

如果c[1]是奇数的话就换符号 ，最后看b[1]的结果就好了。

代码：

/**
*　　┏┓　　　┏┓+ +
*　┏┛┻━━━┛┻┓ + +
*　┃　　　　　　　┃
*　┃　　　━　　　┃ ++ + + +
*  ████━████+
*  ◥██◤　◥██◤ +
*　┃　　　┻　　　┃
*　┃　　　　　　　┃ + +
*　┗━┓　　　┏━┛
*　　　┃　　　┃ + + + +Code is far away from 　
*　　　┃　　　┃ + bug with the animal protecting
*　　　┃　 　 ┗━━━┓ 神兽保佑,代码无bug　
*　　　┃ 　	　　　 ┣┓
*　　  ┃ 　　　　　 　┏┛
*　    ┗┓┓┏━┳┓┏┛ + + + +
*　　　　┃┫┫　┃┫┫
*　　　　┗┻┛　┗┻┛+ + + +
*/
 
#include
#include 
#include 
#include 
#include 
#include 
#include
#include
#include
#define sc_int(x) scanf("%d", &x)
#define sc_ll(x) scanf("%lld", &x)
#define pr_ll(x) printf("%lld", x)
#define pr_ll_n(x) printf("%lld\n", x)
#define pr_int_n(x) printf("%d\n", x)
#define ll long long 
using namespace std;
 
const int N=1000000+100;
int n ,m,h;
ll s[N];
int  a[N],b[N];
int c[N];
vectorint,int>>q;
 
void init()
{	
	char x;
	for(int i =1;i<=n;i++)
	{
		cin>>x;
		a[i]=x-'0';
	}
	for(int i =1;i<=n;i++)
	{
		cin>>x;
		b[i]=x-'0';
	}	
}
 
int main()
{
	int t;
	sc_int(t);
	while(t--)
	{
		for(int i =1;i<=n;i++)c[i]=0;		
		sc_int(n);
		init();
		int flag=0;
		for(int i =1;i<=n;i++)
		if(a[i]!=b[i])flag++;
		if(flag>0&&flag!=n){
			cout<<"NO\n";
		}
		else 
		{
			cout<<"YES\n";
 
			for(int i =1;i<=n;i++)
			{
				if(a[i]==1){
				q.push_back({i,i});
				c[1]+=1,c[i]-=1,c[i+1]+=1;
				}
			}
			if(c[1]%2!=0) b[1]=1-b[1];
 
 
			if(b[1]!=0)
			{
				q.push_back({1,n});
				q.push_back({1,1});
				q.push_back({2,n});								
			}
			cout<size()<
			for(int i =0;isize();i++){
			cout<" "<
			}
			q.erase(q.begin(),q.end());			
		}		
	}
	
	return 0;
}

：感觉时间卡的有点紧

如果有可以优化的地方那就可以自行优化~。