CF1493E

lsj2009 · 2023-11-07 00:27:12 · 题解

Solution

诈骗题。

首先发现如果 l,r 的最高位不同，则答案必然为 2^n-1，因为答案不可能再大，且取 x=2^{n-1}-1,y=2^{n-1} 可以取到。

则接下来考虑 l,r 最高位相同的情况下。

考虑一个结论：当 x\equiv 0\pmod{2} 时，x\oplus(x+1)=1。

那么我们考虑形如 (x\oplus(x+1))\oplus((x+2)\oplus(x+3))\cdots \oplus((x+2k)\oplus(x+2k+1)) 这种结构可以相消成 0。

进一步的，答案只有可能是三种：

显然当 y=r 时答案最大，而且我们希望尽可能取后两种，且 r\equiv 1\pmod{2} 时，r 无法变大，取 x=y 即为最佳。

当 r\equiv 0\pmod{2} 时，考虑什么时候答案可以取 r+1；如果取不到，我们令 x=y 也可以得到 r。

容易发现的是，需要满足 y-x\equiv 2\pmod{4}，令 x 尽可能大，取到 y-2=r-2，判断一下 l+2 是否不大于 r 即可。

复杂度 \Theta(n)。

Code

#include<bits/stdc++.h>
//#define int long long
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
using namespace std;
const int N=1e6+5;
char l[N],r[N];
signed main() {
    int n;
    scanf("%d",&n);
    scanf("%s%s",l+1,r+1);
    if(l[1]!=r[1]) {
        rep(i,1,n)
            putchar('1');
        return 0;
    }
    if(r[n]&1)
        return 0&printf("%s\n",r+1);
    ++l[n-1];
    per(i,n-1,0) {
        if(l[i]>49)
            l[i]-=2,++l[i-1];
    }
    bool flag=true;
    rep(i,0,n) {
        if(l[i]!=r[i]) {
            flag=l[i]<r[i];
            break;
        }
    }
    r[n]+=flag;
    printf("%s\n",r+1);
    return 0;
}