因为11.11为四根棍，所以注定只能写四题

于 2022.11.20 施工完毕.

---

A题　乘方　CSP 2022 T1

题面

a的b次方与1e9的大小比较

思路1(针对有try-catch的语言)

用大数算法直接算，如果算得出来，那就比较；算不出来，也就是溢出了，那么一定是大于1e9的，利用语言特性，捕获这个异常然后输出-1即可。

AC(Java)代码

import java.math.*;
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        try{
            BigInteger a = new BigInteger(scanner.next());
            int b = scanner.nextInt();
            BigInteger ans = a.pow(b);
            if(ans.compareTo(BigInteger.valueOf(1000000000L)) > 0) System.out.println(-1);
            else System.out.println(ans);
        }catch(Throwable e){
            System.out.println(-1); //投机取巧.jpg
        }
    }
}

思路2

很简单，我们只需要循环b次把a乘上自己，判断一下是否大于1e9即可。

AC(Java)代码

import java.util.*;

public class Main{

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int a = scanner.nextInt(), b = scanner.nextInt();
        long ans = 1L;
        for(int i=0;i<b;i++) {
            ans *= a;
            if(ans > 1000000000L) {
                System.out.println(-1);
                return;
            }
        }
        System.out.println(ans);
    }
}

对思路2的优化

可以使用快速幂降低时间复杂度。

注意

可能会爆long，用大数解。

AC(Java)代码

import java.math.*;
import java.util.*;

public class Main{

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        BigInteger weight = BigInteger.valueOf(scanner.nextLong());
        int b = scanner.nextInt();
        BigInteger ans = BigInteger.ONE;
        while(b > 0){
            if(b % 2 == 1) { //二进制非递归快速幂
                ans = ans.multiply(weight);
                if(ans.compareTo(BigInteger.valueOf(1000000000L)) > 0) {
                    System.out.println(-1);
                    return;
                }
            }
            weight = weight.multiply(weight); //这里在测试点9会爆long
            b >>= 1;
        }
        System.out.println(ans);
    }
}

---

B题　解密　CSP 2022 T2

题面

n = p * q , ed = (p - 1) * (q - 1) + 1，给出 n , d , e ，解方程得 p , q。

思路

1.化简第二个式子得到 p + q = n - e * d + 2，设其为 m.

2.由第一个式子得到 p = n / q.

3.由1和2，n / q + q = m => q ^ 2 - m * q + n = 0.

4.求 delta = m ^ 2 - 4 * n，delta < 0 即为无解的第一种情况.

5.求根公式求 p, q，p 和 q 不为整数为无解的第二种情况，为整数就输出.

注意点

1.肉眼可见会爆int，用长整型.

2.不要用java，会tle.

AC(cpp)代码

#include <bits/stdc++.h>

using namespace std;

int main(){
    int k;
    long long n, d, e;
    scanf("%d", &k);
    for(int w=0;w<k;w++){
        scanf("%lld %lld %lld", &n, &d, &e);
        long long m = n + 2 - e * d;
        long long delta = m * m - 4 * n;
        if(delta < 0) printf("NO\n");
        else {
            double p = (m - sqrt(delta)) / 2, q = (m + sqrt(delta)) / 2;
            if((int) p != p || (int) q != q) printf("NO\n");
            else printf("%d %d\n", (int) p, (int) q);
        }
    }
}

---

C题　报数　NOIP 2021 提高组

题面

1.某数字为 x 的倍数， x 的特点是至少有一位有 7 (与7相关)，则该数字不能被报出。

2.报到与7相关的数，输出 -1 ，否则输出下一个非7相关的数。

思路

做一个类似于埃氏筛的预处理。

如果你知道埃氏筛，那这题应该是打卡题（

1.我们用类似于埃氏筛的思路，筛掉与7相关的数的倍数。

2.开一个数组，记录下一个非7相关的数，否则赋值为自己（或者可以是任意非正数）。

3.读它。

值得注意的是，1e7后面第一个非7相关的数是10000010，所以你可以开 1e7+11 大小的数组，防止溢出。

AC(Java)代码

import java.util.*;

public class Main{

    private static boolean relate(int x){ //是否与7相关
        while(x > 0){
            if(x % 10 == 7) return true;
            x /= 10;
        }
        return false;
    }

