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

admin • 2024-03-30 19:52 • Java

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

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

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

试题 A: 特殊日期

本题总分 $： 5$ 分

【问题描述】

记一个日期为

small yy

$yy$ 年

small mm

$mm$ 月

small dd

$dd$ 日，统计从

2000

small 2000

$2000$ 年

small 1

$1$ 月

small 1

$1$ 日到

2000000

small 2000000

$2000000$ 年

small 1

$1$ 月

small 1

$1$ 日，有多少个日期满足年份

small yy

$yy$ 是月份

small mm

$mm$ 的倍数，同时也是

small dd

$dd$ 的倍数。

【答案提交】

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

35813063

朴素解法

考虑到以日为单位计量，时间段的阶并不大，因此直接使用java.time.LocalDate模拟日期变化，判断然后累加，程序在笔者

rm PC

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

倍数法

设函数

(

)

{

∣

f_y(x) = begin{cases} 1 & x,|,y\ 0 & rm otherwise end{cases}

$f_{y} (x) = {10 x ∣ y otherwise$ ，对于正整数

$y$ ，记

d_y

$d_{y}$ 为

∑

(

)

sum_{x=1}^{31}f_y(x)

$\sum_{x = 1 31} f_{y} (x)$ ，

m_y

$m_{y}$ 为

∑

(

)

sum_{x=1}^{12} f_y(x)

$\sum_{x = 1 12} f_{y} (x)$ ，则在不考虑日期是否合法的情况下，答案为

∑

2000

2000000

−

⁡

sum_{y=2000}^{2000000 - 1} operatorname{d}_yoperatorname{m}_y+1

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

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

试题 B: 与或异或

本题总分 $： 5$ 分

【问题描述】

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

：

$：$

图中每个三角形代表着一种门电路，可能是与门、或门、异或门中的任何一种，它接受上一层中的两个圆形中的数据作为输入，产生一个输出值输出到下一级（如图中箭头所示）。图中圆形表示的是暂存的输出结果，取值只可能是

small 0

$0$ 或

small 1

$1$ ，为了便于表示我们用

[

]

[

]

small arr[i][ j]

$a rr [i] [j]$ 表示第

(

≤

)

small i(0 ≤ i ≤ 4)

$i (0 \leq i \leq 4)$ 行第

(

≤

)

small j(0 ≤ j ≤ i)

$j (0 \leq j \leq i)$ 个圆形的值。其中

[

]

(

[

]

[

]

[

]

[

]

[

]

)

small arr[0] = (In[0], In[1], In[2], In[3], In[4])

$a rr [0] = (I n [0], I n [1], I n [2], I n [3], I n [4])$ 表示的是输入数据，对于某个

[

]

[

]

(

≤

)

small arr[i][ j](i ≤ 0)

$a rr [i] [j] (i \leq 0)$ ，计算方式为

[

]

[

]

[

−

]

[

]

[

−

]

[

]

small arr[i][ j] = arr[i − 1][ j] op arr[i − 1][ j + 1]

$a rr [i] [j] = a rr [i - 1] [j] o p a rr [i - 1] [j + 1]$ ，其中

small op

$o p$ 表示的是将

[

−

]

[

]

、

[

−

]

[

]

small arr[i − 1][ j]、arr[i − 1][ j + 1]

$a rr [i - 1] [j] 、 a rr [i - 1] [j + 1]$ 作为输入，将

[

]

[

]

small arr[i][ j]

$a rr [i] [j]$ 作为输出的那个门电路，与门、或门、异或门分别对应于按位与

(

)

small (&)

$(&)$ 、按位或

(

∣

)

small (:|:)

$(∣)$ 、按位异或

(

small (,

$($ ^

)

small ,)

$)$ 运算符。

现在已知输入为

[

]

[

]

[

]

[

]

[

]

small In[0] = 1, In[1] = 0, In[2] = 1, In[3] = 0, In[4] = 1

$I n [0] = 1, I n [1] = 0, I n [2] = 1, I n [3] = 0, I n [4] = 1$ ，小蓝想要使得最终的输出

small Out

$O u t$ 的值为

small 1

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

试题 C: 平均

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

【问题描述】

有一个长度为

small n

$n$ 的数组（

small n

$n$ 是

small 10

$10$ 的倍数），每个数

small a_i

$a_{i}$ 都是区间

[

]

small [0, 9]

$[0, 9]$ 中的整数。小明发现数组里每种数出现的次数不太平均，而更改第

small i

$i$ 个数的代价为

small b_i

$b_{i}$ ，他想更改若干个数的值使得这

small 10

$10$ 种数出现的次数相等（都等于

small frac n{10}

$\frac{n}{10}$ ），请问代价和最少为多少。

【输入格式】

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

small n

$n$ 。

接下来

small n

$n$ 行，第

small i

$i$ 行包含两个整数

small a_i, b_i

$a_{i}, b_{i}$ ，用一个空格分隔。

【输出格式】

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

【样例输入】

【样例输出】

【样例说明】

只更改第

small 1, 2, 4, 5, 7, 8

$1, 2, 4, 5, 7, 8$ 个数，需要花费代价

small 1 + 2 + 4 + 5 + 7 + 8 = 27

$1 + 2 + 4 + 5 + 7 + 8 = 27$ 。

【评测用例规模与约定】

对于

small 20%

$20%$ 的评测用例，

≤

1000

small n ≤ 1000

$n \leq 1000$ ；
对于所有评测用例，

≤

100000

≤

small n ≤ 100000, 0 < bi ≤ 2 × 10^5

$n \leq 100000, 0 < bi \leq 2 \times 1 0^{5}$ 。

贪心

记

[

]

[0, 9]

$[0, 9]$ 中的整数

$x$ 修改为整数

$y$ 的操作为

↦

xxmapsto{c}y

$x c$

y，即花费代价

$c$ 将

$x$ 修改为

$y$ ，如果一个方案中同时出现

↦

、

↦

xxmapsto{c_1}y、yxmapsto{c_2}z

$x c_{1}$

y、yc2

z，那么使用

↦

xxmapsto{c_1}z

$x c_{1}$

z 替换掉这两个操作就能使总代价减小

c_2

$c_{2}$ ，即原方案一定非最优。容易归纳出最优方案中一定不存在长度大于

$1$ 的路径（将

↦

、

↦

xxmapsto{}y、yxmapsto{}z

$x$

y、y

z 看作长度为

$2$ 的路径），那么方案要满足题意只能取每个整数超出目标出现次数

frac n{10}

$\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;
    }
}

