acm-(异或、思维)Codeforces Round #705 (Div. 2) E. Enormous XOR

admin管理员组

文章数量:1582693

传送门

首先给出结论：

1. 若 l 0 = 0 , r 0 = 1 l_0=0,r_0=1 l0​=0,r0​=1，那么答案就是 111...1 111...1 111...1(长度为 n n n)。
2. 否则若 r r r为奇数或 l + 1 ≥ r l+1\ge r l+1≥r，那么答案是 r r r。
3. 否则( r r r为偶数并且 l + 1 < r l+1<r l+1<r)答案是 r + 1 r+1 r+1。

下面给出证明：
第一种情况下我们可以找到长度为 n n n的 01111..1 01111..1 01111..1与 1000..0 1000..0 1000..0串，两者异或就能得到长度为 n n n的 1111..1 1111..1 1111..1。

第二种情况我们先考虑 l + 1 ≥ r l+1\ge r l+1≥r的情况，此时无非有两种 c a s e case case，若 l = r l=r l=r，显然答案是 r r r，否则的话 l + 1 = r l+1=r l+1=r，我们发现 g ( l , l ) , g ( l , l + 1 ) , g ( l + 1 , l + 1 ) g(l,l),g(l,l+1),g(l+1,l+1) g(l,l),g(l,l+1),g(l+1,l+1)中 g ( l + 1 , l + 1 ) g(l+1,l+1) g(l+1,l+1)取得 f ( l , r ) f(l,r) f(l,r)的最大值即 r r r。
现在考虑稍微复杂点的 r r r为奇数的情况，我们已经证明了当 l + 1 ≥ r l+1\ge r l+1≥r时 f ( l , r ) f(l,r) f(l,r)的答案是 r r r，考虑利用数学归纳法证明，设对于 l , r l,r l,r若 r r r为奇数并且 r − l = k r-l=k r−l=k满足 f ( l , r ) = r f(l,r)=r f(l,r)=r成立，那么 r + 2 − l = k + 2 r+2-l=k+2 r+2−l=k+2，此时满足 r + 2 r+2 r+2为奇数，我们需要证明 f ( l , r + 2 ) = r + 2 f(l,r+2)=r+2 f(l,r+2)=r+2依然成立。考虑 g g g的定义域可以分为四种类型(下面用 g l gl gl代表 g g g的第一个参数， g r gr gr代表 g g g的第二个参数)：

1. [ g l , g r ] ⊆ [ r + 1 , r + 2 ] [gl,gr]\subseteq [r+1,r+2] [gl,gr]⊆[r+1,r+2]
2. [ g l , g r ] ⊆ [ l , r ] [gl,gr]\subseteq [l,r] [gl,gr]⊆[l,r]
3. g l ≤ l , g r = r + 2 gl\le l,gr=r+2 gl≤l,gr=r+2
4. g l ≤ l , g r = r + 1 gl\le l,gr=r+1 gl≤l,gr=r+1

