[CF 460D] Little Victor and Set

作法：

首先會發現， ( 2x )  xor ( 2x+1 )  = 1 ，而我們要的是最小的可能，所以只要再討論有哪些情況可以讓 xor 值變成0。再構造一下會發現如果可以選四個數的話，那就選 4x , 4x+1 , 4x+2 , 4x+3 就可以了，所以問題剩下只能選兩個或三個數的時候有沒有辦法讓 xor 值變成0。而兩個數的 xor 值 = 0 若且唯若兩個數字相等，所以在這裡不會出現，所以問題剩下能不能選三個數使得他們的 xor 值相同。

考慮現在已經有三個數 x , y , z 滿足 R >= x > y > z >= L 了，那麼考慮 x 二進位的最高位，那麼 y 在那位也是 1 ， z 在那位是 0 ( 因為要 xor 起來 = 0 ) ，如果 z 的右邊那位也是 0 ，那就把 x 和 y 的最高位都改 0 ，右邊那位改成 1 ，這樣就讓 x , y 和 z 更近了，所以還是會滿足 R >= x > y > z >= L 的性質。所以只要考慮 z 的最高位是 x 最高位的右邊一位的情形，這時把 x , y , z 調整成 1100...0 、 1011...1 、 0111...1 是最好的，所以只要驗證每一個這樣的三元組就可以了。

code :

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
LL ans ;
vector<LL> v ;
 
LL l,r ; int k ;
 
bool get3(LL &a,LL &b,LL &c)
{
    for(int i=0;i<60;i++)
    {
        a=(1LL<<(i+1))+(1LL<<i) ;
        b=a-1 ;
        c=(1LL<<(i+1))-1 ;
        if(a>=l && a<=r && b>=l && b<=r && c>=l && c<=r)
            return 1 ;
    }
    return 0 ;
}
 
void solve()
{
    if(r-l+1 <= 10)
    {
        ans=r+1 ;
        int len=r-l+1 ;
        for(int i=1;i<(1<<len);i++)
        {
            LL num=0LL ;
            int cnt=0 ;
            for(int j=0;j<len;j++) if(i&(1<<j))
                cnt++ , num^=(l+j) ;
            if(cnt<=k && num<ans)
            {
                ans=num ;
                v.clear() ;
                for(int j=0;j<len;j++) if(i&(1<<j))
                    v.push_back(l+j) ;
            }
        }
        return ;
    }
    if(k==1) { ans=l ; v.push_back(l) ; return ; }
    if(k==2)
    {
        ans=1 ; v.push_back(l+1) ;
        if(l%2==0) v.push_back(l) ;
        else v.push_back(l+2) ;
        return ;
    }
    if(k>=4)
    {
        while(l%4) l++ ;
        ans=0 ;
        for(int i=0;i<4;i++) v.push_back(l+i) ;
        return ;
    }
 
    ans=1 ; v.push_back(l+1) ;
    if(l%2==0) v.push_back(l) ;
    else v.push_back(l+2) ;
    LL a,b,c ;
    if(get3(a,b,c))
    {
        ans=0 , v.clear() ;
        v.push_back(a) ;
        v.push_back(b) ;
        v.push_back(c) ;
    }
}
 
main()
{
    scanf("%I64d%I64d%d",&l,&r,&k) ;
    solve() ;
    printf("%I64d\n%d\n",ans,v.size()) ;
    for(int i=0;i<v.size();i++)
        printf("%I64d%c",v[i],i+1==v.size()?'\n':' ') ;
}