实现上可以将

a_i, b_i

$a_{i}, b_{i}$ 用一个整形表示，以减少排序的开销，也可以按

a_i

$a_{i}$ 将

b_i

$b_{i}$ 分类再依次排序。

试题 D: 棋盘

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

【问题描述】

小蓝拥有

small n × n

$n \times n$ 大小的棋盘，一开始棋盘上全都是白子。小蓝进行了

small m

$m$ 次操作，每次操作会将棋盘上某个范围内的所有棋子的颜色取反 (也就是白色棋子变为黑色，黑色棋子变为白色)。请输出所有操作做完后棋盘上每个棋子的颜色。

【输入格式】

输入的第一行包含两个整数

small n, m

$n, m$ ，用一个空格分隔，表示棋盘大小与操作数。

接下来

$m$ 行每行包含四个整数

small x_1, y_1, x_2, y_2

$x_{1}, y_{1}, x_{2}, y_{2}$ ，相邻整数之间使用一个空格分隔，表示将在

small x_1

$x_{1}$ 至

small x_2

$x_{2}$ 行和

small y_1

$y_{1}$ 至

small y_2

$y_{2}$ 列中的棋子颜色取反。

【输出格式】

输出

small n

$n$ 行，每行

small n

$n$ 个

small 0

$0$ 或

small 1

$1$ 表示该位置棋子的颜色。如果是白色则输出

small 0

$0$ ，否则输出

small 1

$1$ 。

【样例输入】

【样例输出】

001
010
100

【评测用例规模与约定】

对于

small 30%

$30%$ 的评测用例，

≤

500

small n m ≤ 500

$n m \leq 500$ ；
对于所有评测用例，

≤

2000

，

≤

，

≤

small 1 ≤ n, m ≤ 2000，1 ≤ x_1 ≤ x_2 ≤ n，1 ≤ y_1 ≤ y_2 ≤ m

$1 \leq n, m \leq 2000 ， 1 \leq x_{1} \leq x_{2} \leq n ， 1 \leq y_{1} \leq y_{2} \leq m$ 。

二维差分

如果我们用数字的奇偶性来表示黑白棋，用

ntimes n

$n \times n$ 大小且元素全为

$0$ 的矩阵来表示初始棋盘，容易发现对棋盘

small x_1

$x_{1}$ 至

small x_2

$x_{2}$ 行和

small y_1

$y_{1}$ 至

small y_2

$y_{2}$ 列中的棋子颜色取反的操作与对矩阵

small x_1

$x_{1}$ 至

small x_2

$x_{2}$ 行和

small y_1

$y_{1}$ 至

small y_2

$y_{2}$ 列中的元素加

$1$ 的操作等价，我们只需要所有操作结束后的棋盘状态，很典型的二维差分问题。
实现上用到了异或运算在相加上不进位与

$0$ 和

$1$ 在

rm ASCII

$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;
    }
}

试题 E: 互质数的个数

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

【问题描述】

给定

small a, b

$a, b$ ，求

≤

small 1 ≤ x < a^b

$1 \leq x < a^{b}$ 中有多少个

small x

$x$ 与

small a^b

$a^{b}$ 互质。由于答案可能很大，你只需要输出答案对

998244353

small 998244353

$998244353$ 取模的结果。

