竞赛讨论区 > 牛客小白月赛31 题解
头像
祝嘉然3月7日生日快乐
编辑于 2021-01-10 23:53
+ 关注

牛客小白月赛31 题解

本人初三，第一次给牛客比赛写题解，轻喷。

因为先开了B以37秒的差距痛失rk1。

代码给的都是考场代码，可能比较丑。（有些后加的注释）

upd:D题证明补了一下。

A. A｜B

考虑 和 的某一个二进制位 ，只有在两个都是 的情况下满足 。

所以不存在一位使得 和 那一位都是 （不然和会大于 or）。

考虑从高位到低位依次填 ，可以发现如果这一位 是 就一定要填 ，如果这一位 是 且目前填的前缀和 相等，那么也一定要填 （不然 就会 ）。

所以令 表示填到了第 位， 的前 位与 的前 位是否相等，的方案数。

转移的时候从高位到低位枚举 ，把这一位填 的情况分别转移。

总复杂度 。

代码：

#include <iostream>
#include <cstring>
using namespace std;
int dp[50][2];
int main(int argc, char** argv) {
    int T;
    cin >> T;
    while(T--)
    {
        memset(dp,0,sizeof dp);
        int a,b;
        cin >> a >> b;
        dp[30][1]=1;
        for(int i=29;i>=0;i--)
        {
            if(a&(1<<i))//这一位必须填0
            {
                if(b&(1<<i)) dp[i][0]=dp[i+1][0]+dp[i+1][1];//x这一位是1的话，从这一位开始前缀就不再相等，所以都转移到dp[i][0]
                else dp[i][0]=dp[i+1][0],dp[i][1]=dp[i+1][1];//x这一位是0，保持原来是否相等的状态
            }
            else
            {
                if(b&(1<<i)) dp[i][0]=dp[i+1][0]*2+dp[i+1][1],dp[i][1]=dp[i+1][1];//这一位可以任选
                else dp[i][0]=dp[i+1][0]*2,dp[i][1]=dp[i+1][1];//x这一位是0的话，只有前缀不等的情况可以填1，否则只能填0
            }
        }
        cout << dp[0][0]+dp[0][1]-1 << "\n";//题目要求b>=1，这里会多算一个0，所以要-1
    }
    return 0;
}

B. A + B

模拟题。

先算出表达式的值，再按要求输出。

把输入分成 一段，每段是一个字符，这个字符只能是 。

维护一个变量 ，表示上一个加号之后到当前位置组成的多位数的值。

如果是加号的话，就把 加到答案里。

如果是数字 的话，就把 更新成 。

分辨这个字符具体是多少的话，就根据每个数字的特征判断一下，比如加号的右下角是 '.'， 左边一列中间的字符是 。（具体可以看代码，这里就不一一列举了）

算出来答案之后按照格式从高位到低位输出，注意每一行的末尾没有'.'，每组数据之间用回车隔开。

代码（考场代码比较丑）：

