2026夏个人训练赛第三十五场

非常的基础，变成手速局了。

A. 求和V

算术
模拟

python

s = []
for i in range(1, 100):
    s += [i] * i
l, r = map(int, input().split())
print(sum(s[l - 1:r]))

B. 猜歌名

数据结构
哈希集合与映射

cpp

#include <bits/stdc++.h>

using namespace std;

set<string> s;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        string t;
        cin >> t;
        s.emplace(t);
    }
    int cnt = 0, tot = s.size();
    int m;
    cin >> m;
    for (int i = 1; i <= m; ++i) {
        string t;
        cin >> t;
        if (s.count(t)) cnt++, s.erase(t);
        if (cnt * 2 >= tot) {
            cout << i << '\n';
            return 0;
        }
    }
    return 0;
}

C. 黑白棋

暴力
模拟

cpp

#include <bits/stdc++.h>

using namespace std;

char a[8][8];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    for (int i = 0; i < 8; ++i)
        for (int j = 0; j < 8; ++j)
            cin >> a[i][j];
    int mx = 0;
    for (int i = 0; i < 8; ++i) {
        for (int j = 0; j < 8; ++j) {
            if (a[i][j] == '.') {
                int tot = 0, cur = 0;
                for (int k = j + 1, t = 0; k < 8; ++k) {
                    if (a[i][k] == 'W') t++;
                    else if (a[i][k] == 'B') { cur = max(cur, t); break;}
                    else break;
                }
                tot += cur;
                cur = 0;
                for (int k = j - 1, t = 0; k >= 0; --k) {
                    if (a[i][k] == 'W') t++;
                    else if (a[i][k] == 'B') { cur = max(cur, t); break;}
                    else break;
                }
                tot += cur;
                cur = 0;
                for (int k = i + 1, t = 0; k < 8; ++k) {
                    if (a[k][j] == 'W') t++;
                    else if (a[k][j] == 'B') { cur = max(cur, t); break;}
                    else break;
                }
                tot += cur;
                cur = 0;
                for (int k = i - 1, t = 0; k >= 0; --k) {
                    if (a[k][j] == 'W') t++;
                    else if (a[k][j] == 'B') { cur = max(cur, t); break;}
                    else break;
                }
                tot += cur;
                cur = 0;
                for (int k = 1, t = 0; i + k < 8 && j + k < 8; ++k) {
                    if (a[i + k][j + k] == 'W') t++;
                    else if (a[i + k][j + k] == 'B') { cur = max(cur, t); break;}
                    else break;
                }
                tot += cur;
                cur = 0;
                for (int k = 1, t = 0; i + k < 8 && j - k >= 0; ++k) {
                    if (a[i + k][j - k] == 'W') t++;
                    else if (a[i + k][j - k] == 'B') { cur = max(cur, t); break;}
                    else break;
                }
                tot += cur;
                cur = 0;
                for (int k = 1, t = 0; i - k >= 0 && j + k < 8; ++k) {
                    if (a[i - k][j + k] == 'W') t++;
                    else if (a[i - k][j + k] == 'B') { cur = max(cur, t); break;}
                    else break;
                }
                tot += cur;
                cur = 0;
                for (int k = 1, t = 0; i - k >= 0 && j - k >= 0; ++k) {
                    if (a[i - k][j - k] == 'W') t++;
                    else if (a[i - k][j - k] == 'B') { cur = max(cur, t); break;}
                    else break;
                }
                tot += cur;
                cur = 0;
                // cout << i << ' ' << j << ' ' << tot << '\n';
                mx = max(mx, tot);
            }
        }
    }
    cout << mx << '\n';
    return 0;
}

D. 跳格子

动态规划

按照步长，先尝试顺着走一轮，然后尝试倒着走一轮，维护 $f_{i, j}$ 表示在 i 位置最后一步为 j 的最小代价。

cpp

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;
int a[N], f[N][N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    memset(f, 0x3f, sizeof(f));
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    f[1][0] = 0;
    int res = 0x3f3f3f3f;
    for (int j = 1; j <= n; ++j) {
        for (int i = j; i <= n; ++i) {
            f[i][j] = min(f[i][j], f[i - j][j - 1] + a[i]);
        }
        res = min(res, f[n][j]);
        for (int i = n - j + 1; i; --i) {
            f[i][j] = min(f[i][j], f[i + j][j] + a[i]);
        }
    }
    cout << res << '\n';
    return 0;
}

E. 锻炼计划

前缀和
模拟

cpp

#include <bits/stdc++.h>
 
using namespace std;
 
int a[1450];
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        string _;
        int l, r, v;
        cin >> _ >> l >> r >> v;
        a[l] += v, a[r + 1] -= v;
    }
    for (int i = 1; i <= 1440; ++i) {
        a[i] += a[i - 1];
        n++;
        if (n <= a[i]) {
            cout << "Runtime Error\n" << i << '\n';
            return 0;
        }
        n -= a[i];
    }
    cout << "Accepted\n" << n << '\n';
    return 0;
}

