2026牛客暑期多校训练营1

LeAf146

公告

叶子的博客，随便看看吧。

Learn More

标签

服务器网络字符串 ACM Agnet AI Blog Blogging codeforces

4281 字

17 分钟

2026牛客暑期多校训练营1

2026-08-03

ACM

Blog

/

ACM

A. 2090 Virus #

给定 $n$ 个字符串，问每个字符串是否满足下述条件：

字符串长度恰好为 $8$ 。
字符串中第 $1,3,5,7$ 个字符是辅音字母。
字符串中第 $2,4,6,8$ 个字符是元音字母。

模拟。

1
int check(string s, int pos) {
2
    if (s[pos] == 'a' || s[pos] == 'e' || s[pos] == 'i'
3
        || s[pos] == 'o' || s[pos] == 'u')
4
        return 1;
5
    else
6
        return 0;
7
}
8
void solve() {
9
    string s;
10
    cin >> s;
11
    if (s.size() == 8
12
        && (check(s, 1) && check(s, 3) && check(s, 5) && check(s, 7))
13
        && !(check(s, 0) || check(s, 2) || check(s, 4) || check(s, 6)))
14
        cout << "Suspected Virus\n";
15
    else
16
        cout << "Well-Being\n";
17
}

C. Fish Eating #

给定一个 $n\times m$ 的网格，在网格上有一个大鱼吃小鱼的游戏，要求不经过障碍、可以吃不大于自己的鱼、每吃一条鱼大小加 $1$ 。初始时所有格子都是障碍，有 $q$ 个操作，操作有两种：

在 $(x,y)$ 处放一条大小为 $v$ 的鱼，问这条鱼最多吃掉多少鱼。保证每个 $v$ 都不小于之前的 $v$ 。
假设将 $(x,y)$ 处的鱼放大，问最少放大多少，能使这条鱼吃掉最多的鱼。

关键在于 “保证每个 $v$ 都不小于之前的 $v$ “，这样我们可以使用并查集。对于每个操作 1，显然我们可以将其相邻的所有鱼连同自己加入到一个集合。这样可以吃到的鱼就是 $最终的集合大小-1$ 。

实际上我认为难点在于处理操作 2，而 mx 数组就是为了实现这个操作。对于鱼 ind，用 mx[ind] 表示吃掉所在集合全部鱼所需的最小 $v$ ，用 mx[ind] 减去原本的 v[ind] 与 $0$ 取较大值即为答案。那要怎么维护 mx 数组呢？

首先我们要确定，每次加入新的鱼，都需要对他周围鱼的 mx 进行更新。把新鱼吃掉所需的最小 $v_{min}=v_{now}-sz_{nxt}+1$ ，即新鱼的 $v_{now}$ 减去周围鱼所在集合合体能增加的重量。而此时周围鱼的 mx 就是 $max(mx_{now},v_{min})$ 。

在通过 merge 合并新鱼之后，更新原本集合的所有 mx 显然是不现实的，所以就像通过 find 传递 f 一样，我们也通过 find 传递 mx。每次我们把当前的 mx[x] 更新为自己和父亲节点中较大的 mx，通过递归调用，即可更新当前节点到跟节点路径上所有未更新的的 mx。实际上，这类似于一种懒标记，只在需要的时候更新。

