ARTICLE · 1387333
2022年CSP-J第二轮(入门级)真题及答案
第一题 乘方(pow)
【题目描述】
小文同学刚刚接触了信息学竞赛,有一天她遇到了这样一个题:给定正整数 a 和 b,求 ab 的值是多少。ab 即 b 个 a 相乘的值,例如 23 即为 3 个 2 相乘,结果为 2×2×2=8。
"简单!"小文心想,同时很快就写出了一份程序,可是测试时却出现了错误。她很快意识到,程序里的变量都是 int 类型的,在大多数机器上 int 能表示的最大数为 231−1,计算结果一旦超过这个数程序就会出错。因此她希望你实现:当 ab 的值超过 109 时,输出一个 -1 进行警示;否则输出正确的 ab 的值。
【输入格式】输入共一行,两个正整数 a, b。
【输出格式】输出共一行:如果 ab 的值不超过 109,输出 ab 的值,否则输出 -1。
【样例输入】
10 9
【样例输出】
1000000000
【样例解释】109 恰好等于上限而没有"超过",所以正常输出 1000000000。这组样例专门卡"判断时误用 ≥"的错误。
【样例输入】
23333 66666
【样例输出】
-1
【数据范围】对于 10% 的数据,保证 b=1;对于 30% 的数据,保证 b≤2;对于 60% 的数据,保证 b≤30 且 ab≤1018;对于 100% 的数据,保证 1≤a,b≤109。
【思路提示】
① 不需要快速幂:用一个变量从 1 开始连乘 b 次 a 即可,但每乘一次就检查一次——一旦 ans 超过 10⁹ 立即输出 -1 并结束,后面的乘法统统不用做。
② 为什么不用怕 b=10⁹?只要 a≥2,每乘一次结果至少翻倍,最多 30 次(log₂10⁹≈30)就必然超过 10⁹ 而提前退出,循环实际跑不满。
③ 唯一跑满的情况是 a=1:1 乘多少次都是 1,永远不超限。必须特判 a=1 直接输出 1,否则 1 10⁹ 这组数据会超时。
④ ans 和 a 都要用 long long:退出前 ans 最大可达 10⁹×10⁹=10¹⁸,int 装不下。另外判断是 >10⁹ 而不是 ≥10⁹,恰好等于时要输出本身。
【参考答案(满分代码)】
#include <iostream>
using namespace std;
int main() {
long long a, b;
cin >> a >> b;
if (a == 1) { // 特判:1 的任何次方都是 1,防止 b=1e9 超时
cout << 1 << endl;
return 0;
}
long long ans = 1;
for (long long i = 0; i < b; i++) {
ans *= a;
if (ans > 1000000000LL) { // 一旦超过 1e9 立即收工
cout << -1 << endl;
return 0;
}
}
cout << ans << endl; // 恰好等于 1e9 也会走到这里,正常输出
return 0;
}
第二题 解密(decode)
【题目描述】
给定一个正整数 k,有 k 次询问。每次给定三个正整数 n, d, e,求两个正整数 p, q,使得:
n = p × q
e × d = (p − 1)(q − 1) + 1
这是 RSA 密码体系的核心关系:n 是两个大质数 p、q 的乘积,e×d ≡ 1(模 (p−1)(q−1))。为使输出统一,你应当保证 p ≤ q。如果无解,请输出 NO。
【输入格式】第一行一个正整数 k,表示有 k 次询问。接下来 k 行,每行三个正整数 n, d, e。
【输出格式】输出 k 行,每行两个正整数 p, q 表示答案(p ≤ q);无解输出 NO。
【样例输入】
10
770 77 5
633 1 211
545 1 499
683 3 227
858 3 257
723 37 13
572 26 11
867 17 17
829 3 263
528 4 109
【样例输出】
2 385
NO
NO
NO
11 78
3 241
2 286
NO
NO
6 88
【样例解释】第一组:n=770, d=77, e=5,取 p=2, q=385:p×q=770 ✓,(p−1)(q−1)+1 = 1×384+1 = 385 = e×d ✓。注意输入顺序是 n, d, e(d 在 e 前面),但因为只用到乘积 e×d,不影响结果。
【数据范围】记 m = n − e×d + 2。对于 100% 的数据:1 ≤ k ≤ 105;1 ≤ n ≤ 1018;1 ≤ e×d ≤ 1018;1 ≤ m ≤ 109。
【思路提示】
① 把第二个等式展开:e×d = (p−1)(q−1)+1 = pq−p−q+2 = n−(p+q)+2,移项得 p+q = n−e×d+2 = m。于是问题变成经典的"已知两数之和 m 与两数之积 n,求这两个数"。
② 已知和与积,p、q 就是一元二次方程 x² − mx + n = 0 的两个根:判别式 Δ = m² − 4n,p = (m−√Δ)/2,q = (m+√Δ)/2。每组询问只需常数次运算,总复杂度 O(k)。
③ 无解的三种情况要逐个排除:Δ < 0(无实根);Δ 不是完全平方数(p、q 不是整数);m−√Δ 是奇数或算出的 p、q 不是正整数。最后再复检一遍 p×q == n 最稳妥(顺带抵御开方精度误差)。
④ 两个大坑:一是 sqrt 的浮点误差——先取近似值再用整数乘法上下修正到精确的整数平方根;二是 n 能到 10¹⁸,m²−4n、e×d 都可能达到 10¹⁸ 量级,全程必须 long long。
【参考答案(满分代码)】
#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
ll isqrt_ll(ll x) { // 整数开方:先估近似值,再上下修正
ll s = (ll)sqrtl((long double)x);
while (s > 0 && s * s > x) s--;
while ((s + 1) * (s + 1) <= x) s++;
return s;
}
int main() {
int k;
cin >> k;
while (k--) {
ll n, d, e;
cin >> n >> d >> e; // 输入顺序:n, d, e
ll m = n - e * d + 2; // 推出 p + q = m
ll delta = m * m - 4 * n; // x^2 - mx + n = 0 的判别式
if (delta < 0) { cout << "NO" << endl; continue; }
ll s = isqrt_ll(delta);
if (s * s != delta || (m - s) % 2 != 0) {
cout << "NO" << endl; continue; // 非完全平方数 / 奇偶不符
}
ll p = (m - s) / 2, q = (m + s) / 2;
if (p > 0 && q > 0 && p * q == n)
cout << p << " " << q << endl; // p<=q 自然成立
else
cout << "NO" << endl;
}
return 0;
}
第三题 逻辑表达式(expr)
【题目描述】
逻辑表达式中元素的值只有 0(假)和 1(真)两种,本题只考虑两种运算:"与"(符号 &):0&0=0&1=1&0=0,1&1=1;"或"(符号 |):0|0=0,0|1=1|0=1|1=1。
运算规则:括号内的部分先运算;两种运算并列时,& 优先于 |;同种运算并列时从左向右。例如 0|1&0 等同于 0|(1&0),0&1&0|1 等同于 ((0&1)&0)|1。
计算时采用 C++ 风格的短路策略:形如 a&b 的表达式先计算 a,若 a=0 则整个表达式已确定为 0,b 无需再算,称这里发生了一次 a&b 型"短路";同理 a|b 中若 a=1 则直接得 1,称发生了一次 a|b 型"短路"。
你需要计算整个表达式的值,并统计两类短路各出现多少次。注意:如果某处短路包含在更外层被短路的部分内则不被统计——如 1|(0&1) 中,外层 1|(...) 本身已短路,内部 0&1 根本不会被计算,不计入。
【输入格式】输入共一行,一个非空字符串 s 表示待计算的逻辑表达式。
【输出格式】第一行输出表达式的值(0 或 1);第二行输出两个非负整数,分别表示 a&b 和 a|b 型短路出现的次数。
【样例输入】
0&(1|0)|(1|1|1&0)
【样例输出】
1
1 2
【样例解释】计算顺序如下(括号标明结合方式):
0&(1|0)|(1|1|1&0)
= (0&(1|0)) | ((1|1)|(1&0))
= 0 | ((1|1)|(1&0)) // 最左侧 0&...:一次 & 短路
= 0 | (1|(1&0)) // 1|...:一次 | 短路
= 0 | 1 // 又一次 | 短路
= 1 // 共 & 短路 1 次、| 短路 2 次
【样例输入】
(0|1&0|1|1|(1|1))&(0&1&(1|0)|0|1|0)&0
【样例输出】
0
2 3
【数据范围】设 |s| 为字符串长度,对于所有数据 1 ≤ |s| ≤ 106。保证 s 仅含字符 0、1、&、|、(、) 且是符合规范的表达式,没有形如 ((a)) 的重复括号嵌套。部分测试点满足特殊性质:没有字符 &、没有字符 |、或没有括号。
【思路提示】
① 这是含括号、双运算符优先级、短路求值三件事叠在一起的模拟题。标准做法:用"运算符栈 + 结点栈"把中缀表达式建成一棵表达式树——遇到数字就建叶子入栈;运算符入栈前先把栈中优先级不低于它的运算符弹出来合并(保证 & 优先于 |、同优先级左结合);右括号负责清空到匹配的左括号。
② 建好树后在树上做短路 DFS:先算左子树;对 & 结点,左值为 0 就计一次 & 短路并直接返回 0(右子树整个不算);对 | 结点,左值为 1 就计一次 | 短路并返回 1。
③ 短路计数的关键:左侧短路时,右侧子树"原本可能发生的短路"必须整体丢弃——因为右子树根本没被求值,它的计数不能加进答案。这正好用"直接 return、不碰右子树"天然实现,千万不要先把两边都算完再合并计数。
④ |s| 可达 10⁶:树结点开数组(按字符位置编号),栈也用数组模拟;表达式树深度的递归实测可以通过,稳妥起见也可把 DFS 改成显式栈的迭代版。
【参考答案(满分代码)】
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1000005;
char str[N];
int nodeOp[N]; // 0: 数字叶子 1: & 2: |
int nodeL[N], nodeR[N];
char nodeV[N]; // 叶子上存的字符
int stkN[N], topN; // 结点栈
int stkO[N], topO; // 运算符栈(存字符)
int cntAnd = 0, cntOr = 0, idx = 0;
int pr(char c) { return c == '&' ? 2 : 1; } // & 优先级高于 |
void build() { // 弹一个运算符,合并栈顶两棵子树
char o = stkO[topO--];
int r = stkN[topN--], l = stkN[topN--];
++idx;
nodeOp[idx] = (o == '&') ? 1 : 2;
nodeL[idx] = l; nodeR[idx] = r;
stkN[++topN] = idx;
}
int dfs(int u) { // 短路求值:左侧短路时右子树不计算、计数不累计
if (nodeOp[u] == 0) return nodeV[u] - '0';
int L = dfs(nodeL[u]);
if (nodeOp[u] == 1) {
if (L == 0) { cntAnd++; return 0; } // & 短路
return dfs(nodeR[u]);
} else {
if (L == 1) { cntOr++; return 1; } // | 短路
return dfs(nodeR[u]);
}
}
int main() {
cin >> (str + 1);
int len = strlen(str + 1);
for (int i = 1; i <= len; i++) {
char c = str[i];
if (c == '0' || c == '1') {
++idx; nodeOp[idx] = 0; nodeV[idx] = c;
stkN[++topN] = idx;
} else if (c == '(') {
stkO[++topO] = c;
} else if (c == ')') {
while (stkO[topO] != '(') build();
topO--; // 弹掉左括号
} else {
while (topO && stkO[topO] != '(' &&
pr(stkO[topO]) >= pr(c)) build(); // 左结合
stkO[++topO] = c;
}
}
while (topO) build(); // 清空剩余运算符,最后建出的就是根
int res = dfs(stkN[1]); // 栈中剩下的唯一结点即整棵树的根
cout << res << endl;
cout << cntAnd << " " << cntOr << endl;
return 0;
}
第四题 上升点列(point)
【题目描述】
在一个二维平面内,给定 n 个整点 (xi, yi),此外你还可以自由添加 k 个整点。
你在自由添加 k 个点后,还需要从这 n+k 个点中选出若干个整点组成一个序列,使得序列中任意相邻两点间的欧几里得距离恰好为 1,而且横坐标、纵坐标值均单调不减,即 xi+1−xi=1, yi+1=yi 或 yi+1−yi=1, xi+1=xi。请给出满足条件的序列的最大长度。
【输入格式】第一行两个正整数 n, k,分别表示给定的整点个数、可自由添加的整点个数。接下来 n 行,每行两个正整数 xi, yi。
【输出格式】输出一个整数,表示满足条件的序列的最大长度。
【样例输入】
8 2
3 1
3 2
3 3
3 6
1 2
2 2
5 5
5 3
【样例输出】
8
【样例解释】取路径 (1,2)→(2,2)→(3,2)→(3,3)→(4,3)→(5,3)→(5,4)→(5,5),共 8 个点。其中 (4,3) 和 (5,4) 是添加的点(恰好用掉 k=2 个),其余 6 个都是给定点,每步距离恰为 1 且坐标单调不减。
【样例输入】
4 100
10 10
15 25
20 20
30 30
【样例输出】
103
【样例解释】从 (10,10) 到 (30,30) 的任何单调路径都恰好走 40 步、含 41 个点。途经 (10,10)、(20,20)、(30,30) 三个给定点((15,25) 与 (20,20) 不可能同时出现在一条单调路径上),途中需补 38 个添加点,剩下 62 个添加点接在 (30,30) 之后,总长 41+62=103。
【数据范围】1 ≤ n ≤ 500;0 ≤ k ≤ 100;给定点坐标 1 ≤ xi, yi ≤ 109,所有给定点互不重合;添加点的坐标不受限制。
【思路提示】
① 相邻两点欧氏距离恰为 1 且坐标单调不减,意味着每一步只能是 (1,0) 或 (0,1)——整条序列是一条"只能向右或向上走单位步"的连续路径。因此两个给定点之间若要都选上,中间必须恰好填 Δx+Δy−1 个添加点(走 Δx+Δy 步、经过 Δx+Δy−1 个中间格点)。
② 把"选哪些给定点"看成子序列问题:按 x 为主、y 为辅排序后,给定点 t 能接在 i 前面当且仅当y_t ≤ y_i(x 已有序),代价 d = Δx+Δy−1。
③ 状态设计 f[i][j]:以第 i 个给定点结尾、共使用 j 个添加点时的最大序列长度。转移:f[i][j] = max(f[i][j], f[t][j−d] + d + 1)(t→i 中间填 d 个添加点,加上 i 本身共多 d+1 个点)。
④ 没用完的添加点全部接在序列末尾即可:基态 f[i][j] = j + 1(只选 i 一个给定点,j 个添加点跟在后面)。答案取所有 f[i][j] 的最大值。复杂度 O(n²k) ≈ 2.5×10⁷,轻松通过。
【参考答案(满分代码)】
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 505;
struct P { int x, y; } a[N];
bool cmp(P i, P j) {
return i.x < j.x || (i.x == j.x && i.y < j.y); // x 为主、y 为辅排序
}
int n, k, ans = 0;
int f[N][N]; // f[i][j]: 以第 i 个给定点结尾、共用了 j 个添加点的最大长度
int main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i].x >> a[i].y;
sort(a + 1, a + n + 1, cmp);
for (int i = 1; i <= n; i++)
for (int j = 0; j <= k; j++)
f[i][j] = j + 1; // 只选 i 一个点,j 个添加点接在末尾
for (int i = 2; i <= n; i++)
for (int t = 1; t < i; t++) {
if (a[t].y > a[i].y) continue; // y 也必须单调不减
int d = a[i].x - a[t].x + a[i].y - a[t].y - 1;
// d = 两给定点之间必须填的添加点数(单位步路径的中间格点)
for (int j = d; j <= k; j++)
f[i][j] = max(f[i][j], f[t][j - d] + d + 1);
}
for (int i = 1; i <= n; i++)
for (int j = 0; j <= k; j++)
ans = max(ans, f[i][j]);
cout << ans << endl;
return 0;
}
全卷考点小结
2022 年 CSP-J 第二轮整体延续"签到题 + 数学 + 模拟 + DP"的结构:
✔ 乘方:考察溢出意识与提前退出的剪枝技巧,a=1 特判是唯一的超时陷阱,边界"恰好等于 10⁹"卡判断符号;✔ 解密:RSA 背景下的代数变形题,核心是把 e×d=(p−1)(q−1)+1 展开成"和与积",再用一元二次方程求根;整数开方的精度修正与 long long 是两大易错点;✔ 逻辑表达式:表达式求值综合题——双栈建树处理优先级与括号,树上短路 DFS 求值,并被短路的子树计数整体丢弃是本题精髓;✔ 上升点列:把几何条件(距离恰 1 + 单调不减)翻译成"两点之间填 Δx+Δy−1 个点",再套排序 + 子序列 DP,属于经典的"带代价的最长上升子序列"变体。
📢 下期预告:2022年CSP-S第二轮(提高级)真题及答案,欢迎持续关注,每天一套真题带答案,稳步冲击 CSP/NOIP!
题目版权归 CCF 所有,本文仅作学习交流之用;答案经多个独立来源交叉核对,若与官方公布不一致,以官方为准。
💪 建议先把四道题独立写一遍再对照代码:乘方动手算一算 a=2 时最多乘几次;解密在草稿纸上把 770 那组从等式推到 (2,385);逻辑表达式对样例 1 一步步标出哪次运算短路;上升点列先画一条从 (1,2) 到 (5,5) 的路径数一数补了几个点。把每题的"坑"亲手踩一遍,考场就再也不怕了。加油,我们明天见!















































































