牛客竞赛

2023石家庄学院新生杯

H 天才少女泠鸢 yousa

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

博弈论

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

1. n 为 k + 1 的倍数。假设先手取 x 颗石子，那么后手只需要取 k + 1 - x 颗石子，就可以一直保持 n为 k + 1 的倍数，此时后手必胜。
2. 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

!!!原题链接 abbE-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;
}