1
int n, m, q;
2
vector<vector<int>> g;
3
int dx[] = { 0, 0, -1, 1 }, dy[] = { -1, 1, 0, 0 };
4
struct DSU {
5
    vector<int> f, sz, mx, v;
6
    DSU() { }
7
    DSU(int n) { init(n); }
8
    void init(int n) {
9
        f.resize(n);
10
        iota(f.begin(), f.end(), 0);
11
        mx.assign(n, 0);
12
        v.assign(n, 0);
13
        sz.assign(n, 1);
14
    }
15
    int find(int x) {
16
        if (f[x] == x)
17
            return x;
18
        int tmp = find(f[x]);
19
        mx[x] = max(mx[x], mx[f[x]]);
20
        return f[x] = tmp;
21
    }
22
    bool merge(int now, int nxt) {
23
        now = find(now);
24
        now = find(nxt);
25
        if (now == nxt)
26
            return false;
27
        f[nxt] = now;
28
        sz[now] += sz[nxt];
29
        mx[nxt] = max(mx[now], v[now] - sz[nxt] + 1);
30
        return true;
31
    }
32
};
33
DSU dsu;
34
signed main() {
35
    cin >> n >> m >> q;
36
    g.resize(n, vector<int>(m, -1));
37
    dsu.init(q);
38
    int x, y, pre = 0, op, val = 0;
39
    for (int i = 0; i < q; i++) {
40
        cin >> op >> x >> y;
41
        x = x ^ pre;
42
        y = y ^ pre;
43
        x--;
44
        y--;
45
        if (op == 1) {
46
            g[x][y] = i;
47
            cin >> val;
48
            dsu.v[i] = val;
49
            for (int i = 0; i < 4; i++) {
50
                int nx = x + dx[i], ny = y + dy[i];
51
                if (nx >= 0 && nx < n && ny >= 0 && ny < m
52
                    && g[nx][ny] != -1) {
53
                    dsu.merge(i, g[nx][ny]);
54
                }
55
            }
56
            pre = dsu.sz[dsu.find(i)] - 1;
57
        } else {
58
            int ind = g[x][y];
59
            dsu.find(ind);
60
            pre = max(0LL, dsu.mx[ind] - dsu.v[ind]);
61
        }
62
        cout << pre << endl;
63
    }
64
    return 0;
65
}

E. Permutation Evaluation #

对于一个 $0$ 到 $n-1$ 的排列 $P$ ，定义其权值 $f(P)=\sum_{0\leq i<j<n}(P_{j}-P_{i})$ 。给定一排列，求其权值。

对于任意位置 $i$ ，其对于答案的贡献是 $v(i)=\sum_{i\leq j<n}(P_{j}-P_{i})=\sum_{i\leq j<n}P_{j}-(n-1-i)\times P_{i}$ 。

1
signed main() {
2
    int n;
3
    cin >> n;
4
    vector<int> p(n), pre(n);
5
    for (int i = 0; i < n; i++) {
6
        cin >> p[i];
7
    }
8
    pre[n - 1] = p[n - 1];
9
    for (int i = n - 2; i >= 0; i--) {
10
        pre[i] = pre[i + 1] + p[i];
11
    }
12
    int ans = 0;
13
    for (int i = 0; i < n - 1; i++) {
14
        ans += pre[i + 1] - (n - 1 - i) * p[i];
15
    }
16
    cout << ans << endl;
17
    return 0;
18
}

F. Permutation Generation #