#include <iostream>
using namespace std;
string a[10]={"###","..#","###","###","#.#","###","###","###","###","###"};
string b[10]={"#.#","..#","..#","..#","#.#","#..","#..","#.#","#.#","#.#"};
string c[10]={"#.#","..#","###","###","###","###","###","#.#","###","###"};
string d[10]={"#.#","..#","#..","..#","..#","..#","#.#","..#","#.#","..#"};
string e[10]={"###","..#","###","###","..#","###","###","..#","###","###"};//输出时候用的
int XX;
inline void print(int X,int x)//第X行
{
    if(x>=10)print(X,x/10);
    int t=x%10;
    if(x==XX)
    {

    if(X==1) cout << a[t] << '\n';
    if(X==2) cout << b[t] << '\n';
    if(X==3) cout << c[t] << '\n';
    if(X==4) cout << d[t] << '\n';
    if(X==5) cout << e[t] << '\n';
    }
    else
    {
        if(X==1) cout << a[t] << '.';
        if(X==2) cout << b[t] << '.';
        if(X==3) cout << c[t] << '.';
        if(X==4) cout << d[t] << '.';
        if(X==5) cout << e[t] << '.';
    }
}
int main(int argc, char** argv) {
    int T;
    cin >> T;
    while(T--)
    {
        string a,b,c,d,e;
        cin >> a >> b >> c >> d >> e;
        int X=0,Y=0,ans=0;
        for(int i=0;i<a.size();i+=4)//四列一组
        {
            int x=0;
            if(e[i+2]=='.')//加号
            {
                ans+=X,X=0;//把当前数加到答案
                continue;
            }//判断这个数是多少
            if(a[i]=='.'&&c[i]=='.'&&e[i]=='.') x=1;
            else if(b[i]=='#'&&c[i]=='#'&&d[i]=='.'&&e[i]=='.'&&c[i+1]=='.'&&a[i+1]=='#') x=7;
            else if(e[i]=='.'&&d[i]=='.') x=4;
            else if(b[i]=='.'&&d[i]=='.') x=3;
            else if(c[i+1]=='.') x=0;
            else if(b[i]=='#'&&b[i+2]=='#'&&d[i]=='#'&&d[i+2]=='#') x=8;
            else if(b[i+2]=='.'&&d[i]=='.') x=5;
            else if(b[i+2]=='.') x=6;
            else if(b[i]=='.') x=2;
            else x=9;
            X*=10,X+=x;//更新当前值
        }
        ans+=X;//把最后一个数加到答案
        XX=ans;
        for(int i=1;i<=5;i++)
        {
            print(i,ans);
        //    cout << "\n";
        }
        cout << "\n";
    }
    return 0;
}

C. 图像存储

第一问就对每个连通块 dfs 一遍。

考虑从一个连通块的左上角 dfs ，并且以任意固定优先级遍历，走的"路径"总是一样的。

比如优先级是右下上左：

1101
0111
1110

"路径"就是从 开始 右 下 右 右 上 回溯 回溯 下 左 左 回溯 回溯 回溯 回溯 回溯 回溯

给每个方向和“回溯”赋一个权值，这个操作序列就变成了 1 2 1 1 3 5 5 2 4 4 5 5 5 5 5 5。

如果两个连通块是全等的，那么操作序列一定是全等的，如果两个连通块不全等，那么操作序列一定不全等。

所以问题就变成了，给定若干个序列，判断有几个本质不同的序列，这个可以哈希+map或者别的方法判断。

总复杂度 其中 是连通块个数，而且跑不满。

#include <iostream>
#include <map>
#define mod 998244353
using namespace std;
int a[1005][1005],now1,now2;
const int fx[5]={0,0,1,-1},fy[5]={1,-1,0,0}; 
const int base1=27;
const int base2=23;
inline void dfs(int x,int y)
{
    for(int i=0;i<=3;i++)
    {
        int nx=x+fx[i],ny=y+fy[i];
        if(a[nx][ny])
        {
            now1=((long long)now1*base1+i+3)%mod;
            now2=((long long)now2*base2+i+7)%mod;
            a[nx][ny]=0,dfs(nx,ny);
        }
    }
    now1=((long long)now1*base1+11)%mod;
    now2=((long long)now2*base2+13)%mod;//双哈希操作序列
}
map <int,int> mp1,mp2;
int main(int argc, char** argv) {
    int n,m;
    while(cin >> n >> m)
    {
        mp1.clear(),mp2.clear();
        if(!n) break;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                char c;
                cin >> c;
                if(c=='1') a[i][j]=1;
                else a[i][j]=0;
            }
        }
        int cnt=0,ans=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(a[i][j])
                {
                    now1=now2=0;
                    a[i][j]=0,dfs(i,j);
                    ++cnt;
                    if(!mp1[now1]||!mp2[now2]) ++ans;
                    mp1[now1]=mp2[now2]=1;//map去重
                }
            }
        }
        cout << cnt << " " << ans << "\n"; 
    }
    return 0;
}

D. 坐标计数

结论：所有点最终都会变成 ，所以答案就是矩形大小。

证明：

如果 异奇偶，那么一次操作之后会变得同奇偶。

如果 都是奇数，那么一次操作之后都会变成偶数。

如果 都是偶数，二进制位下最后一个 就永远不会变了，能到 等价于 能到，所以把它们都 。

发现每次操作之后 二进制最高位不会增加，而在 都是偶数的时候，都会被 。

所以每个点会在 次内变成 。

