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

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

 试题 A: 特殊日期
 试题 B: 与或异或
 试题 C: 平均
 试题 D: 棋盘
 试题 E: 互质数的个数
 试题 F: 阶乘的和
 试题 G: 小蓝的旅行计划
 试题 H: 太阳
 试题  I: 高塔
 试题 J: 反异或 01 串

---

那么根据这个夹逼定理我们容易得出湖北经济学院趋近于武大华科。

---

试题 A: 特殊日期

本题总分：5 分

【问题描述】

  记一个日期为 $yy$ 年 $mm$ 月 $dd$ 日，统计从 $2000$ 年 $1$ 月 $1$ 日到 $2000000$ 年 $1$ 月 $1$ 日，有多少个日期满足年份 $yy$ 是月份 $mm$ 的倍数，同时也是 $dd$ 的倍数。

【答案提交】

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

---

35813063

---

朴素解法

---

  考虑到以日为单位计量，时间段的阶并不大，因此直接使用java.time.LocalDate模拟日期变化，判断然后累加，程序在笔者 $\mathrm{PC}$ 运行 $15$ 秒后得到了答案。

import java.time.LocalDate;

public class Main {

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

    LocalDate start = LocalDate.of(2000, 1, 1);
    LocalDate end = LocalDate.of(2000000, 1, 1);

