ARTICLE · 1287123

2026 CSP-J复赛真题深度解析 | 前两题稳拿分?后两题拉差距?附完整思路+满分代码

发布时间：2026-10-31 19:45:51 最近访问：2026-10-31 19:45:52

2026年CSP-J非专业级软件能力认证第二轮已于10月31日上午正式收官，全国信奥少年完成了210分钟的上机比拼。本次试题由CCF统一命题，延续了“基础题送分、中档题分层、难题拔高度”的经典命题逻辑，四道题目分别对应模拟、字符串、位运算、博弈贪心四大核心考点。

本文基于官方真题题干，为大家带来前两道题的完整思路拆解、部分分与满分代码实现，帮助考生对照估分、复盘考点，也为备赛同学提供真题训练参考。

一、本次复赛命题总览

根据官方赛题设置，2026 CSP-J复赛共4道编程题，满分400分，题型分布如下：

旅游
基础条件模拟题，考察字符串处理与逻辑分支判断
回文串
字符串区间题，考察大数据下的优化思维与前缀和应用
按位与
位运算综合题，考察二进制性质与贪心构造
纸牌游戏
博弈动态规划题，考察区间DP与状态转移设计

整体难度梯度清晰，前两题属于必拿分的基础题型，后两题设置了明显的区分度，贴合NOI大纲对入门组的能力要求。

二、第1题「旅游」深度解析

题目背景

本题以高铁座位判断为场景，给定两张二等座车票信息，要求依次输出4位0/1结果，分别判断：是否同车厢、是否同排、是否过道同侧、是否相邻。

二等座座位规则：每排5个座位，顺序为A、B、C、过道、D、F；相邻需满足同车厢、同排、同侧且座位字母相邻。

部分分解法（测试点1~10）

核心思路

前10个测试点保证两座位同车厢、同排，因此前两位固定输出11，只需判断后两个条件：

同侧判断：A/B/C为左侧，D/F为右侧，通过字符范围即可快速判断
相邻判断：枚举所有相邻组合（A-B、B-C、D-F），双向匹配

时间、空间复杂度均为O(1)，是入门级的条件分支写法。

完整代码

#include <iostream>#include <string>#include <cstdio>using namespace std;int main() {    freopen("travel.in", "r", stdin);    freopen("travel.out", "w", stdout);    ios::sync_with_stdio(false);    cin.tie(nullptr);    string c1, s1, c2, s2;    cin >> c1 >> s1 >> c2 >> s2;    char x = s1[2], y = s2[2];    bool same_side = ((x <= 'C') == (y <= 'C'));    bool is_near = (x == 'A' && y == 'B') || (x == 'B' && y == 'A')                || (x == 'B' && y == 'C') || (x == 'C' && y == 'B')                || (x == 'D' && y == 'F') || (x == 'F' && y == 'D');    cout << "11" << same_side << (same_side && is_near) << '\n';    return 0;}

满分解法（全测试点通过）

核心思路

按照题意逐层递进判断四个条件，后一个条件必须在前一个成立的前提下才为真，严格对应题干的四层逻辑：

p1：
车厢号字符串完全相等
p2：

在同车厢基础上，排号的两位字符均相同

p3：
在同排基础上，座位字母位于过道同侧
p4：
在同侧基础上，座位字母相邻

最终依次输出四个布尔值，即为题目要求的四位结果，全程O(1)复杂度，无任何额外空间开销。

完整满分代码