【输入格式】

输入一行包含两个整数分别表示

small a, b

$a, b$ ，用一个空格分隔。

【输出格式】

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

【样例输入 1】

2 5

【样例输出 1】

【样例输入 2】

12 7

【样例输出 2】

11943936

【评测用例规模与约定】

对于

small 30%

$30%$ 的评测用例，

≤

small a^b ≤ 10^6

$a^{b} \leq 1 0^{6}$ ；
对于

small 70%

$70%$ 的评测用例，

≤

，

≤

small a ≤ 10^6，b ≤ 10^9

$a \leq 1 0^{6} ， b \leq 1 0^{9}$ ；
对于所有评测用例，

≤

，

≤

small 1 ≤ a ≤ 10^9，1 ≤ b ≤ 10^{18}

$1 \leq a \leq 1 0^{9} ， 1 \leq b \leq 1 0^{18}$ 。

欧拉函数

欧拉函数是积性函数，其形式为

(

)

varphi(n)

$φ (n)$ ，表示小于等于

$n$ 且与

$n$ 互质的正整数的个数，因此当

a^b =1

$a^{b} = 1$ 时答案为

$0$ （

(

)

varphi(1)=1

$φ (1) = 1$ ），其他情况答案为

(

)

varphi(a^b)

$φ (a^{b})$ 。
依算术基本定理，将

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}

$(p_{1 α_{1}} p_{2 α_{2}} \dots p_{s α_{s}})^{b} = \prod_{i = 1 s} p_{i b \cdot α_{i}}$ ，因为

varphi

$φ$ 是积性函数，有：

(

)

∏

(

⋅

)

∏

⋅

−

(

−

)

∏

⋅

(

−

)

∏

⋅

∏

(

−

)

∏

(

−

)

