牛客小白月赛31 题解
我是个小菜鸡...只是从今天开始是我认真学习的第一天)不想当划水怪了.赛后感觉和赛时真不一样...
A.A｜B
我写的是数位dp...第一次自己写出数位dp也挺激动的,虽然挺水的..
首先我们开个f[2][31]数组来记忆化一下,然后就是模拟这个过程了,看这位是不是已经比x小了,小了下一位可以任意选...然后模拟下去就好了,代码写的虽然长点,但是思路很清晰,最后减去0的情况.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+6;
const int mod=1e9+7;
int x,a;
int f[2][31];
int dfs(int u,int k,bool limit)
{
int res=0;
if(!limit&&f[k][u]!=-1) return f[k][u];
if(u==0)
{
if(a&(1<<u)&&k==1) return 0;
else return 1;
}
if(limit)
{
if(x&(1<<(u-1)))//下一位是1.
{
if(a&(1<<(u-1)))
{
res+=dfs(u-1,0,0);
}
else
{
res+=dfs(u-1,0,0);
res+=dfs(u-1,1,1);
}
}
else//下一位是0.
{
if(a&(1<<(u-1)))
{
res+=dfs(u-1,0,1);
}
else
{
res+=dfs(u-1,0,1);
}
}
}
else
{
if(x&(1<<(u-1)))//下一位是1.
{
if(a&(1<<(u-1)))
{
res+=dfs(u-1,0,0);
}
else
{
res+=dfs(u-1,0,0);
res+=dfs(u-1,1,0);
}
}
else//下一位是0.
{
if(a&(1<<(u-1)))
{
res+=dfs(u-1,0,0);
}
else
{
res+=dfs(u-1,0,0);
res+=dfs(u-1,1,0);
}
}
}if(!limit) f[k][u]=res;
return res;
}
int main()
{
int T;cin>>T;
while(T--)
{
cin>>a>>x;
memset(f,-1,sizeof f);int dep=0;
for(int i=30;i>=0;i--)
{
if(x>>i&1) dep=max(dep,i);
}
if(a&(1<<dep))
{
printf("%d\n",dfs(dep,0,0)-1);
}
else
{
printf("%d\n",dfs(dep,0,0)+dfs(dep,1,1)-1);
}
}
return 0;
}B.A + B
模拟..
#include <bits/stdc++.h>
using namespace std;
char res[6][1000];
map<string,int>mp = {
{"..#..#..#..#..#",1},
{"###..#####..###",2},
{"###..####..####",3},
{"#.##.####..#..#",4},
{"####..###..####",5},
{"####..####.####",6},
{"####.##.#..#..#",7},
{"####.#####.####",8},
{"####.####..####",9},
{"####.##.##.####",0},
{"....#.###.#....",-1}
};
map<int,string>mp2;
int main()
{
ios;
for(auto it:mp)
{
mp2[it.second] = it.first;
}
int t;
for(cin>>t;t;t--)
{
int n=5;
string raw[6]={};
for(int i = 1;i<=n;i++)cin>>raw[i];
n=raw[1].size();
int cnt=1+(n-3)/4;
ll ans=0,tmp=0;
for(int i=1;i<=cnt;i++)
{
string que = "";
for(int y = 1;y <= 5;y++)
for(int j = 1;j <= 3;j++)
{
int x = (i - 1)*4 + j;
que += raw[y][x-1];
}
if(mp[que]==-1)
{
ans+=tmp;
tmp=0;
}
else
{
tmp*=10;
tmp+=mp[que];
}
}
ans+=tmp;
cnt=0;
ll ans2=ans;
vector<int>tmp3 = {};
while(ans2)
{
cnt++;
tmp3.push_back(ans2%10);
ans2 /= 10;
}
reverse(tmp3.begin(),tmp3.end());
memset(res,0,sizeof res);
for(int i = 1;i <= cnt;i++)
{
string u = mp2[tmp3[i-1]];
for(int y = 1;y <= 5;y++)
{
for(int j = 1;j <= 3;j++)
{
int x = (i-1)*4+j;
char now = u[(y-1)*3 + j - 1];
res[y][x] = now;
}
}
for(int y = 1;y <= 5;y++)
{
res[y][i*4] = '.';
}
}
n=(cnt-1)*4+3;
for(int y=1;y<=5;y++)
{
for(int i=1;i<=n;i++) cout<<res[y][i];
cout << endl;
}
if(t) cout<<'\n';
}
return 0;
}C.图像存储
把dfs序当成哈希值,然后随便选个base和mod都能过.
#include <bits/stdc++.h>
using namespace std;
const int N=1e3+10;
char s[N][N];
int n,m;
bool vis[N][N];
int hx=0;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
const int base=131;
const int mod=1e9+7;
void dfs(int x,int y)
{
if(x>n||x<1||y>m||y<1||vis[x][y]||s[x][y]=='0') return;
vis[x][y]=true;
for(int i=0;i<4;i++)
{
dfs(x+dx[i],y+dy[i]);
hx=(hx*base%mod+5)%mod;
}hx=(hx*base%mod+13)%mod;
}
map<int,bool>mp;
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n==0&&m==0) break;
mp.clear();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
vis[i][j]=false;
for(int i=1;i<=n;i++)
{
scanf("%s",s[i]+1);
}int res=0,ans=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(s[i][j]=='1'&&!vis[i][j])
{
res++;
hx=0;
dfs(i,j);
if(!mp[hx]) ans++,mp[hx]=true;
}
}
}
printf("%d %d\n",res,ans);
}
return 0;
}D. 坐标计数
看下样例就知道是面积了.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int T;
cin>>T;
while(T--)
{
ll x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
cout<<(y2-y1+1)*(x2-x1+1)<<'\n';
}
return 0;
}E.解方程
ax+by=xy->y=ax/(x-b)=(a(x-b)+ab)/(x-b)->y=a+ab/(x-b).然后x,y要是正整数,所以x-b>0的,然后就是看a*b的因子数了.
然后就是质因子数量+1的乘积,可以理解为选0-n个.
#include <bits/stdc++.h>
using namespace std;
int main()
{
int T;
for(cin>>T;T;T--)
{
int ansa,ansb;
int a,b;cin>>a>>b;
map<int,int>cnt;
for(int i=2;i*i<=a;i++)
{
while(a%i==0) cnt[i]++,a/=i;
}if(a!=1) cnt[a]++;
for(int i=2;i*i<=b;i++)
{
while(b%i==0) cnt[i]++,b/=i;
}if(b!=1) cnt[b]++;
int ans=1;
for(auto x:cnt)
{
ans*=(x.second+1);
}cout<<ans<<'\n';
}
return 0;
}F.消减整数
开始看这题的时候就读错了,读对了之后...emmm.暴力算一下就好了.
#include <bits/stdc++.h>
using namespace std;
int main()
{
int T;
for(cin>>T;T;T--)
{
int n;int x=1;cin>>n;
while(n-x>=0) n-=x,x++;
for(int i=1;;i++)
{
if(i*n%x==0)
{
cout<<i<<'\n';break;
}
}
}
return 0;
}G.简单题的逆袭
注意爆ll(可以开int128),然后卡精度,不能直接log2之类的,只能模拟取log的过程.我被这题wa傻了.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+65;
int main()
{
int T;scanf("%d",&T);
while(T--)
{
ll x,y;
scanf("%lld%lld",&x,&y);
if(x<=1||!y)
{
puts("-1");
}
else
{
int Ans=0;
while(y)
{
y/=x;
Ans++;
}
cout<<Ans-1<<endl;
}
}
return 0;
}H.对称之美
遍历这个串以及和它对称的那个串是不是存在相同的即可.
#include <bits/stdc++.h>
using namespace std;
const int N=105,M=27;
bool f[M];
int main()
{
int T;scanf("%d",&T);
while(T--)
{
string s[N];
int n;scanf("%d",&n);
for(int i=1;i<=n;i++) cin>>s[i];
bool flag=true;
for(int i=1;i<=n/2;i++)
{
memset(f,false,sizeof f);
for(int k=0;k<s[i].size();k++)
{
f[s[i][k]-'a']=true;
}
int j=n-i+1;bool fl=false;
for(int k=0;k<s[j].size();k++)
{
if(f[s[j][k]-'a']) fl=true;
}if(!fl) flag=false;
}
if(flag) puts("Yes");
else puts("No");
}
return 0;
}I.非对称之美
注意aaaaa这种情况就好了.
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+65;
char s[N];
int main()
{
bool flag=true;int n;
scanf("%s",s+1);n=strlen(s+1);
for(int i=1;i<=n/2;i++)
{
if(s[i]!=s[n-i+1]) flag=false;
}int len=0;
if(flag)
{
bool f=true;
for(int i=2;i<=n;i++)
if(s[i]!=s[i-1]) f=false;
if(f) cout<<0<<endl;
else cout<<n-1<<endl;
}
else cout<<n<<endl;
return 0;
}J.排列算式
贪心的消就可以了...理性的把-3,3消完之后,其他一定是可以消掉的.
#include <bits/stdc++.h>
using namespace std;
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int cnt[8];//-3 -2 -1 1 2 3
memset(cnt,0,sizeof cnt);
int sum=0;int n;scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int x;cin>>x;
if(x==-3) cnt[1]++,sum-=3;//-3
else if(x==-2) cnt[2]++,sum-=2;//-2
else if(x==-1) cnt[3]++,sum-=1;//-1
else if(x==1) cnt[4]++,sum+=1;//1
else if(x==2) cnt[5]++,sum+=2;//2
else if(x==3) cnt[6]++,sum+=3;//3
}
if(sum>3||sum<0) puts("No");
else
{
//先把-3消掉.
//3 22-1 12 111
int num=cnt[1];
for(int i=1;i<=num;i++)
{
if(cnt[6]) cnt[1]--,cnt[6]--;
else if(cnt[5]>=2&&cnt[3]) cnt[1]--,cnt[3]--,cnt[5]-=2;
else if(cnt[4]&&cnt[5]) cnt[1]--,cnt[4]--,cnt[5]--;
else if(cnt[4]>=3) cnt[1]--,cnt[4]-=3;
}
//再把3消掉.
//-3 -2-21 -1-2 -1-1-1
// cout<<cnt[2]<<' '<<cnt[3]<<endl;
num=cnt[6];
for(int i=1;i<=num;i++)
{
if(cnt[1]) cnt[6]--,cnt[1]--;
else if(cnt[2]>=2&&cnt[4]) cnt[6]--,cnt[2]-=2,cnt[4]--;
else if(cnt[2]&&cnt[3]) cnt[6]--,cnt[2]--,cnt[3]--;
else if(cnt[3]>=3) cnt[6]--,cnt[3]-=3;
}
if(cnt[1]||cnt[6]>1) puts("No");
else puts("Yes");
}
}
return 0;
}
查看12道真题和解析
