2023年（复赛J）CCF非专业级别软件能力认证全国卷真题（附详细答案解析）

2023 CCF 非专业级软件能力认证 CSP-J/S 2023 第二轮认证 提高级 时间：2023 年 10 月 21 日 14:30 ∼ 18:30 题目名称 密码锁 消消乐 结构体 种树 题目类型 传统型 传统型 传统型 传统型 目录 lock game struct tree 可执行文件名 lock game struct tree 输入文件名 lock.in game.in struct.in tree.in 输出文件名 lock.out game.out struct.out tree.out 每个测试点时限 1.0 秒 1.0 秒 1.0 秒 1.0 秒 内存限制 512 MiB 512 MiB 512 MiB 512 MiB 测试点数目 10 20 20 20 测试点是否等分 是 是 是 是 提交源程序文件名 对于 C++ 语言 lock.cpp game.cpp struct.cpp tree.cpp 编译选项 对于 C++ 语言 ‐O2 ‐std=c++14 ‐static .注 .意 .事 .项（ .请 .仔 .细 .阅 .读） 1. 文件名（程序名和输入输出文件名）必须使用英文小写。 2. C/C++ 中函数 main() 的返回值类型必须是 int，程序正常结束时的返回值必须 是 0。 3. 提交的程序代码文件的放置位置请参考各省的具体要求。 4. 因违反以上三点而出现的错误或问题，申诉时一律不予受理。 5. 若无特殊说明，结果的比较方式为全文比较（过滤行末空格及文末回车）。 6. 选手提交的程序源文件必须不大于 100KB。 7. 程序可使用的栈空间内存限制与题目的内存限制一致。 8. 全国统一评测时采用的机器配置为：Intel(R) Core(TM) i7-8700K CPU @3.70GHz， 内存 32GB。上述时限以此配置为准。 9. 只提供 Linux 格式附加样例文件。 10. 评测在当前最新公布的 NOI Linux 下进行，各语言的编译器版本以此为准。 2023 CCF 非专业级软件能力认证 CSP-J/S 2023 第二轮认证 提高级 密码锁（lock） 密码锁（lock） 【题目描述】 小 Y 有一把五个拨圈的密码锁。如图所示，每个拨圈上是从 0 到 9 的数字。每个 拨圈都是从 0 到 9 的循环，即 9 拨动一个位置后可以变成 0 或 8， 图 1: 密码锁 因为校园里比较安全，小 Y 采用的锁车方式是：从正确密码开始，随机转动密码锁 仅一次；每次都是以某个幅度仅转动一个拨圈或者同时转动两个相邻的拨圈。 当小 Y 选择同时转动两个相邻拨圈时，两个拨圈转动的幅度相同，即小 Y 可以将 密码锁从 0 0 1 1 5 转成 1 1 1 1 5，但不会转成 1 2 1 1 5。 时间久了，小 Y 也担心这么锁车的安全性，所以小 Y 记下了自己锁车后密码锁的 n 个状态，注意这 n 个状态都不是正确密码。 为了检验这么锁车的安全性，小 Y 有多少种可能的正确密码，使得每个正确密码 都能够按照他所采用的锁车方式产生锁车后密码锁的全部 n 个状态。 【输入格式】 从文件 lock.in 中读入数据。 输入的第一行包含一个正整数 n，表示锁车后密码锁的状态数。 接下来 n 行每行包含五个整数，表示一个密码锁的状态。 【输出格式】 输出到文件 lock.out 中。 输出一行包含一个整数，表示密码锁的这 n 个状态按照给定的锁车方式能对应多 少种正确密码。 【样例 1 输入】 第 2 页 共 12 页 2023 CCF 非专业级软件能力认证 CSP-J/S 2023 第二轮认证 提高级 密码锁（lock） 1 1 2 0 0 1 1 5 【样例 1 输出】 1 81 【样例 1 解释】 一共有 81 种可能的方案。 其中转动一个拨圈的方案有 45 种，转动两个拨圈的方案有 36 种。 【样例 2】 见选手目录下的 lock/lock2.in 与 lock/lock2.ans。 【数据范围】 对于所有测试数据有：1 ≤ n ≤ 8。 测试点 n ≤ 特殊性质 1 ∼ 3 1 无 4 ∼ 5 2 无 6 ∼ 8 8 A 9 ∼ 10 8 无 特殊性质 A：保证所有正确密码都可以通过仅转动一个拨圈得到测试数据给出的 n 个状态。 第 3 页 共 12 页 2023 CCF 非专业级软件能力认证 CSP-J/S 2023 第二轮认证 提高级 消消乐（game） 消消乐（game） 【题目描述】 小 L 现在在玩一个低配版本的消消乐，该版本的游戏是一维的，一次也只能消除两 个相邻的元素。 现在，他有一个长度为 n 且仅由小写字母构成的字符串。我们称一个字符串是可消 除的，当且仅当可以对这个字符串