[数据结构与算法]2021牛客暑期多校训练营8——D，注释详解

题目链接

思路

我想大家都看了很多题解知道这道题的切入点是
c[i]=a[i-1]+a[i]=a[i-1] | a[i] a[i-1]&a[i]，然后取看a1的第i位可以取0还是1，或者都可以取，只是对具体操作很迷，那么请看下面的注释！

AC代码

#include<bits/stdc++.h>

#define ll long long
using namespace std;

const int N = 1e5+9;
int b[N],c[N],d[N]; 
int main()
{
	int n;
	cin>>n;
	for(int i=2; i<=n; i++) scanf("%d",b+i);
	for(int i=2; i<=n; i++)
	{
		scanf("%d",c+i);
		d[i]=c[i]-b[i];
		if(d[i]<0) 
		{
			puts("0");
			return 0;
		}
	} 
	//我们枚举a1的每一位，a1的第i位
	//要么是0，要么是1，我们就看能取哪个，还是都可以取
	 ll ans=1;
   	for(int i=0; i<31; i++)
   	{
   		//isok[0]=1:表示可以取1
		 //isok[1]=1:表示可以取0 
   		int isok[3]={1,1};
   		//下面进行可行性验证和传递 
   		//这下面的验证确实设计的很巧妙 ,可以仔细看看注释 
   		//isok数组里面初始默认a1的第i位既可以取0，也可以取1
		  
   		for(int j=2; j<=n; j++)
		{
			//表示aj的第i位是否可以取0/1 
		   	int t0=0,t1=0;
		   	//x：b[j]的第i位的值，b[j]=a[i-1]|a[i] 
			//y: d[j]的第i位的值 ,d[j]=a[i-1]&a[i]
			int x=b[j]>>i&1;
			int y=d[j]>>i&1;
			//如果 x和y都是0，那么a[j-1]和a[j]的第i位肯定是0 
			//所以t0=isok[0]，如果isok[0]=0(不合法)，那么t0也无法取了呀 
			if(!x&&!y) t0=isok[0];
			//如果x和y都是1，那么a[j-1]和a[i]的第j位肯定是1 ，同上 
			else if(x&&y) t1=isok[1];
			//如果x=1,y=0，代表a[j-1]和a[j]的第i位，肯定一个是1，一个是0 
			//如果a[j]的第i位要取0,那么a[j-1]的第i位可以取1才行
			//如果a[j]的第i位要取1,那么a[j-1]的第i位可以取0才行
			else if(x&&!y) t0=isok[1],t1=isok[0];
			//这里更新后，代表a[j]的第i位的取值合法性的情况 
			isok[0]=t0,isok[1]=t1;  
			if(!isok[0]&&!isok[1]) break; 
		} 
		//这里累乘上答案，如果0,1都可以取，显然乘2，只能取一个乘1 ，都不能取乘0 
		ans*=1ll*(isok[1]+isok[0]);
	}
	printf("%lld",ans); 
	return 0;
}