begin{split} varphi(a^b) &=prod_{i=1}^svarphi(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^bprod_{i=1}^s(1-frac 1{p_i}) end{split}

$φ (a^{b}) = i = 1 \prod s φ (p_{i b \cdot α_{i}}) = i = 1 \prod s p_{i b \cdot α_{i} - 1} (p_{i} - 1) = i = 1 \prod s p_{i b \cdot α_{i}} (1 - \frac{1}{p _{i}}) = i = 1 \prod s p_{i b \cdot α_{i}} i = 1 \prod s (1 - \frac{1}{p _{i}}) = a^{b} i = 1 \prod s (1 - \frac{1}{p _{i}})$ 右连乘式可以通过

$a$ 质因数分解得出，算法复杂度为

(

)

O(alpha+sqrt a)

$O (α + a$

)，其中

(

)

O(alpha)

$O (α)$ 为计算逆元均摊复杂度。

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

试题 F: 阶乘的和

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

【问题描述】

给定

small n

$n$ 个数

small A_i

$A_{i}$ ，问能满足

small m!

$m!$ 为

∑

(

)

small sum_{i=1}^n(A_i!)

$\sum_{i = 1 n} (A_{i}!)$ 的因数的最大的

small m

$m$ 是多少。其中

small m!

$m!$ 表示

small m

$m$ 的阶乘，即

⋅

small 1 × 2 × 3 × · · · × m

$1 \times 2 \times 3 \times \cdot\cdot\cdot \times m$ 。

【输入格式】

输入的第一行包含一个整数

small n

$n$ 。

第二行包含

small n

$n$ 个整数，分别表示

small A_i

$A_{i}$ ，相邻整数之间使用一个空格分隔。

【输出格式】

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

【样例输入】

3
2 2 2

【样例输出】

【评测用例规模与约定】

对于

small 40%

$40%$ 的评测用例，

≤

5000

small n ≤ 5000

$n \leq 5000$ ；
对于所有评测用例，

≤

small 1 ≤ n ≤ 10^5 1 ≤ A_i ≤ 10^9

$1 \leq n \leq 1 0^{5} 1 \leq A_{i} \leq 1 0^{9}$ 。

贪心

如果我们尽可能的合并较小的阶乘，直至无法合并，如

2!+2!+2!=3times2!=3!

$2! + 2! + 2! = 3 \times 2! = 3!$ ，我们取

$3$ 作

$m$ 一定最优，那么这种策略在任何情况都能受用吗？
首先我们将

⋯

A_1, A_2,cdots,A_n

$A_{1}, A_{2}, \dots, A_{n}$ 按升序重排，即我们可以一般性假设

≤

i < j, A_i leq A_j

$i < j, A_{i} \leq A_{j}$ ，当

A_s

$A_{s}$ 无法被合并时，即

count

⁡

(

)

operatorname{count}(A_s) < A_s + 1

$count (A_{s}) < A_{s} + 1$ ，

∑

sum_{i=1}^nA_i=A_s!sum_{i=s}^ncfrac{A_i!}{A_s!}

$\sum_{i = 1 n} A_{i} = A_{s}! \sum_{i = s n} \frac{A _{i} !}{A _{s} !}$ ，此时我们取

A_s

$A_{s}$ 作

$m$ 一定合法，尝试判断

(

)

(A_s+1)!

$(A_{s} + 1)!$ 是否为

∑

sum_{i=1}^nA_i

$\sum_{i = 1 n} A_{i}$ 的因数，等价于

A_s +1

$A_{s} + 1$ 是否为

∑

sum_{i=s}^ncfrac{A_i!}{A_s!}

$\sum_{i = s n} \frac{A _{i} !}{A _{s} !}$ 的因数。
记

$g$ 为第一个值为

A_S +1

$A_{S} + 1$ 的位置，有

∣

(

)

∑

(

)

A_s+1 | (A_s+1)sum_{i=s}^ncfrac{A_i!}{(A_s+1)!}

$A_{s} + 1 ∣ (A_{s} + 1) \sum_{i = s n} \frac{A _{i} !}{( A _{s} + 1 )!}$ ，而

count

⁡

(

)

operatorname{count}(A_s) < A_s + 1

$count (A_{s}) < A_{s} + 1$ 即

∑

−

(

)

count

⁡

(

)

∤

sum_{i=s}^{g - 1}cfrac{A_i!}{(A_s)!} = operatorname{count}(A_s) not| A_s+1

$\sum_{i = s g - 1} \frac{A _{i} !}{( A _{s} )!} = count (A_{s}) \neq ∣ A_{s} + 1$ ，因此

∤

∑

A_s +1 not| sum_{i=s}^ncfrac{A_i!}{A_s!}

$A_{s} + 1 \neq ∣ \sum_{i = s n} \frac{A _{i} !}{A _{s} !}$ ，故

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

试题 G: 小蓝的旅行计划

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

【问题描述】

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

小蓝要依次经过

small n

$n$ 个地点，其中从第

−

small i − 1

$i - 1$ 个地点到达第 i 个地点需要消耗

small Dis_i

$D i s_{i}$ 升油。小蓝经过的每个地点都有一个加油站，但每个加油站的规定也不同。在第

small i

$i$ 个加油站加

small 1

$1$ 升油需要

small Cost_i

$C os t_{i}$ 的费用，且在这个加油站最多只能加

small Lim_i

$L i m_{i}$ 升油。

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

small m

$m$ 升油。

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

−

small −1

$- 1$ 。

【输入格式】

输入的第一行包含两个整数

small n m

$nm$ ，用一个空格分隔。

接下来

small n

$n$ 行每行包含

small 3

$3$ 个整数

small Dis_i Cost_i Lim_i

$D i s_{i} C os t_{i} L i m_{i}$ ，相邻整数之间使用一个空格分隔。

【输出格式】

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

【样例输入】

【样例输出】

【评测用例规模与约定】

对于

small 30%

$30%$ 的评测用例，

≤

300

small n Dis_i Cost_i Lim_i m ≤ 300

$n D i s_{i} C os t_{i} L i m_{i} m \leq 300$ ；
对于

small 60%

$60%$ 的评测用例，

≤

5000

small n Dis_i Cost_i Lim_i m ≤ 5000

$n D i s_{i} C os t_{i} L i m_{i} m \leq 5000$ ；
对于所有评测用例，

≤

，

≤

，

≤

40000

small 1 ≤ n ≤ 2 × 10^5，1 ≤ Dis_i Lim_i m ≤ 10^9，1 ≤ Cost_i ≤ 40000

$1 \leq n \leq 2 \times 1 0^{5} ， 1 \leq D i s_{i} L i m_{i} m \leq 1 0^{9} ， 1 \leq C os t_{i} \leq 40000$ 。

贪心

记某个方案在第

$i$ 个地点的加油站加了

P_i

$P_{i}$ 升油，

P_0=m

$P_{0} = m$ ，

Dis_0=0

$D i s_{0} = 0$ ，记序列

$A$ 为

{

−

}

{a_i=P_i-Dis_{i}}

${a_{i} = P_{i} - D i s_{i}}$ ，

$A$ 的前缀和

$B$ 为

{

∑

(

−

)

}

{b_i=sum_{j=0}^i(P_j-Dis_{j})}

${b_{i} = \sum_{j = 0 i} (P_{j} - D i s_{j})}$ 。
对于题目给定样例，容易找到加油方案

{

}

{m, 1, 5, 2}

${m, 1, 5, 2}$ 花费为

0times 5+1times 9 + 5times 5 + 2times 2 = 38

$0 \times 5 + 1 \times 9 + 5 \times 5 + 2 \times 2 = 38$ ，代入到

$B$ 得出

{

}

{4, 5, 4, 0}

${4, 5, 4, 0}$ ，事实上

$B$ 对应着方案在相应地点的剩余油量，因此

∉

[

]

b_inotin[0,m]

$b_{i} \neq \in [0, m]$ 或

b_i < Dis_{i+1}

$b_{i} < D i s_{i + 1}$ 时方案不可达，

b_{n}=0

$b_{n} = 0$ 时方案一定非最优（在

−

n-1

$n - 1$ 处少加

b_{n}

$b_{n}$ 的油总花费变低且方案依然合法）。
无论如何

Dis

$D i s$ 是不变量，我们可以先计算出

−

-Dis

$- D i s$ 的前缀和，于是对于题目给定样例有

{

−

}

C={-2, -6, -9, -13}

$C = {- 2, - 6, - 9, - 13}$ ，然后顺序遍历，依次使

[

]

B[:i]

$B [: i]$ 的方案合法，等价于使用

[

−

]

P[:i-1]

$P [: i - 1]$ 令

b_i

$b_{i}$ 非零，对

P_j

$P_{j}$ ，

$j$ 则贪心的选择

Cost_j

$C os t_{j}$ 最小的，

P_j

$P_{j}$ 合法的增量是

min

⁡

{

res

⁡

−

max

⁡

{

≤

}

operatorname{min}{operatorname{res}_j, m - operatorname{max}{b_x,jleq x <i}}

$min {res_{j}, m - max {b_{x}, j \leq x < i}}$ ，其中

res

⁡

operatorname{res}_j

$res_{j}$ 为第

$i$ 个地点的加油站的剩余油量，而右侧算式是限制这个增量增加后不会有

$b$ 大于

$m$ 。
下面给出测试用例对应的

$B$ 的变化过程，没看太懂的读者可以自行推导一下。

{

−

}

{-2, -6, -9, -13}

${- 2, - 6, - 9, - 13}$

{

−

}

←

{:,3:,, -1, -4, ,,-8,} gets 5 times Cost_0

${3, - 1, - 4, - 8} \leftarrow 5 \times C os t_{0}$

{

−

}

←

{:,4:,,:,0:,, -3, ,,-7,} gets 1 times Cost_1

${4, 0, - 3, - 7} \leftarrow 1 \times C os t_{1}$

{

−

}

←

{:,4:,,:,3:,,:,0:,, ,,-4,} gets 3 times Cost_2

${4, 3, 0, - 4} \leftarrow 3 \times C os t_{2}$

{

}

←

{:,4:,,:,5:,,:,4:,, ,,:,0:,,} gets 2 times Cost_2 + 2 times Cost_3

${4, 5, 4, 0} \leftarrow 2 \times C os t_{2} + 2 \times C os t_{3}$
证明也很麻烦，就懒得证了，式中

max

⁡

{

}

operatorname{max}{b_i}

$max {b_{i}}$ 和区间加部分则通过线段树完成，最终算法复杂度为

(

log

⁡

)

O(nlog n)

$O (n lo g 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;
    }
}

试题 H: 太阳

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

【问题描述】

这天，小蓝在二维坐标系的点

(

)

small (X, Y)

$(X, Y)$ 上放了一个太阳，看做点光源。

他拿来了

small n

$n$ 条线段，将它们平行于

small x

$x$ 轴放置在了坐标系中，第

small i

$i$ 条线段的左端点在

small x_i, y_i

$x_{i}, y_{i}$ ，长度为

small l_i

$l_{i}$ 。线段之间不会有重合或部分重合的情况（但可能出现端点相交）。小蓝想知道有多少条线段能被太阳照亮（一条线段有长度大于

small 0

$0$ 的部分被照亮就算）。

【输入格式】

输入的第一行包含三个正整数

small n, X, Y

$n, X, Y$ ，相邻整数之间使用一个空格分隔。

接下来

small n

$n$ 行，第

small i

$i$ 行包含三个整数

small x_i, y_i, l_i

$x_{i}, y_{i}, l_{i}$ ，相邻整数之间使用一个空格分隔。

【输出格式】

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

【样例输入】

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

【样例输出】

【评测用例规模与约定】

对于

small 30%

$30%$ 的评测用例，

≤

1000

small n ≤ 1000

$n \leq 1000$ ；
对于所有评测用例，

≤

100000

small 1 ≤ n ≤ 100000

$1 \leq n \leq 100000$ ，

≤

small 0 ≤ x_i, X ≤ 10^7

$0 \leq x_{i}, X \leq 1 0^{7}$ ，

≤

small 0 < y_i ≤ 10^5

$0 < y_{i} \leq 1 0^{5}$ ，

≤

100

small 0 < l_i ≤ 100

$0 < l_{i} \leq 100$ ，

≤

small 10^6 < Y ≤ 10^7

$1 0^{6} < Y \leq 1 0^{7}$ 。

区间覆盖

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

然后将线段投射到

$x$ 轴上：

可以发现问题等价，且

$y$ 是恒等于

$0$ （这里为了方便图示，将光源拉进了一点，线段作了高亮区分），我们直接按

$y$ 降序重排线段，就变成了区间覆盖问题，魔改下线段树

(

log

⁡

)

O(nlog n)

$O (n lo g n)$ 秒杀。
关于线段在

$x$ 轴上的投射，即线段端点与光源点构成的直线的横截距，将

y = 0

$y = 0$ 代入

(

−

)

(

−

)

(y - Y)=k(x - X)

$(y - Y) = k (x - X)$ 可得

−

x =X-cfrac Yk

$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;
    }
}