    private static int[] preTreat(){
        int[] next = new int[10000011];
        for(int i=1;i<10000011;i++){
            if(next[i] == 0 && relate(i)){ //类似于埃氏筛
                for(int j=1;i*j<10000011;j++) next[i * j] = 1;
            }
        }
        int last = 1;
        for(int i=2;i<10000011;i++){
            if(next[i] == 0){
                next[last] = i;
                last = i;
            } else next[i] = i; //反正只要后面可以特判就行
        }
        return next;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        int[] next = preTreat();
        for(int w=0;w<t;w++){
            int cur = scanner.nextInt();
            System.out.println(next[cur] == cur ? -1 : next[cur]);
        }
    }
}

---

D题　逻辑表达式　CSP 2022 T3

思路1 expr

可以用类似于求中缀表达式的值的思路来做。

1.中缀表达式转后缀表达式

2.建立表达式树

3.计算并统计

这个方法码量有点大，dfs有点深，只能上cpp了（

AC(cpp)代码

#include <bits/stdc++.h>

using namespace std;

struct Node{
    int val, left, right;
};

int ansAnd = 0, ansOr = 0, nodeSize = 0;
vector<Node> nodes;

//expr 中缀转后缀
vector<int> toSuffix(const string& mid) {
    vector<int> ex;
    stack<char> ts;
    map<char, int> pri;
    pri['&'] = 4;
    pri['|'] = 3;
    pri['('] = 2;
    for (char each : mid) {
        if (each == '@') {
            while (!ts.empty()) ex.push_back(pri[ts.top()]), ts.pop();
            break;
        } else if (each >= '0' && each <= '9') ex.push_back(each - '0');
        else {
            if (each == '(') ts.push(each);
            else if (each == ')') {
                while (ts.top() != '(') ex.push_back(pri[ts.top()]), ts.pop();
                ts.pop(); //弹出左括号
            } else {
                while (!ts.empty() && pri[ts.top()] >= pri[each]) ex.push_back(pri[ts.top()]), ts.pop();
                ts.push(each);
            }
        }
    }
    return ex;
}

//建表达式树
void build(const vector<int>& suffix){
    stack<int> index;
    for(int each : suffix){
        if(each == 0 || each == 1){
            nodes.push_back({each, -1, -1});
            index.push(nodeSize ++);
        }else{
            int r = index.top();
            index.pop();
            int l = index.top();
            index.pop();
            nodes.push_back({each, l, r});
            index.push(nodeSize ++);
        }
    }
}

int dfs(int index) {
    if (nodes[index].val == 0 || nodes[index].val == 1) return nodes[index].val;
    int l = dfs(nodes[index].left);
    if (l == 0 && nodes[index].val == 4) {
        ansAnd++;
        return 0;
    }
    if (l == 1 && nodes[index].val == 3) {
        ansOr++;
        return 1;
    }
    return dfs(nodes[index].right); //既然不断路，那么值一定只和右边的值有关
}

int main() {
    string mid;
    cin >> mid;
    mid += "@";
    build(toSuffix(mid));
    printf("%d\n", dfs(nodeSize - 1));
    printf("%d %d\n", ansAnd, ansOr);
}

思路2 DC(分治)

1.对于一个表达式，我们会先去找没有括号的优先级最高的符号，然后计算左右两边的值，这便是中缀表达式的直观求法。

2.由1所述，我们可以将表达式分层，并从优先级最高的那个符号开始左右分治求解，同时特判左边的值即可。

3.显然，我们不可能在每次求左右表达式的时候都遍历一遍字符串找符号，这肯定会tle。于是乎，我们需要一个预处理，将当前位置之前该层最近的符号找出并记录它的下标。这样我们只要每次读取一下记录的下标是否在区间内即可。

同思路1，这里用java写递归依然会栈溢出，这边用cpp呈现

AC(cpp)代码

#include <bits/stdc++.h>

using namespace std;

int nowAnd[1000010], nowOr[1000010], lastAnd[1000010], lastOr[1000010];
string mid;
int ansAnd, ansOr;

