2023年CCF非专业级别软件能力认证第二轮 （CSP-S）提高级C++语言试题答案及解析.pdfVIP

一、实操题

1、密码锁（lock）

【题目描述】

小Y有一把五个拨圈的密码锁。如图所示，每个拨圈上是从0到9的数字。每个拨圈

都是从0到9的循环，即9拨动一个位置后可以变成0或8，

图1:密码锁

因为校园里比较安全，小Y采用的锁车方式是：从正确密码开始，随机转动密码锁

仅一次；每次都是以某个幅度仅转动一个拨圈或者同时转动两个相邻的拨圈。当小

Y选择同时转动两个相邻拨圈时，两个拨圈转动的幅度相同，即小Y可以将密码锁

从00115转成11115，但不会转成12115。

时间久了，小Y也担心这么锁车的安全性，所以小Y记下了自己锁车后密码锁的n个

状态，注意这n个状态都不是正确密码。

为了检验这么锁车的安全性，小Y有多少种可能的正确密码，使得每个正确密码都

能够按照他所采用的锁车方式产生锁车后密码锁的全部n个状态。

【输入格式】

从文件lock.in中读入数据。

输入的第一行包含一个正整数n，表示锁车后密码锁的状态数。

接下来n行每行包含五个整数，表示一个密码锁的状态。

【输出格式】

输出到文件lock.out中。

输出一行包含一个整数，表示密码锁的这n个状态按照给定的锁车方式能对应多少

种正确密码。

【样例1输入】

1

00115

【样例1输出】

81

【样例1解释】

一共有81种可能的方案。

其中转动一个拨圈的方案有45种，转动两个拨圈的方案有36种。

【样例2】

见选手目录下的lock/lock2.in与lock/lock2.ans。

参考答案：由于题目没有给出具体的输入数据，因此无法直接给出答案。但根据题

目描述，我们可以知道，要解决这个问题，我们需要遍历所有可能的密码组合，然

后检查每个组合是否能够按照小Y的锁车方式产生锁车后的n个状态。这个过程可

能比较复杂，需要使用编程来实现。

解析：【喵呜刷题小喵解析】：

这道题目是一个典型的计算机科学问题，涉及到密码学、组合数学和编程。题目要

求找出所有可能的正确密码，使得每个正确密码都能够按照小Y的锁车方式产生锁

车后的n个状态。由于密码锁有五个拨圈，每个拨圈上的数字都是从0到9的循环，

因此总共有10^5种可能的密码组合。

解决这个问题的一个可能的方法是，对于每个可能的密码组合，我们可以模拟小Y

的锁车方式，生成锁车后的n个状态，然后检查这些状态是否和题目给出的n个状态

一致。如果一致，那么这个密码组合就是一个可能的正确密码。

然而，由于密码锁有五个拨圈，每个拨圈上的数字都是从0到9的循环，因此总共有

10^5种可能的密码组合，直接遍历所有可能的密码组合可能会非常耗时。因此，我

们需要使用一些优化技巧来加速这个过程。

一种可能的优化技巧是使用哈希表来存储已经生成过的状态，避免重复生成相同的

状态。另外，我们可以利用小Y的锁车方式的特性，即每次都是以某个幅度仅转动

一个拨圈或者同时转动两个相邻的拨圈，来减少需要生成的状态的数量。

总的来说，解决这个问题需要使用编程和算法知识，同时需要一些优化技巧来加速

过程。由于题目没有给出具体的输入数据，因此无法直接给出答案，需要根据具体

的输入数据来编写程序进行求解。

2、消消乐（game）

【题目描述】

小L现在在玩一个低配版本的消消乐，该版本的游戏是一维的，一次也只能消除两

个相邻的元素。

现在，他有一个长度为n且仅由小写字母构成的字符串。我们称一个字符串是可消

除的，当且仅当可以对这个字符串进行若干次操作，使之成为一个空字符串。

其中每次操作可以从字符串中删除两个相邻的相同字符，操作后剩余字符串会拼接

在一起。

小L想知道，这个字符串的所有非空连续子串中，有多少个是可消除的。

【输入格式】

从文件game.in中读入数据。

输入的第一行包含一个正整数n，表示字符串的长度。

输入的第二行包含一个长度为n且仅由小写字母构成的的字符串，表示题目中询问

的字符串。

【输出格式】

输出到文件game.out中。

输出一行包含一个整数，表示题目询问的答案。

【样例1输入】

8

accabccb

【样例1输出】

5

【样例1解释】

一共有5个可消除的连续子串，分别是cc、acca、cc、bccb、accabccb。

【样例2】

见选手目录下的game/game2.in与game/game2.ans。

【样例3】

见选手目录下的game/game3.in与game/game3.ans。

【样例4】

见选手目录下的game/game4.in与game/game4.ans。

参考答案：本题是一道计算字符串中