这类题粪就粪在编码量和变量精度上，不过这里魔改下线段树编码量还算能接受。关于浮点数离散化映射时的精度有许多解决方法，在关系简单时可以用最简分数表示，内存吃紧时可以用最简分数的商表示，这样可以直接使用双等号来判断浮点数是否相同，极大概率下为

rm true

$true$ 的两个浮点型都是由两个相同的分子母计算得出的，或者像本节程序一样在离散表查找

$d$ 时去找

d + rm prec

$d + prec$ 或

d + rm prec

$d + prec$ 的前驱，

rm prec

$prec$ 是精度。
严格来讲只有第一种做法是正确的，但一般在竞赛中不会去

rm hack

$hack$ 精度在

$1 e$

−

$-$

$6$ 以上的程序，结合性能考量我们一般会选择最后一种，心情到了可以水水离散化。

试题 I: 高塔

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

【问题描述】

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

small n

$n$ 回合。

小蓝一开始拥有

small m

$m$ 点能量，在每个回合都有一个值

small A_i

$A_{i}$ 表示小蓝的角色状态。小蓝每回合可以选择消费任意点能量

small C_i

$C_{i}$ (最低消费

small 1

$1$ 点，没有上限)，他在这回合将最多可以向上攀爬

⋅

small A_icdot C_i