F. 盟军敢死队

状态压缩 DP
动态规划

状压 DP，先给每个人编号， $n^{3}$ 枚举出来每个人的直接前驱压到一个 bitmask 里，然后枚举 bitmask，再枚举最后一个杀的人计数。从小到达枚举 bitmask 天然的符合拓扑序。

cpp

#include <bits/stdc++.h>

using namespace std;

char a[60][60];
int mark[60][60];
int msk[15];
long long f[1 << 15];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int k = 0;
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> a[i][j];
            if (a[i][j] != '#' && a[i][j] != '.') mark[i][j] = ++k;
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (mark[i][j]) {
                for (int k = j + 1; k < m; ++k) {
                    if (a[i][k] == '#') break;
                    else if (a[i][k] == '<') msk[mark[i][j] - 1] |= 1 << mark[i][k] - 1;
                }
                for (int k = j - 1; k >= 0; --k) {
                    if (a[i][k] == '#') break;
                    else if (a[i][k] == '>') msk[mark[i][j] - 1] |= 1 << mark[i][k] - 1;
                }
                for (int k = i + 1; k < n; ++k) {
                    if (a[k][j] == '#') break;
                    else if (a[k][j] == '^') msk[mark[i][j] - 1] |= 1 << mark[k][j] - 1;
                }
                for (int k = i - 1; k >= 0; --k) {
                    if (a[k][j] == '#') break;
                    else if (a[k][j] == 'v') msk[mark[i][j] - 1] |= 1 << mark[k][j] - 1;
                }
            }
        }
    }
    f[0] = 1;
    for (int i = 1; i < (1 << k); ++i) {
        for (int j = 0; j < k; ++j) {
            if (i >> j & 1) {
                if (((i ^ (1 << j)) & msk[j]) == msk[j]) {
                    f[i] += f[i ^ 1 << j];
                }
            }
        }
    }
    if (f[(1 << k) - 1]) cout << f[(1 << k) - 1] << '\n';
    else cout << "Impossible\n";
    return 0;
}

G. 暗黑破坏神

背包
动态规划

就是个分组背包，额外记录一下最后一步的决策就行了。

cpp

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 110, M = 510;
LL f[N][M], w[M];
int pre[N][M], v[N][M], res[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    memset(f, -0x3f, sizeof(f));
    f[0][0] = 0;
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        LL c, p;
        cin >> c >> p;
        for (int j = 1; j <= p; ++j) {
            cin >> w[j];
        }
        for (int k = 0; k <= m; ++k) {
            f[i][k] = f[i - 1][k];
            pre[i][k] = k;
            v[i][k] = 0;
            for (int j = 1; j <= p; ++j) {
                if (k >= j * c && f[i - 1][k - j * c] + w[j] > f[i][k]) {
                    f[i][k] = f[i - 1][k - j * c] + w[j];
                    v[i][k] = j;
                    pre[i][k] = k - j * c;
                }
            }
        }
    }
    int pos = 1;
    for (int i = 1; i <= m; ++i) {
        if (f[n][i] > f[n][pos]) pos = i;
    }
    cout << f[n][pos] << '\n';
    for (int i = n, j = pos; i; j = pre[i][j], i--) {
        res[i] = v[i][j];
    }
    for (int i = 1; i <= n; ++i) cout << res[i] << '\n';
    return 0;
}

H. 排列计数

组合数学
动态规划

选出来 m 个不排序，然后剩下 n - m 个错排。

cpp

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 1000010, MOD = 1000000007;
LL p[N], inv[N], d[N];

LL power(LL n, LL p) {
    LL res = 1, base = n;
    while (p) {
        if (p & 1) res = res * base % MOD;
        base = base * base % MOD;
        p >>= 1;
    }
    return res;
}

void init() {
    int n = 1000000;
    inv[0] = p[0] = 1;
    for (int i = 1; i <= n; ++i) p[i] = p[i - 1] * i % MOD;
    inv[n] = power(p[n], MOD - 2);
    for (int i = n - 1; i; --i) inv[i] = inv[i + 1] * (i + 1) % MOD;
    d[0] = 1, d[1] = 0, d[2] = 1;
    for (int i = 3; i <= n; ++i) d[i] = (d[i - 1] + d[i - 2]) * (i - 1) % MOD;
}

LL comb(LL n, LL m) {
    return p[n] * inv[m] % MOD * inv[n - m] % MOD;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    init();
    int T;
    cin >> T;
    while (T--) {
        LL n, m;
        cin >> n >> m;
        cout << comb(n, m) * d[n - m] % MOD << '\n';
    }
    return 0;
}

2026夏个人训练赛第三十五场 ​

A. 求和V ​

B. 猜歌名 ​

C. 黑白棋 ​

D. 跳格子 ​

E. 锻炼计划 ​

F. 盟军敢死队 ​

G. 暗黑破坏神 ​

H. 排列计数 ​