牛客小白月赛31部分题题解
算是在牛客网参加的第一场比赛。
是小白月赛,难度应该是很低的。一共10题,时间是3小时。
结果我打了3题,果然不给力。
比赛的时候过的题目是D、H、I,比较简单,就不花时间赘述。
这里简单说下D题,反正就是写了个暴力,发现好像随便哪个点最后都可以变回(0,0),那么直接统计一共有多少个点就行。注意开Long long。
贴下比赛链接:
https://ac.nowcoder.com/acm/contest/10746
下面把我补的几个题目按照AC的顺序,简单写下题解:
G 简单题的逆袭
比赛时候死磕的是G题,题目很简单,输入x,y,求x^k<=y中最大的k。
显然分类讨论就可以了,我讨论的比较麻烦,无非就是x<y,x>y,x=y的时候,然后发现x=0或1的时候有点特殊,这个也都判出来了。关键的点在于,x<y的时候,要算k。前面一直套了个换底公式k=log(y)/log(x)在求,结果提交一直返回wa。中间也担心这里的精度问题,但是自己测试的数据都没什么问题。最后想着还是手算,结果用的x乘上去,最后溢出了。反正到结束也没有做出来。
最终还是改成了y除的形式,下面贴一下丑陋的代码:#include<bits/stdc++.h> using namespace std; int main() { int t; cin>>t; while(t--){ long long x,y; cin>>x>>y; if(x==y){ if(x==0){ cout<<-1<<endl; } else if(x==1)cout<<-1<<endl; else cout<<1<<endl; } else if(x>y){ if(y==0){ cout<<-1<<endl; } else if(y==1){ cout<<0<<endl; } else cout<<0<<endl; } else { if(x==0){ cout<<-1<<endl; } else if(x==1)cout<<-1<<endl; else { int k=0; long long t=x; for(;x<=y;k++){ y=y/t; } cout<<k<<endl; } } } return 0; }
F 消减整数
本题一开始的想法是直接模拟。然后想着用map记录下出现的数字,如果数字第二次出现了就impossible了。结果交上去直接T。果然小白赛不是暴力赛。
对于本题,首先尝试了下暴力找规律。果然,发现了一点规律。1,3,6,10,15这些数字是直接能够被减掉的。接着发现介于这些数字之间的数,有一些规律。
假设数为n,可以知道a[i]<n<a[i+1],这里假定a[i]是1,3,6,10...这些数字。
令△=n-a[i],然后执行n+△,如果超过a[i+1]了,那么就减掉a[i+1]再加上n,可以发现这样子肯定可以达到a[i+1],此时就可以结束了。同时可以发现,不可能存在impossible的情况。#include<bits/stdc++.h> using namespace std; int main() { int t,n; cin>>t; while(t--){ cin>>n; int N=n,ans=0; ans++; int k=sqrt(2*n); if(k*(1+k)<2*n)k++; int r=(1+k)*k/2; int l=k*(k-1)/2; int delta=n-l; while(n!=r){ ans++; n+=delta; while(n>r)n=n-r+N,ans++; } cout<<ans<<endl; } return 0; }
本题后来去看了下题解,这里贴上来作为参考 :
假设第一次不够减时,是想要减K而只剩下M。则第二次就会剩下2 * M,第三次剩下3 * M,直到剩下的数量大于等于K时减去K,减去K后剩下的又不足K,又要重头开始减。
所以题目就转化为:每次加M,大于等于K时就减掉K,问多少次以后归零。
稍加观察可以发现,归零的时候加的数值总和为K的倍数,而能够加的有只有M的倍数,所以题目是在问:最快加了多少次以后变为M,K的公倍数,就是求最小公倍数。A A|B
本题很容易发现要让a|b=a+b,只要转化成二进制以后,先计算a的二进制,然后找出对应位置上面的0,那么在这些位置上让b选择性的填1或者0就可以了。
第一反应其实是背包,不同位置上可以填1的地方权值不一样,把它们权值计算出来,然后问题就转变成了背包容量为x,任意选择不同的位置求组合的数量。结果一看x<=10^9,数组开不下,遂作罢。
于是想到数位dp,拉出了我的老年模板。#include<bits/stdc++.h> using namespace std; typedef long long ll; int b[40],c[40],dig[40],dp[40][4]; ll dfs(int pos,int pre,int sta,int limit){ if(pos==-1)return 1; if(!limit&&dp[pos][sta]!=-1)return dp[pos][sta]; int up=limit?dig[pos]:1; int sum=0; for(int i=0;i<=up;i++){ if(c[pos]==0&&i==1)continue; sum+=dfs(pos-1,i,limit,i==up&&limit); } if(!limit)dp[pos][sta]=sum; return sum; } ll solve(ll x){ int cnt=0; while(x){ dig[cnt++]=x%2; x=x/2; } memset(dp,-1,sizeof(dp)); return dfs(cnt-1,-1,0,1); } int main() { int t,a,x; cin>>t; while(t--){ memset(b,0,sizeof(b)); memset(c,0,sizeof(c)); cin>>a>>x; int cnt=0,tot=0; while(a){ b[tot++]=a%2; a=a/2; } for(int i=0;i<40;i++)c[i]=1; for(int i=0;i<tot;i++){ if(b[i]==1){ c[i]=0; } } cout<<solve(x)-1<<endl; } return 0; }
B A+B
看着简单写起来颇麻烦的一道模拟题。
我的思路是把每个数的3列用2的幂次存储一下,然后根据每3列算出一个数,得到结果后再将数字按照列还原放到数组中,最后输出。
写着写着代码就很长了。。
如果用map应该会方便点。。#include<bits/stdc++.h> using namespace std; int num[32][32][32]; char res[5][555]; struct node { int x,y,z; node(){} node(int _x,int _y,int _z):x(_x),y(_y),z(_z){} }p[11]; char shuzi[10]={'0','1','2','3','4','5','6','7','8','9'}; void init(){ num[31][17][31]=0; num[0][0][31]=1; num[29][21][23]=2; num[21][21][31]=3; num[7][4][31]=4; num[23][21][29]=5; num[31][21][29]=6; num[7][1][31]=7; num[31][21][31]=8; num[23][21][31]=9; num[4][14][4]=-1; p[0].x=31;p[0].y=17;p[0].z=31; p[1].x=0;p[1].y=0;p[1].z=31; p[2].x=29;p[2].y=21;p[2].z=23; p[3].x=21;p[3].y=21;p[3].z=31; p[4].x=7;p[4].y=4;p[4].z=31; p[5].x=23;p[5].y=21;p[5].z=29; p[6].x=31;p[6].y=21;p[6].z=29; p[7].x=7;p[7].y=1;p[7].z=31; p[8].x=31;p[8].y=21;p[8].z=31; p[9].x=23;p[9].y=21;p[9].z=31; } void solve(char c,int k){ int a=c-'0'; int x,y,z; x=p[a].x;y=p[a].y;z=p[a].z; //cout<<k<<' '<<x<<' '<<y<<' '<<z<<endl; for(int i=0;i<5;i++){ if(x&(1<<i))res[i][k*4+1]='#'; else res[i][k*4+1]='.'; } for(int i=0;i<5;i++){ if(y&(1<<i))res[i][k*4+2]='#'; else res[i][k*4+2]='.'; } for(int i=0;i<5;i++){ if(z&(1<<i))res[i][k*4+3]='#'; else res[i][k*4+3]='.'; } } int main() { int t; cin>>t; init(); while(t--){ string ans; int sum=0,shu; string s[55]; for(int i=0;i<5;i++)cin>>s[i]; int len=s[1].size(); int a[4]; memset(a,0,sizeof(a)); for(int i=1;i<=len+1;i++){ for(int j=0;j<5;j++){ if(s[j][i-1]=='#')sum=sum+(1<<j); } if(i%4){ a[i%4]=sum; sum=0; } else { shu=num[a[1]][a[2]][a[3]]; a[3]=a[1]=a[2]=0; sum=0; if(shu==-1)ans+="+"; else ans+=shuzi[shu]; } } int tmp=0,tot=0; for(int i=0;i<ans.size();i++){ if(ans[i]>='0'&&ans[i]<='9')tmp=tmp*10+ans[i]-'0'; else { tot+=tmp; tmp=0; } } tot+=tmp; ans=""; while(tot){ ans=shuzi[tot%10]+ans; tot/=10; } for(int i=0;i<ans.size();i++){ solve(ans[i],i); for(int j=0;j<5;j++)res[j][(i+1)*4]='.'; } for(int i=0;i<5;i++){ for(int j=1;j<ans.size()*4;j++){ cout<<res[i][j]; } cout<<endl; } cout<<endl; } return 0; }
暂时先填坑填到这里,等剩下的题做完了再补上。
更新一下,剩下的题打算再补一道。
C 图像存储
显然求个数是一个连通分量问题,我们dfs染色就好了。
关键是种类的计算,这里我考虑的是dfs的时候由于是规定方向的,因此我们去搜索一个连通分量的时候,记录下每次走的方向到一个字符串中,如果种类相同,他们生成的字符串一定是相同的。那么用map存储这个字符串判重就可以了。
交上去wa了,后来发现,回溯的过程也要记录,否则会出现字符串相同,但是连通分量不相同的情况。因此每次搜索方向的时候都记录到字符串就可以了。
考虑到本题的数据比较大,生成的字符串可能会过大。(当然string应该不受影响)。这里改用了字符串哈希来解决。亲测两种方法都可以ac。#include<bits/stdc++.h> using namespace std; int n,m,dir[][2]={0,1,0,-1,1,0,-1,0}; int vis[1005][1005],cnt,num[1000005]; char a[1005][1005]; char ch[]={'0','1','2','3'}; const int p=2333; const int mod=1e9+7; map<int,int>mp; string st; int hx; void dfs(int x,int y){ vis[x][y]=1; for(int i=0;i<4;i++){ int fx,fy; fx=x+dir[i][0]; fy=y+dir[i][1]; hx=hx*p%mod+i; hx=hx%mod; if(vis[fx][fy]||fx<1||fy<1||fx>n||fy>m||a[fx][fy]=='0')continue; vis[fx][fy]=1; dfs(fx,fy); } } int main() { while(~scanf("%d%d",&n,&m)){ if(n==0&&m==0)break; mp.clear(); memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)cin>>a[i][j]; cnt=0; int tot=0; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ hx=0; if(a[i][j]=='1'&&!vis[i][j]){ cnt++; dfs(i,j); if(mp[hx]==0)tot++,mp[hx]=1; } } } printf("%d %d\n",cnt,tot); } return 0; }