$A_{i} \cdot C_{i}$ 层。实际攀爬的层数取决于小蓝自己在这回合的表现，不过最差也会向上爬一层。

当某回合小蓝的能量点数耗尽，那么在完成这个回合后，游戏结束。

small n

$n$ 回合结束后，不管能量还有没有剩余，游戏都会直接结束。

给出小蓝每回合的

small A_i

$A_{i}$ 和自己一开始的能量点数

small m

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

【输入格式】

输入的第一行包含两个整数

small n, m

$n, m$ ，用一个空格分隔。

第二行包含

small n

$n$ 个整数

small A_i

$A_{i}$ ，相邻整数之间使用一个空格分隔，表示小蓝每回合的状态值。

【输出格式】

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

998244353

small 998244353

$998244353$ 取模的结果

【样例输入】

9 15
3 2 5 7 1 4 6 8 3

【样例输出】

392149233

【评测用例规模与约定】

对于

small 40%

$40%$ 的评测用例，

≤

300

，

≤

500

small n ≤ 300，m ≤ 500

$n \leq 300 ， m \leq 500$ ；
对于所有评测用例，

≤

，

≤

，

≤

small 1 ≤ n ≤ 2 × 10^5，n ≤ m ≤ 10^{18}，1 ≤ A_i ≤ 10^9

$1 \leq n \leq 2 \times 1 0^{5} ， n \leq m \leq 1 0^{18} ， 1 \leq A_{i} \leq 1 0^{9}$ 。

组合数学

为了方便讨论，这里先给出一种小蓝在第

$n$ 回合结束游戏的游玩过程数量的计算方法。依题意的，第

$i$ 回合小蓝共消耗了

C_i

$C_{i}$ ，共消耗了

≤

∑

≤

n leqsum_{i=1}^nC_ileq m

$n \leq \sum_{i = 1 n} C_{i} \leq m$ 点能量，第

$i$ 回合有

⋅

A_icdot C_i

$A_{i} \cdot C_{i}$ 总不同的走法，故方案数为：

∑

⋯

≤

∏

∑

⋯

≤

∏

⋅

∏

sum_{substack{c_1,c_2,cdots,c_n > 0\c_1+c_2+cdots+c_nleq m}}prod_{i=1}^nA_iC_i=sum_{substack{c_1,c_2,cdots,c_n > 0\c_1+c_2+cdots+c_nleq m}}prod_{i=1}^nC_icdotprod_{i=1}^nA_i.

$c_{1}, c_{2}, \dots, c_{n} > 0 c_{1} + c_{2} + \dots + c_{n} \leq m \sum i = 1 \prod n A_{i} C_{i} = c_{1}, c_{2}, \dots, c_{n} > 0 c_{1} + c_{2} + \dots + c_{n} \leq m \sum i = 1 \prod n C_{i} \cdot i = 1 \prod n A_{i} .$ 记

(

)

p(n,m)

$p (n, m)$ 为

∑

⋯

≤

∏

sum_{substack{c_1,c_2,cdots,c_n > 0\c_1+c_2+cdots+c_nleq m}}prod_{i=1}^nC_i

$\sum_{c_{1}, c_{2}, \dots, c_{n} > 0 c_{1} + c_{2} + \dots + c_{n} \leq m} \prod_{i = 1 n} C_{i}$ 。因为在小于

