【牛客小白月赛31】部分题解（除了CEJ三题以外）

写在前面的话

这场比赛打了两个半小时过了7题，剩下3题没时间开了。题目质量还是非常高的，不过难度偏大了一点。。

A

知识点：位运算
题意是求不大于x的数中，有多少数和a没有两个数位都是1。
先转为二进制，考虑a的每一位：
首先如果a的当前位是1，那么待选择的数当前位只能选择0，没有其他选项。
如果a的当前位是0，那么根据x的当前位分类讨论：
如果x当前位是1，那么对于待选择的数y而言，当前位若选择0则有 $2^{sum[i+1]}$ 的贡献（其中sum为后面a的二进制的0的数量），若选择1则继续考虑下一位。
如果x当前位是0，那么当前的数只能选0。
然后处理一下尾部的特判就可以了。
（这道题调了好久才过qwq）

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int mod =1e9+7;
ll power(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1)res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
ll inv(ll x){
    return power(x,mod-2);
}
ll bs(ll l,ll r,ll n){
    ll mid=l+r>>1;
    if(l==r)return l;
    if(mid*(mid+1)/2<=n)return bs(mid+1,r,n);
    return bs(l,mid,n);
}
int main(){
  // cout<<inv(2);
   // std::ios::sync_with_stdio(false);
    ll t,n,i,j;
    cin>>t;
    while(t--){
        ll a,x;
        cin>>a>>x;
        ll p=x;
        ll sum[32]={0},s=0,aa[32]={0},xx[32]={0};

        for(i=0;i<32;i++){
            aa[i]=a%2;
            xx[i]=x%2,x/=2;
            sum[i]=s+=a%2==0;
            a/=2;
        }
        ll res=0;
        for(i=31;i>=0;i--){
            if(xx[i])break;
        }
        if(sum[i]==i+1){
            cout<<p<<endl;
            continue;
        }
        for(;i>0;i--){
            if(xx[i]==1){
                if(aa[i]==1){
                    res+=1<<sum[i-1];    //我莫得选择，只能选0。后面随便选
                    break;
                }
                res+=1<<sum[i-1];    //若当前选0
                //继续下一个
            }
            else{
                //我莫得选择，只能选0
            }
        }
        if(i==0){
            res++;
            if(aa[0]==0&&xx[0]==1)res++;
        }
        cout<<res-1<<endl;
    }



}

B

知识点：大模拟
模拟就完事了。我的方法是先把每个数字对应的点和井号看成01转为二进制，然后处理就相对方便一点。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int mod =1e9+7;
ll power(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1)res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
ll inv(ll x){
    return power(x,mod-2);
}
ll bs(ll l,ll r,ll n){
    ll mid=l+r>>1;
    if(l==r)return l;
    if(mid*(mid+1)/2<=n)return bs(mid+1,r,n);
    return bs(l,mid,n);
}
string a[501];
map<ll,int>m;
int f(string s){
    int i,res=0;
    for(i=0;i<s.length();i++){
        res*=2;
        res+=s[i]-'0';
    }
    return res;
}
string d[10]={"111111000111111",
              "111110000000000",
              "101111010111101",
              "111111010110101",
              "111110010000111",
              "111011010110111",
              "111011010111111",
              "111110000100111",
              "111111010111111",
              "111111010110111"};
string add="001000111000100";
int main(){
  // cout<<inv(2);
   // std::ios::sync_with_stdio(false);

    ll t,n,i,j,k;
    cin>>t;
    for(i=0;i<10;i++){
        m[f(d[i])]=i;
    }
    ll ad=f(add);
    while(t--){

        ll temp=0,res=0;
        for(i=0;i<5;i++)cin>>a[i];
        for(i=2;i<a[0].length();i+=4){
            ll ttemp=0;
            for(k=i;k>=i-2;k--)
                for(j=4;j>=0;j--){
                    ttemp*=2;
                    if(a[j][k]=='#')ttemp++;
                }
            if(ttemp==ad)res+=temp,temp=0;
            else temp*=10,temp+=m[ttemp];
        }
        res+=temp;
       // cout<<res<<endl;
        int out[20]={0};
        for(i=0;i<14;i++)out[i]=res%10,res/=10;
        while(i>=0&&out[i]==0)i--;
        if(i==-1)i++;
        char pr[5][500];
        k=2;
        int z;
        for(;i>=0;i--){
            int ttemp=0;
            for(z=k;z>=k-2;z--){
                for(j=4;j>=0;j--){
                    if(d[out[i]][ttemp++]=='1')pr[j][z]='#';
                    else pr[j][z]='.';
                }
            }
            if(i==0){
                for(j=4;j>=0;j--)pr[j][k+1]='\0';
            }
            else{
                k++;
                for(j=4;j>=0;j--)pr[j][k]='.';
                k+=3;
            }
        }
        for(i=0;i<5;i++)printf("%s\n",pr[i]);
        cout<<endl;
    }



}

