HDU 5661 Claris and XOR

淩亂°似流年 2022-07-28 10:50 144阅读 0赞

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=5661][http_acm.hdu.edu.cn_showproblem.php_pid_5661]

题目大意：给你两个区间，每个区间的范围在1-10^18，从两个区间中各挑选一个数，x , y，为这两个区间异或的最大值是多少

题解：我们要尽可能的使最高位为1，只有一种情况最高位是0，那就是  
当两个数最高位都必须取1时，那么最高位就肯定是0，其它的情况最高位取到1，每次都取让最高位等于1的方案就好了，但是有一种情况比较特殊，当两个数最高位取0取1都可以时，我们不用计算后面的值，从最高位到后面全部都是1，因为必定能取到 1（后面n个0），和1（n-1个1）。  
举个例子 假如 给定两个区间 1011 10011  
110 11100  
因为位数不同 必定有一个数能取到 10000 ，另一个数能取到1111，所以是11111

代码：  
我用的直接模拟的做法;

#include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <cstdlib>
    #include <cmath>
    #include <string>
    #include <vector>
    #include <list>
    #include <map>
    #include <queue>
    #include <stack>
    #include <algorithm>
    #include <numeric>
    #include <functional>
    #define RI(N) scanf("%d",&(N))
    #define RII(N,M) scanf("%d %d",&(N),&(M))
    #define RIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))
    #define mem(a) memset((a),0,sizeof(a))
    using namespace std;
    const int inf=1e9;
    const int inf1=-1*1e9;
    typedef long long LL;
    
    void change(int maze[],int &len,LL a)
    {
        while(a)
        {
            maze[len++]=a%2;
            a=a/2;
        }
        len--;
    }
    
    void find_one(int maze[],int &len)//找到最高位后非0的一位
    {
        len--;
        while(len>=0&&maze[len]==0) len--;
    
    }
    int main()
    {
        int t;
        RI(t);
        while(t--)
        {
            LL a,b,c,d;
            scanf("%I64d %I64d %I64d %I64d",&a,&b,&c,&d);
            int a1[100],b1[100],c1[100],d1[100],ans[100];
            mem(ans);
            int alen=0,blen=0,clen=0,dlen=0,anslen=-1;
            change(a1,alen,a);
            change(b1,blen,b);
            change(c1,clen,c);
            change(d1,dlen,d);
            while(!(alen<0&&blen<0&&clen<0&&dlen<0))
            {
                if(alen<0&&blen<0)
                {
                    while(dlen>=0)   {ans[dlen]=d1[dlen]; dlen--;}
                    break;
                }
                else if(clen<0&&dlen<0)
                {
                    while(blen>=0)   {ans[blen]=b1[blen]; blen--;}
                    break;
                }
                int x1=-1,x2=-1;
                if(blen==alen)   x1=1;//区间端点最高位相同
                else x1=2;//区间端点最高位不同
                if(dlen==clen)   x2=1;
                else x2=2;
                if(blen==dlen)//两个数最高位相同
                {
                    if(x1==1&&x2==1)
                    {
                        anslen=max(anslen,dlen);
                        ans[dlen]=0;
                        find_one(a1,alen);
                        find_one(b1,blen);
                        find_one(c1,clen);
                        find_one(d1,dlen);
                    }
                    else if(x1==1&&x2==2)
                    {
                        ans[blen]=1;
                        anslen=max(anslen,blen);
                        find_one(a1,alen);
                        find_one(b1,blen);
                        dlen--;
                        int dlen1=dlen;
                        while(dlen1>=0) d1[dlen1--]=1;
                    }
                    else if(x1==2&&x2==1)
                    {
                        ans[dlen]=1;
                        anslen=max(anslen,dlen);
                        find_one(c1,clen);
                        find_one(d1,dlen);
                        blen--;
                        int blen1=blen;
                        while(blen1>=0)   b1[blen1--]=1;
                    }
                    else if(x1==2&&x2==2)
                    {
                        anslen=max(anslen,blen);
                        while(blen>=0)  {ans[blen--]=1;}
                        break;
                    }
    
                }
                else if(blen<dlen)
                {
                    ans[dlen]=1;
                    anslen=max(anslen,dlen);
                    find_one(d1,dlen);
                    if(x2==1)   find_one(c1,clen);
                    else if(x2==2)   clen=-1;
                }
                else if(blen>dlen)
                {
                    ans[blen]=1;
                    anslen=max(anslen,blen);
                    find_one(b1,blen);
                    if(x1==1)  find_one(a1,alen);
                    else if(x1==2)   alen=-1;
                }
            }
    
            LL ttt=0;
            for(int i=anslen; i>0; i--)
            {
                    ttt+=ans[i];
                    ttt*=2;
            }
            ttt+=ans[0];
            printf("%I64d\n",ttt);
        }
    
        return  0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_5661]: http://acm.hdu.edu.cn/showproblem.php?pid=5661