2026牛客暑期多校训练营1

A. 2090 Virus

实现
字符串

签到成功。

cpp

#include <iostream>

using namespace std;

bool yuan(char c) {
    if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') return true;
    else return false;
}

bool check(string s) {
    if (s.length() != 8) return false;
    for (int i = 0; i < 8; ++i) {
        if ((i & 1) && !yuan(s[i]) || !(i & 1) && yuan(s[i])) return false;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    while (n--) {
        string s;
        cin >> s;
        cout << (check(s) ? "Suspected Virus" : "Well-Being") << endl;
    }
    return 0;
}

B. Fish Eating

图论
数据结构
并查集

类似 Kruskal 重构树 + 并查集的思路，考虑对不同 v 值的连通块情况建树

每次更新的 v 值一定变大，只会产生父亲和兄弟，不会成环
每次查询根节点只会变高，所以可以用带权并查集均摊 O(n) 做查询

边权维护从某个点开始（假定大小只有 1）能吃掉父亲节点需要最少的额外大小，并查集合并的时候对路径取 max。

我开出来了思路，但是只开出了 80%，最后还是 Moscenix 佬调对了。

cpp

#include <iostream>
#include <set>
#define int long long

using namespace std;

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

typedef long long LL;

LL cnt[N], f[N], w[N];
int fa[N];
int n, m, q;

int get(int x, int y) {
    return (x - 1) * m + y;
}

int getfa(int x) {
    if (x == fa[x]) return x;
    int p = fa[x];
    int root = getfa(p);
    f[x] = max(f[x], f[p]);
    fa[x] = root;
    return root;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> q;
    LL ls = 0;
    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            int x, y, v;
            cin >> x >> y >> v;
            x ^= ls;
            y ^= ls;
            int p = get(x, y);
            cnt[p] = 1;
            w[p] = v;
            fa[p] = p;
            f[p] = 0;
            set<int> roots;
            for (int i = 0; i < 4; ++i) {
                int tx = x + dx[i];
                int ty = y + dy[i];
                if (tx < 1 || tx > n || ty < 1 || ty > m) {
                    continue;
                }
                int np = get(tx, ty);
                if (cnt[np]) {
                    roots.insert(getfa(np));
                }
            }
            for (int root : roots) {
                cnt[p] += cnt[root];
                fa[root] = p;
                f[root] = max(0LL, v - cnt[root] + 1);
            }
            ls = cnt[p] - 1;
            cout << ls << '\n';
        } else {
            int x, y;
            cin >> x >> y;
            x ^= ls;
            y ^= ls;
            int p = get(x, y);
            getfa(p);
            ls = max(0LL, f[p] - w[p]);
            cout << ls << '\n';
        }
    }

    return 0;
}

D. Something Different

E. Permutation Evaluation

数学
实现

队友签到，系数从 -n 开始每次 + 2，然后直接求和。

F. Permutation Generation

数学
构造

可恶的诈骗题，最终卡了 1h 多队友发现了所有数同时 + 1 取模结果不变。

G. Precision Error?!

几何
Ad Hoc

还在诈骗，因为精度要求非常的低，导致跟 DRAM 一样的点阵对着两片，相邻点的水平距离开 1.01000001，然后控制距离为 0.99，正好就可以卡到那个精度的边界上。

H. Rock-Paper-Scissors Master

似乎还在诈骗

I. Combination of Two Nice Problems

J. Show Hand

模拟
实现

又是这个可恶的牌，大模拟，队友做出来了不补了

L. Substrings of Substrings

字符串
AC 自动机
数据结构

AC 自动机的模板，但是比较考优化，第一次知道 AC 自动机有 out 指针。

cpp

#include <iostream>
#include <queue>
#include <vector>
#include <climits>

using namespace std;

typedef long long LL;
const int N = 100010, M = 300010;
const int MOD = 998244353;

LL a[N], ps[N], is[N];
int trie[M][26], ne[M], out[M], tot;
int pos[M], len[M];
bool flag[M];
LL pre[N], suf[N];
LL res[M][2];
int idx[M];
int n, q;

void insert(string &t, int flg) {
    int p = 0;
    for (char c : t) {
        if (trie[p][c - 'a']) p = trie[p][c - 'a'];
        else trie[p][c - 'a'] = ++tot, p = tot;
    }
    idx[flg] = p;
    flag[p] = true;
    len[p] = t.length();
}

void build() {
    queue<int> q;
    for (int i = 0; i < 26; ++i) {
        if (trie[0][i]) q.emplace(trie[0][i]);
    }
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i = 0; i < 26; ++i) {
            int &y = trie[x][i];
            if (!y) y = trie[ne[x]][i];
            else {
                ne[y] = trie[ne[x]][i];
                if (flag[ne[y]]) out[y] = ne[y];
                else out[y] = out[ne[y]];
                q.emplace(y);
            }
        }
    }
}

LL calc_s(int prel, int l, int r) {
    return (((((is[l - 1] - is[prel]) % MOD + MOD) % MOD - ((ps[l - 1] - ps[prel]) % MOD * prel % MOD)) % MOD + MOD) % MOD * (n - r + 1) % MOD + 
        ((LL)(l - prel) * (n - r + 1)) % MOD * ((ps[r] - ps[l - 1]) % MOD) % MOD + 
        (((LL)(n + 1) * ((ps[n] - ps[r]) % MOD) % MOD - (is[n] - is[r])) % MOD + MOD) % MOD * (l - prel) % MOD) % MOD;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    string s, t;
    cin >> n >> q >> s;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        ps[i] = ps[i - 1] + a[i];
        is[i] = ((is[i - 1] + a[i] * i) % MOD + MOD) % MOD;
        pre[i] = max(pre[i - 1] + a[i], 0LL);
    }
    for (int i = n; i; --i) {
        suf[i] = max(suf[i + 1] + a[i], 0LL);
    }
    for (int i = 1; i <= q; ++i) {
        cin >> t;
        insert(t, i);
    }
    build();
    for (int i = 1, j = 0; i <= n; ++i) {
        j = trie[j][s[i - 1] - 'a'];
        int p = flag[j] ? j : out[j];
        while (p) {
            int l = i - len[p] + 1, r = i;
            if (!pos[p]) res[p][0] = pre[l - 1] + suf[r + 1] + ps[r] - ps[l - 1];
            else res[p][0] = max(res[p][0], pre[l - 1] + suf[r + 1] + ps[r] - ps[l - 1]);
            res[p][1] = ((res[p][1] + calc_s(pos[p], l, r)) % MOD + MOD) % MOD;
            pos[p] = i - len[p] + 1;

            p = out[p];
        }
    }
    for (int i = 1; i <= q; ++i) {
        cout << res[idx[i]][0] << ' ' << res[idx[i]][1] << '\n';
    }
    return 0;
}

A. 2090 Virus ​

B. Fish Eating ​

D. Something Different ​

E. Permutation Evaluation ​

F. Permutation Generation ​

G. Precision Error?! ​

H. Rock-Paper-Scissors Master ​

I. Combination of Two Nice Problems ​

J. Show Hand ​

L. Substrings of Substrings ​