Star 的档案库

Appearance

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

A. 前缀串 ​

cpp
#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    string s;
    int n;
    cin >> s >> n;
    string res;
    for (int i = 1; i <= n; ++i) {
        string t;
        cin >> t;
        if (t.length() >= s.length() && t.substr(0, s.length()) == s) {
            if (res.empty()) res = t;
            else res = min(res, t);
        }
    }
    cout << res << '\n';
    return 0;
}

B. 放椅子 ​

cpp
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    long long res = 0;
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i] >> b[i];
    }
    sort(a.begin(), a.end()), sort(b.begin(), b.end());
    for (int i = 0; i < n; ++i) res += max(a[i], b[i]);
    cout << res + n << '\n';
    return 0;
}

C. 天天爱消除 ​

cpp
#include <bits/stdc++.h>

using namespace std;

const int N = 310;
int f[N][N], col[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, a, b, c;
    cin >> n >> a >> b >> c;
    for (int i = 1; i <= n; ++i) cin >> col[i];
    for (int i = 1; i <= n; ++i) f[i][i] = a;
    for (int len = 2; len <= n; ++len) {
        for (int l = 1; l <= n - len + 1; ++l) {
            int r = l + len - 1;
            for (int k = l; k < r; ++k) f[l][r] = max(f[l][r], f[l][k] + f[k + 1][r]);
            if (col[l] == col[r]) {
                f[l][r] = max(f[l][r], f[l + 1][r - 1] + b);
                for (int k = l + 1; k < r; ++k) {
                    if (col[k] == col[l])
                        f[l][r] = max(f[l][r], f[l + 1][k - 1] + f[k + 1][r - 1] + c);
                }
            }
        }
    }
    cout << f[1][n] << '\n';
    return 0;
}

D. 四元组计 ​

枚举中间两个，然后维护前缀计数和后缀的计数统计答案。

cpp
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 5010;
int pre[N][N], suf[N][N], a[N];

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 >> a[i];
        pre[i][a[i]] = suf[i][a[i]] = 1;
        for (int j = 1; j <= n; ++j) pre[i][j] += pre[i - 1][j];
    }
    for (int i = n; i; --i) {
        for (int j = 1; j <= n; ++j) {
            suf[i][j] += suf[i + 1][j];
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            pre[i][j] += pre[i][j - 1];
            suf[i][j] += suf[i][j - 1];
        }
    }
    LL res = 0;
    for (int i = 2; i < n - 1; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (a[i] > a[j]) {
                res += (LL)(pre[i - 1][a[j]] * (suf[j + 1][n] - suf[j + 1][a[i]]));
            }
        }
    }
    cout << res << '\n';
    return 0;
}

E. 年会小游戏 ​

最优解的质因数很少，而且是连续的一段最小的，dfs 加剪枝会跑的非常快。

cpp
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
int p[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        LL n, res = 0, cnt = 0;
        cin >> n;
        int c[16]{};
        auto dfs = [&](auto && self, int x, int pre, __int128_t cur, LL prod) {
            if (cur > res && prod < cnt) return;
            else if (cur * 2 > n || x == 16) {
                if (prod > cnt || prod == cnt && cur < res) res = cur, cnt = prod;
                return;
            }
            else {
                int t = 0;
                do {
                    self(self, x + 1, t, cur, prod * (t + 1));
                    t++;
                    cur *= p[x];
                } while (t <= pre && cur <= n);
            }
        };
        dfs(dfs, 0, 60, 1, 1);
        cout << res << ' ' << cnt << '\n';
    }
    return 0;
}

F. 公司搬迁 ​

几乎是 2-SAT 板子题了，每个人有 A 和 B 两个状态二选一

  • 只要能找到对应的人就是要么都在要么都不在，两个人的 A 之间、两个人的 B 之间分别连边
  • 其中一个找不到说明这个人只能选另一个，给另一个连单向边

然后跑 tarjan 看一下是否矛盾。

cpp
#include <bits/stdc++.h>

using namespace std;

const int N = 100010;
int head[N * 2], ne[N * 4], ver[N * 4], tot;
int dfn[N * 2], low[N * 2], st[N * 2], ins[N * 2], id[N * 2], tp, t, scc_cnt;
unordered_map<int, int> mp;
int p[N];

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

void tarjan(int x) {
    dfn[x] = low[x] = ++t;
    st[++tp] = x;
    ins[x] = 1;
    for (int i = head[x]; i; i = ne[i]) {
        int y = ver[i];
        if (!dfn[y]) {
            tarjan(y);
            low[x] = min(low[x], low[y]);
        }
        else if (ins[y]) low[x] = min(low[x], dfn[y]);
    }
    if (dfn[x] == low[x]) {
        int y;
        ++scc_cnt;
        do {
            y = st[tp--];
            id[y] = scc_cnt;
            ins[y] = 0;
        } while (y != x);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int n, a, b;
        cin >> n >> a >> b;
        tot = 0;
        fill(head, head + n * 2 + 1, 0);
        fill(dfn, dfn + n * 2 + 1, 0);
        mp.clear();
        for (int i = 1; i <= n; ++i) cin >> p[i], mp[p[i]] = i;
        auto get = [&](int idx, int ch) {
            return idx + ch * n;
        };
        for (int i = 1; i <= n; ++i) {
            if (mp.find(a - p[i]) == mp.end()) add(get(i, 0), get(i, 1));
            else add(get(i, 0), get(mp[a - p[i]], 0)), add(get(i, 1), get(mp[a - p[i]], 1));

            if (mp.find(b - p[i]) == mp.end()) add(get(i, 1), get(i, 0));
            else add(get(i, 1), get(mp[b - p[i]], 1)), add(get(i, 0), get(mp[b - p[i]], 0));
        }
        for (int i = 1; i <= n * 2; ++i) {
            if (!dfn[i]) tarjan(i);
        }
        bool f = true;
        for (int i = 1; i <= n; ++i) {
            if (id[i] == id[i + n]) {
                f = false;
                break;
            }
        }
        cout << (f ? "YES\n" : "NO\n");
    }

    return 0;
}

其他没做的题

  • 走亲戚
  • K-ary Heap
  • Is Today Friday?
  • Train Driver
  • Can They Go to Galar?
  • Upgrading Technology