题解 | #牛客周赛30#

前言

• 本次比赛有出题人的直播录像讲解，若是更喜欢看视频的话，请点击链接跳转bilibili牛客周赛30讲解

A-小红的删字符

• 简单，跳过

B-小红的正整数

• 简单，不讲解了

以下是代码部分

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

string s;

signed main()
{
    cin >> s;
    sort(s.begin(), s.end());
    if(s[0] == '0')
        for(int i = 1; i < s.length(); i ++)
            if(s[i] != '0')
            {
                swap(s[0], s[i]);
                break;
            }

    cout << s << endl;

    return 0;
}

C-小红构造回文

思路:

• 回文字符串s，假设其中一个字符的位置是pos
  • 则与其对称的位置为s.length() - pos - 1 该字符串的下标为0 ~ s.length()
• 如果每个字符和相邻的不一样的字符交换后均不能保持回文，则输出，否则输出交换后的字符串

以下是代码部分

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

string s;

bool judge(string a, int pos)
{
  //交换这个字符串，与它右边的字符串
    swap(a[pos], a[pos + 1]);
  //两者的对称位置也交换，保证回文
    swap(a[a.length() - pos - 1], a[a.length() - pos - 2]);
  //判断交换后是否还保持回文
    if(a[a.length() - pos - 1] != a[pos] || a[a.length() - pos - 2] != a[pos + 1])
        return false;
  //如果保持回文则直接输出
    cout << a << endl;
    return true;
}

signed main()
{
    cin >> s;
    for(int i = 0; i < s.length() - 1; i ++)
      //找到一个字符，与它相邻的右边的字符不同时进行判断
        if(s[i] != s[i + 1])
            if(judge(s, i))
                return 0;
    cout << "-1\n";

    return 0;
}

D-小红整数操作

思路

• 抛开[l, r]的范围限制，易得x可能的值为值的倍数。

以下是代码部分

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

typedef long long ll;
ll gcd(ll a, ll b){return b ? gcd(b, a % b) : a;}

int main()
{
    ll x, y, l, r, ans = 0;
    cin >> x >> y >> l >> r;
  //计算最大公因数
    ll goncd = gcd(x, y);
      //找到最基础的值
    x /= goncd, y /= goncd;
      //判断范围是否合法，若合法，则计数
    for(ll i = 1; i * x <= r && i * y <= r; i ++)
        if(i * x >= l && i * y >= l)
            ans ++;
  //输出
    cout << ans << '\n';

    return 0;
}

• 更优解，参考代码来源——枫系

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

typedef long long ll;
ll x,y,l,r;

ll gcd(ll a, ll b){return b ? gcd(b, a % b) : a;}

int main()
{
    cin >> x >> y >> l >> r;
    ll n = gcd(x, y);
    x /= n;
    y /= n;
  //计算为使x，y大于l，n最小为多少
    ll min_n = max((l + x - 1) / x,(l+y-1) / y);
  //计算为使x, y小于r, n最大为多少
    ll max_n = min(r / x, r / y);
  //计算差值即可
    cout << max_n-min_n + 1;
}

E-小红树上染色

思路

• dp + dfs做法
• dfs具体看代码注释
• dp
  • 解释，表示以为根节点时，表示白色，表示红色
  • 表示以为根节点时,且此节点为白色时，子树的涂色种类数
  • 表示以为根节点时,且此节点为红色时，子树的涂色种类树

以下是代码部分, 代码参考来源——枫系

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

