牛客竞赛

2023石家庄学院新生杯¶

H 天才少女泠鸢 yousa¶

原题链接

泠鸢yousa 和 Ilyina 在玩一个有趣的游戏。初始有 n 颗石子，双方轮流取走部分石子(最少取1颗，最多取k颗)，泠鸢yousa先手取石子，最后取石子的一方获胜。假设泠鸢yousa 和 Ilyina 都是绝顶聪明的天才少女，问最后谁会获胜？

博弈论

我们可以初始情况分为两种：

n 为 k + 1 的倍数。假设先手取 x 颗石子，那么后手只需要取 k + 1 - x 颗石子，就可以一直保持 n为 k + 1 的倍数，此时后手必胜。
n 不是 k + 1 的倍数。此时先手只需要将 n 变成 k + 1 的倍数，就可以复刻情况 1。变为先手必胜。

int main() {
    if (n % (k + 1) != 0) cout << 1 << endl; 
    else cout << 2 << endl;
    return 0;
}

牛客挑战赛 71¶

A 和的期望¶

原题链接

被遗忘的书籍 (nowcoder.com)

快速幂求逆元

费马小定理：\(a^{\text{MOD}-1} \equiv 1 \pmod{MOD}\)，可以转换为 \(a \cdot a ^{\text{MOD}-2} \equiv 1 \pmod{MOD} \text{ ①}\)。

题目中：\(x \cdot Q \equiv P \pmod{MOD}\)，可以转换为 \(\frac{x}{P} \cdot Q \equiv 1 \pmod{MOD} \text{ ②}\)

由①、②可推导出：\(\frac{x}{P} \equiv Q^{\text{MOD}-2} \pmod{MOD}\) ，可以转换为 \(x \equiv P \cdot Q^{\text{MOD}-2} \pmod{MOD}\)

// 快速幂 (x: 底数 y: 指数 p: MOD)
LL quickPower(LL x, LL y, LL p) {
    LL result = 1;
    x = x % p;
    while (y > 0) {
        if (y & 1)
            result = (result * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return result;
}

// Q^(MOD - 2)
LL Q_inv = quickPower(Q, MOD - 2, MOD);
// x = P * Q^(MOD - 2) % MOD
LL x = (P * Q_inv) % MOD;

牛客小白月赛 82¶

C 被遗忘的书籍¶

原题链接

被遗忘的书籍 (nowcoder.com)

状态压缩DP

分析最后三个字母，可以得出四种状态：空串、\(t\)、\(tx\)、\(txt\)。下一个出现的字符情况分别为\(x\)、\(t\)、\(*\)（其他字符），来分析出状态之间的转移。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD = 998244353;
const int N = 2e5 + 5;

LL dp[N][4];

int main() {
    dp[0][0] = 1;
    for(int i = 1; i < N; i ++ ) {
        dp[i][0] = dp[i - 1][2] * 25 + dp[i - 1][1] * 24 + dp[i - 1][0] * 25;
        dp[i][1] = dp[i - 1][1] * 1 + dp[i - 1][0] * 1;
        dp[i][2] = dp[i - 1][1] * 1;
        dp[i][3] = dp[i - 1][2] * 1 + dp[i - 1][3] * 26;
        dp[i][0] %= MOD;
        dp[i][1] %= MOD;
        dp[i][2] %= MOD;
        dp[i][3] %= MOD;
    }
    int T;
    cin >> T;
    while(T--) {
        int n;
        cin >> n;
        cout << dp[n][3] << endl;
    }
    return 0;
}

2023 传智杯初赛¶

E abb¶

原题链接

abb E-abb

DP

开一个后缀和数组 \(sum[n][26]\)，\(sum[i][j]\) 代表 \(j\) 对应的字母，在坐标 \(i\) 到 \(n\) 出现的次数。这样就能 \(O(1)\)查询到每个字母后缀的出现次数。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
#define LL long long 

int sum[N][26];

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    for(int i = n - 1; i >= 0; i --) {
        int temp = s[i] - 'a';
        sum[i][temp] = 1;
        for(int j = 0; j < 26; j ++) {
            sum[i][j] += sum[i + 1][j];
        }
    }
    LL ans = 0;
    for(int i = 0; i < n; i ++) {
        int temp = s[i] - 'a';
        for(int j = 0; j < 26; j ++) {
            if(j == temp || !sum[i][j]) continue;
            ans += sum[i][j] * (sum[i][j] - 1) / 2;
        }
    }
    cout << ans;
    return 0;
}