当前位置：首页>考研真题>2026 CSP-J组复赛真题 & 真题解析

2026 CSP-J组复赛真题 & 真题解析

2026-11-02 01:17:21

新赛道OI｜2026年CSP-J真题赛后在线自测（民间数据）

比赛链接：https://xsdoi.com/contest/2634

比赛密码：xsdoi

PDF 版复赛真题见文末。

CSP-J 2026 真题部分分解析

T1 · 旅游

逐层补条件：同车厢 → 同排 → 同侧 → 相邻

每排座位为 ABC ∣ DF，竖线是过道。相邻对只有 AB,BA,BC,CB,DF,FD。四个输出必须全部正确，不能按小问分别计分。

20 分

默认同车厢、同排、同侧，只判断邻接；覆盖第 1 ∼ 4 点。

50 分

默认同车厢、同排，再判断同侧和邻接；覆盖第 1 ∼ 10 点。

70 分

默认同车厢，再判断排号、同侧和邻接；覆盖第 1 ∼ 14 点。

100 分

完整判断四个条件；覆盖第 1 ∼ 20 点。

travel_100.cpp · C++14

#include<bits/stdc++.h>

usingnamespacestd;

typedeflonglongll;

stringc1, s1, c2, s2, s;

charx, y;

boolf1, f2, f3, f4;

intmain() {

freopen("travel.in", "r", stdin);

freopen("travel.out", "w", stdout);

ios::sync_with_stdio(false);

cin.tie(0);

cin >> c1 >> s1 >> c2 >> s2;

x = s1[2], y = s2[2];

f1 = (c1 == c2);

f2 = f1 && s1.substr(0, 2) == s2.substr(0, 2);

f3 = f2 && ((x <= 'C') == (y <= 'C'));

s += x, s += y;

f4 = f3 && (s == "AB"|| s == "BA"||

s == "BC"|| s == "CB"||

s == "DF"|| s == "FD");

cout << f1 << f2 << f3 << f4 << endl;

return0;

}

性质 D：还能单独争取 15 分

两人的座位分别为 D、F 时，同排就一定同侧且相邻。判断车厢与排号后，令 f₃ = f₄ = f₂，覆盖第 15 ∼ 17 点。与 20、50、70 分版本合并，分别覆盖 35、65、85 分。

上方代码将前三个判断设为 true 即为 20 分；只改前两个为 50 分；只改第一个为 70 分。排号要比较完整两位。时间、额外空间均为 O(1)。

T2 · 回文串 · 部分分

用区间长度代替逐个字符比较

每对镜像字符不同就改一次。设 L = ∑a_i，只比较前 ⌊L/2⌋ 个位置。各档覆盖有重叠，合并时同一测试点只算一次。

16 分

n = 1 为 0；n = 2 同字符为 0，否则 min(a₁,a₂)；覆盖第 1 ∼ 4 点。

56 分

L ≤ 200000，展开后比较镜像字符；覆盖第 1 ∼ 12,17,18 点。

64 分

n ≤ 2000，枚举段对并计算区间交集；覆盖第 1 ∼ 16 点。

72 分

短串展开 + 长串区间枚举；覆盖第 1 ∼ 18 点。

84 分

将展开阈值提高到 10⁸；覆盖第 1 ∼ 21 点。

令 p₀ = 0, p_i = ∑ⁱ_k = 1a_k。第 i 段与翻转后的第 j 段分别为

[p_i − 1 + 1,p_i], [L − p_j + 1,L − p_j − 1].

字符不同时，累加两区间与 [1,⌊L/2⌋] 的交集长度，避免重复计数。

string_72.cpp · C++14

#include<bits/stdc++.h>

usingnamespacestd;

typedeflonglongll;

lln, a[200005], p[200005], ans = 0, len = 0;

charc[200005];

chars[200005];