int dc(int l, int r) {
    if (nowOr[r] >= l) { //or的优先级更高
        int left = dc(l, nowOr[r] - 1);
        if (left == 1) {
            ansOr++;
            return 1;
        }
        return left | dc(nowOr[r] + 1, r);
    } else if (nowAnd[r] >= l) {
        int left = dc(l, nowAnd[r] - 1);
        if (left == 0) {
            ansAnd++;
            return 0;
        }
        return left & dc(nowAnd[r] + 1, r);
    } else if (mid[l] == '(' && mid[r] == ')') return dc(l + 1, r - 1);
    return mid[l] - '0';
}

int main() {
    cin >> mid;
    int n = mid.size(), layer = 0;
    mid = " " + mid;
    for (int i = 1; i < n + 1; i++) { //预处理
        switch (mid[i]) {
            case '(':
                layer++;
                break;
            case ')':
                layer--;
                break;
            case '|':
                lastOr[layer] = i;
                break;
            case '&':
                lastAnd[layer] = i;
                break;
        }
        nowAnd[i] = lastAnd[layer];
        nowOr[i] = lastOr[layer];
    }
    printf("%d\n", dc(1, n));
    printf("%d %d\n", ansAnd, ansOr);
}

---

E题　音量调节　HAOI 2012

一眼丁真，鉴定为 分组背包

不会做的去看背包九讲

思路

1.题目特点：每个c都要选上，可以+c可以-c，有范围限定。

2.分组：分成c组，每组为c和-c。

3.我们可以用boolean类型的dp数组存储当前音量能否达到，对此，有如下状态转移方程: dp[i][v] = dp[i][v] || dp[i - 1][v ± c]

4.套模板，解毕

AC(Java)代码

import java.util.*;

//快乐分组背包呀
public class Main{
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt(), begin = scanner.nextInt(), V = scanner.nextInt();
        boolean[][] dp = new boolean[N + 1][V + 1];
        dp[0][begin] = true;
        for(int i=1;i<=N;i++){
            int c = scanner.nextInt();
            for(int v = V;v>=0;v--){
                if(v - c >= 0) dp[i][v] |= dp[i - 1][v - c];
                if(v + c <= V) dp[i][v] |= dp[i - 1][v + c];
            }
        }
        for(int v=V;v>=0;v--) if(dp[N][v]){
            System.out.println(v);
            return;
        }
        System.out.println(-1);
    }
}

---

F题　上升点列　CSP 2022 T4

题面

给出 n 个点坐标，可添加 k 个任意坐标，求出最长单调欧几里得距离序列。

思路

这道题如果联想到最长上升子序列就迎刃而解了。

1.用二维dp做，前 i 个点插入 j 个点的最长长度。

2.观察欧几里得距离可发现，若要使i~j序列可取，那么需要加上 d 个点， d = xi - xj + yi - yj + 1 。

3.类似于最长上升子序列，得到状态转移方程 dp[i][p] = max(dp[i][p], dp[j][p - d] + d + 1) p∈[d, k] 。

AC(Java)代码

import java.util.*;

public class Main{

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(), k = scanner.nextInt();
        int[][] data = new int[n + 1][2];
        for(int i=1;i<=n;i++) {
            data[i][0] = scanner.nextInt();
            data[i][1] = scanner.nextInt();
        }
        Arrays.sort(data, 1, n + 1, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0]);
        int[][] dp = new int[n + 1][k + 1];
        for(int i=1;i<=n;i++) for(int j=0;j<=k;j++) dp[i][j] = j + 1; //差了j个那就塞上j个
        for(int i=2;i<=n;i++){
            for(int j=i-1;j>=1;j--){ //i状态由j状态推得
                if(data[j][1] > data[i][1]) continue;
                //因为i状态由j状态推得，所以需要至少d个点才能满足欧几里得距离
                int d = data[i][0] - data[j][0] + data[i][1] - data[j][1] - 1;
                for(int p=d;p<=k;p++) dp[i][p] = Math.max(dp[i][p], dp[j][p - d] + d + 1); //最长上升子序列模板
            }
        }
        int ans = 0;
        for(int i=1;i<=n;i++) ans = Math.max(ans, dp[i][k]);
        System.out.println(ans);
    }
}

---

G题　星球大战　JSOI 2008

一句话题意

断开指定边后图中联通的块数。

思路

1.首先是建立无向图，可以使用邻接表的方式存储。

2.标记这些需要断开的边，然后依次遍历各个边，若端点的根节点一样，那么就处于同一个连通块了。