对于一个 $0$ 到 $n-1$ 的排列 $P$ ，定义其权值 $f(P)=\sum_{0\leq i<j<n}(P_{j}-P_{i})$ 。给定一排列和两整数 $k,x$ 。求一排列 $P'$ 满足 $P'_k=x$ 且 $f(P)\equiv f(P') \pmod {n}$ 。

注意到，对于一排列 $P$ ，循环位移任意位后 $f(P) \bmod n$ 不变。记录原本 $x$ 所在位置 pos，循环位移位数即为 $(k-pos+n)\bmod n$ 。模拟循环位移即得答案。

1
signed main() {
2
    int n, k, x, pos = -1;
3
    cin >> n >> k >> x;
4
    vector<int> p(n);
5
    for (int i = 0; i < n; i++) {
6
        cin >> p[i];
7
        if (p[i] == x)
8
            pos = i;
9
    }
10
    int d = (k - pos + n) % n;
11
    for (int i = 0; i < n; i++) {
12
        cout << p[(i - d + n) % n] << ' ';
13
    }
14
    return 0;
15
}

G. Precision Error?!#

给定一个整数 $n$ ，需要构建一个点集 $S$ ，其中有不超过 $2n+2$ 个点位于三维欧几里得空间中。要求对于每个点 $P\in S$ 恰好有 $n$ 个不同的点 $Q\in S$ 满足 $dis(P,Q)=1$ ，其中 $dis(P,Q)$ 表示两点的欧几里得距离。允许误差 $\epsilon=0.01$ ，即满足下面条件视为正确答案：

对于任意两个不同的点 $P,Q \in S$ ，有 $dis(P,Q)>\epsilon$ 。
对于每个点 $P\in S$ ，恰好有 $n$ 个点 $Q\in S$ 满足 $1-\epsilon<dis(P,Q)<1+\epsilon$ 。

依旧注意到这一块。由于 $\epsilon$ 的存在，假设 $dis(P,Q)=1.001,|z_{P}-z_{Q}|=1$ ，可得到 $max(|x_{P}-x_{Q}|)=0.1002$ 。此时相对于 $(0,0,0)$ 处的点，在 $z=1$ 处恰好有长宽为 $0.1$ 的正方形可以放得开 $10$ 个满足 $dis(P,Q)>\epsilon$ 的点，在正方形中共可以放置 $100$ 个点。满足题意要求。

1
const double d=0.0105;
2
void solve(){
3
    int n;cin>>n;
4
    cout<<2*n<<endl;
5
    for(int i=0;i<n;i++){
6
       double x=(i%10)*d;
7
       double y=(i/10)*d;
8
       cout<<x<<' '<<y<<' '<<0.0<<endl;
9
    }
10
    for(int i=0;i<n;i++){
11
       double x=(i%10)*d;
12
       double y=(i/10)*d;
13
       cout<<x<<' '<<y<<' '<<1.0<<endl;
14
    }
15
}

H. Rock-Paper-Scissors Master #

Alice 和 Bob 玩一个 $k$ 轮的石头剪刀布游戏。游戏开始时，两人各有 $3$ 张牌，每张牌是石头 (R)、剪刀 (S) 或布 (P)。每轮游戏规则如下：

双方可看到彼此手中的全部 $6$ 张牌。
Alice 先选一张手牌打出。
Bob 在看到 Alice 打出的牌后，选择自己的一张牌打出。
根据标准规则判断胜负。若 Alice 获胜则得到 $3$ 分，平局则得到 $1$ 分，输得 $0$ 分。
双方丢弃打出的牌，并独自等概率地获得一张新的石头、剪刀或布。

Alice 希望最大化自己的期望总分，Bob 则希望最小化 Alice 的期望总分。给定游戏轮数 $k$ 、Alice 和 Bob 的初始手牌，求出双方均采用最优策略时，Alice 的最终得分。

期望 DP。其实在补题的时候对我影响最大的是编码状态。总纠结于 $100$ 种状态，想要找到一种最优编码，反倒浪费了很多时间，实际上直接用 3 进制也是可以的。下面给出一种 GPT 实现的 $100$ 种状态的编码方式。

1
int encode(int r, int s, int p) {//每人 10 种状态，分别作为十位和个位。
2
    int rank = r * 4 - r * (r - 1) / 2;
3
    rank += s;
4
    return rank;
5
}

这道题解决了编码之后的第二个点，就是要注意到，在足够多轮次之后，每一轮的期望得分收敛为常数这个事实。严谨的数学推导我不太擅长，但是在被告知这个事实后，略加思考便可以知道这个结论的正确性。

也就是说，大 $k$ 对于我们的影响微乎其微，我们只需要计算出在不同初始状态下的小轮次中的期望得分即可。这就是 init() 在做的事。而对于每轮游戏，我们不能想当然地认为 Bob 一定会获胜，Bob 可能当前手中没有获胜所需的牌，也可能赢了这轮，反倒导致后面全盘皆输，所以我们需要计算所有可能后的期望。每轮游戏 Alice 和 Bob 各自可能出 $3$ 种牌，可能获得 $3$ 种牌，共 $3^4=81$ 种可能，而我们只需要计算较小轮次。假设计算前 $100$ 轮，最优编码下，只需要计算 $100\times 100\times 81=8.1\times 10^5$ 次。即使设置共 $729$ 种状态，也只需要计算 $729\times 100\times 81 \approx 6 \times 10^6$ 次。

对于每轮游戏期望得分的计算，由于我们枚举了状态，假设开始前状态为 $S'$ ，结束后状态为 $S$ ，当前轮次得分为 $score$ 。这里使用开始前状态为 $S'$ 的原因是，对于状态 $S$ ，我们有不同的方式可以到达。每种出牌的可能我们需要计算得分，然后再根据得到的牌来确定状态，最后确定期望得分。而 Bob 希望期望得分最小，Alice 希望期望得分最大。所以 Bob 选择所有期望里最小的，而 Alice 选择 Bob 的选择中最大的。那么状态转移显然为 $dp[i+1][S]= max\left( min\left( score+ \frac{1}{9}\sum dp[i][S'] \right) \right)$ 。

在大轮次游戏中，由于每轮的期望得分收敛，完全可以用一个常数乘以轮数代替，最后得到如下代码。

1
map<char, int> mp = { { 'R', 0 }, { 'S', 1 }, { 'P', 2 } };
2
double dp[101][729];
3
int encode(vector<int> state) {
4
    int ans = 0;
5
    for (int i = 5; i >= 0; i--) {
6
        ans = ans * 3 + state[i];
7
    }
8
    return ans;
9
}
10
vector<int> decode(int x) {
11
    vector<int> state(6);
12
    for (int i = 0; i < 6; i++) {
13
        state[i] = x % 3;
14
        x /= 3;
15
    }
16
    return state;
17
}
18
double win(int a, int b) {
19
    if ((a == 0 && b == 1) || (a == 1 && b == 2) || (a == 2 && b == 0))
20
        return 3;
21
    else if (a == b)
22
        return 1;
23
    else
24
        return 0;
25
}
26
void init() {
27
    for (int i = 1; i < 101; i++) {
28
        for (int j = 0; j < 729; j++) {
29
            vector<int> state = decode(j);
30
            double mx = 0;
31
            for (int a = 0; a < 3; a++) {
32
                double mn = 1e18;
33
                for (int b = 3; b < 6; b++) {
34
                    double sum = win(state[a], state[b]);
35
                    for (int nxt1 = 0; nxt1 < 3; nxt1++) {
36
                        int tmp1 = state[a];
37
                        state[a] = nxt1;
38
                        for (int nxt2 = 0; nxt2 < 3; nxt2++) {
39
                            int tmp2 = state[b];
40
                            state[b] = nxt2;
41
                            sum += dp[i - 1][encode(state)] / 9;
42
                            state[b] = tmp2;
43
                        }
44
                        state[a] = tmp1;
45
                    }
46
                    mn = min(mn, sum);
47
                }
48
                mx = max(mx, mn);
49
            }
50
            dp[i][j] = mx;
51
        }
52
    }
53
}
54
void solve() {
55
    int k;
56
    cin >> k;
57
    string alice, bob;
58
    cin >> alice >> bob;
59
    vector<int> state(6);
60
    for (int i = 0; i < 3; i++) {
61
        state[i] = mp[alice[i]];
62
        state[i + 3] = mp[bob[i]];
63
    }
64
    if (k <= 100)
65
        cout << dp[k][encode(state)] << endl;
66
    else {
67
        double avg = (dp[100][0] - dp[99][0]);
68
        cout << dp[100][encode(state)] + avg * (k - 100) << endl;
69
    }
70
}
71
signed main() {
72
    cout << fixed << setprecision(12);
73
    init();
74
    int _t;
75
    cin >> _t;
76
    while (_t--)
77
        solve();
78
    return 0;
79
}

J. Show Hand #

模拟德州扑克。。没啥可说的，今年我见过的最极致最纯粹的模拟。

L. Substrings of Substrings #

AC 自动机 · 改。等有空再补题解吧，我要先补题了。。。

1
using namespace std;
2
const int MOD = 998244353;
3
int n, q;
4
string S;
5
vector<int> a, pre, minpre, maxsuff, prepre, presuff;
6
vector<int> length, lastpos, finalans, finalsum;
7
inline int mmod(int x) {
8
    x %= MOD;
9
    return (x < 0 ? (x + MOD) : x);
10
}
11
void solve(int id, int l) {
12
    int len = length[id];
13
    int r = l + len - 1;
14
    int mx = maxsuff[r + 1] - minpre[l];
15
    finalans[id] = max(finalans[id], mx);
16
    int previous = lastpos[id];
17
    int countl = l - previous, countr = n - r;
18
    int lsum = prepre[l];
19
    if (previous >= 0)
20
        lsum = mmod(lsum - prepre[previous]);
21
    int rsum = presuff[r + 1];
22
    finalsum[id] = mmod(finalsum[id] + mmod(mmod(countl) * rsum - mmod(countr) * lsum));
23
    lastpos[id] = l;
24
}
25
struct AC {
26
    struct Node {
27
        int child[26], fail, outputlink;
28
        vector<int> index;
29
        Node() {
30
            memset(child, -1, sizeof(child));
31
            fail = 0;
32
            outputlink = 0;
33
        }
34
    };
35
    vector<Node> tree;
36
    vector<int> length;
37
    AC(int q) {
38
        tree.emplace_back();
39
        length.resize(q);
40
    }
41
    void insert(string& s, int id) {
42
        int u = 0;
43
        length[id] = s.size();
44
        for (char x : s) {
45
            int c = x - 'a';
46
            if (tree[u].child[c] == -1) {
47
                tree[u].child[c] = tree.size();
48
                tree.emplace_back();
49
            }
50
            u = tree[u].child[c];
51
        }
52
        tree[u].index.push_back(id);
53
    }
54
    void build() {
55
        queue<int> q;
56
        for (int c = 0; c < 26; c++) {
57
            int v = tree[0].child[c];
58
            if (v == -1)
59
                tree[0].child[c] = 0;
60
            else {
61
                tree[v].fail = 0;
62
                tree[v].outputlink = 0;
63
                q.push(v);
64
            }
65
        }
66
        while (q.size()) {
67
            int u = q.front();
68
            q.pop();
69
            for (int c = 0; c < 26; c++) {
70
                int v = tree[u].child[c];
71
                if (v == -1) {
72
                    tree[u].child[c] = tree[tree[u].fail].child[c];
73
                    continue;
74
                }
75
                tree[v].fail = tree[tree[u].fail].child[c];
76
                int f = tree[v].fail;
77
                if (tree[f].index.size())
78
                    tree[v].outputlink = f;
79
                else
80
                    tree[v].outputlink = tree[f].outputlink;
81
                q.push(v);
82
            }
83
        }
84
    }
85
    void query(const string& s) {
86
        int u = 0;
87
        for (int r = 0; r < s.size(); r++) {
88
            int c = s[r] - 'a';
89
            u = tree[u].child[c];
90
            for (int id : tree[u].index) {
91
                int l = r - length[id] + 1;
92
                solve(id, l);
93
            }
94
            for (int v = tree[u].outputlink; v != 0; v = tree[v].outputlink) {
95
                for (int id : tree[v].index) {
96
                    int l = r - length[id] + 1;
97
                    solve(id, l);
98
                }
99
            }
100
        }
101
    }
102
};
103

104
signed main() {
105
    std::ios::sync_with_stdio(false);
106
    std::cin.tie(0);
107
    cin >> n >> q;
108
    cin >> S;
109
    a.resize(n), pre.resize(n + 1);
110
    minpre.resize(n + 1), maxsuff.resize(n + 1);
111
    prepre.resize(n + 1), presuff.resize(n + 1);
112
    for (int i = 0; i < n; i++)
113
        cin >> a[i];
114
    for (int i = 1; i <= n; i++)
115
        pre[i] = pre[i - 1] + a[i - 1];
116
    for (int i = 1; i <= n; i++)
117
        minpre[i] = min(minpre[i - 1], pre[i]);
118
    maxsuff[n] = pre[n];
119
    for (int i = n - 1; i >= 0; i--)
120
        maxsuff[i] = max(maxsuff[i + 1], pre[i]);
121
    for (int i = 1; i <= n; i++)
122
        prepre[i] = mmod(prepre[i - 1] + pre[i]);
123
    presuff[n] = mmod(pre[n]);
124
    for (int i = n - 1; i >= 0; i--)
125
        presuff[i] = mmod(presuff[i + 1] + pre[i]);
126
    AC ac(q);
127
    unordered_map<string, int> mp;
128
    vector<int> rmp(q);
129
    int uniquecount = 0;
130
    for (int i = 0; i < q; i++) {
131
        string p;
132
        cin >> p;
133
        auto it = mp.find(p);
134
        if (it == mp.end()) {
135
            mp[p] = uniquecount;
136
            rmp[i] = uniquecount;
137
            ac.insert(p, uniquecount);
138
            uniquecount++;
139
        } else
140
            rmp[i] = it->second;
141
    }
142
    length = ac.length;
143
    lastpos.resize(uniquecount, -1);
144
    finalans.resize(uniquecount, LLONG_MIN);
145
    finalsum.resize(uniquecount, 0);
146
    ac.build();
147
    ac.query(S);
148
    for (int i = 0; i < q; i++) {
149
        int id = rmp[i];
150
        cout << finalans[id] << ' ' << finalsum[id] << endl;
151
    }
152
    return 0;
153
}

2026牛客暑期多校训练营1

https://leaf146.cn/posts/2026牛客暑期多校训练营1

作者

LeAf146

发布于

2026-08-03

许可协议

MIT

部分信息可能已经过时

Agent 核心概念

AC 自动机

LeAf146's blog