夜雨聆风学习资料网

ARTICLE · 1387333

2022年CSP-J第二轮(入门级)真题及答案

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) 的路径数一数补了几个点。把每题的"坑"亲手踩一遍,考场就再也不怕了。加油,我们明天见!

回首页,搜索你想要的文档

在首页搜索框输入关键词,快速定位资料

文库首页搜索指引 立即搜索

相关学习资料