    void run() {
        long ans = 0;
        for (LocalDate i = start; i.compareTo(end) <= 0; i = i.plusDays(1))
            if (i.getYear() % i.getMonthValue() == 0 
                    && i.getYear() % i.getDayOfMonth() == 0) ++ans;
        System.out.println(ans);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

---

倍数法

---

  设函数 f y ( x ) = { 1 x   ∣   y 0 o t h e r w i s e f_y(x) =

$$\begin{cases} 1 & x\,|\,y\\ 0 & \rm otherwise \end{cases}$$ fy​(x)={10​x∣yotherwise​，对于正整数 $y$，记 $d_y$为${\sum }_{x=1}^{31}{f}_y(x)$，$m_y$为${\sum }_{x=1}^{12}{f}_y(x)$，则在不考虑日期是否合法的情况下，答案为 ${\sum }_{y=2000}^{2000000-1}{d}_y{m}_y+1$。因此我们用倍数法在线性时间复杂度意义下求出 $d$ 与 $m$，将答案拆分成若干合法部分累加，最后得到正确答案。

import java.util.function.IntPredicate;
import java.util.stream.IntStream;

public class Main {

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

    void run() {
        System.out.println(
                calc(IntStream.rangeClosed(1, 12), IntStream.range(1, 29), y  -> true)
                + calc(IntStream.of(2), IntStream.of(29), y -> y % 100 == 0 ? (y % 400 == 0) : (y % 4 == 0))
                + calc(IntStream.iterate(1, m -> m == 1 ? 3 : m + 1).limit(11), IntStream.rangeClosed(29, 30), y  -> true)
                + calc(IntStream.of(1, 3, 5, 7, 8, 10, 12), IntStream.of(31), y  -> true)
                + 1
        );
    }

    final int start = 2000, end = 2000000;

    int calc(IntStream m, IntStream d, IntPredicate yf) {
        int[] my = new int[end + 1];
        int[] dy = new int[end + 1];
        m.forEach(
                a -> {
                    for (int i = 1; i * a <= end; ++i) ++my[i * a];
                }
        );
        d.forEach(
                a -> {
                    for (int i = 1; i * a <= end; ++i) ++dy[i * a];
                }
        );
        return IntStream.range(start, end).filter(yf).map(
                a -> my[a] * dy[a]
        ).sum();
    }
}
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

  帅是帅，但放在竞赛中性价比极低，编程多耗费时间都够你针对朴素解法的程序给出好几个测试用例了。

---

试题 B: 与或异或

本题总分：5 分

【问题描述】

  小蓝有一张门电路的逻辑图，如下图所示$：$

  图中每个三角形代表着一种门电路，可能是与门、或门、异或门中的任何一种，它接受上一层中的两个圆形中的数据作为输入，产生一个输出值输出到下一级（如图中箭头所示）。图中圆形表示的是暂存的输出结果，取值只可能是 $0$ 或 $1$，为了便于表示我们用 $arr[i][j]$ 表示第 $i(0\le i\le 4)$ 行第 $j(0\le j\le i)$ 个圆形的值。其中 $arr[0]=(In[0],In[1],In[2],In[3],In[4])$ 表示的是输入数据，对于某个 $arr[i][j](i\le 0)$，计算方式为 $arr[i][j]=arr[i-1][j]oparr[i-1][j+1]$，其中 $op$ 表示的是将 $arr[i-1][j]、arr[i-1][j+1]$ 作为输入，将 $arr[i][j]$ 作为输出的那个门电路，与门、或门、异或门分别对应于按位与 $(\&)$、按位或 $(|)$、按位异或$($^$)$ 运算符。

  现在已知输入为 $In[0]=1,In[1]=0,In[2]=1,In[3]=0,In[4]=1$，小蓝想要使得最终的输出 $Out$ 的值为 $1$，请问一共有多少种不同的门电路组合方式？其中上图中显示的就是一种合法的方式。

【答案提交】

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

---

30528

---

深度优先搜索

---

  暴搜杯！我的青春回来了，开搜！

public class Main {

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

    int[][] cir = new int[6][6];

    int ans = 0, target = 1;

    void run() {
        cir[5] = new int[]{ 0, 1, 0, 1, 0, 1 };
        dfs(1, 5);
        System.out.println(ans);
    }

    void dfs(int i, int n) {
        if (n <= 1) {
            if (cir[n][i] == target) ++ans;
        } else {
            if (i < n) {
                cir[n - 1][i] = cir[n][i] & cir[n][i + 1];
                dfs(i + 1, n);
                cir[n - 1][i] = cir[n][i] | cir[n][i + 1];
                dfs(i + 1, n);
                cir[n - 1][i] = cir[n][i] ^ cir[n][i + 1];
                dfs(i + 1, n);
            } else {
                dfs(1, n - 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

---

试题 C: 平均

时间限制：3.0s 内存限制：512.0MB 本题总分：10 分

【问题描述】

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

【输入格式】

  输入的第一行包含一个正整数 $n$ 。

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

【输出格式】

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

【样例输入】

10
1 1
1 2
1 3
2 4
2 5
2 6
3 7
3 8
3 9
4 10
1
2
3
4
5
6
7
8
9
10
11

【样例输出】

27
1

【样例说明】

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

【评测用例规模与约定】

  对于 $20\%$ 的评测用例，$n\le 1000$；
  对于所有评测用例，$n\le 100000,0<bi\le 2\times 10^5$。

---

贪心

---

  记 $[0,9]$ 中的整数 $x$ 修改为整数 $y$ 的操作为 $x\stackrel{c}{\mapsto }y$，即花费代价 $c$ 将 $x$ 修改为 $y$，如果一个方案中同时出现 $x\stackrel{c_1}{\mapsto }y、y\stackrel{c_2}{\mapsto }z$，那么使用 $x\stackrel{c_1}{\mapsto }z$ 替换掉这两个操作就能使总代价减小 $c_2$，即原方案一定非最优。容易归纳出最优方案中一定不存在长度大于 $1$ 的路径（将 $x\mapsto y、y\mapsto z$ 看作长度为 $2$ 的路径），那么方案要满足题意只能取每个整数超出目标出现次数 $\frac{n}{10}$ 的部分，在这个基础上最小代价和就是每个整数取超出部分个最小代价之和。

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(); }

    int[] buffer = new int[200000], cnt = new int[10];

    void run() {
        int n = nextInt(), m = n / 10;
        long ans = 0;
        for (int i = 0; i < n; ++i) {
            buffer[i] = nextInt();
            buffer[i] |= nextInt() << 4;
        }
        Arrays.sort(buffer, 0, n);
        for (int i = n - 1; i >= 0; --i)
            if (++cnt[buffer[i] & 0xf] > m)
                ans += buffer[i] >> 4;
        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

  实现上可以将 $a_i,b_i$ 用一个整形表示，以减少排序的开销，也可以按 $a_i$ 将 $b_i$ 分类再依次排序。

---

试题 D: 棋盘

时间限制：3.0s 内存限制：512.0MB 本题总分：10 分

【问题描述】

  小蓝拥有 $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$。

【样例输入】

3 3
1 1 2 2
2 2 3 3
1 1 3 3
1
2
3
4

【样例输出】

001
010
100
1
2
3

【评测用例规模与约定】

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

---

二维差分

---

  如果我们用数字的奇偶性来表示黑白棋，用 $n\times n$ 大小且元素全为 $0$ 的矩阵来表示初始棋盘，容易发现对棋盘 $x_1$ 至 $x_2$ 行和 $y_1$ 至 $y_2$ 列中的棋子颜色取反的操作与对矩阵 $x_1$ 至 $x_2$ 行和 $y_1$ 至 $y_2$ 列中的元素加 $1$ 的操作等价，我们只需要所有操作结束后的棋盘状态，很典型的二维差分问题。
  实现上用到了异或运算在相加上不进位与 $0$ 和 $1$ 在 $\mathrm{ASCII}$ 相邻的特性。

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(); }

    byte[][] low = new byte[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();
            low[x][y] ^= 1;
            low[x][g + 1] ^= 1;
            low[k + 1][y] ^= 1;
            low[k + 1][g + 1] ^= 1;
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                low[i][j] ^= low[i - 1][j] ^ low[i][j - 1] ^ low[i - 1][j - 1];
                out.write('0' ^ low[i][j]);
            }
            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

---

试题 E: 互质数的个数

时间限制：3.0s 内存限制：512.0MB 本题总分：15 分

【问题描述】

  给定 $a,b$，求 $1\le x<a^b$ 中有多少个 $x$ 与 $a^b$ 互质。由于答案可能很大，你只需要输出答案对 $998244353$ 取模的结果。

【输入格式】

  输入一行包含两个整数分别表示 $a,b$，用一个空格分隔。

【输出格式】

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

【样例输入 1】

2 5
1

【样例输出 1】

16
1

【样例输入 2】

12 7
1

【样例输出 2】

11943936
1

【评测用例规模与约定】

  对于 $30\%$ 的评测用例，$a^b\le 10^6$；
  对于 $70\%$ 的评测用例，$a\le 10^6，b\le 10^9$；
  对于所有评测用例，$1\le a\le 10^9，1\le b\le 10^{18}$。

---

欧拉函数

---

  欧拉函数是积性函数，其形式为 $\phi (n)$，表示小于等于 $n$ 且与 $n$ 互质的正整数的个数，因此当 $a^b=1$ 时答案为 $0$（$\phi (1)=1$），其他情况答案为 $\phi (a^b)$。
  依算术基本定理，将 $a^b$ 分解为 $(p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots p_s^{{\alpha }_s}{)}^b={\prod }_{i=1}^s{p}_i^{b\cdot {\alpha }_i}$，因为 $\phi$ 是积性函数，有： φ ( a b ) = ∏ i = 1 s φ ( p i b   ⋅   α i ) = ∏ i = 1 s p i b   ⋅   α i − 1 ( p i − 1 ) = ∏ i = 1 s p i b   ⋅   α i ( 1 − 1 p i ) = ∏ i = 1 s p i b   ⋅   α i ∏ i = 1 s ( 1 − 1 p i ) = a b ∏ i = 1 s ( 1 − 1 p i )

$$\begin{split} \varphi(a^b) &=\prod_{i=1}^s\varphi(p_i^{b\,\cdot\,\alpha_i})\\ &=\prod_{i=1}^sp_i^{b\,\cdot\,\alpha_i-1}(p_i-1)\\ &=\prod_{i=1}^sp_i^{b\,\cdot\,\alpha_i}(1-\frac 1{p_i})\\ &=\prod_{i=1}^s p_i^{b\,\cdot\,\alpha_i}\prod_{i=1}^s(1-\frac 1{p_i})\\ &=a^b\prod_{i=1}^s(1-\frac 1{p_i}) \end{split}$$ φ(ab)​=i=1∏s​φ(pib⋅αi​​)=i=1∏s​pib⋅αi​−1​(pi​−1)=i=1∏s​pib⋅αi​​(1−pi​1​)=i=1∏s​pib⋅αi​​i=1∏s​(1−pi​1​)=abi=1∏s​(1−pi​1​)​  右连乘式可以通过 $a$ 质因数分解得出，算法复杂度为 $O(\alpha +\sqrt{a})$，其中 $O(\alpha )$ 为计算逆元均摊复杂度。

import java.util.Scanner;

public class Main {

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

    final int mod = 998244353;

    long qpow(long a, long b) {
        long pow = 1;
        for (; b > 0; b >>= 1) {
            if ((b & 1) == 1) pow = pow * a % mod;
            a = a * a % mod;
        }
        return pow;
    }

    void run() {
        Scanner in = new Scanner(System.in);
        int a = in.nextInt();
        if (a == 1) {
            System.out.print("0");
            return;
        }
        long ans = qpow(a, in.nextLong());
        for (int p = 2, root = (int) Math.sqrt(a + 0.5); p <= root; ++p)
            if (a % p == 0){
                ans = ans * qpow(p, mod - 2) % mod * (p - 1) % mod;
                while (a % p == 0) a /= p;
            }
        if (a > 1) ans = ans * qpow(a, mod - 2) % mod * (a - 1) % mod;
        System.out.print(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
30
31
32
33
34

---

试题 F: 阶乘的和

时间限制：3.0s 内存限制：512.0MB 本题总分：15 分

【问题描述】

  给定 $n$ 个数 $A_i$，问能满足 $m!$ 为 ${\sum }_{i=1}^n(A_i!)$ 的因数的最大的 $m$ 是多少。其中 $m!$ 表示 $m$ 的阶乘，即 $1\times 2\times 3\times \cdot \cdot \cdot \times m$。

【输入格式】

  输入的第一行包含一个整数 $n$。

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

【输出格式】

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

【样例输入】

3
2 2 2
1
2

【样例输出】

3
1

【评测用例规模与约定】

  对于 $40\%$ 的评测用例，$n\le 5000$；
  对于所有评测用例，$1\le n\le 10^{5}1\le A_i\le 10^9$。

---

贪心

---

  如果我们尽可能的合并较小的阶乘，直至无法合并，如 $2!+2!+2!=3\times 2!=3!$，我们取 $3$ 作 $m$ 一定最优，那么这种策略在任何情况都能受用吗？
  首先我们将 $A_1,A_2,\cdots ,A_n$ 按升序重排，即我们可以一般性假设 $i<j,A_i\le A_j$，当 $A_s$ 无法被合并时，即 $\mathrm{count}(A_s)<A_s+1$，${\sum }_{i=1}^n{A}_i=A_s!{\sum }_{i=s}^n\frac{A_i!}{A_s!}$，此时我们取 $A_s$ 作 $m$ 一定合法，尝试判断 $(A_s+1)!$ 是否为 ${\sum }_{i=1}^n{A}_i$ 的因数，等价于 $A_s+1$ 是否为 ${\sum }_{i=s}^n\frac{A_i!}{A_s!}$ 的因数。
  记 $g$ 为第一个值为 $A_S+1$ 的位置，有 $A_s+1|(A_s+1){\sum }_{i=s}^n\frac{A_i!}{(A_s+1)!}$，而 $\mathrm{count}(A_s)<A_s+1$ 即 ${\sum }_{i=s}^{g-1}\frac{A_i!}{(A_s)!}=\mathrm{count}(A_s)\nmid A_s+1$，因此 $A_s+1\nmid {\sum }_{i=s}^n\frac{A_i!}{A_s!}$ ，故 $A_s$ 最优。

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(); }

    void run() {
        int n = nextInt();
        int[] A = new int[n];
        for (int i = 0; i < n; ++i)
            A[i] = nextInt();
        Arrays.sort(A);
        int m = A[0], k = 1;
        for (int i = 1; i < n; ++i)
            if (m == A[i]) ++k;
            else {
                while (k > 0 && k % (m + 1) == 0) {
                    k /= ++m;
                    if (m == A[i]) {
                        ++k;
                        break;
                    }
                }
            }
        while (k > 0 && k % (m + 1) == 0) k /= ++m;
        System.out.print(m);
    }

    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

---

试题 G: 小蓝的旅行计划

时间限制：5.0s 内存限制：512.0MB 本题总分：20 分

【问题描述】

  小蓝正计划进行一次漫长的旅行。小蓝计划开车完成这次旅行。显然他在途中需要加油，否则可能无法完成这次旅行。

  小蓝要依次经过 $n$ 个地点，其中从第 $i-1$ 个地点到达第 i 个地点需要消耗 $Di{s}_i$ 升油。小蓝经过的每个地点都有一个加油站，但每个加油站的规定也不同。在第 $i$ 个加油站加 $1$ 升油需要 $Cos{t}_i$ 的费用，且在这个加油站最多只能加 $Li{m}_i$升油。

  小蓝的车的油箱也有容量限制，他的车上最多只能装载 $m$ 升油。

  一开始小蓝的油箱是满的，请问小蓝需要准备多少钱才能顺利完成他的旅行计划。如果小蓝按给定条件无论准备多少钱都不能完成他的旅行计划，请输出 $-1$。

【输入格式】

  输入的第一行包含两个整数 $nm$，用一个空格分隔。

  接下来 $n$ 行每行包含 $3$ 个整数 $Di{s}_{i}Cos{t}_{i}Li{m}_i$，相邻整数之间使用一个空格分隔。

【输出格式】

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

【样例输入】

4 5
2 9 2
4 5 6
3 2 2
4 1 3
1
2
3
4
5

【样例输出】

38
1

【评测用例规模与约定】

  对于 $30\%$ 的评测用例，$nDi{s}_{i}Cos{t}_{i}Li{m}_{i}m\le 300$；
  对于 $60\%$ 的评测用例，$nDi{s}_{i}Cos{t}_{i}Li{m}_{i}m\le 5000$；
  对于所有评测用例，$1\le n\le 2\times 10^5，1\le Di{s}_{i}Li{m}_{i}m\le 10^9，1\le Cos{t}_i\le 40000$。

---

贪心

---

  记某个方案在第 $i$ 个地点的加油站加了 $P_i$ 升油，$P_0=m$，$Di{s}_0=0$，记序列 $A$ 为 { a i = P i − D i s i } \{a_i=P_i-Dis_{i}\} {ai​=Pi​−Disi​}，$A$ 的前缀和 $B$ 为 { b i = ∑ j = 0 i ( P j − D i s j ) } \{b_i=\sum_{j=0}^i(P_j-Dis_{j})\} {bi​=∑j=0i​(Pj​−Disj​)}。
  对于题目给定样例，容易找到加油方案 { m , 1 , 5 , 2 } \{m, 1, 5, 2\} {m,1,5,2} 花费为 $0\times 5+1\times 9+5\times 5+2\times 2=38$，代入到 $B$ 得出 { 4 , 5 , 4 , 0 } \{4, 5, 4, 0\} {4,5,4,0}，事实上 $B$ 对应着方案在相应地点的剩余油量，因此 $b_i\notin [0,m]$ 或 $b_i<Di{s}_{i+1}$ 时方案不可达，$b_n=0$ 时方案一定非最优（在 $n-1$ 处少加 $b_n$ 的油总花费变低且方案依然合法）。
  无论如何 $Dis$ 是不变量，我们可以先计算出 $-Dis$ 的前缀和，于是对于题目给定样例有 C = { − 2 , − 6 , − 9 , − 13 } C=\{-2, -6, -9, -13\} C={−2,−6,−9,−13}，然后顺序遍历，依次使 $B[:i]$ 的方案合法，等价于使用 $P[:i-1]$ 令 $b_i$ 非零，对 $P_j$，$j$ 则贪心的选择 $Cos{t}_j$ 最小的，$P_j$ 合法的增量是 min ⁡ { res ⁡ j , m − max ⁡ { b x , j ≤ x < i } } \operatorname{min}\{\operatorname{res}_j, m - \operatorname{max}\{b_x,j\leq x <i\}\} min{resj​,m−max{bx​,j≤x<i}}，其中 ${\mathrm{res}}_j$为第 $i$ 个地点的加油站的剩余油量，而右侧算式是限制这个增量增加后不会有 $b$ 大于 $m$。
  下面给出测试用例对应的 $B$ 的变化过程，没看太懂的读者可以自行推导一下。
   { − 2 , − 6 , − 9 , − 13 } \{-2, -6, -9, -13\} {−2,−6,−9,−13}
   {    3    , − 1 , − 4 ,    − 8   } ← 5 × C o s t 0 \{\:\,3\:\,, -1, -4, \,\,-8\,\} \gets 5 \times Cost_0 {3,−1,−4,−8}←5×Cost0​
   {    4    ,    0    , − 3 ,    − 7   } ← 1 × C o s t 1 \{\:\,4\:\,,\:\,0\:\,, -3, \,\,-7\,\} \gets 1 \times Cost_1 {4,0,−3,−7}←1×Cost1​
   {    4    ,    3    ,    0    ,    − 4   } ← 3 × C o s t 2 \{\:\,4\:\,,\:\,3\:\,,\:\,0\:\,, \,\,-4\,\} \gets 3 \times Cost_2 {4,3,0,−4}←3×Cost2​
   {    4    ,    5    ,    4    ,      0     } ← 2 × C o s t 2 + 2 × C o s t 3 \{\:\,4\:\,,\:\,5\:\,,\:\,4\:\,, \,\,\:\,0\:\,\,\} \gets 2 \times Cost_2 + 2 \times Cost_3 {4,5,4,0}←2×Cost2​+2×Cost3​
  证明也很麻烦，就懒得证了，式中 max ⁡ { b i } \operatorname{max}\{b_i\} max{bi​} 和区间加部分则通过线段树完成，最终算法复杂度为 $O(n\log n)$。

import java.io.IOException;
import java.io.BufferedReader;
import java.io.StreamTokenizer;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main {

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

    int[] cost = new int[200001], lim = new int[200001];

    void run() {
        Queue<Integer> pq = new PriorityQueue<>((a, b) -> cost[a] - cost[b]);
        int n = nextInt(), m = nextInt();
        while (this.m <= n) this.m <<= 1;
        long sum = m, ans = 0;
        for (int i = 1; i <= n; ++i) {
            tree[this.m + i] = sum -= nextInt();
            cost[i] = nextInt();
            lim[i] = nextInt();
        }
        for (int i = n + 1; i < this.m; ++i)
            tree[this.m + i] = -inf;
        tree[this.m] = -inf;
        for (int i = this.m - 1; i > 0; --i)
            tree[i] = Math.max(tree[i << 1], tree[(i << 1) | 1]);
        for (int i = 1; i <= n; ++i) {
            long need = query(i);
            while (need < 0 && pq.size() > 0) {
                int cheap = pq.peek();
                long res = Math.min(m - query(cheap, i - 1), lim[cheap]);
                if (res > -need) res = -need;
                else pq.poll();
                need += res;
                lim[cheap] -= res;
                add(cheap, n, (int) res);
                ans += res * cost[cheap];
            }
            if (need < 0) {
                System.out.print("-1");
                return;
            }
            pq.offer(i);
        }
        System.out.print(ans);
    }

    long[] tree = new long[1 << 19], mark = new long[1 << 19];

    long inf = 0x3f3f3f3f3f3f3f3fl;

    int m = 1;

    void add(int l, int r, int k) {
        for (l += m - 1, r += m + 1; (l ^ r) != 1; l >>= 1, r >>= 1) {
            if (l < m) {
                tree[l] = Math.max(tree[l << 1], tree[(l << 1) | 1]) + mark[l];
                tree[r] = Math.max(tree[r << 1], tree[(r << 1) | 1]) + mark[r];
            }
            if ((l & 1) == 0) {
                tree[l ^ 1] += k;
                mark[l ^ 1] += k;
            }
            if ((r & 1) == 1) {
                tree[r ^ 1] += k;
                mark[r ^ 1] += k;
            }
        }
        for (; l > 0; l >>= 1, r >>= 1) {
            tree[l] = Math.max(tree[l << 1], tree[(l << 1) | 1]) + mark[l];
            tree[r] = Math.max(tree[r << 1], tree[(r << 1) | 1]) + mark[r];
        }
    }

    long query(int i) {
        long elem = tree[i += m];
        while ((i >>= 1) > 0)
            elem += mark[i];
        return elem;
    }

    long query(int l, int r) {
        long maxL = -inf, maxR = -inf;
        for (l += m - 1, r += m + 1; (l ^ r) != 1; l >>= 1, r >>= 1) {
            maxL += mark[l];
            maxR += mark[r];
            if ((l & 1) == 0)
                maxL = Math.max(maxL, tree[l ^ 1]);
            if ((r & 1) == 1)
                maxR = Math.max(maxR, tree[r ^ 1]);
        }
        for (; l > 0; l >>= 1, r >>= 1) {
            maxL += mark[l];
            maxR += mark[r];
        }
        return Math.max(maxL, maxR);
    }

    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

---

试题 H: 太阳

时间限制：3.0s 内存限制：512.0MB 本题总分：20 分

【问题描述】

  这天，小蓝在二维坐标系的点 $(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\le 1000$；
  对于所有评测用例，$1\le n\le 100000$，$0\le x_i,X\le 10^7$，$0<y_i\le 10^5$，$0<l_i\le 100$，$10^6<Y\le 10^7$。

---

区间覆盖

---

  用例数据可可视化表现为：

  

  然后将线段投射到 $x$ 轴上：

  

  可以发现问题等价，且 $y$ 是恒等于 $0$（这里为了方便图示，将光源拉进了一点，线段作了高亮区分），我们直接按 $y$ 降序重排线段，就变成了区间覆盖问题，魔改下线段树 $O(n\log n)$ 秒杀。
  关于线段在 $x$ 轴上的投射，即线段端点与光源点构成的直线的横截距，将 $y=0$ 代入 $(y-Y)=k(x-X)$ 可得 $x=X-\frac{Y}{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(); }

    class MappedLine implements Comparable<MappedLine> {

        int w;

        double x1, x2;

        MappedLine(int w, double x1, double x2) {
            this.w = w;
            this.x1 = x1;
            this.x2 = x2;
        }

        @Override
        public int compareTo(MappedLine line) {
            return Integer.compare(line.w, this.w);
        }
    }

    MappedLine[] lines = new MappedLine[100000];

    double[] itd = new double[200000];

    int m = 0, X, Y;

    void run() {
        int n = nextInt(), ans = 0;
        X = nextInt();
        Y = nextInt();
        for (int i = 0; i < n; ++i) {
            int x = nextInt(), y = nextInt(), l = nextInt();
            double x1 = mapping(x, y), x2 = mapping(x + l, y);
            lines[i] = new MappedLine(y, x1, x2);
            itd[m++] = x1;
            itd[m++] = x2;
        }
        Arrays.sort(itd, 0, m);
        Arrays.sort(lines, 0, n);
        for (int i = 0; i < n; ++i) {
            int l = dti(lines[i].x1);
            int r = dti(lines[i].x2);
            if (!qau(l, r - 1)) ++ans;
        }
        System.out.print(ans);
    }

    double mapping(int x, int y) {
        if (x == X) return X;
        double k = (double) (Y - y) / (X - x);
        return X - Y / k;
    }

    int dti(double d) {
        int l = 0, r = m - 1;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (itd[mid] < d + 1e-8) l = mid + 1;
            else r = mid;
        }
        return l;
    }

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

    boolean qau(int l, int r) {  return queryAndUpdate(1, 0, m - 1, 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

  这类题粪就粪在编码量和变量精度上，不过这里魔改下线段树编码量还算能接受。关于浮点数离散化映射时的精度有许多解决方法，在关系简单时可以用最简分数表示，内存吃紧时可以用最简分数的商表示，这样可以直接使用双等号来判断浮点数是否相同，极大概率下为 $\mathrm{true}$ 的两个浮点型都是由两个相同的分子母计算得出的，或者像本节程序一样在离散表查找 $d$ 时去找 $d+\mathrm{prec}$ 或 $d+\mathrm{prec}$ 的前驱，$\mathrm{prec}$ 是精度。
  严格来讲只有第一种做法是正确的，但一般在竞赛中不会去 $\mathrm{hack}$ 精度在 $1e$$-$$6$ 以上的程序，结合性能考量我们一般会选择最后一种，心情到了可以水水离散化。

---

试题  I: 高塔

时间限制：3.0s 内存限制：512.0MB 本题总分：25 分

【问题描述】

  小蓝正在玩一个攀登高塔的游戏。高塔的层数是无限的，但游戏最多只有 $n$ 回合。

  小蓝一开始拥有 $m$ 点能量，在每个回合都有一个值 $A_i$ 表示小蓝的角色状态。小蓝每回合可以选择消费任意点能量 $C_i$ (最低消费 $1$ 点，没有上限)，他在这回合将最多可以向上攀爬 $A_i\cdot C_i$ 层。实际攀爬的层数取决于小蓝自己在这回合的表现，不过最差也会向上爬一层。

  当某回合小蓝的能量点数耗尽，那么在完成这个回合后，游戏结束。$n$ 回合结束后，不管能量还有没有剩余，游戏都会直接结束。

  给出小蓝每回合的 $A_i$ 和自己一开始的能量点数 $m$。小蓝想知道有多少种不同的可能出现的游玩过程。如果小蓝在两种游玩过程中的任一对应回合花费的能量点数不同或该回合结束时所处层数不同，那么这两种游玩过程就被视为不同。

【输入格式】

  输入的第一行包含两个整数 $n,m$，用一个空格分隔。

  第二行包含 $n$ 个整数 $A_i$，相邻整数之间使用一个空格分隔，表示小蓝每回合的状态值。

【输出格式】

  输出一行包含一个整数表示给定条件下不同游玩过程的数量。由于答案可能很大，你只需要输出答案对 $998244353$ 取模的结果

【样例输入】

9 15
3 2 5 7 1 4 6 8 3
1
2

【样例输出】

392149233
1

【评测用例规模与约定】

  对于 $40\%$ 的评测用例，$n\le 300，m\le 500$；
  对于所有评测用例，$1\le n\le 2\times 10^5，n\le m\le 10^{18}，1\le A_i\le 10^9$。

---

组合数学

---

  为了方便讨论，这里先给出一种小蓝在第 $n$ 回合结束游戏的游玩过程数量的计算方法。依题意的，第 $i$ 回合小蓝共消耗了 $C_i$，共消耗了 $n\le {\sum }_{i=1}^n{C}_i\le m$点能量，第 $i$ 回合有 $A_i\cdot C_i$ 总不同的走法，故方案数为：$$\sum _{\begin{array}{c}{c}_1,c_2,\cdots ,c_n>0\\ c_1+c_2+\cdots +c_n\le m\end{array}}\prod _{i=1}^n{A}_i{C}_i=\sum _{\begin{array}{c}{c}_1,c_2,\cdots ,c_n>0\\ c_1+c_2+\cdots +c_n\le m\end{array}}\prod _{i=1}^n{C}_i\cdot \prod _{i=1}^n{A}_i.$$  记 $p(n,m)$ 为 ${\sum }_{\begin{array}{c}{c}_1,c_2,\cdots ,c_n>0\\ c_1+c_2+\cdots +c_n\le m\end{array}}{\prod }_{i=1}^n{C}_i$。因为在小于 $n$ 的回合结束要耗尽能量，所以整理可以知最终答案为：$$p(n,m)\prod _{i=1}^n{A}_i+\sum _{j=1}^{n-1}(p(j,m)-p(j,m-1))\prod _{i=1}^j{A}_i.$$  因此该思路下，$p(n,m)$ 求解的复杂度与整体直接关联，考虑 $p$ 的边界情况，当 $n=1$ 时，$p(1,m)=1+2+\cdots +m=\frac{m(m+1)}{2}$。考虑 $n+1$ 情况，枚举 $C_{n+1}$ 可能的取值 $1,2,\cdots m-n$，则有递推式： p ( n , m ) = { 1 + 2 + ⋯ + m n = 1 ∑ i = 1 m − n + 1 i p ( i − 1 , m − i ) 1 < n ≤ m . p(n,m) =

$$\begin{cases} 1+2+\cdots+m &n=1 \\ \sum_{i=1}^{m-n+1} ip(i-1,m-i) &1< n\leq m \end{cases}$$ . p(n,m)={1+2+⋯+m∑i=1m−n+1​ip(i−1,m−i)​n=11<n≤m​.  观察到 $p(1,m)=\frac{m(m+1)}{2}=C_{m+1}^2$，有 $$\begin{array}{rl}p(2,m)& =C_m^2+2C_{m-1}^2+\cdots +(m-1)C_2^2\\ & =(C_m^2+C_{m-1}^2+\cdots +C_2^2)+(C_{m-1}^2+C_{m-2}^2+\cdots +C_2^2)+\cdots C_2^2\\ & =C_{m+1}^3+C_m^3+\cdots +C_3^3\\ & =C_{m+2}^4\end{array}.$$  类似的，可得关系式 $p(n,m)=C_{n+m}^{2n}$，故最终答案为：$$C_{n+m}^{2n}\prod _{i=1}^n{A}_i+\sum _{j=1}^{n-1}(C_{j+m}^{2j}-C_{j+m-1}^{2j})\prod _{i=1}^j{A}_i.$$  不对 $p$ 做优化的情况下时间复杂度为 $O(n^2\log m)$，因此 $p$ 的值还需迭代计算，最终复杂度为 $O(n\log m)$。此外，在杨辉三角中我们也可以看到 $p(n,m)、p(n-1,m-1)、p(n-1,n-1)$ 恰围成一个矩形。

  大概就是这么个感觉，可以直接考虑 $p(n,i)$ 到 $p(n+1,m),i<n$ 的贡献，可以发现贡献恰为 $i$，但图画出来太丑了，就懒的画了。

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

public class Main {

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

    final int mod = 998244353;

    long qpow(long a, int b) {
        long res = 1;
        a %= mod;
        for (; b > 0; b >>= 1) {
            if (b % 2 == 1)
                res = res * a % mod;
            a = a * a % mod;
        }
        return res;
    }

    void run() {
        int n = nextInt();
        long m = nextLong() % mod;
        long A = 1, p1 = 1, p2 = 1, ans = 0;
        for (int i = 1; i <= n; ++i) {
            A = A * nextInt() % mod;
            p1 = p1 * (m + i) % mod * (m - i + 1) % mod * qpow(2 * i, mod - 2) % mod * qpow(2 * i - 1, mod - 2) % mod;
            p2 = p2 * (m - 1 + i) % mod * (m - i) % mod * qpow(2 * i, mod - 2) % mod * qpow(2 * i - 1, mod - 2) % mod;
            if (i == n) p2 = 0;
            ans = (ans + (p1 - p2) * A) % mod;
        }
        System.out.print((ans + mod) % mod);
    }

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

    StringTokenizer token;

    String next() {
        while (token == null || !token.hasMoreTokens()) {
            try {
                token = new StringTokenizer(in.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return token.nextToken();
    }

    int nextInt() { return Integer.parseInt(next()); }

    long nextLong() { return Long.parseLong(next()); }
}
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

  $n$ 小两阶就蛮好，但这样 $\mathrm{dp}$ 可以骗到不少分，不过要是在比赛时推导出来但迭代写的有 $\mathrm{bug}$，半天 $\mathrm{de}$ 不出来，心态就会挺炸的。

---

试题 J: 反异或 01 串

时间限制：3.0s 内存限制：512.0MB 本题总分：25 分

【问题描述】

  初始有一个空的 $01$ 串，每步操作可以将 $0$ 或 $1$ 添加在左侧或右侧。也可以对整个串进行反异或操作: 取 $s^{\prime }=s\oplus rev(s)$，其中 $s$ 是目前的 $01$ 串，$\oplus$ 表示逐位异或，$rev(s)$ 代表将 $s$ 翻转，也就是说取中心位置并交换所有对称的两个位置的字符。例如，$rev(0101)=1010rev(010)=010rev(0011)=1100$。

  反异或操作最多使用一次（可以不用，也可以用一次）。

  给定一个 $01$ 串 $T$，问最少需要添加多少个 $1$ 才能从一个空 $01$ 串得到 $T$。在本题中 $0$ 可以添加任意个。

【输入格式】

  输入一行包含一个 $01$ 串表示给定的 $T$。

【输出格式】

  输出一行包含一个整数，表示需要最少添加多少个 $1$。

【样例输入】

00111011
1

【样例输出】

3
1

【评测用例规模与约定】

  对于 $20\%$ 的评测用例，$|T|\le 10$；
  对于 $40\%$ 的评测用例，$|T|\le 500$；
  对于 $60\%$ 的评测用例，$|T|\le 5000$；
  对于 $80\%$ 的评测用例，$|T|\le 10^5$；
  对于所有评测用例，$1\le |T|\le 10^6$，保证 $T$ 中仅含 $0$ 和 $1$。

---

Manacher

---

  如果 $T$ 没有使用反异或操作，那么答案为 $T$ 中 $1$ 的个数 ${\mathrm{count}}_{‘1’}(T)$。如果 $T$ 使用过反异或操作，由于每次添加操作都是发生在两侧，操作后得到的回文串 $T^{\prime }$ 回文性不会被破坏且仍能在 $T$ 中找到。
  于是我们可以考虑将 $T$ 还原到 $T^{\prime }$，构造出 $T^{\prime }[0:\lceil |T^{\prime }|/2\rceil ]$，右侧添加 $\lfloor |T^{\prime }|/2\rfloor$ 个 $0$ 后使用反异或操作，此时答案为 ${\mathrm{count}}_{‘1’}(T)-{\mathrm{count}}_{‘1’}(T^{\prime }[0:\lfloor |T^{\prime }|/2\rfloor ])$，因此找到最大的 ${\mathrm{count}}_{‘1’}(T^{\prime }[0:\lfloor |T^{\prime }|/2\rfloor ])$ 就能使答案最小，算法复杂度和回文串求解相关，于是选用 $\mathrm{Manacher}$ 算法结合前缀和 $O(|T|)$ 求解。
  不过需要注意的是在 $T^{\prime }$ 的长度为奇数时，$T^{\prime }$ 的中位字符为 $1$ 时是非法的，因为反异或操作后该位就变成了 $0$，这一点可以在实现 $\mathrm{Manacher}$ 时在 $T$ 字符间插入 $0$ 字符，然后只记 $0$ 字符的回文串有效即可。

import java.io.BufferedInputStream;
import java.io.IOException;

public class Main {

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

    int[] dp = new int[2000010], sum = new int[2000010];

    byte[] T = new byte[2000010];

    void run() {
        int n = 0, ans = 0;
        while (true) {
            T[++n] = '0';
            sum[n] = sum[n - 1];
            T[++n] = read();
            sum[n] = sum[n - 2] + T[n] - '0';
            if ('1' != (T[n] | 1)) break;
        }
        T[n] = 0x7f;
        for (int i = 1, l = 0, r = 0; i < n; ++i) {
            int k = i > r ? 0 : Math.min(dp[l + r - i], r - i);
            while (T[i - k] == T[i + k]) ++k;
            dp[i] = --k;
            if (T[i] == '0')
                ans = Math.max(ans, sum[i + k] - sum[i]);
            if (i + k > r) {
                r = i + k;
                l = i - k;
            }
        }
        System.out.println(sum[n - 2] - ans);
    }

    BufferedInputStream in = new BufferedInputStream(System.in);

    byte read() {
        try {
            return (byte) in.read();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return -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
44
45
46

  但比赛时 $\mathrm{Manacher}$ 怎么写还真就那个忘了，后缀数组也不会写，胡掐了半个 $\mathrm{Manacher}$ 上去，拿这个压轴是真离谱啊。