#include <iostream>
using namespace std;
int main(int argc, char** argv) {
    int T;
    cin >> T;
    while(T--)
    {
        long long a,b,c,d;
        cin >> a >> b >> c >> d;
        cout << (max(a,c)-min(a,c)+1)*(max(d,b)-min(b,d)+1) << "\n";
    }
    return 0;
}

E. 解方程

结论：答案是 的因数个数。

目前也不太会证。

所以把 和 每个质因数次数加起来，然后 (次数+1) 的乘积就是答案。

#include <iostream>
#include <vector>
using namespace std;
inline long long F(long long x)
{
    long long rtn=0;
    for(long long i=2;i*i<=x;i++)
        if(x%i==0) rtn+=2-(i*i==x);
    return rtn;
}
long long cnt[1000005];
vector <long long> v;
int main(int argc, char** argv) {
    long long T;
    cin >> T;
    while(T--)
    {
        long long a,b;
        v.clear();
        cin >> a >> b;
        if(a==1&&b==1)
        {
            cout << 1 << "\n";
            continue;
        }
        long long ans=1;
        for(long long i=2;i*i<=a;i++)
        {
            while(a%i==0)
            {
                ans/=cnt[i]+1;
                v.push_back(i);
                ++cnt[i],a/=i;
                ans*=cnt[i]+1;
            }
        }
        if(a>1)
        {
                v.push_back(a);
            ans/=cnt[a]+1; 
            ++cnt[a];
            ans*=cnt[a]+1;
        }
        for(long long i=2;i*i<=b;i++)
        {
            while(b%i==0)
            {
                v.push_back(i);
                ans/=cnt[i]+1; 
                ++cnt[i],b/=i;
                ans*=cnt[i]+1;
            }
        }
        if(b>1)
        {
                v.push_back(b);
            ans/=cnt[b]+1; 
            ++cnt[b];
            ans*=cnt[b]+1;
        }
        for(auto t:v) cnt[t]=0;
        cout << ans << '\n';
    }
    return 0;
}

F. 消减整数

先暴力模拟一轮，假设减到了 ， 还剩下 。

由于自然数之和是平方级别的，所以 是根号级别的。

如果 ，答案就是 。

否则的话，之后每一轮都会剩下 。

所以答案就是 满足 的最小 。

暴力枚举 判断即可，可以发现最多判断 次。

复杂度 

#include <iostream>
using namespace std;
int main(int argc, char** argv) {
    int T;
    cin>> T;
    while(T--)
    {
        int n,X;
        cin >> n;
        X=n;
        int x=1;
        while(n>=x)
            n-=x++;//模拟
        for(int i=1;i<=X;i++)//枚举答案
        {
            if(n*i%x==0)
            {
                cout << i << "\n";
                break;
            }
        }
    }
    return 0;
}

G. 简单题的逆袭

发现 的时候一定无解（因为如果 满足条件，那么 一定满足条件）。

的时候也一定无解，（因为显然 的任意幂次 ）。

否则一定有解 （）。

所以就从小到大枚举 ，找到最大的合法的解。

由于 ，所以 。

复杂度 。

可能会爆 long long，所以可以用 double 或者 __int128 等方式实现。

#include <iostream>
using namespace std;
int main(int argc, char** argv) {
    int T;
    cin >> T;
    while(T--)
    {
        long long x,y;
        cin >> x >> y;
        if(x==0||x==1)//x<=1无解
        {
            puts("-1");
            continue;
        }
        if(y==0)//y=0无解
        {
            puts("-1");
            continue;
        }
        __int128 X=x;
        int ans=0;
        while(X<=y)//枚举答案
        {
            ++ans;
            X*=x;
        }
        cout << ans << "\n";
    }
    return 0;
}

H. 对称之美

如果 回文的话，当且仅当对于任意 满足 。

所以只需判断是否对于任意 ，满足 和 存在相同字符。

暴力判断任意两字符即可。

#include <iostream>
using namespace std;
string a[105];
int main(int argc, char** argv) {
    int T;
    cin >> T;
    while(T--)
    {
        int n;
        cin >> n;
        for(int i=1;i<=n;i++)
            cin >> a[i];
        int ans=1;
        for(int i=1;i<=n;i++)
        {
            int t=n-i+1;
            if(t<=i) break;
            int flag=0;
            for(auto x:a[i])//从a[i]里枚举字符
            {
                for(auto y:a[t])//从a[t]里枚举字符
                {
                    if(x==y){
                        flag=1;
                        break;
                    }
                }
                if(flag) break;
            }
            if(!flag)
            {
                ans=0;
                break;
            }
        }
        if(ans) puts("Yes");
        else puts("No");
    }
    return 0;
}

