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。
【样例】
10 9

2 30
【样例解释】
1000000000

-1
第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
第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）。
第二行输出 & 短路运算的次数。
第三行输出 | 短路运算的次数。
【样例】
0&(1|0)|(1|1|1&0)

(0|1&0|1|1|(1|1))&(0&1&(1|0)|0|1|0)&0
【样例解释】
1
1
2

0
2
3
第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 中。
输出一行一个整数，表示最长序列的点数。
【样例】
5 2
2 1
3 1
5 4
4 5
5 5

8 3
1 1
1 2
1 3
2 1
2 3
3 1
3 2
3 3
【样例解释】
5

8
💬