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 借几张牌才能凑成一副完整的扑克牌。
【样例1输入】 2 SA 【样例1输出】 51 【样例 1 解释】 这一副牌中包含一张黑桃 A，小 P 还需要借除了黑桃 A 以外的 51 张牌以构成一副完整的扑克牌。 【样例2输入】 4 DQ H3 DQ DT 【样例2输出】 49 【样例 2 解释】 这一副牌中包含两张方片 Q、一张方片 T（方片 10）以及一张红桃 3。不重复的牌有 3 张，因此最少需要借 52-3=49 张牌。 【数据范围】 对于 100% 的数据，保证 1 ≤ n ≤ 52。 保证输入的每张牌都是合法的，即第一个字符为 D/C/H/S，第二个字符为 A/2/3/4/5/6/7/8/9/T/J/Q/K。
地图探险（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 【样例解释】 对于第一组数据，机器人初始位置 (1, 1)，朝向西。执行 4 步操作后，经过的位置有 (1,1), (1,2), (1,3)，共 3 个。 对于第二组数据，机器人初始位置 (1, 1)，朝向东。由于东侧第一行有障碍，机器人右转但不移动。执行 0 步操作后，只经过初始位置，共 1 个。 【数据范围】 对于所有测试数据，保证：1 ≤ T ≤ 5，1 ≤ n, m ≤ 1000，1 ≤ k ≤ 10⁶，1 ≤ x₀ ≤ n，1 ≤ y₀ ≤ m，0 ≤ d₀ ≤ 3，且初始位置为空地。
小木棍（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 【样例解释】 对于第一组测试数据，不存在任何一个正整数可以使用恰好一根小木棍摆出，故输出 -1。 对于第二组测试数据，数字 1 需要 2 根小木棍，是最小的满足条件的数。 对于第三组测试数据，数字 7 需要 3 根小木棍，是最小的满足条件的数。 对于第四组测试数据，注意 0 并不是一个满足要求的方案。摆出 9、41 以及 111 都恰好需要 6 根小木棍，但它们不是摆出的数最小的方案。最小的方案是 6（需要 6 根小木棍）。 对于第五组测试数据，摆出 208 需要 5+6+7=18 根小木棍。可以证明摆出任何小于 208 的正整数需要的小木棍数都不是 18。 【数据范围】 对于所有测试数据，保证：1 ≤ T ≤ 50，1 ≤ n ≤ 10⁵。
接龙（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 【样例解释】 该样例中 n=3, k=3。 对于询问 (1, 1)：第 1 轮可以从第 1 个人的词库中选出子序列 [1, 2]，最后一个数为 2，不满足条件。但可以选择 [1, 2, 3] 或 [2, 3, 4] 等，使得最后一个数为 3 或 4。但题目要求第一个数可以是任意整数，因此可以选择子序列 [1]（长度为 1 不满足）... 经过分析，可以选择子序列 [1, 2]，最后一个数是 2。但这不符合询问条件。实际上，第一轮可以从第 2 个人的词库中选出 [1, 2]，使得最后一个数为 2，满足 (1, 2) 的询问。 （注：样例解释较为复杂，需要根据具体数据推导） 【数据范围】 对于所有测试数据，保证： 1 ≤ T ≤ 10，1 ≤ n ≤ 10⁵，1 ≤ k ≤ 10⁵，1 ≤ q ≤ 10⁵。 1 ≤ l_i ≤ 2 × 10⁵，且所有 l_i 之和不超过 2 × 10⁵。 1 ≤ 词库中所有整数 ≤ 2 × 10⁵。 1 ≤ r_j ≤ 10⁵，1 ≤ c_j ≤ 2 × 10⁵。