很楠不爱3

这个屌丝很懒，什么也没留下！

热门标签

第十四届蓝桥杯大赛软件赛省赛（Java 大学C组）_蓝桥杯真题java,c组

作者：很楠不爱3 | 2024-02-10 01:14:13

踩

蓝桥杯真题java,c组

蓝桥杯 2023年省赛真题
^{Java 大学C组}

试题 A: 求和
试题 B: 分糖果
试题 C: 三国游
试题 D: 平均
试题 E: 填充
试题 F: 棋盘
试题 G: 子矩阵
试题 H: 公因数匹配
试题 I: 异或和之差
试题 J: 太阳

开胃小菜。

试题 A: 求和

本题总分： $5$ 分

【问题描述】

求 $1$ （含）至 $20230408$ （含）中每个数的和。

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

204634714038436

自然数列求和， $1+2+\cdots+n=\cfrac {n(n+1)}2$ 。

public class Main {

    public static void main(String ...args) { new Main().run(); }

    void run() {
        System.out.println(
                20230408 * (20230408 + 1l) / 2
        );
    }
}
1
2
3
4
5
6
7
8
9
10

或者迭代答案。

public class Main {

    public static void main(String ...args) { new Main().run(); }

    void run() {
        long ans = 0;
        for (int i = 1; i <= 20230408; ++i)
            ans += i;
        System.out.println(ans);
    }
}
1
2
3
4
5
6
7
8
9
10
11

试题 B: 分糖果

本题总分： $5$ 分

【问题描述】

两种糖果分别有 $9$ 个和 $16$ 个，要全部分给 $7$ 个小朋友，每个小朋友得到的糖果总数最少为 $2$ 个最多为 $5$ 个，问有多少种不同的分法。
只要有其中一个小朋友在两种方案中分到的糖果不完全相同，这两种方案就算作不同的方案。

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

5067671

观察到两种糖果组成二至五个的方案为 $3 + 4 + 5 + 6 = 18$ 种，以该方案为蓝本枚举 $7$ 个小朋友构成的总分配方案一共有 $18^7$ 种，时间复杂度显然不理想，于是考虑枝剪。
一个可以观察到的上界是 $C_{15}^6C_{22}^6\approx 3.7e8$ ，因为一个自然数 $n$ 被拆分成 $k$ 个非负整数根据插板法共有 $C_{n +k - 1}^{k-1}$ 种方案。

public class Main {

    public static void main(String ...args) { new Main().run(); }

    int n = 7, c1 = 9, c2 = 16, l = 2, r = 5;

    long ans = 0;

    void dfs(int depth) {
        if (depth == n) {
            if (c1 == 0 && c2 == 0) ++ans;
        } else {
            for (int i = l; i <= r; ++i)
                for (int k = 0, g = i; k <= i; ++k, --g) {
                    if (c1 < k || c2 < g) continue;
                    c1 -= k;
                    c2 -= g;
                    dfs(depth + 1);
                    c1 += k;
                    c2 += g;
                }
        }
    }

    void run() {
        dfs(0);
        System.out.println(ans);
    }
}
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

试题 C: 三国游

时间限制: $3.0\mathrm s$ 内存限制: $512.0\mathrm{MB}$ 本题总分： $10$ 分

【问题描述】

小蓝正在玩一款游戏。游戏中魏蜀吴三个国家各自拥有一定数量的士兵 $X, Y, Z$ (一开始可以认为都为 $0$ )。游戏有 $n$ 个可能会发生的事件，每个事件之间相互独立且最多只会发生一次，当第 $i$ 个事件发生时会分别让 $X, Y, Z$ 增加 $A_i, B_i,C_i$ 。
当游戏结束时 (所有事件的发生与否已经确定)，如果 $X, Y, Z$ 的其中一个大于另外两个之和，我们认为其获胜。例如，当 $X > Y + Z$ 时，我们认为魏国获胜。小蓝想知道游戏结束时如果有其中一个国家获胜，最多发生了多少个事件?
如果不存在任何能让某国获胜的情况，请输出 $- 1$ 。

