ARTICLE · 1286091

CSP-J 2026 第二轮全真试题通俗剖析与模拟讲义

发布时间：2026-10-31 15:22:03 最近访问：2026-10-31 15:22:03

CSP-J 2026 第二轮 · J 组

四道题，逐题拆到底

从出题意图到满分代码
每一行都告诉你为什么这么写

今天的四道题，考的是什么

题号	题目	核心考点	难度
T1	旅游 travel	模拟 · 逻辑分层	易
T2	回文串 string	双指针 · 区间压缩	易
T3	按位与 and	贪心 · 二进制试填	中
T4	纸牌游戏 card	逆向思维 · 链式转移	难

这套题的难度曲线很标准：T1、T2 是稳分题，必须一分不丢；T3 是分水岭；T4 决定能不能上高分。下面按这个顺序拆。

旅游 travel · 模拟与逻辑分层

入门组第一题，考的从来不是算法，而是基本功：字符串拆分、判断条件的层层递进、以及细节的把控。题目给出四个递进的是非判断，要求输出一个长度为 4 的 01 串。

先把座位规则讲清楚

四个判断，一层套一层
① 同车厢：c1 == c2
② 同排：在 ① 基础上排号相同
③ 同侧：在 ② 基础上字母同属 {A,B,C} 或 {D,F}
④ 相邻：在 ③ 基础上是 A-B、B-C 或 D-F

这里最容易翻车：四个答案不是独立判断，是层层依赖。② 必须建立在 ① 之上，④ 必须建立在 ③ 之上。写成四个并列的 if，样例里「不同车厢」那组就会输出 0011 而不是 0000。

五组样例，一眼对完

02 01A 02 01B1111

同车厢 · 同排 · 同侧 · A-B 相邻

02 01C 02 01A1110

同侧，但中间隔着座位 B

02 01C 02 01D1100

C 在左、D 在右，被过道隔断

02 02B 02 01A1000

排号 02 ≠ 01，后三问全为 0

02 01A 03 01A0000

车厢都不同，全为 0

满分代码

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

bool isLeft(char c) {
    return c >= 'A' && c <= 'C';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string c1, s1, c2, s2;
    if (!(cin >> c1 >> s1 >> c2 >> s2)) return 0;

// 拆出排号(前2位)与座位字母(第3位)
    string row1 = s1.substr(0, 2);
    string row2 = s2.substr(0, 2);
    char col1 = s1[2], col2 = s2[2];

    bool q1 = (c1 == c2);             // 同车厢
    bool q2 = q1 && (row1 == row2);    // 同排

    bool same = isLeft(col1) == isLeft(col2);
    bool q3 = q2 && same;             // 同侧

    bool adj = false;
    if (same) {
        char u = min(col1, col2);
        char v = max(col1, col2);
        if (isLeft(u))
            adj = (v == u + 1);       // AB / BC
        else
            adj = (u == 'D' && v == 'F');  // DF
    }
    bool q4 = q3 && adj;              // 相邻

    cout << (q1?1:0) << (q2?1:0)
         << (q3?1:0) << (q4?1:0) << "\n";
    return 0;
}

三个丢分点
1. 四个判断写成并列，样例 5 直接错
2. 忘记 C 和 D 中间是过道
3. 把 A-B、B-C 之外也算相邻（比如误判 A-C）

回文串 string · 压缩区间的双指针

考点是行程长度编码（RLE）下的双指针区间处理。字符串以「段长度 + 字符」的形式给出，问最少改几个字符能变成回文串。

⚠ 数据规模陷阱，这是本题最大的坑
字符串总长最大可达 2 × 10⁵ × 10⁹ = 2 × 10¹⁴。
绝对不能把串还原出来——不是慢一点的问题，是内存直接爆掉。但段数 n ≤ 2 × 10⁵，这个规模完全够用。

核心思路：只比前半段
回文串的修改次数 = 前半部分与后半部分对称位置不同的字符对数。

