2023CCF非专业级软件能力认证
CSP-J/S2023第二轮认证
提高级
时间：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秒
js的基本数据类型
内存限制512MiB512MiB512MiB512MiB
测试点数目10202020
测试点是否等分是是是是提交源程序文件名
对于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下进行，各语言的编译器版本以此为准。
密码锁（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输入】
11
200115
【样例1输出】
181
【样例1解释】
一共有81种可能的方案。
其中转动一个拨圈的方案有45种，转动两个拨圈的方案有36种。
【样例2】
见选手目录下的lock/lock2.in与lock/lock2.ans。
【数据范围】
对于所有测试数据有：1≤n≤8。
测试点n≤特殊性质
1∼31无
4∼52无
6∼88A
9∼108无
特殊性质A：保证所有正确密码都可以通过仅转动一个拨圈得到测试数据给出的n 个状态。
消消乐（game）
【题目描述】
小L现在在玩一个低配版本的消消乐，该版本的游戏是一维的，一次也只能消除两个相邻的元素。
现在，他有一个长度为n且仅由小写字母构成的字符串。我们称一个字符串是可消除的，当且仅当可以对这个字符串进行若干次操作，使之成为一个空字符串。
其中每次操作可以从字符串中删除两个相邻的相同字符，操作后剩余字符串会拼接在一起。
小L想知道，这个字符串的所有非空连续子串中，有多少个是可消除的。
【输入格式】
从文件game.in中读入数据。
输入的第一行包含一个正整数n，表示字符串的长度。
输入的第二行包含一个长度为n且仅由小写字母构成的的字符串，表示题目中询问的字符串。
【输出格式】
输出到文件game.out中。
输出一行包含一个整数，表示题目询问的答案。
【样例1输入】
18
2accabccb
【样例1输出】
15
【样例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。
【数据范围】
对于所有测试数据有：1≤n≤2×106，且询问的字符串仅由小写字母构成。
测试点n≤特殊性质
1∼510无
6∼7800无
8∼108000无
11∼122×105A
13∼142×105B
15∼172×105无
18∼202×106无
特殊性质A：字符串中的每个字符独立等概率地从字符集中选择。
特殊性质B：字符串仅由a和b构成。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。