专栏文章

题解：CF1493E Enormous XOR

llkjlkjlkj2012
CF1493E题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minft1td
此快照首次捕获于
2025/12/02 01:42
3 个月前
此快照最后确认于
2025/12/02 01:42
3 个月前
查看原文

思路

首先注意到对于任意偶数 nn，n⊕(n+1)=1n\oplus (n+1)=1。那么我们考虑 g(x,y)g(x,y) 如何化简。
  1. 如果 x≡0(mod2)x\equiv0\pmod2 且 y≡0(mod2)y\equiv0\pmod2，则
    g(x,y)={y(y−x2≡0(mod2))y⊕1=y+1(y−x2≡1(mod2))g(x,y)=\begin{cases}y&\left(\frac{y-x}{2}\equiv0\pmod2\right)\\y\oplus1=y+1&\left(\frac{y-x}{2}\equiv1\pmod2\right)\end{cases}。
  2. 如果 x≡0(mod2)x\equiv0\pmod2 且 y≡1(mod2)y\equiv1\pmod2，则
    g(x,y)={0(y−x+12≡0(mod2))1(y−x+12≡1(mod2))g(x,y)=\begin{cases}0&\left(\frac{y-x+1}{2}\equiv0\pmod2\right)\\1&\left(\frac{y-x+1}{2}\equiv1\pmod2\right)\end{cases}。
  3. 如果 x≡1(mod2)x\equiv1\pmod2 且 y≡0(mod2)y\equiv0\pmod2，则
    g(x,y)={x⊕y(y−x−12≡0(mod2))x⊕y⊕1=(x⊕y)−1(y−x−12≡1(mod2))g(x,y)=\begin{cases}x\oplus y&\left(\frac{y-x-1}{2}\equiv0\pmod2\right)\\x\oplus y\oplus1=(x\oplus y)-1&\left(\frac{y-x-1}{2}\equiv1\pmod2\right)\end{cases}。
  4. 如果 x≡1(mod2)x\equiv1\pmod2 且 y≡1(mod2)y\equiv1\pmod2，则
    g(x,y)={x(y−x2≡0(mod2))x⊕1=x−1(y−x2≡1(mod2))g(x,y)=\begin{cases}x&\left(\frac{y-x}{2}\equiv0\pmod2\right)\\x\oplus1=x-1&\left(\frac{y-x}{2}\equiv1\pmod2\right)\end{cases}。
显然第二种情况没有第一种情况优。第一种情况在 y={r(r≡0(mod2))r−1(r≡1(mod2))y=\begin{cases}r&\left(r\equiv0\pmod2\right)\\r-1&\left(r\equiv1\pmod2\right)\end{cases} 时最优，此时 x=r∨x=r−2x=r\lor x=r-2 最优。第四种情况在 x=y={r(r≡1(mod2))r−1(r≡0(mod2))x=y=\begin{cases}r&\left(r\equiv1\pmod2\right)\\r-1&\left(r\equiv0\pmod2\right)\end{cases} 时最优。而第三种情况只在 l≤2n−1−1l\le2^{n-1}-1（题目保证 r≥2n−1r\ge2^{n-1}）可以取到最大值 2n−12^n-1，其他情况下肯定小于 2n−12^{n-1} 也就小于等于第一种或第四种情况。因此最大值只可能为 {r(g(r,r))r+1(r−l+1≥3∧r≡0(mod2))(g(r−2,r))2n−1(l≤2n−1−1)(g(2n−1−1,2n−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\KaTeX 分类大括号真难打啊……

代码

真的要查看代码吗？CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...