显然第1种情况下 g g g的最大值为 f ( r + 1 , r + 2 ) = r + 2 f(r+1,r+2)=r+2 f(r+1,r+2)=r+2。
第2种情况下根据数学归纳法我们知道 g g g最大值为 r r r。
第3种情况下我们发现 [ r + 1 , r + 2 ] ⊂ [ g l , g r ] [r+1,r+2]\subset [gl,gr] [r+1,r+2]⊂[gl,gr]，由于 ( r + 1 )    x o r    ( r + 2 ) = 1 (r+1)\; xor\;(r+2)=1 (r+1)xor(r+2)=1，那么 g ( g l , g r ) = X O R i = g l g r i = ( X O R i = g l r i )    x o r    1 ≤ f ( l , r )    x o r    1 ≤ r g(gl,gr)=XOR_{i=gl}^{gr}i=(XOR_{i=gl}^{r}i)\;xor\;1\le f(l,r)\;xor\;1\le r g(gl,gr)=XORi=glgr​i=(XORi=glr​i)xor1≤f(l,r)xor1≤r，因此该情况下最大值不超过 r r r。
最后一种情况稍微复杂点，我们考虑如何找到一个 g l gl gl使得 X O R i = g l g r i > r + 2 XOR_{i=gl}^{gr}i>r+2 XORi=glgr​i>r+2，为了达到这个目的，我们需要验证我们至少可以找到 r + 2 r+2 r+2的二进制位中的一个为 0 0 0的位，而 g ( g l , g r ) g(gl,gr) g(gl,gr)在这些位上为 1 1 1即可。我们取这些二进制位中的一个(满足 r + 2 r+2 r+2在这一位上为 0 0 0)，假设这一位是 p o s ( 0 < p o s ≤ n − 1 ) pos(0< pos\le n-1) pos(0<pos≤n−1)，然后从 g r gr gr开始递减找到第一个满足 p o s pos pos位为 1 1 1的数 x x x，一定有 x 0 = 1 x_0=1 x0​=1，注意到 ( x + 1 ) 0 = 0 , g r 0 = 0 (x+1)_0=0,gr_0=0 (x+1)0​=0,gr0​=0，那么有 g r − x gr-x gr−x是一个奇数。为了保证 p o s pos pos位异或出来是 1 1 1，我们还需要保证从 [ g l , x ] [gl,x] [gl,x]在 p o s pos pos位上有奇数个 1 1 1，注意到从 x x x开始递减，恰好有偶数个数(包括 x x x)满足 p o s pos pos位为 1 1 1，继续递减的话(如果还没有变成 0 0 0)恰好有偶数个数满足 p o s pos pos为 0 0 0，再继续递减的话(如果还没有变成 0 0 0)仍然是恰好有偶数个数满足 p o s pos pos为 1 1 1…以此类推。这个事实意味着我们需要保证 [ g l , x ] [gl,x] [gl,x]是一个奇数长度的区间才行，否则 [ g l , x ] [gl,x] [gl,x]区间在 p o s pos pos位上为 1 1 1的数字个数必定是偶数。
结合之前 [ x + 1 , g r ] [x+1,gr] [x+1,gr]是一个奇数长度区间的结论，我们发现 [ g l , g r ] [gl,gr] [gl,gr]是一个偶数长度的区间，也就是说 g ( g l , g r ) g(gl,gr) g(gl,gr)在第 n − 1 n-1 n−1位上的值是 0 0 0，显然小于 r + 2 r+2 r+2，也就是说我们无法找到一个 g l gl gl使得当 g r = r + 1 gr=r+1 gr=r+1时 g ( g l , g r ) > r + 2 g(gl,gr)>r+2 g(gl,gr)>r+2，即在第4种情况下 g ( g l , g r ) ≤ r + 2 g(gl,gr)\le r+2 g(gl,gr)≤r+2。
综合上述四个分类讨论我们证明了 f ( l , r + 2 ) = r + 2 f(l,r+2)=r+2 f(l,r+2)=r+2，根据数学归纳法我们有当 r r r是奇数的时候， f ( l , r ) = r f(l,r)=r f(l,r)=r。

第三种情况就比较容易了，首先有 f ( l , r ) ≤ f ( l , r + 1 ) = r + 1 f(l,r)\le f(l,r+1)=r+1 f(l,r)≤f(l,r+1)=r+1(因为 r + 1 r+1 r+1是奇数)，又由于 g ( r − 2 , r ) = r + 1 g(r-2,r)=r+1 g(r−2,r)=r+1，故 f ( l , r ) = r + 1 f(l,r)=r+1 f(l,r)=r+1。

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e6+5;
char l[maxn],r[maxn],tl[maxn];
int main(){
	int t=1;
	while(t--){
	int n;
	scanf("%d%s%s",&n,l+1,r+1);
	if(l[1]=='0' && r[1]=='1'){
		for(int i=1;i<=n;++i)printf("1");puts("");
	}else{
		bool ok=true;
		for(int i=1;i<=n;++i){
			if(l[i]!=r[i]){
				ok=false;
				break;
			}
		}
		if(!ok){
			ok=true;
			memcpy(tl,l,sizeof(char)*(n+2));
			int now=n;
			while(tl[now]=='1'){
				tl[now]='0';
				now--;
			}
			tl[now]='1';
			for(int i=1;i<=n;++i){
				if(tl[i]!=r[i]){
					ok=false;
					break;
				}
			}
		}
		if(ok){
			printf("%s\n",r+1);
		}else{
			r[n]='1';
			printf("%s\n",r+1);
		}
	}
}
}

本文标签： 思维codeforcesACMxorEnormous