A. Simple Palindrome

题意

让你构造一个长度为n的，只含5种字符的，回文子串最少的字符串

大概思路

同种字符内部配对，对回文子串总数的贡献与字符位置无关。但若出现“aba”这种相间的，则会产生额外贡献。根据自觉，不能让整个字符串字符全一样，得尽可能平均。

参考代码

void solve(){
    int n;
    cin >> n;

    string s = "aeiou";
    vector<int> a(5);
    for (int i = 0; i < n; i++) {
        a[i % 5]++;
    }
    for (int i = 0; i < 5; i++) {
        while (a[i]--) cout << s[i];
    }
    cout << "\n";
}

B2. The Strict Teacher (Hard Version)

题意

n个格子，上面有m个老师，进行q次询问，每次要回答“若学生在x处，则老师抓到学生的最短时间是多少”，老师学生互相能看到行动，所以都会最优地移动。（老师学生同时移动，每次都只能移动一格，或者原地不动）

大概思路

贪心，分类讨论学生在最左边的老师的左边和最右边的老师的右边的情况，以及被两个老师夹住的情况就行

参考代码

void solve(){
    int n, m, q;
    cin >> n >> m >> q;
    
    vector<int> p(m);
    for (auto &i : p) cin >> i;

    sort(p.begin(), p.end());

    while (q--) {
        int x;
        cin >> x;

        auto it = upper_bound(p.begin(), p.end(), x);

        if (it == p.end()) {
            cout << n - p.back() << "\n";
            continue;
        }
        if (it == p.begin()) {
            cout << p.front() - 1 << "\n";
            continue    ;
        }

        int i = it - p.begin();
        cout << (p[i] - p[i - 1]) / 2 << "\n";
    }
}

C. Lazy Narek

题意

给定n个长度为m的字符串，从中不改变顺序的情况下选任意的字符串拼接到一起，然后从左到右依次匹配 “n”, “a”, “r”, “e”, 和 “k”，循环匹配，要是遗漏了任何一个"narek"字符，GPT得1分，否则，每匹配成功一个"narek"，玩家得一分。问玩家得分 $score_n$ 和 GPT得分 $score_c$ 的差值最大为多少

大概思路

一开始看错题了，写了个逆天4维dp

考虑dp转移，设dp[i][j]代表考虑到第i个字符串时，以5个字符的第j个字符结尾时的差值最大值。

设从字符结尾为第j个开始，若选了第i个字符串，最后的字符结尾为k，得分变化为S，那么转移方程如下：

$$ dp[i + 1][k] = max(dp[i + 1][k], dp[i][j] + S) $$

然后注意边界条件和一些转移的细节就行。

参考代码

std::string mt = "narek";

void solve(){
    int n, m;
    std::cin >> n >> m;

    std::vector<std::string> a(n);
    for (auto &s : a) std::cin >> s;
    std::vector<std::array<i64, 5>> dp(n + 1);

    auto wk = [&](int now, int i) -> std::pair<i64, i64> {
        std::string& s = a[i];
        int ans = 0;
        for (int i = 0; i < m; i++) {
            if (s[i] == mt[now]) {
                now++;
                if (now == 5) ans += 10, now = 0;
            }
            if (mt.find(s[i]) != -1) ans--;
        }
        return {now, ans};
    };

    for (int i = 0; i <= n; i++)for (int j = 0; j < 5; j++) {
        dp[i][j] = -2e9;
    }
    dp[0][0] = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 5; j++) {
            dp[i + 1][j] = std::max(dp[i + 1][j], dp[i][j]);
            auto [N, S] = wk(j, i);
            dp[i + 1][N] = std::max(dp[i + 1][N], dp[i][j] + S);
        }
    }
    i64 ans = 0;
    for (int i = 0; i < 5; i++) ans = std::max(ans, dp[n][i]);
    std::cout << ans << "\n";
}