typedef long long ll;
const int N = 1e5+5, Mod = 1e9+7;
int n;
vector<int> tree[N];
ll f[N][2];
void dfs(int u,int father)
{
    f[u][0] = f[u][1] = 1;
  //遍历tree[u]中的相邻节点
    for(int x : tree[u])
      //若不是父节点，再进行下一步操作
        if(x != father)
        {
            dfs(x,u);
          //当根节点为白色时，种类数为自身为白色时的数量 * 子节点为红色时的数量
            f[u][0] = f[u][0] * f[x][1] % Mod;
          //当根节点为红色时，种类数为自身为白色时的数量 * 子节点为（红色或白色）时的数量
            f[u][1] = f[u][1] * (f[x][0] + f[x][1]) % Mod;
        }
}
int main()
{
    cin>>n;
  //建立邻接表
    for(int i = 1; i < n; i ++)
    {
        int u, v;
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    dfs(1,-1);
  //输出树的根部时，红色加白色的种类数的总和即使所求值
    cout<<(f[1][0]+f[1][1]) % Mod <<'\n';
    return 0;
}

F-小红叒战小紫

前情提要

引出乘法逆元

• 摘抄至CSDN
• 我们都知道（a + b） % p = (a % p + b % p) % p
  • (a * b) % p = (a % p) * (b % p) % p
• 而求(a/b)%p时，可能会因为a是一个很大的数，不能直接算出来，却又不能(a/b)%p=(a%p/b%p)%p
• 这个时候就需要乘法逆元了

乘法逆元：

• 若 则称 为 的逆元
• 写作
• 费马小定理
• 可由费马小定理得
• 所以可由快速幂计算出逆元

思路

• 均摘自出题的直播，直播回放
• 我们定义为：小红剩余恰好个血量，小紫剩余恰好个血量怪物时，需要进行的回合数
• 一共有4种情况：两人都抽到1(无事发生，转移到)，两人都抽到2(无事发生，转移到)，小红抽到1小紫抽到2(转移到)，小红抽到2小紫抽到1(转移到)我们列方程后即可推出转移方程：
• dp[i][j] = p1 * dp[i][j] + p2 * dp[i - 1][j] + p3 * dp[i][j - 1] + 1
• 变形：
• (1 - p1) * dp[i][j] = p2 * dp[i - 1][j] + p3 * dp[i][j - 1] + 1
• 推出：
• (p2 + p3) * dp[i][j] = p2 * dp[i - 1][j] + p3 * dp[i][j - 1] + 1

以下是代码部分，参考代码来源——出题人题目讲解直播回放

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

typedef long long ll;
int mod = 1e9 + 7;
ll dp[55][55];//dp[i][j]代表小红剩i个1，小紫剩j个1时，还需要的回合数
int t[3], tt[3];//t[i]代表小红的i战力的牌剩余几张，tt[i]代表小紫的i战力的牌剩几张
//快速幂
ll quick_power(ll base, ll pow)
{
    ll res = 1;
    while(pow)
    {
        if(pow & 1)
            res = res * base % mod;
        pow >>= 1;
        base = base * base % mod;
    }
    return res;
}
//乘法逆元
ll inv(ll x) {return quick_power(x, mod - 2);}

int main()
{
    int n, m, x;
    cin >> n >> m;
    for(int i = 0; i < n; i ++)
        cin >> x, t[x] ++;
    for(int j = 0; j < m; j ++)
        cin >> x, tt[x] ++;

    //特判，当小红和小紫都没牌的时候
    if(!t[2] && !tt[2])
        return cout <<0, 0;
    for(int i = 0; i <= n; i ++)
        for(int j = 0; j <= m; j ++)
        {
            if(i == 0 && j == 0) continue;
            //p2, 小红抽到1，小紫抽到2的概率
            ll p2 = (i * inv(i + t[2]) % mod) * (tt[2] * inv(j + tt[2]) % mod) % mod;
            //p3, 小红抽到2，小紫抽到1的概率
            ll p3 = (t[2] * inv(i + t[2]) % mod) * (j * inv(j + tt[2]) % mod) % mod;
            dp[i][j] = 1;
            if(i) dp[i][j] += p2 * dp[i - 1][j] % mod;
            if(j) dp[i][j] += p3 * dp[i][j - 1] % mod;
            dp[i][j] = dp[i][j] * inv(p2 + p3) % mod;
        }
    cout << dp[t[1]][tt[1]] << endl;

    return 0;
}