Overview & Preface

I saw many reviews, saying that this time CSP-J \texttt{CSP-J} The quality of CSP-J's competition questions is not even as good as your valley's mock competition, and whk is really missing too much, so I didn't plan to make up the questions. But the teacher at the school insisted that I make up for it, and said that I would decide the arrangement of the courses in the future. So, make up. So, it's AK.

Overall, I feel that although the quality of the questions in this competition is not very good, it is still in the past. In addition to the poor evaluation of the second question, the one-dimensional quadratic equation, the other questions are still very good. (The first question directly A B A^B Is AB a little over water? )

Subjective difficulty rating (full score 5 5 5. Relative to other topics in PJ) as follows:

topic	Difficulty of thinking	Difficulty handling details	code complexity
A. Power	1	1	1
B. Decryption	1	1	1
C. Logical Expressions	3	4	3
D. Ascendant column	4	2	2

A. Power

Topic link: Luogu P8813 [CSP-J 2022] Power

Use brute force/quick exponentiation a b a^b ab will do. It is worth mentioning that the use of brute force here does not time out. Because the worst-case base is 2 2 2, you only need to multiply 30 30 30 times will exceed 1 0 9 10^9 109. But in actual operation, fast power is tens of milliseconds faster than brute force, so just paste the code of fast power.

#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. Decryption

Topic link: P8814 [CSP-J 2022] Decryption

The meaning of the question is so clear that at a glance it can be seen that it is a math problem.