D

可以发现，经过一定数量的操作后一定能产生（0，0）的点，所以统计所有点数量就可以了。
ps.这道题刚开始以为是必须满足x|y=y的情况才可以，然后推了半天dp没推出来，浪费了好多时间。。。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int mod =1e9+7;
ll power(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1)res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
ll inv(ll x){
    return power(x,mod-2);
}
ll f(ll x,ll y){        //0 0到x y
    return (x+1)*(y+1);

}
int main(){
  // cout<<inv(2);
   // std::ios::sync_with_stdio(false);
    ll t,n,i,j;
    cin>>t;
    while(t--){
        ll x,y,x1,y1;
        cin>>x>>y>>x1>>y1;
        cout<<f(x1,y1)-f(x-1,y1)-f(x1,y-1)+f(x-1,y-1)<<endl;

    }



}

F

首先，一次能消完的一定是形如 $x*(x+1)/2$ 的数。
那么可以先二分出小于等于n的最大的这种形式，那么令 $p1=x*(x+1)/2$ ， $p2=(x+1)*(x+2)/2$ ，则n每次要么减p1然后加n 要么减p2然后加n，这个问题就是看什么时候能回到n（完成一次循环）
我们发现，不管是减p1加n，还是减p2加n，最后一定是形成p2-p1的一个剩余系，并且这个剩余系要通过操作n的方式得出，所以最终能形成的就是 $(p1-p2)/gcd(p1-p2,n-p1)$ （或者 $(p1-p2)/gcd(p1-p2,n-p1)$ ）这么多个数。
这也是循环的大小，即所求的解。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int mod =1e9+7;
ll power(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1)res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
ll inv(ll x){
    return power(x,mod-2);
}
ll bs(ll l,ll r,ll n){
    ll mid=l+r>>1;
    if(l==r)return l;
    if(mid*(mid+1)/2<=n)return bs(mid+1,r,n);
    return bs(l,mid,n);
}
int main(){
  // cout<<inv(2);
   // std::ios::sync_with_stdio(false);
    ll t,n,i,j;
    cin>>t;
    while(t--){
        cin>>n;
        ll so=bs(1,1e9,n)-1;
        ll p=so*(so+1)/2,pp=(so+2)*(so+1)/2;
        if(p==n)cout<<1<<endl;
        else{
            ll cha1=n-p,cha2=pp-p;
         //   cout<<p<<" "<<n<<" "<<pp<<endl;
            ll g=__gcd(cha1,cha2);
            cout<<cha2/g<<endl;

        }
    }



}

G

这道题求 $x^k\leq y$ 的最大k。由于y小于1e18，而2的64次方已经爆longlong了，所以当x大于1的时候模拟就可以了。
但还是要注意爆longlong的问题。可以写大数或者__int128，但我为了省事就直接上py了（

t=int(input())
while t>0:
    t-=1
    x,y=map(int,input().split())
    if y<=0 or x<=1:
        print(-1)
    else:
        res=1
        p=x
        while p<=y:
            p*=x
            res+=1
        print(res-1)

H

模拟就可以了，看对称的字符串能不能取到相同的字符，只要有一个取不到就gg

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int mod =1e9+7;
ll power(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1)res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
ll inv(ll x){
    return power(x,mod-2);
}
int main(){
  // cout<<inv(2);
   // std::ios::sync_with_stdio(false);
    ll t,n,i,j;
    cin>>t;
    while(t--){
        string s[1000];
        cin>>n;
        for(i=0;i<n;i++)cin>>s[i];
        int jud=0;
        for(i=0;i<n/2;i++){
            int tong1[26]={0},tong2[26]={0};
            for(j=0;j<s[i].length();j++)tong1[s[i][j]-'a']++;
            for(j=0;j<s[n-i-1].length();j++)tong2[s[n-i-1][j]-'a']++;
            for(j=0;j<26;j++)if(tong1[j]&&tong2[j])break;
            if(j==26)jud=1;
        }
        if(jud)cout<<"No\n";
        else cout<<"Yes\n";

    }



}

I

如果字符串所有字符都相同，输出0。
如果字符串不是回文，输出n
否则输出n-1即可。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int mod =1e9+7;
ll power(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1)res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
ll inv(ll x){
    return power(x,mod-2);
}
int main(){
  // cout<<inv(2);
   // std::ios::sync_with_stdio(false);
    string s;
    int i;
    cin>>s;
    int jud=0;
    for(i=1;i<s.length();i++){
        if(s[i]!=s[i-1])jud=1;
    }
    if(!jud)cout<<0;
    else{
        for(i=0;i<s.length();i++){
            if(s[i]!=s[s.length()-i-1])break;
        }
        if(i!=s.length())cout<<s.length();
        else cout<<s.length()-1;
    }


}