2025CSPJ初赛

h_h__h_h · 2025-09-20 23:30:46 · 生活·游记

原题和主要内容来源，感谢！ 修改了部分答案，主要是阅读题和最后摩尔投票部分，如有异议辛苦指出。全卷只有摩尔投票上课没讲过。做了琪露诺的有福了，j超纲考了滑动窗口。

【算法讲解116【扩展】摩尔投票大加强，线段树里捉海王-哔哩哔哩】 https://b23.tv/IL8dH0F

【【漫士】这是你学明白组合数学最好的机会-哔哩哔哩】 https://b23.tv/T74ik41

选择

T16 两两互质的三元组+辗转相除法求GCD

import math

def gcd(a, b):
    return math.gcd(a, b)

n = 8
ans = 0

for i in range(1, n + 1):
    for j in range(i + 1, n + 1):
        for k in range(j + 1, n + 1):
            if gcd(i, j) == 1 and gcd(j, k) == 1 and gcd(i, k) == 1:
                ans += 1
                print(i,j,k)

print(ans)

⭐T17把已排序、去重后的数组切成最少连续子段，使得每一段内部最大值减最小值 ≤ k，最终输出最少段数。（一般看到本题直接二分答案来着，学一下滑动窗口+DP）

#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

int n, k;
int a[200007];
int ans[200007];

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);

    /* 去重：unique 返回去重后尾端指针，减 a 得新长度 */
    sort(a + 1, a + n + 1);
    n = unique(a + 1, a + n + 1) - a - 1;

    /* 滑动窗口核心逻辑 */
    for (int i = 1, j = 0; i <= n; ++i) {
        while (j < i && a[i] - a[j + 1] > k) ++j;   // 把过期的左端点右移
        ans[i] = ans[j] + 1;                        // 以 a[i] 结尾的最少段数
    }

    printf("%d\n", ans[n]);
    return 0;
}

T18 LCS纯模板，典中典

完善程序T19字符串解码T20摩尔投票

#include <cctype>
#include <iostream>
#include <string>
using namespace std;

int main() {
    string z;
    cin >> z;
    string s = "";
    for (int i = 0; i < z.length(); ) {        // ① 初始化 i = 0
        char ch = z[i];
        if (isalpha(ch) && i + 1 < z.length() && isdigit(z[i + 1])) {
            i++;                               // 跳过字母
            int count = 0;                     // ② 初始值 count = 0
            while (i < z.length() && isdigit(z[i])) {
                count = count * 10 + (z[i] - '0'); // ③ 数字拼接
                i++;
            }
            for (int j = 0; j < count; j++)    // ④ 重复 count 次
                s += ch;
        } else {
            s += ch;                           // 普通字母
            i++;
        }
    }
    cout << s << endl;
    return 0;                                  // ⑤ return 0
}