2026夏个人训练赛第十六场

A. 最短路

Dijkstra
最短路

没想到直接 dijkstra 就能跑过，但是别人 T 飞了。

cpp

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

typedef long long LL;
const int N = 5000010, M = 20000010;
int head[N], ver[M], ne[M], w[M], tot;
bool vis[N];
LL dis[N];
priority_queue<pair<LL, int>, vector<pair<LL, int>>, greater<pair<LL, int>>> q;

void add(int x, int y, int z) {
    ver[++tot] = y;
    ne[tot] = head[x];
    head[x] = tot;
    w[tot] = z;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, m, t;
    cin >> n >> m >> t;
    for (int i = 1; i <= m; ++i) {
        int x, y, z;
        cin >> x >> y >> z;
        add(x, y, z), add(y, x, z);
    }
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0;
    q.emplace(dis[1], 1);
    while (!q.empty()) {
        auto [_, x] = q.top();
        q.pop();
        if (vis[x]) continue;
        vis[x] = true;
        if (x == t) {
            cout << dis[x] << endl;
            return 0;
        }
        for (int i = head[x]; i; i = ne[i]) {
            int y = ver[i];
            if (dis[y] > dis[x] + w[i]) {
                dis[y] = dis[x] + w[i];
                q.emplace(dis[y], y);
            }
        }
    }
    return 123;
}

B. 种树

图论
深度优先搜索
图搜索

分两类情况

如果本身是一棵树，那么所有叶子都是能删的
如果不是，用 tarjan 找到所有的桥，然后枚举每个点，如果没有桥连到它，而且删掉之后边数正好是 n - 2，那么它就是能删的

cpp

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

typedef long long LL;
const int N = 100010;
int head[N], ver[N * 2], ne[N * 2], tot = 1;
int dfn[N], low[N], t;
int deg[N];
bool bridge[N * 2];
int res[N], len;

void add(int x, int y) {
    ver[++tot] = y;
    ne[tot] = head[x];
    head[x] = tot;
    deg[y]++;
}

void tarjan(int x, int from) {
    dfn[x] = low[x] = ++t;
    for (int i = head[x]; i; i = ne[i]) {
        if ((i ^ 1) == from) continue;
        int y = ver[i];
        if (!dfn[y]) {
            tarjan(y, i);
            low[x] = min(low[x], low[y]);
            if (dfn[x] < low[y]) bridge[i] = bridge[i ^ 1] = true;
        }
        else low[x] = min(low[x], dfn[y]);
    }
}

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) {
        int x, y;
        cin >> x >> y;
        add(x, y), add(y, x);
    }
    if (n == m + 1) {
        for (int i = 1; i <= n; ++i) {
            if (deg[i] == 1) res[++len] = i;
        }
    }
    else {
        tarjan(1, 0);
        for (int i = 1; i <= n; ++i) {
            int cnt = 0;
            bool f = true;
            for (int j = head[i]; j; j = ne[j]) {
                cnt++;
                if (bridge[j]) {
                    f = false;
                    break;
                }
            }
            // cout << cnt << ' ' << f << endl;
            if (f && cnt + n - 2 == m) res[++len] = i;
        }
    }
    cout << len << endl;
    for (int i = 1; i <= len; ++i) cout << res[i] << ' ';
    cout << endl;
    return 0;
}

C. 约束排列

暴力
分类讨论

直接暴力

cpp

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 20;
char a[N];
int c[N], pos[N];
pair<char, char> b[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, k;
    int t = 1;
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) cin >> a[i], c[i] = i, t *= i;
    for (int i = 1; i <= k; ++i) {
        auto &[x, y] = b[i];
        cin >> x >> y;
    }
    sort(a + 1, a + n + 1);
    for (int tt = 0; tt < t; ++tt) {
        for (int i = 1; i <= n; ++i) pos[a[c[i]]] = i;
        bool f = true;
        for (int i = 1; i <= k; ++i) {
            auto [x, y] = b[i];
            if (pos[x] > pos[y]) {
                f = false;
                break;
            }
        }
        if (f) {
            for (int i = 1; i <= n; ++i) cout << a[c[i]];
            cout << endl;
        }
        next_permutation(c + 1, c + n + 1);
    }
    return 0;
}

D. 盘子序列^（补）

栈
模拟

我不知道为什么一上午都一直想这个还没想到，直接从 1 开始入栈顺着模拟就行了……

cpp

#include <iostream>
#include <algorithm>
 
using namespace std;
 
const int N = 100010;
int a[N], b[N];
int st[N], tp;
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    while (cin >> n) {
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
            b[i] = a[i];
        }
        sort(b + 1, b + n + 1);
        tp = 0;
        bool f = true;
        for (int i = 1, cur = 1; i <= n; ++i) {
            if (i == a[cur]) {
                cur++;
                while (tp && st[tp] == a[cur]) {
                    tp--, cur++;
                }
            }
            else if (a[cur] > i) {
                st[++tp] = i;
                continue;
            }
            else if (st[tp] != a[cur]) {
                f = false;
                break;
            }
            else {
                while (tp && st[tp] == a[cur]) {
                    tp--, cur++;
                }
                st[++tp] = i;
            }
        }
        if (tp) f = false;
        cout << (f ? "Y" : "J") << endl;
    }
    return 0;
}

E. 四轮车

几何
哈希集合与映射
暴力

对于所有点的坐标用 map 统计一下，枚举两个点然后算出另外两个点，查 map 统计数量即可。

cpp

#include <iostream>
#include <unordered_map>

