2021-01-10 23:53 已编辑枝江大学 Java

关注

牛客小白月赛31 题解

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

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

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

upd:D题证明补了一下。

A. A｜B

考虑 $a$ 和 $b$ 的某一个二进制位 $a_x,b_x$ ，只有在两个都是 $1$ 的情况下满足 $a_x|b_x<a_x+b_x$ 。

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

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

所以令 $dp_{i,0/1}$ 表示填到了第 $i$ 位， $b$ 的前 $i$ 位与 $x$ 的前 $i$ 位是否相等，的方案数。

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

总复杂度 $O(T\log a)$ 。

代码：

#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

模拟题。

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

把输入分成 $4$ 一段，每段是一个字符，这个字符只能是 $0,1,2,3,4,5,6,7,8,9,+$ 。

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

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

如果是数字 $x$ 的话，就把 $now$ 更新成 $now\times 10+x$ 。

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

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

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

#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,1)$ 开始右下右右上回溯回溯下左左回溯回溯回溯回溯回溯回溯

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

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

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

总复杂度 $O(nm+CNT\times \log CNT)$ 其中 $CNT$ 是连通块个数，而且跑不满。

#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. 坐标计数

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

证明：

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

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

如果 $x,y$ 都是偶数，二进制位下最后一个 $0$ 就永远不会变了，能到 $(0,0)$ 等价于 $(\frac{x}{2},\frac{y}{2})$ 能到，所以把它们都 $/2$ 。

发现每次操作之后 $\max(x,y)$ 二进制最高位不会增加，而在 $x,y$ 都是偶数的时候， $x,y$ 都会被 $/2$ 。

所以每个点会在 $\leq 3\times log_2 max(x,y)$ 次内变成 $(0,0)$ 。

#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. 解方程

结论：答案是 $a\times b$ 的因数个数。

目前也不太会证。

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

$O(T(\sqrt a+\sqrt b))$

#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. 消减整数

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

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

如果 $y=0$ ，答案就是 $1$ 。

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

所以答案就是满足 $ky=0(\mod x)$ 的最小 $k$ 。

暴力枚举 $k$ 判断即可，可以发现最多判断 $O(x)$ 次。

复杂度 $O(T\sqrt n)$

#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. 简单题的逆袭

发现 $x=0,1$ 的时候一定无解（因为如果 $k$ 满足条件，那么 $k+1$ 一定满足条件）。

$y=0$ 的时候也一定无解，（因为显然 $x$ 的任意幂次 $>0$ ）。

否则一定有解（ $k=0$ ）。

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

由于 $x^k\leq y$ ，所以 $k \leq \log _x y$ 。

复杂度 $O(T\log y)$ 。

可能会爆 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. 对称之美

如果 $a$ 回文的话，当且仅当对于任意 $i$ 满足 $a_i=a_{n-i+1}$ 。

所以只需判断是否对于任意 $i$ ，满足 $s_i$ 和 $s_{n-i+1}$ 存在相同字符。

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

$O(Tn|s_i|^2)$

#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. 非对称之美

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

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

否则答案一定是 $\text{长度} -1$ 。

证明：

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

那么一定有 $a_1=a_n$ （原串回文）， $a_2=a_n$ （删之后回文），所以 $a_1=a_2$ 。

同理， $a_2=a_{n-1}=a_3$ ， $a_3=a_{n-2}=a_4\cdots$ 。

所以 $a$ 的所有字符都相等。

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

#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. 排列算式

首先 $+0$ 没有用。

显然如果总和 $\not \in [0,3]$ 一定无解。

然后可以发现，如果只存在 $-1,-2,+1,+2$ 那么一定合法。

构造性证明：

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

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

所以就要尽可能消耗 $+3$ 和 $-3$ 。

只有在当前值 $=0$ 才能用 $+3$ ， $=3$ 才能用 $-3$ 。

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

然后用 $-1-1-1$ 或者 $-2-1$ 或者 $-2+1-2$ 可以消耗一个 $+3$ 。

（如果用了 $+2$ 就会白白浪费一些 $-1,-2$ ，如果同时用了 $+1,-1$ 就相当于白浪费一个 $+1$ 一个 $-1$ ）

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

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

$O(nT)$

#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;
}