题解：CF1493E Enormous XOR

· · 题解

思路

首先注意到对于任意偶数 n，n\oplus (n+1)=1。那么我们考虑 g(x,y) 如何化简。

  1. 如果 x\equiv0\pmod2 且 y\equiv0\pmod2，则
  2. 如果 x\equiv0\pmod2 且 y\equiv1\pmod2，则
  3. 如果 x\equiv1\pmod2 且 y\equiv0\pmod2，则
  4. 如果 x\equiv1\pmod2 且 y\equiv1\pmod2，则

显然第二种情况没有第一种情况优。第一种情况在 y=\begin{cases}r&\left(r\equiv0\pmod2\right)\\r-1&\left(r\equiv1\pmod2\right)\end{cases} 时最优，此时 x=r\lor x=r-2 最优。第四种情况在 x=y=\begin{cases}r&\left(r\equiv1\pmod2\right)\\r-1&\left(r\equiv0\pmod2\right)\end{cases} 时最优。而第三种情况只在 l\le2^{n-1}-1（题目保证 r\ge2^{n-1}）可以取到最大值 2^n-1，其他情况下肯定小于 2^{n-1} 也就小于等于第一种或第四种情况。因此最大值只可能为 \begin{cases}r& &\left(g\left(r,r\right)\right)\\r+1&\left(r-l+1\ge3\land r\equiv0\pmod2\right)&\left(g\left(r-2,r\right)\right)\\2^n-1&\left(l\le2^{n-1}-1\right)&\left(g\left(2^{n-1}-1,2^{n-1}\right)\right)\end{cases}。字符串操作计算即可。

PS: \KaTeX 分类大括号真难打啊……

代码

:::warning[真的要查看代码吗？]

#include <bits/stdc++.h>
using namespace std;
int n;
string l,r;
int compare(const string &a,const string &b)
// Warning: Compare as numbers instead of dictionary order. Time optimization is O(n).
{
    if(a.length()<b.length())
        return -1;
    else if(a.length()>b.length())
        return 1;
    else if(a==b)
        return 0;
    else
        return (a>b?1:-1);
}
string max(string a,string b)
// Warning: Compare as numbers instead of dictionary order. Time optimization is O(n).
{
    if(compare(a,b)>=0)
        return a;
    else
        return b;
}
void increase1(string &a)
{
    int i;
    for(i=a.length()-1;i>=0&&a[i]=='1';i--)
        a[i]='0';
    if(i>=0)
        a[i]='1';
    else
        cout<<"[increase1]Warning: Number overflow."<<endl;
}
void decrease1(string &a)
{
    int i;
    for(i=a.length()-1;i>=0&&a[i]=='0';i--)
        a[i]='1';
    if(i>=0)
        a[i]='0';
    else
        cout<<"[decrease1]Warning: Number overflow."<<endl;
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    #define endl '\n';
    cin>>n>>l>>r;
    assert(l.size()==n),assert(r.size()==n);
    string mn,mx;
    for(int i=1;i<=n;i++)
        mn+='0',mx+='1';
    // string ans=mn;
    string ans=r;
    // You can choose [r,r]
    {
        // Trying choose [r-2,r](if it is even,odd,even, bigger than r)
        if(r[r.length()-1]=='0')
        {
            string tmp=r;
            for(int i=1;i<=2;i++)
            {
                if(compare(tmp,l)<=0)
                    goto end;
                decrease1(tmp);
            }
            // cout<<"choose ["<<tmp<<","<<r<<"]"<<endl;
            string tmp2=r;
            tmp2[tmp2.length()-1]='1';
            ans=max(ans,tmp2);
        }
        end:;
    }
    {
        if(l[0]=='0'&&r[0]=='1')
            ans=max(ans,mx);
        // Use 01111... and 10000...
    }
    cout<<ans;
}

:::