【题解】牛客周赛 round 1

A 游游画U

知识点： C语言语法

观察每个U的形状和厚度，然后按题意模拟输出即可。

参考代码：

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

#define N(a, b) (3 + (int)a##e##b)

const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};

int a[N(2, 5)], b[N(2, 5)];
int n, m;

int main() {
    cin >> n;
    assert(1 <= n && n <= 50);
    for (int i = 1; i <= 4 * n - (n + 1); ++i) {
        for (int j = 1; j <= n; ++j) {
            cout << "*";
        }
        for (int j = 1; j <= 2 * n; ++j) {
            cout << ".";
        }
        for (int j = 1; j <= n; ++j) {
            cout << "*";
        }
        cout << endl;
    }
    for (int i = 0; i <= n; ++i) {
        for (int j = 1; j <= i; ++j) {
            cout << ".";
        }
        for (int j = 1; j <= n; ++j) {
            cout << "*";
        }
        for (int j = 1; j <= 2 * n - 2 * i; ++j) {
            cout << ".";
        }
        for (int j = 1; j <= n; ++j) {
            cout << "*";
        }
        for (int j = 1; j <= i; ++j) {
            cout << ".";
        }
        cout << endl;
    }
    return 0;
}

B 游游的数组染色

知识点：乘法原理

我们需要做的是存取每个字符每种颜色的数量。若有 $a$ 个红色的 $x$ 和 $b$ 个蓝色的 $x$ ，那么根据乘法原理，取两个 $x$ 则有 $a * b$ 种取法。

参考代码：

#include <bits/stdc++.h>
using namespace std;
int a[202020];
int main() {
    int x;
    map<int,int>m[26];
    int n,i;
    cin>>n;
    for(i=0;i<n;i++)cin>>a[i];
    string s;
    long long res=0;
    cin>>s;
    for(i=0;i<n;i++)m[s[i]-'A'][a[i]]++;
    for(auto i:m['B'-'A']){
        res+=1ll*i.second*m['R'-'A'][i.first];
    }
    cout<<res;
}

C 游游的交换字符

知识点：枚举

alt

我们注意题面的最后一句话，这句话其实是告诉我们，'1'的数量和'0'的数量相差的绝对值不大于1（否则一定无解）。那么我们便可以开始分类讨论，根据 $c n t (1) - c n t (0)$ 的情况进行讨论修改次数。

如果'0'和'1'的次数是相等的，那么最后有两种可能的字符串："010101……"或者"101010……"。否则，答案一定是唯一的。

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
    string s;
    cin>>s;
    int n=s.size();
    int num=0;
    for(auto i:s){
        if(i=='0')num++;
    }
    ll ans=1e15;
    if(n-num!=num){
        int pre=num>n-num?0:1;
        ll res=0;
        for(int i=0;i<n;i++){
            if(s[i]=='0'){
                res+=abs(i-pre);
                pre+=2;
            }
        }
        ans=min(ans,res);
    }else{
        int pre=0;
        ll res=0;
        for(int i=0;i<n;i++){
            if(s[i]=='0'){res+=abs(i-pre);
                pre+=2;
            }
        }
        ans=min(ans,res);
        pre=1;
        res=0;
        for(int i=0;i<n;i++){
            if(s[i]=='0'){res+=abs(i-pre);
                pre+=2;
            }
        }
        ans=min(ans,res);
    }
    cout<<ans<<endl;
}

D 游游的9的倍数

知识点：dp

非常经典的dp了，设 $d p [i] [j]$ 为取前 $i$ 个字符，取一个子序列模9为 $j$ 的方案数，那么可以轻松得到转移方程。

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

#define N(a, b) (3 + (int)a##e##b)

const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
const int mod = 7 + 1e9;

char s[N(2, 5)];
LL dp[N(2, 5)][9];

int main() {
    cin >> s + 1;
    int n = strlen(s + 1);
    assert(1 <= n && n <= 2e5);
    dp[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < 9; ++j) {
            dp[i][j] += dp[i - 1][j];
            dp[i][(j * 10 + s[i] - '0') % 9] += dp[i - 1][j];
            dp[i][j] %= mod;
            dp[i][(j * 10 + s[i] - '0') % 9] %= mod;
        }
    }
    cout << (dp[n][0] - 1 + mod) % mod << endl;
    return 0;
}