【输入格式】

输入的第一行包含一个整数 $n$ 。
第二行包含 $n$ 个整数表示 $A_i$ ，相邻整数之间使用一个空格分隔。
第三行包含 $n$ 个整数表示 $B_i$ ，相邻整数之间使用一个空格分隔。
第四行包含 $n$ 个整数表示 $C_i$ ，相邻整数之间使用一个空格分隔。

【输出格式】

输出一行包含一个整数表示答案。

【样例输入】

【样例输出】

2
1

【样例说明】

发生两个事件时，有两种不同的情况会出现获胜方。
发生 $1, 2$ 事件时蜀国获胜。
发生 $1, 3$ 事件时吴国获胜。

【评测用例规模与约定】

对于 $40\%$ 的评测用例， $n \leq 500$ ；
对于 $70\%$ 的评测用例， $n \leq 5000$ ；
对于所有评测用例， $1 ≤ n ≤ 10^5，1 ≤ A_i, B_i,C_i ≤ 10^9$ 。

贪心

同时考虑三个国家是相当困难的，于是考虑分别求出魏蜀吴分别获胜的话最大事件数，最优答案就是这若干个数中的最大值。
以魏举例，记第 $i$ 个事件对魏获胜的贡献为 $x_i -y_i -z_i$ ，按贡献降序重排事件，找到一个 $k$ ，满足 $\sum_{i=1}^kx_i >\sum_{i=1}^k(y_i + z_i)$ 且 $k$ 尽可能大，若 $k < n$ ，易知 $\sum_{i=1}^{k+1}x_i \leq\sum_{i=1}^{k+1}(y_i + z_i)$ 且 $[1, k]$ 间的或 $(k, n]$ 间的事件交换不会对和式值造成影响， $[1, k]$ 间与 $(k, n]$ 间的元素交换会使 $\sum_{i=1}^{k+1}(x_i-y_i - z_i)$ 变小，不等式无法成立，从而 k 对魏来说最优。

import java.io.IOException;
import java.io.BufferedReader;
import java.io.StreamTokenizer;
import java.io.InputStreamReader;
import java.util.function.Function;
import java.util.Comparator;
import java.util.Arrays;

public class Main {

    public static void main(String ...args) { new Main().run(); }

    class Tuple {

        int x, y, z;
    }

    Tuple[] events;

    int greedy(Comparator<Tuple> comp, Function<long[], Boolean> func) {
        Arrays.sort(events, comp);
        long[] sum = new long[3];
        int res = -2;
        for (int i = 0; i < events.length; ++i) {
            sum[0] += events[i].x;
            sum[1] += events[i].y;
            sum[2] += events[i].z;
            if (func.apply(sum)) res = i;
        }
        return res + 1;
    }

    int max(int arg1, int arg2, int arg3) { return Math.max(arg1, Math.max(arg2, arg3)); }

    void run() {
        int n = nextInt();
        events = new Tuple[n];
        for (int i = 0; i < n; ++i) events[i] = new Tuple();
        for (int i = 0; i < n; ++i) events[i].x = nextInt();
        for (int i = 0; i < n; ++i) events[i].y = nextInt();
        for (int i = 0; i < n; ++i) events[i].z = nextInt();
        System.out.println(
                max(
                        greedy((a, b) -> Integer.compare(b.x - b.y - b.z, a.x - a.y - a.z), s->s[0] > s[1] + s[2]),
                        greedy((a, b) -> Integer.compare(b.y - b.x - b.z, a.y - a.x - a.z), s->s[1] > s[0] + s[2]),
                        greedy((a, b) -> Integer.compare(b.z - b.x - b.y, a.z - a.x - a.y), s->s[2] > s[0] + s[1])
                )
        );
    }

    StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    int nextInt() {
        try {
            in.nextToken();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return (int) in.nval;
    }
}
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

试题 D: 平均

时间限制: $3.0\mathrm s$ 内存限制: $512.0\mathrm{MB}$ 本题总分： $10$ 分

【问题描述】

有一个长度为 $n$ 的数组（ $n$ 是 $10$ 的倍数），每个数 $a_i$ 都是区间 $[0, 9]$ 中的整数。小明发现数组里每种数出现的次数不太平均，而更改第 $i$ 个数的代价为 $b_i$ ，他想更改若干个数的值使得这 $10$ 种数出现的次数相等（都等于 $\frac n{10}$ ），请问代价和最少为多少。

【输入格式】

输入的第一行包含一个正整数 $n$ 。
接下来 $n$ 行，第 $i$ 行包含两个整数 $a_i, b_i$ ，用一个空格分隔。

【输出格式】

输出一行包含一个正整数表示答案。

【样例输入】

【样例输出】

27
1

【样例说明】

只更改第 $1, 2, 4, 5, 7, 8$ 个数，需要花费代价 $1 + 2 + 4 + 5 + 7 + 8 = 27$ 。

【评测用例规模与约定】

对于 $20\%$ 的评测用例， $n \leq 1000$ ；
对于所有评测用例， $n ≤ 100000, 0 < b_i ≤ 2 × 10^5$ 。

贪心

头一次见蓝桥贪心连着出的。
若 $[0, 9]$ 间的整数 $k$ 在原数组中出现的次数小于等于 $\frac n{10}$ ，则最优解中一定不存在由 $k$ 变为某个数字 $g$ 的花费 $k g$ ，因为要是答案合法，则一定存在由 $x$ 到 $k$ 的花费 $x k$ ，若直接使 $x$ 变为 $g$ 则总花费可以减 $k g$ ，由此我们可以归纳出最优解一定是 $[0, 9]$ 间的出现次数大于 $\frac n{10}$ 的整数每个整数变化超出的个数，而这种变化方式的最优解则是每种数字取 $b$ 最小。

import java.io.StreamTokenizer;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;
import java.util.Arrays;

public class Main {

    public static void main(String ...args) { new Main().run(); }

    class Pair {

        int a, b;

        Pair(int a, int b) {
            this.a = a;
            this.b = b;
        }
    }

    int[] cnt = new int[10];

    void run() {
        int n = nextInt(), m = n / 10;
        long ans = 0;
        Pair[] abs = new Pair[n];
        for (int i = 0; i < n; ++i)
            abs[i] = new Pair(nextInt(), nextInt());
        Arrays.sort(abs, (a, b) -> Integer.compare(b.b, a.b));
        for (int i = 0; i < n; ++i)
            if (++cnt[abs[i].a] > m) ans += abs[i].b;
        System.out.println(ans);
    }

    StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    int nextInt() {
        try {
            in.nextToken();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return (int) in.nval;
    }
}
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
44
45

试题 E: 填充

时间限制: $3.0\mathrm s$ 内存限制: $512.0\mathrm{MB}$ 本题总分： $15$ 分

【问题描述】

有一个长度为 $n$ 的 $01$ 串，其中有一些位置标记为 $?$ ，这些位置上可以任意填充 $0$ 或者 $1$ ，请问如何填充这些位置使得这个 $01$ 串中出现互不重叠的 $00$ 和 $11$ 子串最多，输出子串个数。

【输入格式】

输入一行包含一个字符串。

【输出格式】

输出一行包含一个整数表示答案。

【样例输入】

1110?0
1

【样例输出】

2
1

【样例说明】

如果在问号处填 $0$ ，则最多出现一个 $00$ 和一个 $11 ： 111000$ 。

【评测用例规模与约定】

对于所有评测用例， $1 \leq n \leq 1000000$ 。

贪心

？怎么还是贪心
如果以01相接的地方为断点，将01串拆分开来，如1110?0拆分成111、0?0，则显然第二段中的问号应填0，于是只需考虑若干问号存在01之间的情况，如果若干问号的左侧段长为奇数，则考虑将一个问号变为左侧段对应的值，使总答案加一，然后将所有问号变为右侧段对应的值，若剩余问号为奇数则这个数字除二向下取整是雷打不动的，而多余的一个变为左侧对答案无贡献，所以直接变右，这么模拟着递推过来就行。
实现时连续的问号同时当做0、1来看待，然后找到子串后清空累计即可。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {

    public static void main(String ...args) { new Main().run(); }

    void run() {
        try (BufferedReader in = new BufferedReader(new InputStreamReader(System.in))) {
            String s = in.readLine();
            int ans = 0, cnt0 = 0, cnt1 = 0;
            for (int i = 0; i < s.length(); ++i) {
                switch (s.charAt(i)) {
                    case '0':
                        ++cnt0;
                        cnt1 = 0;
                        break;
                    case '1':
                        ++cnt1;
                        cnt0 = 0;
                        break;
                    default:
                        if (cnt0 > 0) ++cnt0;
                        else if (cnt1 > 0) ++cnt1;
                        else {
                            ++cnt0;
                            ++cnt1;
                        }
                }
                if (cnt0 == 2 || cnt1 == 2) {
                    cnt0 = cnt1 = 0;
                    ++ans;
                }
            }
            System.out.println(ans);
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}
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

试题 F: 棋盘

时间限制: $3.0\mathrm s$ 内存限制: $512.0\mathrm{MB}$ 本题总分： $15$ 分

【问题描述】

小蓝拥有 $n \times n$ 大小的棋盘，一开始棋盘上全都是白子。小蓝进行了 $m$ 次操作，每次操作会将棋盘上某个范围内的所有棋子的颜色取反 (也就是白色棋子变为黑色，黑色棋子变为白色)。请输出所有操作做完后棋盘上每个棋子的颜色。

【输入格式】

输入的第一行包含两个整数 $n, m$ ，用一个空格分隔，表示棋盘大小与操作数。
接下来 $m$ 行每行包含四个整数 $x_1, y_1, x_2, y_2$ ，相邻整数之间使用一个空格分隔，表示将在 $x_1$ 至 $x_2$ 行和 $y_1$ 至 $y_2$ 列中的棋子颜色取反。

【输出格式】

输出 $n$ 行，每行 $n$ 个 $0$ 或 $1$ 表示该位置棋子的颜色。如果是白色则输出 $0$ ，否则输出 $1$ 。

【样例输入】

【样例输出】

【评测用例规模与约定】

对于 $30\%$ 的评测用例， $nm \leq 500$ ；
对于所有评测用例， $1 ≤ n, m ≤ 2000，1 ≤ x_1 ≤ x_2 ≤ n，1 ≤ y_1 ≤ y_2 ≤ m$ 。

二维差分，捞的不谈。

import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;

public class Main {

    public static void main(String ...args) { new Main().run(); }

    boolean[][] board = new boolean[2002][2002];

    void run() {
        PrintWriter out = new PrintWriter(System.out);
        int n = nextInt(), m = nextInt();
        for (int i = 0; i < m; ++i) {
            int x = nextInt(), y = nextInt();
            int k = nextInt(), g = nextInt();
            board[x][y] = !board[x][y];
            board[x][g + 1] = !board[x][g + 1];
            board[k + 1][y] = !board[k + 1][y];
            board[k + 1][g + 1] = !board[k + 1][g + 1];
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                board[i][j] = (board[i][j] ^ board[i - 1][j] ^ board[i][j - 1]) ^ board[i - 1][j - 1];
                out.write(board[i][j] ? '1' : '0');
            }
            out.write('\n');
        }
        out.flush();
    }

    StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    int nextInt() {
        try {
            in.nextToken();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return (int) in.nval;
    }
}
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
44

试题 G: 子矩阵

时间限制: $5.0\mathrm s$ 内存限制: $512.0\mathrm{MB}$ 本题总分： $20$ 分

【问题描述】

给定一个 $n \times m$ （ $n$ 行 $m$ 列）的矩阵。
设一个矩阵的价值为其所有数中的最大值和最小值的乘积。求给定矩阵的所有大小为 $a \times b$ （ $a$ 行 $b$ 列）的子矩阵的价值的和。
答案可能很大，你只需要输出答案对 $998244353$ 取模后的结果。

【输入格式】

输入的第一行包含四个整数分别表示 $n, m, a, b$ ，相邻整数之间使用一个空格分隔。
接下来 $n$ 行每行包含 $m$ 个整数，相邻整数之间使用一个空格分隔，表示矩阵中的每个数 $A_{i, j}$ 。

【输出格式】

输出一行包含一个整数表示答案。

【样例输入】

【样例输出】

58
1

【样例说明】

$1 \times 2 + 2 \times 3 + 4 \times 5 + 5 \times 6 = 58$ 。

【评测用例规模与约定】

对于 $40\%$ 的评测用例， $1 \leq n, m \leq 100$ ；
对于 $70\%$ 的评测用例， $1 \leq n, m \leq 500$ ；
对于所有评测用例， $1 ≤ a ≤ n ≤ 1000\ 1 ≤ b ≤ m ≤ 1000\ 1 ≤ A_{i, j} ≤ 10^9$ 。

通过单调队列，先将矩阵(i-a+1,j)(i,j)的最值求出，然后如法炮制求出(i-a+1,j-b+1)(i,j-b+1)、(i-a+1,j-b+2)(i,j-b+2)、…、(i-a+1,j)(i,j)的最值，即(i-a+1,j-b+1)(i,j)的最值。
单调队列求最值懒得讲了，关键字：单调队列、滑动窗口、区间最值，自己搜着看吧。

import java.io.StreamTokenizer;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;
import java.util.ArrayDeque;
import java.util.Deque;

public class Main {

    public static void main(String ...args) { new Main().run(); }

    int[][] matrix = new int[1001][1001], max = new int[1001][1001], min = new int[1001][1001];

    void run() {
        int n = nextInt(), m = nextInt();
        int a = nextInt(), b = nextInt();
        long ans = 0;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j)
                matrix[i][j] = nextInt();
        Deque<Integer> maxq = new ArrayDeque();
        Deque<Integer> minq = new ArrayDeque();
        for (int j = 1; j <= m; ++j) {
            maxq.clear();
            minq.clear();
            for (int i = 1; i <= n; ++i) {
                while (!maxq.isEmpty() && maxq.peekFirst() <= i - a) maxq.pollFirst();
                while (!minq.isEmpty() && minq.peekFirst() <= i - a) minq.pollFirst();
                while (!maxq.isEmpty() && matrix[i][j] >= matrix[maxq.peekLast()][j]) maxq.pollLast();
                while (!minq.isEmpty() && matrix[i][j] <= matrix[minq.peekLast()][j]) minq.pollLast();
                maxq.offerLast(i);
                minq.offerLast(i);
                max[i][j] = matrix[maxq.peekFirst()][j];
                min[i][j] = matrix[minq.peekFirst()][j];
            }
        }
        for (int i = 1; i <= n; ++i) {
            maxq.clear();
            minq.clear();
            for (int j = 1; j <= m; ++j) {
                while (!maxq.isEmpty() && maxq.peekFirst() <= j - b) maxq.pollFirst();
                while (!minq.isEmpty() && minq.peekFirst() <= j - b) minq.pollFirst();
                while (!maxq.isEmpty() && max[i][j] >= max[i][maxq.peekLast()]) maxq.pollLast();
                while (!minq.isEmpty() && min[i][j] <= min[i][minq.peekLast()]) minq.pollLast();
                maxq.offerLast(j);
                minq.offerLast(j);
                if (i >= a && j >= b)
                    ans = (ans + (long) max[i][maxq.peekFirst()] * min[i][minq.peekFirst()]) % 998244353;
            }
        }
        System.out.println(ans);
    }

    StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    int nextInt() {
        try {
            in.nextToken();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return (int) in.nval;
    }
}
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

试题 H: 公因数匹配

时间限制: $3.0\mathrm s$ 内存限制: $512.0\mathrm{MB}$ 本题总分： $20$ 分

【问题描述】

给定 $n$ 个正整数 $A_i$ ，请找出两个数 $i, j$ 使得 $i < j$ 且 $A_i$ 和 $A_j$ 存在大于 $1$ 的公因数。
如果存在多组 $i, j$ ，请输出 $i$ 最小的那组。如果仍然存在多组 $i, j$ ，请输出 $i$ 最小的所有方案中 $j$ 最小的那组。

【输入格式】

输入的第一行包含一个整数 $n$ 。
第二行包含 $n$ 个整数分别表示 $A_1 A_2 \cdots A_n$ ，相邻整数之间使用一个空格分隔。

【输出格式】

输出一行包含两个整数分别表示题目要求的 $i, j$ ，用一个空格分隔。

【样例输入】

【样例输出】

2 4
1

【评测用例规模与约定】

对于 $40\%$ 的评测用例， $n \leq 5000$ ；
对于所有评测用例， $1 ≤ n ≤ 10^5，1 ≤ A_i ≤ 10^6$ 。

欧拉筛计算出A范围内每个整数的本质不同质因数，易知 $10^6$ 内整数本质不同质因数不会超过十个，从后往前遍历并记录每个因数最新一次出现位置，线性时间就能跑出来。

import java.io.StreamTokenizer;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;

public class Main {

    public static void main(String ...args) { new Main().run(); }

    static int[][] pfs = new int[1000001][];

    static {
        int[] ps = new int[328498];
        pfs[1] = new int[0];
        for (int i = 2, m = 0; i <= 1000000; ++i) {
            if (pfs[i] == null) {
                pfs[i] = new int[] { i };
                ps[m++] = i;
            }
            for (int j = 0; j < m; ++j) {
                if (i * ps[j] > 1000000) break;
                if (i % ps[j] == 0) {
                    pfs[i * ps[j]] = pfs[i];
                    break;
                }
                pfs[i * ps[j]] = new int[pfs[i].length + 1];
                System.arraycopy(pfs[i], 0, pfs[i * ps[j]], 0, pfs[i].length);
                pfs[i * ps[j]][pfs[i].length] = ps[j];
            }
        }
    }

    int[] A = new int[100001], last = new int[1000000];

    void run() {
        int n = nextInt();
        int k = n, g = n;
        for (int i = 1; i <= n; ++i)
            A[i] = nextInt();
        for (int i = n; i >= 1; --i) {
            for (int j = 0; j < pfs[A[i]].length; ++j) {
                if (last[pfs[A[i]][j]] != 0) {
                    if (k != i) {
                        k = i;
                        g = last[pfs[A[i]][j]];
                    }
                    if (last[pfs[A[i]][j]] < g) {
                        g = last[pfs[A[i]][j]];
                    }
                }
                last[pfs[A[i]][j]] = i;
            }
        }
        System.out.println(k + " " + g);
    }

    StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    int nextInt() {
        try {
            in.nextToken();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return (int) in.nval;
    }
}
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

试题 I: 异或和之差

时间限制: $3.0\mathrm s$ 内存限制: $512.0\mathrm{MB}$ 本题总分： $25$ 分

【问题描述】

给定一个含有 $n$ 个元素的数组 $A_i$ ，你可以选择两个不相交的子段。求出这两个子段内的数的异或和的差值的最大值。

【输入格式】

输入的第一行包含一个整数 $n$ 。
第二行包含 $n$ 个整数 $A_i$ ，相邻整数之间使用一个空格分隔。

【输出格式】

输出一行包含一个整数表示答案。

【样例输入】

6
1 2 4 9 2 7
1
2

【样例输出】

14
1

【样例说明】

两个子段可以分别选 $1$ 和 $4 ， 9 ， 2$ ，差值为 $15 - 1 = 14$ 。

【评测用例规模与约定】

对于 $40\%$ 的评测用例， $n \leq 5000$ ；
对于所有评测用例， $2 ≤ n ≤ 2 × 10^5，0 ≤ A_i ≤ 2^{20}$ 。

01字典树，里面存前缀异或和，然后查询[1,i][i,n]的最值，做个dp最后枚举答案。

import java.io.StreamTokenizer;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;

public class Main {

    public static void main(String ...args) { new Main().run(); }

    int[] A = new int[200001], lmax = new int[200002], lmin = new int[200002], rmax = new int[200002], rmin = new int[200002];

    void run() {
        int n = nextInt(), ans = 0;
        for (int i = 1; i <= n; ++i)
            A[i] = nextInt();
        Trie lt = new Trie(), rt = new Trie();
        lmin[0] = rmin[n + 1] = 0x3f3f3f3f;
        for (int i = 1, s = 0; i <= n; ++i) {
            lt.insert(s);
            s ^= A[i];
            lmax[i] = Math.max(lmax[i - 1], lt.xorMax(s));
            lmin[i] = Math.min(lmin[i - 1], lt.xorMin(s));
        }
        for (int i = n, s = 0; i >= 1; --i) {
            rt.insert(s);
            s ^= A[i];
            rmax[i] = Math.max(rmax[i + 1], rt.xorMax(s));
            rmin[i] = Math.min(rmin[i + 1], rt.xorMin(s));
        }
        for (int i = 1; i < n; ++i) {
            ans = Math.max(ans, rmax[i + 1] - lmin[i]);
            ans = Math.max(ans, lmax[i] - rmin[i + 1]);
        }
        System.out.println(ans);
    }

    class Trie {

        int high = 20;

        Node root = new Node();

        void insert(int x) {
            Node cur = root;
            for (int i = high; i >= 0; --i) {
                int bit = (x >> i) & 1;
                if (cur.ch[bit] == null)
                    cur.ch[bit] = new Node();
                cur = cur.ch[bit];
            }
        }

        int xorMax(int x) {
            int max = 0;
            Node cur = root;
            for (int i = high; i >= 0; --i) {
                int bit = (x >> i) & 1;
                if (cur.ch[bit ^ 1] != null) {
                    cur = cur.ch[bit ^ 1];
                    max |= 1 << i;
                } else {
                    cur = cur.ch[bit];
                }
            }
            return max;
        }

        int xorMin(int x) {
            int min = 0;
            Node cur = root;
            for (int i = high; i >= 0; --i) {
                int bit = (x >> i) & 1;
                if (cur.ch[bit] != null) {
                    cur = cur.ch[bit];
                } else {
                    min |= 1 << i;
                    cur = cur.ch[bit ^ 1];
                }
            }
            return min;
        }

        class Node {

            Node[] ch = new Node[2];
        }

    }

    StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    int nextInt() {
        try {
            in.nextToken();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return (int) in.nval;
    }
}
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

试题 J: 太阳

时间限制: $3.0\mathrm s$ 内存限制: $512.0\mathrm{MB}$ 本题总分： $25$ 分

【问题描述】

这天，小蓝在二维坐标系的点 $(X, Y)$ 上放了一个太阳，看做点光源。
他拿来了 $n$ 条线段，将它们平行于 $x$ 轴放置在了坐标系中，第 $i$ 条线段的左端点在 $x_i, y_i$ ，长度为 $l_i$ 。线段之间不会有重合或部分重合的情况（但可能出现端点相交）。小蓝想知道有多少条线段能被太阳照亮（一条线段有长度大于 $0$ 的部分被照亮就算）。

【输入格式】

输入的第一行包含三个正整数 $n, X, Y$ ，相邻整数之间使用一个空格分隔。
接下来 $n$ 行，第 $i$ 行包含三个整数 $x_i, y_i, l_i$ ，相邻整数之间使用一个空格分隔。

【输出格式】

输出一行包含一个正整数表示答案。

【样例输入】

3 10 2000000
5 3 5
6 2 4
0 1 10
1
2
3
4

【样例输出】

2
1

【评测用例规模与约定】

对于 $30\%$ 的评测用例， $n \leq 1000$ ；
对于所有评测用例， $1 \leq n \leq 100000$ ， $0 ≤ x_i, X ≤ 10^7$ ， $0 < y_i ≤ 10^5$ ， $0 < l_i ≤ 100$ ， $10^6 < Y ≤ 10^7$ 。

线段按高度降序重排，然后投射到x轴上就成了区间覆盖问题，x轴上的端点将y=0代入y=kx+b可得x=-b/k

import java.io.StreamTokenizer;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;
import java.util.Arrays;

public class Main {

    public static void main(String ...args) { new Main().run(); }

    Fraction[] y0 = new Fraction[200000];

    int X, Y, m = -1;

    class Line {

        int w;

        Fraction x1, x2;
    }

    Fraction y0x(int x, int y) {
        if (X == x) return new Fraction(1, x);
        Fraction k = new Fraction(X - x, Y - y);
        Fraction b = new Fraction(k.numerator, k.denominator * x - k.numerator * y);
        return new Fraction(b.numerator * k.denominator, b.denominator * k.numerator);
    }

    void run() {
        int n = nextInt(), ans = 0, t = 0;
        X = nextInt();
        Y = nextInt();
        Line[] lines = new Line[n];
        for (int i = 0; i < n; ++i) {
            int x = nextInt(), y = nextInt(), l = nextInt();
            lines[i] = new Line();
            lines[i].w = y;
            y0[t++] = lines[i].x1 = y0x(x, y);
            y0[t++] = lines[i].x2 = y0x(x + l, y);
        }
        Arrays.sort(lines, (a, b) -> Integer.compare(b.w, a.w));
        Arrays.sort(y0, 0, t);
        for (int i = 0; i < t; ++i)
            if (m == -1 || !y0[i].equals(y0[m]))
                y0[++m] = y0[i];
        for (int i = 0; i < n; ++i) {
            int l = Arrays.binarySearch(y0, 0, m + 1, lines[i].x1);
            int r = Arrays.binarySearch(y0, 0, m + 1, lines[i].x2);
            if (!query(l, r - 1)) ++ans;
        }
        System.out.println(ans);
    }

    class Fraction implements Comparable<Fraction> {

        long numerator, denominator;

        Fraction(long numerator, long denominator) {
            this.denominator = denominator;
            this.numerator = numerator;
            this.simple();
        }

        void simple() {
            long gcd = gcd(numerator, denominator);
            this.denominator = denominator /gcd;
            this.numerator = numerator / gcd;
        }

        long gcd(long a, long b) { return b == 0 ? a : gcd(b, a % b); }

        public boolean equals(Object obj) {
            Fraction fobj = (Fraction) obj;
            return this.numerator == fobj.numerator && this.denominator == fobj.denominator;
        }

        public int compareTo(Fraction o) {
            if (this.equals(o)) return 0;
            return Double.compare((double) this.denominator / this.numerator, (double) o.denominator / o.numerator);
        }

        @Override
        public String toString() {
            return Double.toString((double) this.denominator / this.numerator);
        }
    }

    boolean[] tree = new boolean[1 << 19];

    boolean query(int l, int r) { return queryAndUpdate(1, 0, m, l ,r); }

    boolean queryAndUpdate(int n, int L, int R, int l, int r) {
        if (tree[n]) return true;
        if (l <= L && r >= R) {
            tree[n] = true;
            return false;
        }
        int mid = (L + R) >> 1;
        boolean full = true;
        if (l <= mid) full &= queryAndUpdate(n << 1, L, mid, l, r);
        if (r > mid) full &= queryAndUpdate((n << 1) | 1, mid + 1, R, l, r);
        tree[n] = tree[n << 1] & tree[(n << 1) | 1];
        return full;
    }

    StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    int nextInt() {
        try {
            in.nextToken();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return (int) in.nval;
    }
}
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/很楠不爱3/article/detail/73641

第十四届蓝桥杯大赛软件赛省赛（Java 大学C组）_蓝桥杯真题java,c组

蓝桥杯 2023年省赛真题 Java 大学C组

试题 A: 求和

试题 B: 分糖果

试题 C: 三国游

贪心

试题 D: 平均

贪心

试题 E: 填充

贪心

试题 F: 棋盘

试题 G: 子矩阵

试题 H: 公因数匹配

试题 I: 异或和之差

试题 J: 太阳

蓝桥杯 2023年省赛真题
^{Java 大学C组}