WillHou's Blog
0%

【题解】CSP-J 2022 题解

发表于 分类于 Valine：
CSP-J 2022 题解

概述 & 前言

看到许多评价，说这次 \(\texttt{CSP-J}\) 的比赛题目质量甚至不如你谷的模拟赛，再加上 whk 实在落下太多了，所以就没打算补题。但是学校的老师非让我补不可，说要决定一下以后课程的安排。于是，就补了。于是，就 AK 了。

总体来讲，我感觉这次比赛的题目质量虽然不算很好，但也说的过去。除了第二题裸的一元二次方程差评外，其它的题目出的还是挺好的。（第一题直接 \(A^B\) 是不是有点过水？）

主观的难度评价（满分 \(5\)，相对与 PJ 其它题目来说）如下：

题目 思维难度 细节处理难度 代码复杂度
A. 乘方 1 1 1
B. 解密 1 1 1
C. 逻辑表达式 3 4 3
D. 上升点列 4 2 2

A. 乘方

题目链接：洛谷 P8813 [CSP-J 2022] 乘方

使用 暴力/快速幂 求 \(a^b\) 即可。值得一提的是，这里使用暴力并不会超时。因为最坏情况底数为 \(2\) 的话，也只需要乘 \(30\) 次就会超过 \(10^9\)。但是实际运行下来，快速幂比暴力要快个几十毫秒，所以就贴快速幂的代码好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using LL = long long;
const LL MOD = 1e9;
LL n, m;
LL qpow(LL a, LL b) {
    LL ans = 1;
    for (; b; b >>= 1) {
        if (a > MOD) return -1;
        if (b & 1) {
            if (ans*a > MOD)
                return -1;
            ans = ans * a;
        }
        a *= a;
    }
    return ans;
}
int main() {
    scanf("%lld%lld", &n, &m);
    printf("%lld", qpow(n, m));
    return 0;
}

B. 解密

题目链接：P8814 [CSP-J 2022] 解密

题意太清晰了，一眼就能看出是一道数学题。

推导过程如下： \[ \begin{cases} n = p \times q \ \ ①\\ e \times d = (p-1)(q-1) + 1 \ \ ② \end{cases} \] 化简 \(②\) 式，得： \[ ed = pq - p - q + 2 \ \ ③ \] 将 \(①\) 代入 \(③\) 中，得： \[ ed = n - p - q + 2 \] 变形后得： \[ p + q = n - ed + 2 \] 按照题目「数据范围」中的字母，我们将 \(n - ed + 2\) 替换为 \(m\)，即 \[ p + q = m \ \ ④ \] 代入 \(①\)： \[ p(m-p) = n \] 展开并整理为关于 \(p\) 的一元二次方程： \[ p^2 - mp + n = 0 \] 这个方程有解，当且仅当 \(\Delta\) 为完全平方数。即： \[ \Delta = b^2 - 4ac = m^2 - 4n \] 所以原方程的解为： \[ p = \frac{m\pm \sqrt{m^2 - 4n}}{2} \] 由于 \(p,q\) 必须要是整数，所以当 \(m\pm \sqrt{m^2 - 4n}\) 为奇数时也应该输出 NO。

需要注意的是 \(n\) 的取值范围是 \(n\leq 10^{18}\)，注意开 long long。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <cmath>
using LL = long long;
int T;
LL n, d, e;
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%lld%lld%lld", &n, &d, &e);
        LL m = n + 2 - e*d;
        LL delta = m*m - 4*n;
        if (delta < 0) {
            puts("NO");
            continue;
        }
        LL x = sqrt(delta);
        if ((double)x!=sqrt(delta) or ((m-x)&1)) {
            puts("NO");
            continue;
        }
        printf("%lld %lld\n", (m-x)/2, (m+x)/2);
    }
    return 0;
}

C. 逻辑表达式

题目链接：洛谷 P8815 [CSP-J 2022] 逻辑表达式

这道题呢，说简单也不简单，说难呢也没啥难的，思路十分好想，但是实现起来有一定难度。

本题的思路很简单，\([1,n]\) 的值，就是 \([1,p-1]\) 的值与 \([p+1,n]\) 的值运算后的结果，其中 \(p\) 为 \([1,n]\) 括号外第一个逻辑运算符的下标。不难发现这就是一个递归的过程，所以直接模拟上述操作即可。

根据这个思路，我们不难设计出递归的参数：\(solve(l,r,c)\) 代表当前递归要计算 \([l,r]\) 的值，并且以操作符 \(c\) 作为这一轮递归的分界点。

