资讯 / 正文

【真题复盘】CSP-J/S 第二轮认证真题复盘:入门组四道题,你家孩子卡在第几题

2026-11-06 16:21

PART.01

这一轮考了什么

2026 年 10 月 31 日上午 08:30—12:00，CSP-J/S 2026 第二轮认证入门组（CSP-J2）开考。三个半小时，四道程序题，满分 400 分。孩子交上去的不是答题卡，是四个源文件，由 CCF 在 NOI Linux 下统一评测。

这篇文章把入门组四道题的真题内容一次讲完：每道题考什么、样例怎么读、数据范围里埋了什么坑、正解怎么想、拿不到正解还能拿哪一档分。文末附一张考点图，四道题的关键处可以一次看清。

认证名称CCF 非专业级别软件能力认证 CSP-J/S 2026 第二轮（入门组）

主办单位中国计算机学会（CCF）

认证时间2026 年 10 月 31 日 08:30—12:00

题目与分值4 道程序题，满分 400 分

题目目录名travel / string / and / card

作答方式文件输入输出，提交 .cpp 源程序

评测环境NOI Linux 2.0，编译选项 -O2 -std=c++14

测试点每题 20—25 个测试点，每个测试点等分

PART.02

四道题考什么

四道题放在一起看，考点并不花哨：一道字符串处理、一道把字符串压成段、一道位运算贪心、一道模拟加递推。没有需要背的高级算法，分数差基本落在细节上——读题漏了哪一句、数据范围算准没有、特殊情况想到没有。

四道题各自的分工

✓第一题是送分题。规则全在题面里，代码不到三十行，读题慢一点就能拿满。

✓第二题是关键题，也是全卷最容易丢分的地方。难点不在双指针，而在 n 到 20 万、字符串最长 200 万亿位这个限制上。

✓第三题是拉分题。看着可以枚举，其实要从最高位逐位贪心；判每一位时还得把已经锁定的高位带上。

✓第四题是压轴题。先写模拟能拿到一档分，想通「最后一次出现位置」这个跳转才能满分。

PART.03

四道题逐题拆

下面四段按题号顺序写。每段先讲题意和样例，再讲数据和正解，最后点出考场上最容易失手的地方。

入门组四道题：真题内容与正解

01 旅游 travel

两人坐高铁出门，买了两张二等座票，要判断四件事：是否同一节车厢、是否同一排、是否在过道同一侧、两个座位是否相邻，输出一个 4 位的 01 串。题目的信息几乎都在座位规则里：车厢从 01 到 17，其中 01 和 16 是一等座不会出现；每排五个座位，过道左边是 A、B、C，右边是 D、F，中间没有 E 座。样例已经把坑摆出来了。01C 和 01A 同排同侧，但中间隔着 B，答案是 1110；01C 和 01D 隔着过道，答案是 1100；车厢不同直接 0000。正解是四个判断层层包含，前面为 0 后面必然为 0，可以一路短路输出。最容易错的两处：一是把右侧的 D、F 也按「字母相邻」去判（F 减 D 等于 2，但它们是真邻居）；二是把 0000 当整数输出，结果只有一个 0。

02 回文串 string

字符串不会直接给你，而是压成 n 段：第 i 段是 a[i] 个字符 c[i]。每次可以把任意一个位置的字符改成任意小写字母，问最少改几位能变成回文串。数据范围是全题的关键：n 不超过 20 万，每段最多 10 亿个字符，整个字符串最长能到 200 万亿位。把字符串真展开再双指针，一定超时，也一定会爆内存。正解利用「段」这个结构：左右两个指针指向最外侧还没处理的两段，每次同时处理 t = min(左段剩余, 右段剩余) 对字符，两段字符不同就让答案加上 t；扣掉 t 之后哪一段先用完，就移动那一边的指针。整个过程 O(n)。第三个样例专门用来打溢出：六段各 10 亿个字符，答案是 30 亿，用 int 交上去会变成负数。

03 按位与 and

从 n 个非负整数里恰好选 m 个，让选出的数的按位与最大。样例 1 选 15 和 12 得 12，选 3 和 15 只有 3，选 12 和 12 也是 12。做法是从最高位往低位贪心：假设第 29 位能给 1，就尝试一个候选值 x，数一数有多少个数满足 a[i] 与 x 的按位与等于 x，够 m 个就锁定这一位，接着往下试。一位一位来，每位扫一遍数组，30 次扫描，O(30n)。这里有一个必须点出来的细节：判定时要把已经锁定过的高位一起带上，不能每一位单独统计。只数「这一位是 1 的数有几个」，凑出来的会是一批根本不在同一组的数，答案偏大。分档上，枚举子集只能过最小的几个点；题面还给了 A、B 两档特殊性质，对应数值形态的额外限制，能再拿一档。

04 纸牌游戏 card

n 张牌，点数从 1 到 m，每种点数至少出现一次。要玩 n 局：第 i 局跳过前 i-1 张，从第 i 张一直打到第 n 张。桌面规则是，打出的点数不在桌上就放到最右端；已经在桌上，就把那张牌连同它右边所有牌一起收走，再把新牌放到最右端。问每种点数在多少局结束时还留在桌面上。样例 1 的牌是 1、2、1、3，答案是 3、1、4，逐局手推一遍就能把规则吃透。但 n 能到 50 万，逐局模拟是平方级，过不了。正解要看出一个性质：第 i 局的第一张牌 a[i] 会一直待在桌面最左边，直到打到这个点数的最后一次出现位置，此时右边被清空、桌上只剩它一张；而这之后的结果，和从那个位置的下一张开始新打一局没有区别。于是每一局都变成一条向右的跳转链。把 n 个起点一起统计：每个位置都先算一个起点，从前往后扫，把经过这里的局数记到对应点数的答案上，再把这些局数整体推给跳转后的位置。一遍 O(n) 结束。

PART.04

三个半小时怎么分

把四道题放到一张时间表上看，入门组这三个半小时怎么花，往往比「会不会某一道题」更影响最后的分数。

一份可以直接照着用的时间表

✓20—30 分钟拿下第一题。这题代码不到三十行，但读题要慢：座位号三位，前两位是排号，第三位才是字母。

✓40—50 分钟做第二题。先写能过小数据的版本，再改成按段处理。段式双指针不是背出来的，是「不能展开字符串」这个限制逼出来的。

✓第三题不要恋战。逐位贪心的框架十几分钟就能写完，写不完就先交暴力，回头再补。

✓给第四题留足一小时。它的部分分很实在：用栈老老实实模拟每一局，能过一档；想通「最后一次出现位置」这个跳转，才是满分。

✓交卷前十分钟一定做一次自查：文件读写的名字对不对、该开 long long 的地方开了没有、数组有没有开到 50 万。

PART.05

出分前的复盘

出分前，把「做过」变成「会做」