【牛客小白月赛31】部分题解（除了CEJ三题以外）
写在前面的话
这场比赛打了两个半小时过了7题，剩下3题没时间开了。题目质量还是非常高的，不过难度偏大了一点。。
A
知识点：位运算
题意是求不大于x的数中，有多少数和a没有两个数位都是1。
先转为二进制，考虑a的每一位：
首先如果a的当前位是1，那么待选择的数当前位只能选择0，没有其他选项。
如果a的当前位是0，那么根据x的当前位分类讨论：
如果x当前位是1，那么对于待选择的数y而言，当前位若选择0则有的贡献（其中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
首先，一次能消完的一定是形如 的数。
那么可以先二分出小于等于n的最大的这种形式，那么令 ，
，则n每次要么减p1然后加n 要么减p2然后加n，这个问题就是看什么时候能回到n（完成一次循环）
我们发现，不管是减p1加n，还是减p2加n，最后一定是形成p2-p1的一个剩余系，并且这个剩余系要通过操作n的方式得出，所以最终能形成的就是 （或者
）这么多个数。
这也是循环的大小，即所求的解。
#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
这道题求 的最大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;
}
}
字节跳动公司氛围 560人发布
投递阿里国际数字商业集团等公司10个岗位 >