$n$ 的回合结束要耗尽能量，所以整理可以知最终答案为：

(

)

∏

∑

−

(

)

−

(

−

)

∏

p(n,m)prod_{i=1}^nA_i+sum_{j=1}^{n-1}(p(j,m) -p(j,m-1))prod_{i=1}^jA_i.

$p (n, m) i = 1 \prod n A_{i} + j = 1 \sum n - 1 (p (j, m) - p (j, m - 1)) i = 1 \prod j A_{i} .$ 因此该思路下，

(

)

p(n,m)

$p (n, m)$ 求解的复杂度与整体直接关联，考虑

$p$ 的边界情况，当

n=1

$n = 1$ 时，

(

)

⋯

(

)

p(1,m) = 1+2+cdots+m=cfrac {m(m+1)}2

$p (1, m) = 1 + 2 + \dots + m = \frac{m ( m + 1 )}{2}$ 。考虑

n+1

$n + 1$ 情况，枚举

C_{n+1}

$C_{n + 1}$ 可能的取值

⋯

−

1,2,cdots m-n

$1, 2, \dots m - n$ ，则有递推式：

(

)

{

⋯

∑

−

(

−

)

≤

p(n,m) = begin{cases} 1+2+cdots+m &n=1 \ sum_{i=1}^{m-n+1} ip(i-1,m-i) &1< nleq m end{cases}.

$p (n, m) = {1 + 2 + \dots + m \sum_{i = 1 m - n + 1} i p (i - 1, m - i) n = 1 1 < n \leq m .$ 观察到

(

)

(

)

p(1,m)=cfrac {m(m+1)}2=C_{m+1}^2

$p (1, m) = \frac{m ( m + 1 )}{2} = C_{m + 1 2}$ ，有

(

)

−

⋯

(

−

)

(

−

⋯

)

(

−

⋯

)

⋯

begin{split} 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{split}.

$p (2, m) = C_{m 2} + 2 C_{m - 1 2} + \dots + (m - 1) C_{22} = (C_{m 2} + C_{m - 1 2} + \dots + C_{22}) + (C_{m - 1 2} + C_{m - 2 2} + \dots + C_{22}) + \dots C_{22} = C_{m + 1 3} + C_{m 3} + \dots + C_{33} = C_{m + 2 4} .$ 类似的，可得关系式

(

)

p(n,m)=C_{n+m}^{2n}

$p (n, m) = C_{n + m 2 n}$ ，故最终答案为：

∏

∑

−

(

−

)

∏

C_{n+m}^{2n}prod_{i=1}^nA_i+sum_{j=1}^{n-1}(C_{j+m}^{2j}-C_{j+m-1}^{2j})prod_{i=1}^jA_i.

$C_{n + m 2 n} i = 1 \prod n A_{i} + j = 1 \sum n - 1 (C_{j + m 2 j} - C_{j + m - 1 2 j}) i = 1 \prod j A_{i} .$ 不对

$p$ 做优化的情况下时间复杂度为

(

log

⁡

)

O(n^2log m)

$O (n^{2} lo g m)$ ，因此

$p$ 的值还需迭代计算，最终复杂度为

(

log

⁡

)

O(nlog m)

$O (n lo g m)$ 。此外，在杨辉三角中我们也可以看到

(

)

、

(

−

)

、

(

−

)

p(n,m)、p(n-1,m-1)、p(n-1,n-1)

$p (n, m) 、 p (n - 1, m - 1) 、 p (n - 1, n - 1)$ 恰围成一个矩形。

大概就是这么个感觉，可以直接考虑

(

)

p(n,i)

$p (n, i)$ 到

(

)

p(n+1,m),i< n

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

$n$ 小两阶就蛮好，但这样

rm dp

$dp$ 可以骗到不少分，不过要是在比赛时推导出来但迭代写的有

rm bug

$bug$ ，半天

rm de

$de$ 不出来，心态就会挺炸的。

试题 J: 反异或 01 串

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

【问题描述】

初始有一个空的

small 01

$01$ 串，每步操作可以将

small 0

$0$ 或

small 1

$1$ 添加在左侧或右侧。也可以对整个串进行反异或操作: 取

′

⊕

(

)

small s^′ = s oplus rev(s)

$s^{'} = s \oplus re v (s)$ ，其中

small s

$s$ 是目前的

small 01

$01$ 串，

⊕

small oplus

$\oplus$ 表示逐位异或，

(

)

small rev(s)

$re v (s)$ 代表将

small s

$s$ 翻转，也就是说取中心位置并交换所有对称的两个位置的字符。例如，

(

0101

)

1010

(

010

)

010

(

0011

)

1100

small rev(0101) = 1010 rev(010) = 010 rev(0011) = 1100

$re v (0101) = 1010 re v (010) = 010 re v (0011) = 1100$ 。

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

给定一个

small 01

$01$ 串

small T

$T$ ，问最少需要添加多少个

small 1

$1$ 才能从一个空

small 01

$01$ 串得到

small T

$T$ 。在本题中

small 0

$0$ 可以添加任意个。

【输入格式】

输入一行包含一个

small 01

$01$ 串表示给定的

small T

$T$ 。

【输出格式】

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

small 1

$1$ 。

【样例输入】

00111011

【样例输出】

【评测用例规模与约定】

对于

small 20%

$20%$ 的评测用例，

∣

≤

small |T| ≤ 10

$∣ T ∣ \leq 10$ ；
对于

small 40%

$40%$ 的评测用例，

∣

≤

500

small |T| ≤ 500

$∣ T ∣ \leq 500$ ；
对于

small 60%

$60%$ 的评测用例，

∣

≤

5000

small |T| ≤ 5000

$∣ T ∣ \leq 5000$ ；
对于

small 80%

$80%$ 的评测用例，

∣

≤

small |T| ≤ 10^5

$∣ T ∣ \leq 1 0^{5}$ ；
对于所有评测用例，

≤

∣

≤

small 1 ≤ |T| ≤ 10^6

$1 \leq ∣ T ∣ \leq 1 0^{6}$ ，保证

small T

$T$ 中仅含

small 0

$0$ 和

small 1

$1$ 。

Manacher

如果

$T$ 没有使用反异或操作，那么答案为

$T$ 中

$1$ 的个数

count

⁡

‘

’

(

)

operatorname{count}_{‘1’}(T)

$count_{‘1’} (T)$ 。如果

$T$ 使用过反异或操作，由于每次添加操作都是发生在两侧，操作后得到的回文串

′

$T^{'}$ 回文性不会被破坏且仍能在

$T$ 中找到。
于是我们可以考虑将

$T$ 还原到

′

$T^{'}$ ，构造出

′

[

⌈

∣

′

∣

⌉

]

T'[0:lceil|,T'|/2rceil]

$T^{'} [0 : ⌈ ∣ T^{'} ∣/2 ⌉]$ ，右侧添加

⌊

∣

′

∣

⌋

lfloor|,T'|/2rfloor

$⌊ ∣ T^{'} ∣/2 ⌋$ 个

$0$ 后使用反异或操作，此时答案为

count

⁡

‘

’

(

)

−

count

⁡

‘

’

(

′

[

⌊

∣

′

∣

⌋

]

)

operatorname{count}_{‘1’}(T) - operatorname{count}_{‘1’}(T'[0:lfloor|,T'|/2rfloor])

$count_{‘1’} (T) - count_{‘1’} (T^{'} [0 : ⌊ ∣ T^{'} ∣/2 ⌋])$ ，因此找到最大的

count

⁡

‘

’

(

′

[

⌊

∣

′

∣

⌋

]

)

operatorname{count}_{‘1’}(T'[0:lfloor|,T'|/2rfloor])

$count_{‘1’} (T^{'} [0 : ⌊ ∣ T^{'} ∣/2 ⌋])$ 就能使答案最小，算法复杂度和回文串求解相关，于是选用

