Skip to content

进制 & 位运算

P7442

~~众所周知，二进制有一类提需要你找规律~~

每次的1操作相当于将\(x\)这个二进制数看成一个环，并且将它旋转\(cnt \mod n\)次，\(cnt\)为总的操作次数。

而2操作就是在2操作前的\(cnt\mod n\)位上异或上一个1。

#include<iostream>
#include<cstdio>
#define int long long 
using namespace std;
int cnt,n,m,op,x,tmp;
signed main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=m;++i){
        scanf("%lld%lld",&op,&x);
        if(op==1){
            tmp^=(x)*(long long)(1ll<<cnt);cnt=(cnt+1ll)%n;
        }else{
            int tot=x>>(n-cnt);
            x=x^(tot<<(n-cnt));
            printf("%lld\n",(long long)(x<<cnt)^tot^tmp);
        }
    }
    return 0;
}

P1582

通过不断求得当前的n有多少个1，并与k判断，若小于k则符合题意，否则就将最后一位1加到贡献里去。

//求最后一位1
int lowbit(int x){
    return x&-x;
}
完整code： 
#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long 
using namespace std;
const int K=1e3+10;
int n,k;
int lowbit(int x){
    return x&-x;
}
signed main(){
    scanf("%lld%lld",&n,&k);
    int m=n,t=0;
    while(m){
        m-=lowbit(m);
        ++t;
    }
    if(t<=k){
        printf("0");
        return 0;
    }else{
        int ans=0;
        while(t>k){
            int tmp=lowbit(n);
            ans+=tmp;
            n+=tmp;
            int m=n;
            t=0;
            while(m){
                m-=lowbit(m);
                t++;
            }
        }
        printf("%lld",ans);
    }
    return 0;
}

P1015

模拟题.

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e4+10;
int n;
struct HP{
    int p[N],len;
    void clear1(){
        memset(p,0,sizeof p);
        len=1;
    }
    void read1(){
        memset(p,0,sizeof p);
        len=0;
        p[0]=1;
        char ch=getchar();
        int x=0,f=1;
        while(!(ch<='9' && ch>='0' || ch<='F' && ch>='A' || ch<='f' && ch>='a')){
            ch=getchar();
        }
        while((ch<='9' && ch>='0' || ch<='F' && ch>='A' || ch<='f' && ch>='a')){
            ++len;
            if(n==16){
                if(ch<='F' && ch>='A'){
                    p[len]=ch-'A'+10;   
                }else if(ch<='f' && ch>='a'){
                    p[len]=ch-'a'+10;   
                }else p[len]=ch-'0';
            }else p[len]=ch-'0';
            ch=getchar();
        }
        for(int i=1;i<=len/2;++i){
            swap(p[i],p[len-i+1]);
        } 
    }
    void write1(){
        for(int i=len;i>=1;--i){
            printf("%d",p[i]);
        }
        putchar('\n');
    }
};
HP operator +(const HP &a,const HP &b){
    HP c;
    c.clear1();
    int la=a.len,lb=b.len,lc=max(la,lb),x=0;
    for(int i=1;i<=lc;++i){
        c.p[i]=a.p[i]+b.p[i]+x;
        x=c.p[i]/n;
        c.p[i]%=n;
    }
    if(x)c.p[++lc]=x;
    c.len=lc;
    return c;
}
HP new1(HP a){
    HP b;
    b.clear1();
    int la=a.len;
    b.len=la;
    for(int i=1;i<=la;++i){
        b.p[la-i+1]=a.p[i];
    }
    a=a+b;
    return a;
}
bool check(HP a){
    bool flag=true;
    for(int i=1;i<=a.len/2;++i){
        if(a.p[i]!=a.p[a.len-i+1])flag=false;
    }
    return flag;
}
int main(){
    scanf("%d",&n);
    HP a;
    a.read1();
    int cnt=0;
    while(!check(a) && cnt<=31){
        a=new1(a);
        cnt++;
    }
    if(cnt>=31)printf("Impossible!");
    else printf("STEP=%d",cnt);
    return 0;
}

P2852

这道题时\(hash\)优化的字符串表示法，将每个字符串看成一个\(C\)进制数即可，并将它\(mod\)上一个大质数\(P\),因为我们用前缀和的思想表示每一个子串，所以对于\(n\)个数的序列总共只有\(n\)个字符串，如果\(P\)足够大并且是质数就不会出现状态重复的情况。~~如果有，就换一个更♂大♂的~~

代码在\(hash\)优化里有。

P3760

~~位运算好题~~

对于所有复杂的位运算，我们有个常用的\(Trick\)，就是将每个数拆位，每个数只用记录\(O(\log n)\)个位.

对于枚举的位数\(v\)，我们只需要统计有多少个\(s\)满足：

\((s[j]-s[i]>>v)&1==1\)即可。

那么可以开两个树状数组，记录第\(v\)位分别为0或1的状态。

对于当前枚举到的\(s[i]\)：

1) 第\(v\)位为1，那只需要找到第\(v\)位之前比他小且0的个数或比他大且1的个数。

2) 第\(v\)位为0，那只需要找到第\(v\)位之前比他大且0的个数或比他小且1的个数。

#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long 
#define lowbit(x) (x&-x)
using namespace std;
const int N=1e5+10,C=1e6+10;
int s[N],a[N],f[C][2];
int n,maxn,ans;
void change(int i,int x,int d){
    while(x<C)f[x][i]+=d,x+=lowbit(x);
}
int sum(int i,int x){
    int ans=0;
    while(x>0)ans+=f[x][i],x-=lowbit(x);
    return ans;
}
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;++i)scanf("%lld",&a[i]),s[i]=s[i-1]+a[i],maxn=max(maxn,s[i]);
    for(int v=0;v<=20;++v){
        if((1<<v)>maxn)break;
        int cnt=0;
        memset(f,0,sizeof f);
        change(0,1,1);
        for(int i=1;i<=n;++i){
            int tmp=s[i]&((1<<v)-1),type=(s[i]>>v)&1;

            if(type)cnt+=sum(1,C-1)-sum(1,tmp+1)+sum(0,tmp+1);
            else cnt+=sum(0,C-1)-sum(0,tmp+1)+sum(1,tmp+1);
            change(type,tmp+1,1);
        }
        if(cnt%2)ans|=(1<<v);
    }

    printf("%lld",ans);
    return 0;
}