• 周二. 8月 16th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

Codeforces Round #735 (Div. 2)

admin

11月 28, 2021

这次的cf依旧掉分…..

A题和B题在不懈死磕下瞎搞出来了,不过还是被C题卡住了…

C. Mikasa

简述题意就是给定n和m,让n^0,n^1,n^2…,n^m,求着m+1个数中没有出现过的最小的非负整数.假设答案为x,则n^k=x,则k>m,我们还可以转化成n^x=k>m,也就是说我们要找一个最小的数x使得n^x>m

若n>m,不难发现x为0就满足题意.之后考虑n<=m的情况:我们考虑一个数比另一个数大在二进制上是什么体现,比如x>y,那么我们把他们都写成二进制数,那么一定存在一个位数使得在这个位数之前x与y的二进制数是相等的,在这个位数上x>y,即x=1,y=0,只要满足这个条件,这个位数之后随意,x一定大于y,那我们考虑这里的n^k>m的情况,我们可以先把n和m写成二进制数,对于k来说,我们要求它尽可能小,但n^k必须大于m,那我们就考虑n^k要在哪一位上大于m,对于n和m的每一位,从m开始讨论,若m这一位为1,则n^k无论如何都无法在这一位上实现大于m的目标,并且我们要求n^k要大于m,那么在这一位上n^k也必须是1,期望在之后的某一位上大于m的目标,所以无论n的这一位是0还是1,我们的k的这一位与n、的这一位异或必须是1,这样的k的这一位就是确定的。若m的这一位是0,若n=1,可以发现k=0,n^k=1>0,即可完成超越m的目标并且k也没有增大,这是我们优先选择的目标,因为在某一位上超越m之后,后面的位数无论怎样都可以,所以这样的位(m=0,n=1)在越靠前,我们得到的k就越小,我们可以从最高位往下扫来确定有没有这样的位数。考虑m=.0,n=0的情况,我们有两种选择,将k赋为0,没有增加k的值,但却只能在后面超越m,还有一种选择就是令k=1,在这一位上选择超越m,之后的就不用考虑了,很显然,若有多个这样的位的话,我们肯定是让前面这样的位为0,在最后一个这样的位上为1超越m,因为k的二进制中1越在后面肯定越小。致此整个分析过程结束,我们只需要做如下操作。

首先从最高位往下扫,看有没有m=0,n=1的位,若有,从最高位到这一位,若m=1,我们令构造k使得n^k=1,若m=0,令k=0,结束。

若无m=0,n=1的位,从最低位到最高位扫,看有没有m=0,n=0的位,是第一个扫到的位终点,重新从最高位开始扫到终点,重复上面的赋值法则。

//不等,不问,不犹豫,不回头.
#include<bits/stdc++.h>
#define _ 0
#define ls p<<1
#define db double
#define rs p<<1|1
#define RE register
#define P 1000000007
#define ll long long
#define INF 1000000000
#define get(x) x=read()
#define PLI pair<ll,int>
#define PII pair<int,int>
#define ull unsigned long long
#define put(x) printf("%d
",x)
#define putl(x) printf("%lld
",x)
#define rep(x,y,z) for(RE int x=y;x<=z;++x)
#define fep(x,y,z) for(RE int x=y;x>=z;--x)
#define go(x) for(RE int i=link[x],y=a[i].y;i;y=a[i=a[i].next].y)
using namespace std;

inline int read()
{
    int x=0,ff=1;
    char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getchar();}
    while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*ff;
}

int main()
{
//    freopen("1.in","r",stdin);
    int get(T);
    while(T--)
    {
        int get(n),get(m);
        if(n>m) {puts("0");continue;}
        int id=-1,ans=0;
        fep(i,30,0) //先找有没有m=0,n=1的位. 
        {
            int s1=(m&1<<i)?1:0;
            int s2=(n&1<<i)?1:0;
            if(!s1&&s2) {id=i;break;} 
        }
        if(id!=-1) //存在m=0,n=1的位数. 
        {
            fep(i,30,id)
            {
                int s1=(m&1<<i)?1:0;
                int s2=(n&1<<i)?1:0;
                if(s1) ans+=(s1^s2)<<i;
            }    
        }
        else//不存在m=0,n=1的位数. 
        {
            rep(i,0,30) //找最低位的m=0,n=0的位 
            {
                int s1=(m&1<<i)?1:0;
                int s2=(n&1<<i)?1:0;
                if(!s1&&!s2) {id=i;break;}
            }
            fep(i,30,id)
            {
                int s1=(m&1<<i)?1:0;
                int s2=(n&1<<i)?1:0;
                if(s1) ans+=(s1^s2)<<i;
                if(i==id) ans+=1<<i;
            }
        }
        put(ans);
    }
    return (0^_^0);
}
//以吾之血,铸吾最后的亡魂.

View Code

发表回复

您的电子邮箱地址不会被公开。