rm Manacher

$Manacher$ 算法结合前缀和

(

∣

)

O(|T|)

$O (∣ T ∣)$ 求解。
不过需要注意的是在

′

$T^{'}$ 的长度为奇数时，

′

$T^{'}$ 的中位字符为

$1$ 时是非法的，因为反异或操作后该位就变成了

$0$ ，这一点可以在实现

rm Manacher

$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;
    }
}

但比赛时

rm Manacher

$Manacher$ 怎么写还真就那个忘了，后缀数组也不会写，胡掐了半个

rm Manacher

$Manacher$ 上去，拿这个压轴是真离谱啊。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。

THE END

二维码

Jenkins安装多个jdk版本，并在项目中选择对应jdk版本

< <上一篇

数据结构之顺序表（C语言版）

下一篇>>

搜索内容

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

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

试题 A: 特殊日期

朴素解法

倍数法

试题 B: 与或异或

深度优先搜索

试题 C: 平均

贪心

试题 D: 棋盘

二维差分

试题 E: 互质数的个数

欧拉函数

试题 F: 阶乘的和

贪心

试题 G: 小蓝的旅行计划

贪心

试题 H: 太阳

区间覆盖

试题 I: 高塔

组合数学

试题 J: 反异或 01 串

Manacher

最新文章

分类

标签云

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

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

试题 A: 特殊日期

朴素解法

倍数法

试题 B: 与或异或

深度优先搜索

试题 C: 平均

贪心

试题 D: 棋盘

二维差分

试题 E: 互质数的个数

欧拉函数

试题 F: 阶乘的和

贪心

试题 G: 小蓝的旅行计划

贪心

试题 H: 太阳

区间覆盖

试题 I: 高塔

组合数学

试题 J: 反异或 01 串

Manacher

最新文章

分类

标签云

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