I. 非对称之美

考虑如果原串不是回文串，答案就是原串的长度。

如果原串所有字符都相等，那么答案一定是 。

否则答案一定是 。

证明：

如果一个长度为 的回文串 删掉第一个字符之后还是回文串，

那么一定有 （原串回文）， （删之后回文），所以 。

同理， ，。

所以 的所有字符都相等。

暴力判断是否回文，是否都相等即可。

#include <iostream>
using namespace std;
int main(int argc, char** argv) {
    string s;
    cin >> s;
    int x=0,y=s.size()-1;
    int F=1;
    for(auto t:s) if(t!=s[0]) F=0;//均相等
    if(F)
    {
        cout << 0;
        return 0;
     } 
    int flag=1;
    while(x<y)//回文
    {
        if(s[x]!=s[y])
        {
            flag=0;
            break;
        }
        ++x,--y;
    }
    cout << s.size()-flag;
    return 0;
}

J. 排列算式

首先 没有用。

显然如果总和 一定无解。

然后可以发现，如果只存在 那么一定合法。

构造性证明：

如果当前表达式 ，任选一个加法，否则任选一个减法。

如果没有加法/减法的话，就都选上，由于总和在 所以肯定合法。

所以就要尽可能消耗 和 。

只有在当前值 才能用 ， 才能用 。

首先先把 和 内部尽量消耗，之后至少有一个被用完了，不妨设剩下的是 。

然后用 或者 或者 可以消耗一个 。

（如果用了 就会白白浪费一些 ，如果同时用了 就相当于白浪费一个 一个 ）

尽量消完 后，如果还有 或者 个数不止一个，那么就无解，否则有解。

因为如果剩一个 可以一开始用掉，由于之前已经尽量消耗 ，所以之后的序列里不可能再出现 。

#include <iostream>
using namespace std;
int main(int argc, char** argv) {
    int T;
    cin >> T;
    while(T--)
    {
        int n,a,b,c,d,e,f;
        a=b=c=d=e=f=0;
        cin >> n;
        for(int i=1;i<=n;i++)
        {
            int x;
            cin >> x;
            if(x==1) ++a;
            if(x==2) ++b;
            if(x==3) ++c;
            if(x==-1) ++d;
            if(x==-2) ++e;
            if(x==-3) ++f;//统计个数
        }
        while(c&&f) --c,--f;//+3-3
        while(f&&a&&b) --a,--b,--f;//+1+2-3
        while(d&&e&&c) --d,--c,--e;//-1-2+3
        while(c&&d>=3) d-=3,--c;//-1-1-1+3
        while(f&&a>=3) a-=3,--f;//+1+1+1-3
        while(c&&e>=2&&a) e-=2,--c,--a;//-2+1-2+3
        while(f&&b>=2&&d) b-=2,--f,--d;//+2-1+2-3
        if(c>1||f||a+b+b+c+c+c-d-e-e-f-f-f<0||a+b+b+c+c+c-d-e-e-f-f-f>3)//判断总和以及剩余 +-3 个数
        {
            puts("No");
            continue;
        }
        else puts("Yes");
    }
    return 0;
}
2025最新求职资料大礼包领取
真题
历年笔试真题附答案
度小满校招数据库工程师第2批
中国农业银行校招笔试真题-模拟卷1
搜狐2018秋招第二批-社交产品中心-狐友产品专员及邮箱产品经理试卷
全部 >
面经
面试常考问题整理
23届联想面经分享： 秋招上岸
面试真题：经典海量数据处理题最详解析（下）
Springboot全套注解解析《看不懂算我输》
全部 >
内推
员工内推码获取
米哈游内推~内推码：AFX50～
全部 >
大家都在关注
校招日程表 笔试日历 ai模拟面试 面试宝典 剑指offer 知识点专项练习

全部评论

(1) 回帖
加载中...
话题 回帖
返回全部帖子

本文相关内容

等你来战

查看全部

热门推荐

牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”