用一左一右两个游标在压缩段上走：
① 左指针在段L，剩lr个，字符cL
② 右指针在段R，剩rr个，字符cR
③ 本次能同时匹配min(lr, rr)个
④ 若cL ≠ cR，这若干个位置都得改，答案加进去
⑤ 两边各扣掉匹配量，哪段用完就推进下一段
⑥ 累计匹配达到总长 / 2 就停

样例 1 手推一遍

输入 2 a2 b1 c，拼起来是 aabbc，总长 5，只需比较前 ⌊5/2⌋ = 2 个位置。

步	左端剩	右端剩	结果
1	段1 'a' 剩2	段3 'c' 剩1	a≠c，+1
2	段1 'a' 剩1	段2 'b' 剩2	a≠b，+1

累计代价 1 + 1 = 2。中间第 3 位 b 自己和自己对称，不用改。输出 2，与样例一致。

满分代码

#include <iostream>
#include <vector>
using namespace std;

struct Seg { long long len; char ch; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    vector<Seg> seg(n);
    long long total = 0;
    for (int i = 0; i < n; ++i) {
        cin >> seg[i].len >> seg[i].ch;
        total += seg[i].len;
    }

    long long need = total / 2;   // 只比前半段
    long long ans = 0;

    int l = 0, r = n - 1;
    long long lr = seg[0].len;
    long long rr = seg[n - 1].len;

    while (need > 0) {
        long long cur = min(lr, rr);
        cur = min(cur, need);     // 别越过中线

        if (seg[l].ch != seg[r].ch)
            ans += cur;

        need -= cur;
        lr -= cur;
        rr -= cur;

        if (lr == 0) {
            l++;
            if (l < n) lr = seg[l].len;
        }
        if (rr == 0) {
            r--;
            if (r >= 0) rr = seg[r].len;
        }
    }

    cout << ans << "\n";
    return 0;
}

四个丢分点
1. 试图还原字符串——内存爆
2. ans、total 用 int——超范围
3. 少了 cur = min(cur, need)，越过中线多算
4. 只遍历段不设终点，奇数长度时中间段被误算

按位与 and · 高位贪心 + 集合筛选

从 n 个数里挑 m 个，让它们的按位与结果尽可能大。这道题是本次的分水岭，会做与不会做完全两极。

关键洞察：二进制的位权是压倒性的
对任意 k 都满足 2^k > 2^k-1 + 2^k-2 + … + 2⁰。
也就是说，高位的一个 1，比所有低位加起来的和还要大。
所以策略必然是：从最高位往最低位，逐位贪心试探。

四步流程
① 维护一个候选池，初始是全部 n 个数
② 从第 29 位往第 0 位，数一数池里有多少个数这一位是 1
③ 如果数量 ≥ m：这一位能保住 1。答案这一位置 1，并把池里该位为 0 的数全部剔除（选了它们就把这一位拉成 0 了）
④ 如果数量 < m：就算全选上也不够 m 个，这一位只能是 0。池子不动，看下一位

样例 1 逐位推演

n = 4, m = 2，四个数是 3、15、12、12。
二进制低 4 位：3 = 0011，15 = 1111，12 = 1100，12 = 1100

考查位	该位为 1	数量是否够	ans
第3位 (8)	15, 12, 12	3 ≥ 2 ✓	8
第2位 (4)	15, 12, 12	3 ≥ 2 ✓	12
第1位 (2)	只有 15	1 < 2 ✗	12
第0位 (1)	只有 15	1 < 2 ✗	12

最终答案 12。注意第 1 位虽然 15 有，但只有一个，凑不满 2 个，只能放弃——这就是「贪心必须验证可行性」的地方。

满分代码

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    vector<unsigned int> pool(n);
    for (int i = 0; i < n; ++i) cin >> pool[i];

    unsigned int ans = 0;

