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

A. 幸运数字

• 暴力bruteforcing
• 排序sorting

#include <iostream>
#include <algorithm>

using namespace std;

bool check(string s) {
    sort(s.begin(), s.end());
    for (int i = 0; i < s.length(); ++i) {
        if (s[i] != i + 48) return false;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int l, r, res = 0;
    cin >> l >> r;
    for (int i = l; i <= r; ++i) {
        if (check(to_string(i))) res++;
    }
    cout << res << '\n';
    return 0;
}

B. 坐标转换

• 数学math
• 几何geometry

前置知识: 逆时针旋转 $\theta$ 相当于左乘 $\left[\begin{array}{cc}\cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array}\right]$

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
    int x = (k + m - 1) / m, y = k - (x - 1) * m;
    x = x - n; y --;
    int tx = x + y, ty = -x + y;
    cout << n + tx << ' ' << ty + 1 << '\n';
    return 0;
}

C. 美味水果

• 贪心greedy
• 暴力bruteforcing

贪心吃大的，另外考虑到 x 会快速变成 1，所以可以暴力解决。

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 100010;

int 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];
    }
    sort(a + 1, a + n + 1, greater<int>());
    long long res = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j < i; ++j) {
            a[i] = floor(sqrt(a[i])) + 0.5;
        }
        if (a[i] == 1) {
            res += (n - i + 1);
            break;
        }
        else res += a[i];
    }
    cout << res << '\n';
    return 0;
}

E. 程序套娃

• 字符串string

主要就是注意套娃的时候 \ 数量得加对

h = "#include <iostream>\nint main() {printf(\""
t = "\\n\");}"

def work(s: str) -> str:
    s = s.replace("\\", "\\\\")
    s = s.replace("\n", "\\n")
    s = s.replace("\"", "\\\"")
    return s

def solve(n: int, k: int) -> str:
    if n == 1:
        return str(k)
    else:
        return h + work(solve(n - 1, k)) + t


n, k = map(int, input().split())
print(solve(n, k))

F. Restricted Permutation

• 拓扑排序topological_sorting
• 优先队列priority_queue

优先队列做 topsort 即可。

#include <iostream>
#include <queue>

using namespace std;

const int N = 200010;

vector<int> adj[N];
int deg[N];
int a[N], l;

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;
        adj[x].emplace_back(y);
        deg[y]++;
    }
    priority_queue<int, vector<int>, greater<int>> q;
    for (int i = 1; i <= n; ++i) if (!deg[i]) q.emplace(i);
    while (!q.empty()) {
        int x = q.top();
        q.pop();
        a[++l] = x;
        for (auto y : adj[x]) {
            if (--deg[y] == 0) {
                q.emplace(y);
            }
        }
    }
    if (l == n) {
        for (int i = 1; i <= l; ++i) cout << a[i] << ' ';
        cout << '\n';
    }
    else cout << -1 << '\n';
    return 0;
}

J. Crazy Binary String

• 前缀和prefix_sum
• 双指针two_pointer

对于子序列直接统计 0 和 1 的个数即可，对于子串统计前缀 1 和 0 个数的不同差值出现的第一次和最后一次位置，通过这个统计值维护。

#include <iostream>

using namespace std;

const int N = 100010;
int l[N * 2], r[N * 2];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    fill(l, l + N * 2, -1);
    fill(r, r + N * 2, -1);
    int n;
    cin >> n;
    int c0 = 0, c1 = 0;
    l[N] = 0;
    for (int i = 1; i <= n; ++i) {
        char c;
        cin >> c;
        if (c == '0') c0++;
        else c1++;
        int pos = c0 - c1 + N;
        if (l[pos] == -1) l[pos] = i;
        r[pos] = i;
    }
    int res = 0;
    for (int i = 0; i < N * 2; ++i) {
        res = max(res, r[i] - l[i]);
    }
    cout << res << ' ' << min(c0, c1) * 2 << '\n';
    return 0;
}

其他没做的题

• 成语接龙
• From D to E and back
• Shortcut
• Graph Games
• Guessing ETT
• Big Integer
• Trees in the Pocket II