现在的问题是每一层递归中应该干什么事情。由于「或」的优先级比「与」低，所以我们应该先找到 \([l,r]\) 中第一个或运算符的位置（为表示方便，下文将其用 \(p_c\) 代替），这样 \([l,r]\) 就可以被分割为 \([l,p_c-1]\) 与 \([p_c+1,r]\) 这两个部分。由于找的是或运算符的位置，所以从 \([l,p_c-1]\) 中括号外的运算符一定全部为「与」。计算出 \([l,p_c-1]\) 的值（即 \(solve(l,p_c-1,'\&')\) ）即可。

这样描述实在是太抽象了，再加上我表达能力有限，可能一些原本会做的同学都被我整不会了。所以我画了几张图，可能会更清晰一点。同时，在模拟样例的过程中，我们还可以发现一些前面没有提到的细节。

这张图已经说明了一切。

这里再补充一点。由于每次我们要跳过括号内的内容，所以我们要知道每一个括号与谁配对。如果每次都遍历字符串来找括号的话，那时间复杂度为 \(\mathcal{O}(N)\)，妥妥的超时。所以我们可以先预处理出与每个左括号配对的右括号的下标，然后用 \(\mathcal{O}(1)\) 的时间复杂度找到下标。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <cstring>
const int N = 1e6 + 9;
char a[N];
int n, cntAnd, cntOr, nxt[N];
int tp, stk[N];
// nxt[i] 表示第 i 个位置的左括号匹配的右括号所在的下标是几
int find(int pos, int r, char c) {
    while (a[pos]!=c and pos<=r)
        if (a[pos] == '(') {
            pos = nxt[pos] + 1;
        } else {
            pos++;
        }
    return pos;
}
int solve(int l, int r, char tgt = '|') {
    while (nxt[l] == r) l++, r--, tgt = '|';
    if (l == r) return a[l] == '1';
    int p = find(l, r, tgt);
    int res = solve(l, p-1, '&');
    for (int t; p < r; p = t) {
        t = find(p+1, r, tgt);
        if (a[p]=='&' and res==0) {
            cntAnd++;
        } else if (a[p]=='|' and res) {
            cntOr++;
        } else {
            res = solve(p+1, t-1);
        }
    }
    return res;
}
int main() {
    scanf("%s", a + 1);
    n = strlen(a+1);
    for (int i = 1; i <= n; i++)
        if (a[i] == '(') stk[++tp] = i;
        else if (a[i] == ')') nxt[stk[tp--]] = i;
    printf("%d\n", solve(1, n));
    printf("%d %d\n", cntAnd, cntOr);
    return 0;
}

D. 上升点列

题目链接：P8816 [CSP-J 2022] 上升点列

很显然是一道 DP 题。一开始我想到的是 DP 每个坐标，但是这样肯定不行(\(10^9\))，于是就想着先打骗分 DP。然后写到循环后发现我重复做了非常多重复的操作。只需要 DP 每个点就可以了。再看了一眼点数的数据范围，小的可怜。于是正解就这么想出来了。

\(n,k\) 的数据范围给我们了一个非常重要的提示，就是设计 DP 状态的时候可以依赖于这两个值。结合抄原题大法，很容易设计出 DP 状态： \[ f_{i,j}\ 表示以第\ i\ 个点结尾并且加\ j\ 个点能构成的序列的最大长度 \] 然后就根据这个状态，设计一个状态转移方程： \[ f_{i, l+dis(i,j)-1} = max\{f_{j,l}+dis(i,j)\} \] 其中，\(l\) 表示第 \(j\) 个点前加了 \(l\) 个点

不要问我这个方程是怎么推出来的，问就是点这里

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <algorithm>
const int N = 509, K = 109;
struct Node {
    int x, y;
} a[N];
int n, k, ans, dp[N][K];
// f[i][j] 表示以第 i 个点结尾并且加 j 个点能构成的序列的最大长度
int dis(int p1, int p2) { return abs(a[p1].x-a[p2].x)+abs(a[p1].y-a[p2].y); }
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &a[i].x, &a[i].y);
    std::sort(a + 1, a + n + 1, [](const Node A, const Node B) {
        return A.x==B.x ? A.y<B.y : A.x<B.x;
    });
    for (int i = 1; i <= n; i++) { // 到第 i 个点
        dp[i][0] = 1;
        for (int j = 1; j < i; j++) // 接到第 j 个点后面
            if (a[j].y <= a[i].y)
                for (int l = 0; l+dis(i,j)-1 <= k; l++) { // 第 j 个点前加了 l 个点
                    int t = l + dis(i, j) - 1;
                    dp[i][t] = std::max(dp[i][t], dp[j][l] + dis(i, j));
                }
    }
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= k; j++)
            ans = std::max(ans, dp[i][j]+k-j);
    printf("%d", ans);
    return 0;
}