The derivation process is as follows:
{ n = p × q   ① e × d = ( p − 1 ) ( q − 1 ) + 1   ② \begin{cases} n = p \times q \ \ ①\\ e \times d = (p-1)(q-1) + 1 \ \ ② \end{cases} {n=p×q  ①e×d=(p−1)(q−1)+1  ②​
Simplification ② ② ② formula, get:
e d = p q − p − q + 2   ③ ed = pq - p - q + 2 \ \ ③ ed=pq−p−q+2  ③
Will ① ① ① Substitute ③ ③ ③ In, get:
e d = n − p − q + 2 ed = n - p - q + 2 ed=n−p−q+2
After deformation:
p + q = n − e d + 2 p + q = n - ed + 2 p+q=n−ed+2
According to the letters in the title "Data Range", we will n − e d + 2 n - ed + 2 n−ed+2 is replaced by m m m, that is
p + q = m   ④ p + q = m \ \ ④ p+q=m  ④
substitute ① ① ①:
p ( m − p ) = n p(m-p) = n p(m−p)=n
Expand and organize as About p p The quadratic equation in one variable for p:
p 2 − m p + n = 0 p^2 - mp + n = 0 p2−mp+n=0
This equation has a solution if and only if Δ \Delta Δ is the perfect square number. which is:
Δ = b 2 − 4 a c = m 2 − 4 n \Delta = b^2 - 4ac = m^2 - 4n Δ=b2−4ac=m2−4n
So the solution of the original equation is:
p = m ± m 2 − 4 n 2 p = \frac{m\pm \sqrt{m^2 - 4n}}{2} p=2m±m2−4n ​​
because p , q p,q p,q must be integers, so when m ± m 2 − 4 n m\pm \sqrt{m^2 - 4n} m±m2−4n ​ should also output NO when it is an odd number.

have to be aware of is n n The range of values ​​for n is n ≤ 1 0 18 n\leq 10^{18} n≤1018, pay attention to open long long.

#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. Logical Expressions

Topic link: Luogu P8815 [CSP-J 2022] Logical Expressions

As for this question, it is not easy to say that it is simple, and it is not difficult to say that it is difficult. The idea is very easy to think, but it is difficult to realize.

The idea of ​​this question is very simple, [ 1 , n ] [1,n] The value of [1,n] is [ 1 , p − 1 ] [1,p-1] The value of [1,p−1] is the same as [ p + 1 , n ] [p+1,n] The result of the operation on the values ​​of [p+1,n], where p p p is [ 1 , n ] [1,n] [1,n] The subscript of the first logical operator outside the parentheses. It is not difficult to find that this is a recursive process, so you can directly simulate the above operation.

According to this idea, it is not difficult for us to design recursive parameters: s o l v e ( l , r , c ) solve(l,r,c) solve(l,r,c) represents the current recursion to be calculated [ l , r ] [l,r] The value of [l,r] and the operator c c c as the dividing point for this round of recursion.

The question now is what should be done at each level of recursion. Since "or" has lower priority than "and", we should find first [ l , r ] [l,r] The position of the first OR operator in [l,r] (for convenience, it will be used below p c p_c pc​ instead), so that [ l , r ] [l,r] [l,r] can be split into [ l , p c − 1 ] [l,p_c-1] [l,pc​−1] and [ p c + 1 , r ] [p_c+1,r] [pc​+1,r] These two parts. Since you are looking for the position of the OR operator, from [ l , p c − 1 ] [l,p_c-1] The operators outside the brackets in [l,pc​−1] must all be AND. Calculate [ l , p c − 1 ] [l,p_c-1] [l,pc​−1] (i.e. s o l v e ( l , p c − 1 , ′ & ′ ) solve(l,p_c-1,'\&') solve(l,pc​−1,′&′) ).

This description is really too abstract, plus my ability to express is limited, I may not be able to fix some of my classmates who could do it originally. So I drew a few pictures, it might be a little clearer. At the same time, in the process of simulating the sample, we can also find some details not mentioned above.

This picture has it all.

One more thing to add here. Since each time we want to skip the content inside the parentheses, we need to know who each parenthesis is paired with. If you traverse the string to find the parentheses every time, the time complexity is O ( N ) \mathcal{O}(N) O(N), a proper timeout. So we can first preprocess the subscript of the closing parenthesis paired with each opening parenthesis, and then use O ( 1 ) \mathcal{O}(1) O(1) time complexity to find the subscript.

#include <iostream>
#include <cstring>
const int N = 1e6 + 9;
char a[N];
int n, cntAnd, cntOr, nxt[N];
int tp, stk[N];
// nxt[i] indicates that the subscript of the right parenthesis matched by the left parenthesis at position i is a few
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. Ascendant column

Topic link: P8816 [CSP-J 2022] Rising Point Column

Obviously a DP question. At first I thought of DP every coordinate, but that definitely won't work ( 1 0 9 10^9 109), so I thought about cheating to score DP first. Then after writing to the loop, I found that I repeated a lot of repeated operations. Just need to DP every point. I took another look at the data range of points, which is pitifully small. So the correct solution came up.

n , k n,k The data range of n,k gives us a very important hint that we can rely on these two values ​​when designing the DP state. Combined with copying the original question Dafa, it is easy to design the DP state:
f i , j Indicates with the i end with a dot and add j The maximum length of a sequence that can be formed by points f_{i,j}\ represents the maximum length of a sequence that ends with the \i\ point and adds \j\ points fi,j​ indicates the maximum length of the sequence that can be formed by adding j points at the end of the i-th point
Then according to this state, design a state transition equation:
f i , l + d i s ( i , j ) − 1 = m a x { f j , l + d i s ( i , j ) } f_{i, l+dis(i,j)-1} = max\{f_{j,l}+dis(i,j)\} fi,l+dis(i,j)−1​=max{fj,l​+dis(i,j)}
in, l l l means the first j j added before j dots l l l points

Don't ask me how this equation came about, just ask click here

#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] represents the maximum length of the sequence that can be formed by adding j points at the end of the i-th point
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++) { // to the ith point
        dp[i][0] = 1;
        for (int j = 1; j < i; j++) // After the j th point
            if (a[j].y <= a[i].y)
                for (int l = 0; l+dis(i,j)-1 <= k; l++) { // l points are added before the j th point
                    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;
}