2024年CSP-J2复赛试题
__SECTIONS__:[{"name": "编程题", "count": 4}] 从PDF导入：2024年CSP-J2复赛试题
试卷题目预览
扑克牌（poker）
小 P 从同学小 Q 那儿借来一副 n 张牌的扑克牌。本题中我们不考虑大小王，此时每张牌具有两个属性：花色和点数。花色共有 4 种：方片、草花、红桃和黑桃。点数共有 13 种，从小到大分别为 A 2 3 4 5 6 7 8 9 T J Q K。注意：点数 10 在本题中记为 T。
我们称一副扑克牌是完整的，当且仅当对于每一种花色和每一种点数，都恰好有一张牌具有对应的花色和点数。由此，一副完整的扑克牌恰好有 4 × 13 = 52 张牌。
小 P 借来的牌可能不是完整的，为此小 P 准备再向同学小 S 借若干张牌。可以认为小 S 每种牌都有无限张，因此小 P 可以任意选择借来的牌。小 P 想知道他至少得向小 S 借多少张牌，才能让从小 S 和小 Q 借来的牌中，可以选出 52 张牌构成一副完整的扑克牌。
为了方便你的输入，我们使用字符 D 代表方片，字符 C 代表草花，字符 H 代表红桃，字符 S 代表黑桃，这样每张牌可以通过一个长度为 2 的字符串表示，其中第一个字符表示这张牌的花色，第二个字符表示这张牌的点数，例如 CA 表示草花 A，ST 表示黑桃 T（黑桃 10）。
从文件 poker.in 中读入数据。 输入的第一行包含一个整数 n 表示牌数。 接下来 n 行，每行包含一个长度为 2 的字符串描述一张牌，其中第一个字符描述其花色，第二个字符描述其点数。
输出到文件 poker.out 中。 输出一行一个整数，表示最少还需要向小 S 借几张牌才能凑成一副完整的扑克牌。
2 SA 4 DQ H3 DQ DT
51 49
地图探险（explore）
小 A 打算前往一片丛林去探险。丛林的地理环境十分复杂，为了防止迷路，他先派遣了一个机器人前去探路。
丛林的地图可以用一个 n 行 m 列的字符表来表示。我们将第 i 行第 j 列的位置的坐标记作 (i, j)。如果这个位置的字符为 x，即代表这个位置上有障碍，不可通过。反之，若这个位置的字符为 .，即代表这个位置是一片空地，可以通过。
这个机器人的状态由位置和朝向两部分组成。其中位置由坐标 (x, y) 刻画，它表示机器人处在地图上第 x 行第 y 列的位置。而朝向用一个 0 ~ 3 的整数 d 表示，其中 d = 0 代表向东，d = 1 代表向南，d = 2 代表向西，d = 3 代表向北。
初始时，机器人的位置为 (x₀, y₀)，朝向为 d₀。保证初始时机器人所在的位置为空地。
接下来机器人将要进行 k 次操作。每一步，机器人将按照如下的模式操作：
假设机器人当前处在的位置为 (x, y)，朝向为 d。则它的方向上的下一步的位置 (x', y') 定义如下：
若 d = 0，则令 (x', y') = (x, y + 1)；
若 d = 1，则令 (x', y') = (x + 1, y)；
若 d = 2，则令 (x', y') = (x, y - 1)；
若 d = 3，则令 (x', y') = (x - 1, y)。
接下来，机器人判断它下一步的位置是否在地图内，且是否为空地。如果条件成立，则机器人会向前走一步，新的位置变为 (x', y')，且朝向不变。如果条件不成立，则它会执行"向右转"操作，即令 d' = (d + 1) mod 4，且它所处的位置保持不变，但朝向由 d 变为 d'。
小 A 想要知道，在机器人执行完 k 步操作之后，地图上所有被机器人经过的位置（包括起始位置）有几个。
从文件 explore.in 中读入数据。 输入的第一行包含一个正整数 T，表示数据组数。 接下来包含 T 组数据。每组数据的格式如下： 第一行包含三个正整数 n, m, k，表示地图的行数、列数，以及机器人执行的操作次数。 第二行包含三个正整数 x₀, y₀, d₀，表示机器人初始时所处的位置和朝向。 接下来 n 行，每行一个长度为 m 的字符串，表示地图。保证字符串只包含 . 和 x 两种字符。
输出到文件 explore.out 中。 对于每组数据，输出一行一个整数，表示地图上被机器人经过的位置有几个。
2 1 5 4 1 1 2 ....x 2 5 0 1 1 0 ....x ....x
3 1
小木棍（sticks）
小 S 喜欢收集小木棍。在收集了 n 根长度相等的小木棍之后，他闲来无事，便用它们拼起了数字。用小木棍拼每种数字的方法如下图所示：
数字 0: 6 根小木棍
数字 1: 2 根小木棍
数字 2: 5 根小木棍
数字 3: 5 根小木棍
数字 4: 4 根小木棍
数字 5: 5 根小木棍
数字 6: 6 根小木棍
数字 7: 3 根小木棍
数字 8: 7 根小木棍
数字 9: 6 根小木棍
现在小 S 希望拼出一个正整数，满足如下条件：
1. 拼出这个数恰好使用 n 根小木棍；
2. 拼出的数没有前导 0；
3. 在满足以上两个条件的前提下，这个数尽可能小。
小 S 想知道这个数是多少，可 n 很大，把木棍整理清楚就把小 S 折腾坏了，所以你需要帮他解决这个问题。如果不存在正整数满足以上条件，你需要输出 -1 进行报告。
从文件 sticks.in 中读入数据。 本题有多组测试数据。 输入的第一行包含一个正整数 T，表示数据组数。 接下来包含 T 组数据，每组数据的格式如下： 一行包含一个整数 n，表示木棍数。
输出到文件 sticks.out 中。 对于每组数据：输出一行，如果存在满足题意的正整数，输出这个数；否则输出 -1。
5 1 2 3 6 18
-1 1 7 6 208
接龙（chain）
在玩惯了成语接龙之后，小 J 和他的朋友们发明了一个新的接龙规则。
总共有 n 个人参与这个接龙游戏，第 i 个人会获得一个整数序列 Si 作为他的词库。
游戏会进行若干轮，每轮游戏规则如下：
1. n 个人中的某个人 p 带着他的词库 Sp 进行接龙。若这不是游戏的第一轮，那么这一轮进行接龙的人不能与上一轮相同，但可以与上上轮或更往前的轮相同。
2. 接龙的人选择一个长度在 [2, k] 范围内的 Sp 的连续子序列，其中 k 是给定的参数。若这不是游戏的第一轮，则这个子序列的第一个数必须等于上一轮接龙所用的子序列的最后一个数。这个选出的子序列就是本轮接龙的结果。
小 J 和他的朋友们想进行 q 次询问，第 j 次询问为：是否存在一个恰好进行 r_j 轮的游戏方案，使得第 r_j 轮接龙结束时的那一个子序列的最后一个数恰好等于 c_j。如果存在方案，回答 1，否则回答 0。
注意：第一轮接龙选出的子序列的第一个数可以是任意整数。
从文件 chain.in 中读入数据。 输入的第一行包含一个正整数 T，表示数据组数。 接下来包含 T 组数据，每组数据的格式如下： 第一行包含三个正整数 n, k, q，分别表示参与接龙的人数、子序列长度的上限和询问次数。 接下来 n 行，第 i 行描述第 i 个人的词库： 首先给出一个正整数 l_i，表示第 i 个人的词库中整数的个数；然后给出 l_i 个用空格分隔的整数，依次表示词库中的每个整数。 接下来 q 行，每行包含两个用空格分隔的正整数 r_j, c_j，表示一次询问。
输出到文件 chain.out 中。 对于每组数据，输出 q 行，每行包含一个整数 1 或 0，表示对应询问的答案。
1 3 3 7 5 1 2 3 4 1 3 1 2 3 3 2 3 1 1 1 1 2 1 3 2 1 2 2 2 3 3 1
1 1 1 1 1 0 1