牛客小白月赛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;
}

牛客小白月赛31部分题题解

G 简单题的逆袭

F 消减整数

A A|B

B A+B

C 图像存储