#include <iostream>#include <string>#include <cstdio>using namespace std;int main() {    freopen("travel.in", "r", stdin);    freopen("travel.out", "w", stdout);    ios::sync_with_stdio(false);    cin.tie(nullptr);    string c1, s1, c2, s2;    cin >> c1 >> s1 >> c2 >> s2;    char x = s1[2], y = s2[2];    bool p1 = (c1 == c2);    bool p2 = p1 && s1[0] == s2[0] && s1[1] == s2[1];    bool p3 = p2 && ((x <= 'C') == (y <= 'C'));    bool is_near = (x == 'A' && y == 'B') || (x == 'B' && y == 'A')                || (x == 'B' && y == 'C') || (x == 'C' && y == 'B')                || (x == 'D' && y == 'F') || (x == 'F' && y == 'D');    bool p4 = p3 && is_near;    cout << p1 << p2 << p3 << p4 << '\n';    return 0;}

本题考点总结

本题是标准的复赛签到题，核心考察细心程度与字符串基础操作。易错点集中在座位字母的边界判断、相邻组合的双向枚举，只要逻辑分层清晰，属于必拿的100分。

三、第2题「回文串」深度解析

题目背景

给定n段连续字符，第i段由a_i个相同字符c_i拼接而成，形成一个超长字符串。求最少修改多少个字符，可以让整个字符串变为回文串。

本题核心难点：字符串总长度可能极大，无法直接展开存储，必须通过数学区间方法计算对称位置差异。

部分分解法一：展开字符串（测试点112、1718）

核心思路

当总长度不超过20万时，可以直接将所有段展开为完整字符数组，使用经典双指针法：

左指针从首端开始，右指针从尾端开始
对称位置字符不同则答案+1，两指针同步向中心移动
仅统计左半部分，避免重复计数

时间复杂度O(n+L)，空间复杂度O(n+L)，适合总长度较小的测试点。

完整代码

#include <iostream>#include <cstdio>#define LL long longusing namespace std;const int N = 200000 + 5;LL a[N];char c[N], s[N];int main() {    freopen("string.in", "r", stdin);    freopen("string.out", "w", stdout);    ios::sync_with_stdio(false);    cin.tie(nullptr);    int n;    cin >> n;    LL sum = 0;    for (int i = 1; i <= n; i++) {        cin >> a[i] >> c[i];        sum += a[i];    }    if (sum > 200000) return 0;    int len = 0;    for (int i = 1; i <= n; i++) {        for (int j = 1; j <= a[i]; j++) {            s[++len] = c[i];        }    }    int ans = 0;    int l = 1, r = len;    while (l < r) {        if (s[l] != s[r]) ans++;        l++; r--;    }    cout << ans << '\n';    return 0;}

部分分解法二：枚举段区间（测试点1~16）

核心思路

当n≤2000时，无需展开字符串，通过前缀和+区间交集计算差异数：

预处理前缀和数组pre[i]，表示前i段总长度，总长度L=pre[n]
原第i段区间为[pre[i-1]+1, pre[i]]，镜像后第j段区间为[L-pre[j]+1, L-pre[j-1]]
枚举所有段对，若字符不同，计算两个区间与左半区间[1, L/2]的交集长度，累加到答案

时间复杂度O(n²)，空间复杂度O(n)，可以处理总长度极大、但段数较少的场景。

完整代码

#include <iostream>#include <cstdio>#include <algorithm>#define LL long longusing namespace std;const int N = 2000 + 5;LL pre[N];char c[N];int main() {    freopen("string.in", "r", stdin);    freopen("string.out", "w", stdout);    ios::sync_with_stdio(false);    cin.tie(nullptr);    int n;    cin >> n;    for (int i = 1; i <= n; i++) {        LL a;        cin >> a >> c[i];        pre[i] = pre[i-1] + a;    }    LL L = pre[n];    LL ans = 0;    for (int i = 1; i <= n; i++) {        for (int j = 1; j <= n; j++) {            if (c[i] == c[j]) continue;            LL l1 = pre[i-1] + 1, r1 = pre[i];            LL l2 = L - pre[j] + 1, r2 = L - pre[j-1];            LL l = max(l1, max(l2, 1LL));            LL r = min(r1, min(r2, L / 2));            if (l <= r) ans += r - l + 1;        }    }    cout << ans << '\n';    return 0;}