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

全部评论

(1) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