2022年CSP-J2复赛
__SECTIONS__:[{"name": "编程题", "count": 4}] 从PDF导入：2022年CSP-J2复赛试题
C++
210分钟
总分 400.0
4 题
试卷题目预览
第1题
中级
100.0分
编程
乘方（pow）
小文同学刚刚接触了信息学竞赛，有一天她遇到了这样一个题：给定正整数 a 和 b，求 a^b 的值。
因为 a^b 的值可能非常大，如果 a^b > 10^9，则输出 -1。
注意：a^b 表示 a 的 b 次方。
【输入格式】
从文件 pow.in 中读入数据。 输入一行包含两个正整数 a 和 b，含义如题所述。
【输出格式】
输出到文件 pow.out 中。 输出一行，如果 a^b ≤ 10^9，则输出 a^b 的值，否则输出 -1。
【样例1输入】 10 9 【样例1输出】 1000000000 【样例2输入】 2 30 【样例2输出】 -1 【数据范围】 对于所有测试数据，保证 1 ≤ a, b ≤ 10^9。
第2题
中级
100.0分
编程
解密（decode）
给定一个正整数 k，有 k 次询问，每次给定三个正整数 n, e, d，要求输出正整数 p, q 使得：
n = p × q
e × d = (p-1)(q-1) + 1
数据保证一定有解。
【输入格式】
从文件 decode.in 中读入数据。 输入第一行包含一个正整数 k，表示询问次数。 接下来 k 行，每行三个正整数 n, e, d。
【输出格式】
输出到文件 decode.out 中。 输出 k 行，每行两个正整数 p, q，其中 p ≤ q。
【样例输入】 3 242 3 31 1829 5 331 16151 7 1499 【样例输出】 11 22 3 610 17 949 【样例解释】 对于第一组询问：n=242, e=3, d=31。 p=11, q=22 时：n=11×22=242，e×d=3×31=93，(p-1)(q-1)+1=10×21+1=211。 实际上，根据公式推导：由 e×d=(p-1)(q-1)+1 和 n=p×q 可得 p+q=n-e×d+2。 联立方程可解得 p 和 q 的值。 【数据范围】 对于所有测试数据，保证：1 ≤ k ≤ 10^5，1 ≤ n, e, d ≤ 10^18。 保证存在唯一解。
第3题
中级
100.0分
编程
逻辑表达式（expr）
给定一个逻辑表达式，计算该表达式的值，并统计 & 和 | 短路运算的次数。
逻辑表达式的定义：
1. 0 和 1 是逻辑表达式，其值分别为 0 和 1。
2. 如果 A 和 B 是逻辑表达式，则 (A&B) 和 (A|B) 也是逻辑表达式，其中 & 表示逻辑与，| 表示逻辑或。
3. 短路运算：
- 对于 A&B，如果 A 的值为 0，则整个表达式的值为 0，不需要计算 B 的值（称为 & 短路）。
- 对于 A|B，如果 A 的值为 1，则整个表达式的值为 1，不需要计算 B 的值（称为 | 短路）。
【输入格式】
从文件 expr.in 中读入数据。 输入一行一个字符串，表示给定的逻辑表达式。
【输出格式】
输出到文件 expr.out 中。 输出三行： 第一行输出逻辑表达式的值（0 或 1）。 第二行输出 & 短路运算的次数。 第三行输出 | 短路运算的次数。
【样例1输入】 0&(1|0)|(1|1|1&0) 【样例1输出】 1 1 2 【样例2输入】 (0|1&0|1|1|(1|1))&(0&1&(1|0)|0|1|0)&0 【样例2输出】 0 2 3 【数据范围】 对于所有测试数据，保证：表达式的长度不超过 10^6。 表达式中只包含字符 0、1、&、|、(、)。
第4题
中级
100.0分
编程
上升点列（point）
给定 n 个点的坐标 (xi, yi)，以及 m 个可添加的虚拟点。
要求选出一些点（包括给定点和虚拟点），使得这些点构成一个序列，满足：
1. 序列中相邻两点在平面直角坐标系上必须相邻，即它们在 x 轴或 y 轴方向上的距离恰好为 1。
2. 序列中的点必须按 x 坐标和 y 坐标都不减的顺序排列（即上升序列）。
问：最多能选出多少个点构成满足条件的序列？
【输入格式】
从文件 point.in 中读入数据。 输入的第一行包含两个正整数 n, m，分别表示给定点数和可添加虚拟点数。 接下来 n 行，每行包含两个正整数 xi, yi，表示第 i 个点的坐标。
【输出格式】
输出到文件 point.out 中。 输出一行一个整数，表示最长序列的点数。
【样例1输入】 5 2 2 1 3 1 5 4 4 5 5 5 【样例1输出】 5 【样例2输入】 8 3 1 1 1 2 1 3 2 1 2 3 3 1 3 2 3 3 【样例2输出】 8 【数据范围】 对于所有测试数据，保证：1 ≤ n ≤ 500，1 ≤ m ≤ 100，1 ≤ xi, yi ≤ 10^9。