3.因为至少存在 n 条边，那么连通块最多为 n - k 个。

4.综合2和3可知，答案即为 n - k - cnt ，其中 cnt 为满足2条件的个数。

5.至于要输出每次打击后的值，我们可以逆向思维，将最后的状态还原到最初状态即可。

优化

我们可以使用并查集算法来优化。

没有解释地很清楚哈，还是有点难写的

AC(cpp)代码

#include <bits/stdc++.h>

using namespace std;

typedef struct{
    int a, b; //两点
    int to;
}Edge;

int parent[400010];
Edge edges[400010];
int tot = 0;
int head[400010], broken[400010], ans[400010];
bool visited[400010];

//并查集查询，返回父节点id并将child全设为父节点直属下司(
int findParent(int child) {
    int ground = child, father = child;
    while (father != parent[father]) father = parent[father];
    //更新father
    while (ground != parent[ground]) {
        int tmp = ground;
        ground = parent[ground];
        parent[tmp] = father;
    }
    return father;
}

//联通两个子树的爸爸即可(把一个爸爸设为另一个爸爸的直属下司
void unionIt(int x, int y) {
    parent[findParent(x)] = findParent(y);
}

void addEdge(int a, int b){
    edges[++tot].a = a;
    edges[tot].b = b;
    edges[tot].to = head[a];
    head[a] = tot;
}

int main() {
    int n, m, u, v, k;
    long long w;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) parent[i] = i; //初始化并查集，我是我爸爸
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &u, &v);
        addEdge(u, v);
        addEdge(v, u);
    }
    scanf("%d", &k);
    for(int i=1;i<=k;i++){
        scanf("%d", &broken[i]);
        visited[broken[i]] = true;
    }
    int united = n - k;
    for (int i = 0; i < 2 * m; i++) {
        if (!visited[edges[i].a] && !visited[edges[i].b] && findParent(edges[i].a) != findParent(edges[i].b)) {//爸爸不一样，由union函数的写法可以看出俩玩意儿没联通
            united --;
            unionIt(edges[i].a, edges[i].b);
        }
    }
    ans[k + 1] = united;
    for(int i=k;i>=1;i--){
        int x = broken[i];
        visited[x] = false;
        united ++;
        for (int j = head[x]; j != 0; j = edges[j].to) {
            int nowB = edges[j].b;
            if(!visited[nowB] && findParent(x) != findParent(nowB)){
                united --;
                unionIt(x, nowB);
            }
        }
        ans[i] = united;
    }
    for(int i=1;i<=k+1;i++) printf("%d\n", ans[i]);
}

---

I题　泡泡堂　ZJOI 2008

很明显是贪心

思路：田忌赛马

1.田忌最快的马比齐王最快的马快，比之

2.田忌最快的马比齐王最快的马慢，用田忌最慢的马跟齐王最快的马比

3.田忌最快的马的速度与齐王最快的马速度相等

①田忌最慢的比齐王最慢的快，比之。

②田忌最慢的比齐王最慢的慢，田忌慢马VS齐王快马

③田忌最慢的与齐王最慢的相等，田忌慢马VS齐王快马

不予证明。

方法

维护双指针 head 和 end , 按上述思路写

AC(Java)代码

import java.util.*;

public class Main{

    //md，一个贪心想了我好久
    private static long judge(int n, long[] a, long[] b){
        int score = 0;
        int headA = 0, headB = 0, endA = n - 1, endB = n - 1; //双指针？
        while(headA <= endA && headB <= endB){
            if(a[headA] > b[headB]){
                score += 2;
                headA ++;
                headB ++;
            }else if(a[endA] > b[endB]){
                score += 2;
                endA --;
                endB --;
            } else {
                if(a[headA] == b[endB]) score ++;
                headA ++;
                endB --;
            }
        }
        return score;
    }

    //我就猜一猜
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        long[] zj = new long[n], sb = new long[n];
        for(int i=0;i<n;i++) zj[i] = scanner.nextLong();
        for(int i=0;i<n;i++) sb[i] = scanner.nextLong();
        Arrays.sort(zj);
        Arrays.sort(sb);
        System.out.printf("%d %d\n", judge(n, zj, sb), 2L * n - judge(n, sb, zj)); //有个小技巧（（（
    }
}

Done.

大佬帮纠正，谢谢。