using namespace std;

typedef long long LL;
const int N = 1010;

unordered_map<LL, int> mp;
int x[N], y[N];

LL get(int x, int y) {
    if (abs(x) > 20000 || abs(y) > 20000) return -1;
    return (LL)(x + 20001) * 40001 + (LL)(y + 20001);
}

LL count(int x, int y) {
    LL v = get(x, y);
    if (mp.count(v)) return mp[v];
    else return 0;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> x[i] >> y[i];
        mp[get(x[i], y[i])]++;
    }
    LL res = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            if (x[i] == x[j] && y[i] == y[j]) continue;
            int dx = y[i] - y[j], dy = x[i] - x[j];
            LL c1 = count(x[i] + dx, y[i] + dy), c2 = count(x[j] + dx, y[j] + dy);
            res += c1 * c2;
            c1 = count(x[i] - dx, y[i] - dy), c2 = count(x[j] - dx, y[j] - dy);
            res += c1 * c2;
        }
    }
    cout << (res >> 2) << endl;
    return 0;
}

F. 评估

数学
前缀和

整理一下式子

\sum_{i = 1}^{n} \sum_{j = i + 1}^{n} (a_{i} - a_{j})^{2} = \sum_{i = 1}^{n} a_{i}^{2} (n - 1) - 2 \sum_{i = 1}^{n} a_{i} \sum_{j = i + 1}^{n} a_{j}

最后一个求和可以用前缀和来计算，复杂度 O(n)。

cpp

#include <iostream>

using namespace std;

typedef long long LL;
const int N = 100010;

LL a[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    LL res = 0, s = 0;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        res += a[i] * a[i] * (n - 1) - 2LL * a[i] * s;
        s += a[i];
    }
    cout << res << endl;
    return 0;
}

G. 拆分数字^（补）

数学
数论

最少的表示是 n 的三进制表示的各位求和，最多的表示是 n，一个高位 1 可以拆成 3 个低位的 1，所以如果 k 在这两个阈值之间而且奇偶性一致就满足。

cpp

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

template<typename T>
void read(T &n) {
    n = 0;
    char c = getchar();
    while (!isdigit(c)) c = getchar();
    while (isdigit(c)) n = n * 10 + c - 48, c = getchar();
}

int main() {
    int T;
    read(T);
    while (T--) {
        __int128_t n, k, s = 0, t;
        read(n), read(k);
        t = n;
        while (n) {
            s += n % 3;
            n /= 3;
        }
        if (t % 2 == k % 2 && s <= k && k <= t) puts("Yes");
        else puts("No");
    }
    return 0;
}

H. 露营

暴力
数学

数据太小了，直接暴力即可。

cpp

#include <iostream>

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int x[3], y[3];
    int res = 0x3f3f3f3f;
    for (int i = 0; i < 3; ++i) {
        cin >> x[i] >> y[i];
    }
    for (int i = 0; i <= 1000; ++i) {
        for (int j = 0; j <= 1000; ++j) {
            res = min(res, abs(i - x[0]) + abs(j - y[0]) + abs(i - x[1]) + abs(j - y[1]) + abs(i - x[2]) + abs(j - y[2]));
        }
    }
    cout << res + 1 << endl;
    return 0;
}

I. 寻宝

动态规划
贪心
字符串

需要分两步做，一定是先用完这 k 次，然后再贪心走。

用二维 DP 统计从左上角开始到每个点最多路过 a 的个数，根据这个找到开局最长的连续 a
然后从所有的最长连续 a 的终点同时开始沿着主对角线一层一层走，贪心的选最小的字符，直到走到终点

cpp

#include <iostream>
#include <algorithm>
 
using namespace std;
 
const int N = 1010;
char a[N][N];
int f[N][N], g[N][N];
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, k;
    cin >> n >> k;
    int t = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cin >> a[i][j];
            f[i][j] = max(f[i - 1][j], f[i][j - 1]) + (a[i][j] == 'a');
            if (i + j - 1 - f[i][j] <= k) g[i][j] = true, t = max(t, i + j);
        }
    }
    for (int i = 1; i <= n * 2 - 1; ++i) {
        if (i < t) cout << 'a';
        else if (i == 1) g[1][1] = true, cout << a[1][1];
        else {
            char mn = 'z';
            for (int x = 1; x <= n; ++x) {
                int y = i - x;
                if (x >= 1 && x <= n && y >= 1 && y <= n && g[x][y]) {
                    if (x + 1 <= n) mn = min(mn, a[x + 1][y]);
                    if (y + 1 <= n) mn = min(mn, a[x][y + 1]);
                }
            }
            cout << mn;
            for (int x = 1; x <= n; ++x) {
                int y = i - x;
                if (x >= 1 && x <= n && y >= 1 && y <= n && g[x][y]) {
                    if (x + 1 <= n && a[x + 1][y] == mn) g[x + 1][y] = true;
                    if (y + 1 <= n && a[x][y + 1] == mn) g[x][y + 1] = true;
                }
            }
        }
    }
    cout << endl;
    return 0;
}

没人开过的题

J. Mindiff and Maxdiff
K. Rock-Paper-Scissors Tournament
L. Class Division
M. Tree Subset Diameter
N. Sudoku Subrectangles

2026夏个人训练赛第十六场 ​

A. 最短路 ​

B. 种树 ​

C. 约束排列 ​

D. 盘子序列（补） ​

E. 四轮车 ​

F. 评估 ​

G. 拆分数字（补） ​

H. 露营 ​

I. 寻宝 ​

没人开过的题 ​