intmain() {

freopen("string.in", "r", stdin);

freopen("string.out", "w", stdout);

ios::sync_with_stdio(false);

cin.tie(0);

cin >> n;

for(inti = 1; i <= n; i++) {

cin >> a[i] >> c[i];

p[i] = p[i - 1] + a[i];

}

llL = p[n];

if(L <= 200000LL) {

for(inti = 1; i <= n; i++) {

for (int j = 1; j <= a[i]; j++) s[++len] =c[i];

}

for(inti = 1; i <= L / 2; i++) {

if (s[i] != s[L - i + 1]) ans++;

}

} elseif(n <= 2000) {

for(inti = 1; i <= n; i++) {

for (int j = 1; j <= n; j++) {

if(c[i] == c[j]) continue;

lll = max(p[i - 1] + 1, L - p[j] + 1);

llr = min(p[i], L - p[j - 1]);

r = min(r, L / 2);

if(l <= r) ans += r - l + 1;

}

cout << ans << endl;

return0;

}

展开为 O(n + L)，区间枚举为 O(n²)。84 分版本将阈值改为 100000000，并将字符数组扩大到 100000005；单独采用这一展开法覆盖 68 分。长度和答案均用 ll。

T2 · 回文串 · 双指针

100 分 / 时间 O(n) / 空间 O(n)

两端各取一段，每次处理 t = min(a_l,a_r) 对字符。字符不同则答案加 t，两端长度同时减去 t，用完的段向中间移动。

string_100.cpp · C++14

#include<bits/stdc++.h>

usingnamespacestd;

typedeflonglongll;

lln, a[200005], p[200005], ans = 0, len = 0;

charc[200005];

intmain() {

freopen("string.in", "r", stdin);

freopen("string.out", "w", stdout);

ios::sync_with_stdio(false);

cin.tie(0);

cin >> n;

for(inti = 1; i <= n; i++) {

cin >> a[i] >> c[i];

p[i] = p[i - 1] + a[i];

}

intl = 1, r = n;

while(l < r) {

llt = min(a[l], a[r]);

if(c[l] != c[r]) ans += t;

a[l] -= t, a[r] -= t;

if(a[l] == 0) l++;

if(a[r] == 0) r--;

}

cout << ans << endl;

return0;

}

例：aabbc

剩余字符串：aabbc

a 与 c 比较 1 对；本轮贡献 1。

剩余字符串：abb

a 与 b 比较 1 对；本轮贡献 1。

剩余字符串：b

只剩中间一段，结束；本轮贡献 0。

记住三点

每轮至少消耗一段，所以总共 O(n) 轮。l = r 时剩余字符全部相同，不必再比较。两个独立的 if 可以同一轮跳过两端空段。

总长最多 2 × 10¹⁴，答案最多 10¹⁴，使用 long long。先保存 t，再同时扣除两端长度。

T3 · 按位与 · 分档突破

逐项组合：25 → 50 → 60 → 75 → 95 分

累计 25 分｜n ≤ 20

搜索选或不选，选够 m 个；新增第 1 ∼ 5 点。

累计 30 分｜m = 1

取最大值；新增第 6 点。

累计 35 分｜m = n

全部按位与；新增第 7 点。

累计 50 分｜m = 2, n ≤ 2000

枚举两个不同下标；新增第 8 ∼ 10 点。

累计 60 分｜m = n − 1

前后缀与，枚举删掉谁；新增第 11,12 点。

累计 65 分｜A：a_i = 2^k_i − 1

取第 m 大的数；新增第 13 点。

累计 75 分｜B：依次给出 0 ∼ 2^k − 1

n − 2^{⌈log₂m⌉}；新增第 14,15 点。

累计 85 分｜a_i < 4

统计频次，枚举候选掩码；新增第 16,17 点。

累计 95 分｜a_i < 1024

同上，最多 1024² 次检查；新增第 18,19 点。

搜索与前后缀：初始与值不能是 0

令 FULL = 2³⁰ − 1，因为 x&FULL = x。搜索从 dfs(1, 0, FULL) 开始；剩余数量不足时剪枝。

搜索 · C++14

voiddfs(inti, intnum, llv) {

if(num == m) {

ans = max(ans, v);

return;

}

if(n - i + 1< m - num) return;

dfs(i + 1, num + 1, v & a[i]);

dfs(i + 1, num, v);

}

m = n − 1 时，预处理前后缀与，再枚举删除下标 i：

前后缀与 · C++14

pre[0] = suf[n + 1] = FULL;

for(inti = 1; i <= n; i++) pre[i] = pre[i - 1] & a[i];

for(inti = n; i >= 1; i--) suf[i] = suf[i + 1] & a[i];

for(inti = 1; i <= n; i++) {

ans = max(ans, pre[i - 1] & suf[i + 1]);

}

性质 A、B 与小值域

A：各数均为低位连续的 1，其按位与等于最小值，故选最大的 m 个。 B：至少放开 q = ⌈log₂m⌉ 位才能保留 m 个候选；让低 q 位自由、高位为 1，答案为 n − 2^q。 小值域：掩码 v 可行，当且仅当至少 m 个位置满足 (a_i&v) = v。统计频次后从大到小枚举，第一个可行掩码即答案。

搜索 O(2ⁿ)；枚举数对 O(n²)；前后缀 O(n)；性质 A 排序 O(nlogn)；小值域 O(n + U²)。

T3 · 按位与 · 高位贪心

100 分 / 时间 O(30n) / 空间 O(n)

从第 29 位到第 0 位尝试填 1。每次连同此前确定的高位一起检查：若至少有 m 个数包含候选掩码的全部 1，就保留这一位，否则跳过。

and_100.cpp · C++14

#include<bits/stdc++.h>

usingnamespacestd;

typedeflonglongll;

lln, m, a[200005], ans = 0;

intmain() {

freopen("and.in", "r", stdin);

freopen("and.out", "w", stdout);

ios::sync_with_stdio(false);

cin.tie(0);

cin >> n >> m;

for(inti = 1; i <= n; i++) cin >> a[i];

for(intbit = 29; bit >= 0; bit--) {

llt = ans | (1LL<< bit), cnt = 0;

for(inti = 1; i <= n; i++) {

if ((a[i] & t) == t) cnt++;

}

if(cnt >= m) ans = t;

}

cout << ans << endl;

return0;

}

为什么可以从高位开始？

高位的一个 1，比所有更低位的 1 加起来还大。只要当前候选可行，保留它就不会错过更优解。判定用 cnt ≥ m，因为候选足够时可以任取 m 个。

不能直接选最大的 m 个

8,7,7 选两个：8&7 = 0，而 7&7 = 7。

不能逐位独立拼接

6,5,3 选两个，每位都各有两个数为 1，但没有同一对数能得到 7；正确答案是 4。

所有输入小于 2³⁰，最高有效位为 29。移位写作 1LL << bit。

T4 · 纸牌游戏 · 模拟与压缩

48 → 52 → 60 → 72 分

栈保存桌面，pos[x] 记录位置。重复时弹出旧 x 及其右侧所有牌，再压入新 x。

累计 48 分

n ≤ 5000，逐局栈模拟，O(n²)；新增第 1 ∼ 12 点。

累计 52 分

不下降序列：ans[x] = last[x]；新增第 20 点。

累计 60 分

m ≤ 2：末尾点数留 n 局，另一点数留其频次局；新增第 13,14 点。

累计 72 分

压缩连续相同段，按起始段长度加权；新增第 15 ∼ 17 点。

读入时保存最后位置与频次，并检查序列是否不下降。核心处理如下：

card_72.cpp · 核心代码 · C++14

for(inti = 1; i <= n; i++) {

if(r == 0|| col[r] != a[i]) {

r++;

col[r] = a[i], w[r] = 1;

} elsew[r]++;

}

if(flag) {

for(inti = 1; i <= m; i++) ans[i] = last[i];

} elseif(m <= 2) {

ans[a[n]] = n;

for(inti = 1; i <= m; i++) {

if(i != a[n]) ans[i] = cnt[i];

}

} elseif(r <= 5000) {

for(inti = 1; i <= r; i++) {

fill(pos + 1, pos + m + 1, 0);

top = 0;

for(intj = i; j <= r; j++) {

llx = col[j], p = pos[x];

if(p != 0) {

while(top >= p) pos[st[top--]] = 0;

}

st[++top] = x;

pos[x] = top;

}

for(intj = 1; j <= top; j++) ans[st[j]] += w[i];

}

性质 B 保证连续段数 r ≤ 5000；同一段内的起点最终桌面相同，故每次加 w[i]。压缩后时间 O(n + r²)，空间 O(n + m)。弹出牌时同步清空 pos。

T4 · 纸牌游戏 · 按点数分组

76 分按链累加；80 分保留有序分支

第一张牌为 x 时，桌面最左端始终是 x；打到最后一个 x 时，桌面只剩 [x]。因此第一张牌点数相同，最终桌面相同，后续等价于从 last[x] + 1 开始。

next[x] = a_{last[x] + 1}（last[x] < n）next[x] = 0（last[x] = n）

从每个点数沿链前进，给经过的点数加上起点的出现次数。链上最后出现位置严格增大，不会成环。

card_80.cpp · C++14

#include<bits/stdc++.h>

usingnamespacestd;

typedeflonglongll;

lln, m, a[500005], last[300005], cnt[300005];

llans[300005], nxt[300005];

intmain() {

freopen("card.in", "r", stdin);

freopen("card.out", "w", stdout);

ios::sync_with_stdio(false);

cin.tie(0);

cin >> n >> m;

boolflag = true;

for(inti = 1; i <= n; i++) {

cin >> a[i];

last[a[i]] = i;

cnt[a[i]]++;

if(i > 1&& a[i] < a[i - 1]) flag = false;

}

if(flag) {

for(inti = 1; i <= m; i++) ans[i] = last[i];

} elseif(m <= 3000) {

for(inti = 1; i <= m; i++) {

if (last[i] < n) nxt[i] = a[last[i] + 1];

}

for(inti = 1; i <= m; i++) {

for (ll x = i; x != 0; x = nxt[x]) ans[x] += cnt[i];

}

for(inti = 1; i <= m; i++) cout << ans[i] << " ";

cout << endl;

return0;

}

序列 [1,1,2,1,1,3]

第一张为 1

最终点数链：1 → 3；代表 4 局。

第一张为 2

最终点数链：2 → 1 → 3；代表 1 局。

第一张为 3

最终点数链：3；代表 1 局。

答案为 5,1,6。前 19 点保证 m ≤ 3000，按链枚举覆盖 76 分；有序分支再覆盖第 20 点，得 80 分。时间 O(n + m²)，空间 O(n + m)。

T4 · 纸牌游戏 · 合并次数

100 分 / 时间与空间均为 O(n + m)

先令 ans[x] 等于 x 的出现次数。按最后出现位置从小到大处理，将 ans[x] 加给 ans[next[x]]。所有前驱都更早处理，所以传递的是到达 x 的完整次数。

card_100.cpp · C++14

#include<bits/stdc++.h>

usingnamespacestd;

typedeflonglongll;

lln, m, a[500005], last[300005], ans[300005];

intmain() {

freopen("card.in", "r", stdin);

freopen("card.out", "w", stdout);

ios::sync_with_stdio(false);

cin.tie(0);

cin >> n >> m;

for(inti = 1; i <= n; i++) {

cin >> a[i];

last[a[i]] = i;

ans[a[i]]++;

}

for(inti = 1; i < n; i++) {

llx = a[i];

if(last[x] == i) ans[a[i + 1]] += ans[x];

}

for(inti = 1; i <= m; i++) cout << ans[i] << " ";

cout << endl;

return0;

}

不用排序，直接扫原序列

只在 i = last[a_i] 时传递一次；若 i < n，后继就是 a_i + 1。每种点数只处理一次，总时间 O(n + m)。

序列 [1,1,2,1,1,3]

初始频次

ans[1] = 4，ans[2] = 1，ans[3] = 1。

i = 3：2 → 1

ans[1] = 5，ans[2] = 1，ans[3] = 1。

i = 5：1 → 3

ans[1] = 5，ans[2] = 1，ans[3] = 6。

顺序与次数都不能错

按最后出现位置处理，不能按点数大小。例如 [2,1,3] 的传递顺序是 2 → 1 → 3。

保留 last[x] == i，避免同一种点数重复传递。

每种点数在某局最终桌面至多出现一次，单个答案不超过 n。

本文来自网友投稿或网络内容，如有侵犯您的权益请联系我们删除，联系邮箱：wyl860211@qq.com 。

2026 CSP-J组复赛真题 & 真题解析

CSP-J 2026 真题部分分解析

T1 · 旅游

性质 D：还能单独争取 15 分

T2 · 回文串 · 部分分

T2 · 回文串 · 双指针

例：aabbc

记住三点

T3 · 按位与 · 分档突破

搜索与前后缀：初始与值不能是 0

性质 A、B 与小值域

T3 · 按位与 · 高位贪心

为什么可以从高位开始？

T4 · 纸牌游戏 · 模拟与压缩

T4 · 纸牌游戏 · 按点数分组

T4 · 纸牌游戏 · 合并次数

不用排序，直接扫原序列

中山市九年级上物理期中试卷

26秋人教版七上英语期中押题卷|含答案解析