// 10^9 < 2^30，从第29位贪到第0位
    for (int b = 29; b >= 0; --b) {
        int cnt = 0;
        for (unsigned int x : pool)
            if ((x >> b) & 1) cnt++;

        if (cnt >= m) {
            ans |= (1U << b);

            vector<unsigned int> np;
            np.reserve(cnt);
            for (unsigned int x : pool) {
                if ((x >> b) & 1)
                    np.push_back(x);
            }
            pool = move(np);
        }
    }

    cout << ans << "\n";
    return 0;
}

三个丢分点
1. 从第 0 位往第 29 位试——方向反了，结果完全错
2. 判断成功后忘记剔除池里该位为 0 的数——后面的位被污染
3. 只看「有没有数这一位是 1」，没检查够不够 m 个

纸牌游戏 card · 逆向思维与状态继承

压轴题。正向模拟每一局游戏，复杂度 O(n²)，必然超时。这题的突破口只有一个：换个方向想。

先看清楚消除规则
「若桌上有 k，收走 k 及其右侧的所有牌，再把新的 k 放在最右端。」

假设第i个位置打出的牌是a[i]，它后面下一次出现的位置是nxt[i]。跟着走一遍：
① 第i局刚打出a[i]时，桌上只有这一张牌
② 一路打到nxt[i]，触发消除：把原来的 a[i] 连同它右边的牌全收走
③ 清空后把新的a[nxt[i]]放到最右——桌上又只剩这一张牌
④ 于是第 i 局此刻的状态，和第 nxt[i] 局刚开始时一模一样

由此得到两条状态继承定理
定理 1（有后继）：若 a[i] 后面还会出现，第 i 局最终留存的牌集 完全等于 第 nxt[i] 局的留存牌集。
定理 2（无后继）：若 a[i] 是最后一次出现，没有牌能消除它，a[i] 必定留存；右侧留存的牌就是第 i+1 局的牌集。

样例 1 手推验证

n = 4, m = 3，牌序列 1、2、1、3

局	打牌	局末桌面	依据
第4局	3	{3}	无后继，保留
第3局	1, 3	{1, 3}	继承第4局
第2局	2, 1, 3	{2, 1, 3}	继承第3局
第1局	1, 2, 1, 3	{1, 3}	继承第3局

统计每个点数留存的局数
点数 1：第 1、2、3 局 → 3 局
点数 2：只有第 2 局 → 1 局
点数 3：第 1、2、3、4 局 → 4 局
输出 3 1 4，与标准答案一致。

这道题有个极易写反的地方
把每个起点映射到它所属的「根」（某个点数的最后出现位置），再统计多少局归到了根 p 上，记作 cnt[p]。
点数 x 的留存局数 = 所有位置 ≤ last[x] 的 cnt 之和，是前缀和，必须从左往右累加。
写成从右往左的后缀和，答案顺序会整体颠倒——样例 1 会输出 3 4 1 而不是 3 1 4。这种错误样例可能过、大样例必挂，最难查。

满分代码

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;

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

// 第一步：倒扫，求每位的下一次出现
    vector<int> last(m + 1, 0);
    vector<int> nxt(n + 2, 0);
    for (int i = n; i >= 1; --i) {
        nxt[i] = last[a[i]];
        last[a[i]] = i;
    }

// 第二步：每个起点归到所属的根
    vector<int> root(n + 2, 0);
    vector<int> cnt(n + 2, 0);
    for (int i = n; i >= 1; --i) {
        root[i] = nxt[i] ? root[nxt[i]] : i;
        cnt[root[i]]++;
    }

// 第三步：前缀和，赋给对应点数
// 方向别写反：是前缀和，不是后缀和
    vector<int> ans(m + 1, 0);
    int pre = 0;
    for (int i = 1; i <= n; ++i) {
        if (nxt[i] == 0) {    // 最后出现
            pre += cnt[i];
            ans[a[i]] = pre;
        }
    }

    for (int i = 1; i <= m; ++i)
        cout << ans[i] << (i == m ? "" : " ");
    cout << "\n";
    return 0;
}