【NWPU2018 练着玩】入门班day1 枚举贪心[Cloned] F - Claris and XOR (HDU-5661 Claris and XOR )

题目链接：https://vjudge.net/contest/246949#problem/F

先参考大佬的博客：

https://blog.csdn.net/idealism_xxm/article/details/51112303

通过这道题发现学会用位运算真的可以让程序简便很多。比如：

都是让接下来的所有位数全部变为1

和：

差距就明显了。。。

 

至于这题的细节我说明一下：

（1）

解释：

本来y的这一位可以取0/1的，比如0010 / 1100,但是现在这里强制取了1，所以下界最小值变成了1000，所有原本这里取0的值全部舍去，原本上界为1111，现在同样可以取到1111，所以上界不用改。同理，如果这一位强制取0，则左右原本这里是1的所有数全部舍去，即最大值变为了0111,但是现在下界不用变，因为原本最小值是0000，现在照样可以取到0000。

（2）

比如第i位x和y都可以取0/1，这里假如x取1，y取0，所以10000<=x<=11111 , 00000<=y<=011111 , 所以i-1位一直向右到第0位都可以取到0/1（无论x/y都是如此）

 

（3）

 

 

 

至于高端玩家的

这种写法老百姓还是不要轻易模仿，还是像我这样的稳如老狗的比较安全：

 

代码：

//F - Claris and XOR
#include<stdio.h>
#include<string.h>
typedef long long LL;

int main()
{
    int i;
    int kase;
    LL a,b,c,d;
    LL cur;
    LL aa,bb,cc,dd;
    LL ans;

    scanf("%d",&kase);
    while(kase--)
    {
        scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
        ans=0;
        for(cur=(LL)1<<62;cur>0;cur>>=1)
        {
            aa=a&cur;//记录a在这一位的数字
            bb=b&cur;
            cc=c&cur;
            dd=d&cur;
            if(aa==bb)
            {
                if(cc==dd)
                    ans|=aa^cc;
                else//y的这一位可取0或1
                {
                    ans|=cur;
                    if(aa==0)//意思是y在这一位必须取1，贪心得到最大值
                        c&=cur;
                    else//y在这一位必须取0，需要改变上界
                        d|=cur-1;
                }
            }
            else//x在这一位可取0/1
            {
                ans|=cur;
                if(cc==dd)//y在这一位只能取一个
                {
                    ans|=cur;
                    if(cc==0)//y只能在这一位取0，则x必须取1,需要改变下界
                        a&=cur;
                    else
                        b|=cur-1;
                }
                else//x和y都是在这一位任意取一个
                {
                    //ans|=cur-1;
                    while(cur)
                    {
                        ans|=cur;
                        cur>>=1;
                    }
                    break;
                }
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}