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

蓝桥杯 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);}}

倍数法

  设函数 fy( x ) = {1 x  ∣  y0 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$，记 dy d_ydy​为 ∑ x = 131fy( x )\sum_{x=1}^{31}f_y(x)∑x=131​fy​(x)， my m_ymy​为 ∑ x = 112fy( x )\sum_{x=1}^{12} f_y(x)∑x=112​fy​(x)，则在不考虑日期是否合法的情况下，答案为 ∑ y = 2000 2000000 − 1 d ⁡y m ⁡y+ 1\sum_{y=2000}^{2000000 – 1} \operatorname{d}_y\operatorname{m}_y+1∑y=20002000000−1​dy​my​+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 分

【问题描述】

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

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

试题 C: 平均

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

【问题描述】

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

【输入格式】

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

  接下来 $n$ 行，第 $i$ 行包含两个整数 a i, b i \small a_i, b_iai​,bi​，用一个空格分隔。

【输出格式】

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

【样例输入】

101 11 21 32 42 52 63 73 83 94 10

【样例输出】

27

【样例说明】

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

【评测用例规模与约定】

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

贪心

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

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

  实现上可以将 ai, bi a_i, b_iai​,bi​ 用一个整形表示，以减少排序的开销，也可以按 ai a_iai​ 将 bi b_ibi​ 分类再依次排序。

试题 D: 棋盘

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

【问题描述】

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

【输入格式】

  输入的第一行包含两个整数 $n,m$，用一个空格分隔，表示棋盘大小与操作数。

  接下来 $m$ 行每行包含四个整数 x 1, y 1, x 2, y 2 \small x_1, y_1, x_2, y_2x1​,y1​,x2​,y2​，相邻整数之间使用一个空格分隔，表示将在 x 1 \small x_1x1​ 至 x 2 \small x_2x2​ 行和 y 1 \small y_1y1​ 至 y 2 \small y_2y2​ 列中的棋子颜色取反。

【输出格式】

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

【样例输入】

3 31 1 2 22 2 3 31 1 3 3

【样例输出】

001010100

【评测用例规模与约定】

  对于 $30\%$ 的评测用例，$nm\le 500$；
 对于所有评测用例， 1≤n,m≤2000，1≤ x 1≤ x 2≤n，1≤ y 1≤ y 2≤m \small 1 ≤ n, m ≤ 2000，1 ≤ x_1 ≤ x_2 ≤ n，1 ≤ y_1 ≤ y_2 ≤ m1≤n,m≤2000，1≤x1​≤x2​≤n，1≤y1​≤y2​≤m。

二维差分

  如果我们用数字的奇偶性来表示黑白棋，用 $n\times n$ 大小且元素全为 $0$ 的矩阵来表示初始棋盘，容易发现对棋盘 x 1 \small x_1x1​ 至 x 2 \small x_2x2​ 行和 y 1 \small y_1y1​ 至 y 2 \small y_2y2​ 列中的棋子颜色取反的操作与对矩阵 x 1 \small x_1x1​ 至 x 2 \small x_2x2​ 行和 y 1 \small y_1y1​ 至 y 2 \small y_2y2​ 列中的元素加 $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;}}

试题 E: 互质数的个数

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

【问题描述】

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

【输入格式】

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

【输出格式】

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

【样例输入 1】

2 5

【样例输出 1】

16

【样例输入 2】

12 7

【样例输出 2】

11943936

【评测用例规模与约定】

  对于 $30\%$ 的评测用例，a b≤1 0 6 \small a^b ≤ 10^6ab≤106；
 对于 $70\%$ 的评测用例， a≤1 0 6，b≤1 0 9 \small a ≤ 10^6，b ≤ 10^9a≤106，b≤109；
 对于所有评测用例， 1≤a≤1 0 9，1≤b≤1 0 18 \small 1 ≤ a ≤ 10^9，1 ≤ b ≤ 10^{18}1≤a≤109，1≤b≤1018。

欧拉函数

  欧拉函数是积性函数，其形式为 $\phi (n)$，表示小于等于 $n$ 且与 $n$ 互质的正整数的个数，因此当 ab= 1a^b =1ab=1 时答案为 $0$（$\phi (1)=1$），其他情况答案为 φ ( ab)\varphi(a^b)φ(ab)。
 依算术基本定理，将 ab a^bab 分解为 ( p1 α 1p2 α 2⋯ ps α s)b= ∏ i = 1spi b  ⋅  αi(p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_s^{\alpha_s})^b=\prod_{i=1}^s p_i^{b\,\cdot\,\alpha_i}(p1α1​​p2α2​​⋯psαs​​)b=∏i=1s​pib⋅αi​​，因为 $\phi$ 是积性函数，有：φ( a b) = ∏ i=1sφ( p i b   ⋅  α i ) = ∏ i=1s p i b   ⋅  α i−1 ( p i−1) = ∏ i=1s p i b   ⋅  α i (1− 1 pi ) = ∏ i=1s p i b   ⋅  α i∏ i=1s(1− 1 pi ) = a b ∏ i=1s(1− 1 pi )\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 ( α + a)O(\alpha+\sqrt a)O(α+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);}}

试题 F: 阶乘的和

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

【问题描述】

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

【输入格式】

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

  第二行包含 $n$ 个整数，分别表示 A i \small A_iAi​，相邻整数之间使用一个空格分隔。

【输出格式】

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

【样例输入】

32 2 2

【样例输出】

3

【评测用例规模与约定】

  对于 $40\%$ 的评测用例，$n\le 5000$；
 对于所有评测用例， 1≤n≤1 0 51≤ A i≤1 0 9 \small 1 ≤ n ≤ 10^5\ 1 ≤ A_i ≤ 10^91≤n≤1051≤Ai​≤109。

贪心

  如果我们尽可能的合并较小的阶乘，直至无法合并，如 $2!+2!+2!=3\times 2!=3!$，我们取 $3$ 作 $m$ 一定最优，那么这种策略在任何情况都能受用吗？
 首先我们将 A1, A2, ⋯  , An A_1, A_2,\cdots,A_nA1​,A2​,⋯,An​ 按升序重排，即我们可以一般性假设 i < j , Ai≤ Aj i < j, A_i \leq A_ji<j,Ai​≤Aj​，当 As A_sAs​ 无法被合并时，即 count ⁡ ( As) < As+ 1\operatorname{count}(A_s) < A_s + 1count(As​)<As​+1， ∑ i = 1nAi= As! ∑ i = snA i! A s!\sum_{i=1}^nA_i=A_s!\sum_{i=s}^n\cfrac{A_i!}{A_s!}∑i=1n​Ai​=As​!∑i=sn​As​!Ai​!​，此时我们取 As A_sAs​ 作 $m$ 一定合法，尝试判断 ( As+ 1 ) !(A_s+1)!(As​+1)! 是否为 ∑ i = 1nAi \sum_{i=1}^nA_i∑i=1n​Ai​ 的因数，等价于 As+ 1A_s +1As​+1 是否为 ∑ i = snA i! A s!\sum_{i=s}^n\cfrac{A_i!}{A_s!}∑i=sn​As​!Ai​!​ 的因数。
 记 $g$ 为第一个值为 AS+ 1A_S +1AS​+1 的位置，有 As+ 1∣( As+ 1 ) ∑ i = snA i!( A s+1)!A_s+1\ |\ (A_s+1)\sum_{i=s}^n\cfrac{A_i!}{(A_s+1)!}As​+1∣(As​+1)∑i=sn​(As​+1)!Ai​!​，而 count ⁡ ( As) < As+ 1\operatorname{count}(A_s) < A_s + 1count(As​)<As​+1 即 ∑ i = s g − 1A i!( A s)! = count ⁡ ( As) ∤As+ 1\sum_{i=s}^{g – 1}\cfrac{A_i!}{(A_s)!} = \operatorname{count}(A_s) \not|\ A_s+1∑i=sg−1​(As​)!Ai​!​=count(As​)∣As​+1，因此 As+ 1 ∤∑ i = snA i! A s!A_s +1 \not|\ \sum_{i=s}^n\cfrac{A_i!}{A_s!}As​+1∣∑i=sn​As​!Ai​!​ ，故 As A_sAs​ 最优。

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 分

【问题描述】

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

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

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

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

【输入格式】

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

  接下来 $n$ 行每行包含 $3$ 个整数 Di s iCos t iLi m i \small Dis_i\ Cost_i\ Lim_iDisi​Costi​Limi​，相邻整数之间使用一个空格分隔。

【输出格式】

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

【样例输入】

4 52 9 24 5 63 2 24 1 3

【样例输出】

38

【评测用例规模与约定】

  对于 $30\%$ 的评测用例， nDi s iCos t iLi m im≤300 \small n\ Dis_i\ Cost_i\ Lim_i\ m ≤ 300nDisi​Costi​Limi​m≤300；
 对于 $60\%$ 的评测用例， nDi s iCos t iLi m im≤5000 \small n\ Dis_i\ Cost_i\ Lim_i\ m ≤ 5000nDisi​Costi​Limi​m≤5000；
 对于所有评测用例， 1≤n≤2×1 0 5，1≤Di s iLi m im≤1 0 9，1≤Cos t i≤40000 \small 1 ≤ n ≤ 2 × 10^5，1 ≤ Dis_i\ Lim_i\ m ≤ 10^9，1 ≤ Cost_i ≤ 400001≤n≤2×105，1≤Disi​Limi​m≤109，1≤Costi​≤40000。

贪心

  记某个方案在第 $i$ 个地点的加油站加了 Pi P_iPi​ 升油， P0= mP_0=mP0​=m， D i s0= 0Dis_0=0Dis0​=0，记序列 $A$ 为 { ai= Pi− D i si}\{a_i=P_i-Dis_{i}\}{ai​=Pi​−Disi​}，$A$ 的前缀和 $B$ 为 { bi= ∑ j = 0i( Pj− D i sj) }\{b_i=\sum_{j=0}^i(P_j-Dis_{j})\}{bi​=∑j=0i​(Pj​−Disj​)}。
 对于题目给定样例，容易找到加油方案 $\{m,1,5,2\}$ 花费为 $0\times 5+1\times 9+5\times 5+2\times 2=38$，代入到 $B$ 得出 $\{4,5,4,0\}$，事实上 $B$ 对应着方案在相应地点的剩余油量，因此 bi∉ [ 0 , m ]b_i\not\in[0,m]bi​∈[0,m] 或 bi< D i s i + 1 b_i < Dis_{i+1}bi​<Disi+1​ 时方案不可达， bn= 0b_{n}=0bn​=0 时方案一定非最优（在 $n-1$ 处少加 bn b_{n}bn​ 的油总花费变低且方案依然合法）。
 无论如何 $Dis$ 是不变量，我们可以先计算出 $-Dis$ 的前缀和，于是对于题目给定样例有 $C=\{-2,-6,-9,-13\}$，然后顺序遍历，依次使 $B[:i]$ 的方案合法，等价于使用 $P[:i-1]$ 令 bi b_ibi​ 非零，对 Pj P_jPj​，$j$ 则贪心的选择 C o s tj Cost_jCostj​ 最小的， Pj P_jPj​ 合法的增量是 min ⁡ {res ⁡j, m − max ⁡ { bx, 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}}，其中 res ⁡j \operatorname{res}_jresj​为第 $i$ 个地点的加油站的剩余油量，而右侧算式是限制这个增量增加后不会有 $b$ 大于 $m$。
 下面给出测试用例对应的 $B$ 的变化过程，没看太懂的读者可以自行推导一下。
 $\{-2,-6,-9,-13\}$
  {   3   , − 1 , − 4 ,   − 8  } ← 5 × C o s t0 \{\:\,3\:\,, -1, -4, \,\,-8\,\} \gets 5 \times Cost_0{3,−1,−4,−8}←5×Cost0​
  {   4   ,   0   , − 3 ,   − 7  } ← 1 × C o s t1 \{\:\,4\:\,,\:\,0\:\,, -3, \,\,-7\,\} \gets 1 \times Cost_1{4,0,−3,−7}←1×Cost1​
  {   4   ,   3   ,   0   ,   − 4  } ← 3 × C o s t2 \{\:\,4\:\,,\:\,3\:\,,\:\,0\:\,, \,\,-4\,\} \gets 3 \times Cost_2{4,3,0,−4}←3×Cost2​
  {   4   ,   5   ,   4   ,     0    } ← 2 × C o s t2+ 2 × C o s t3 \{\:\,4\:\,,\:\,5\:\,,\:\,4\:\,, \,\,\:\,0\:\,\,\} \gets 2 \times Cost_2 + 2 \times Cost_3{4,5,4,0}←2×Cost2​+2×Cost3​
 证明也很麻烦，就懒得证了，式中 max ⁡ { bi}\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;}}

试题 H: 太阳

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

【问题描述】

  这天，小蓝在二维坐标系的点 $(X,Y)$ 上放了一个太阳，看做点光源。

  他拿来了 $n$ 条线段，将它们平行于 $x$ 轴放置在了坐标系中，第 $i$ 条线段的左端点在 x i, y i \small x_i, y_ixi​,yi​，长度为 l i \small l_ili​。线段之间不会有重合或部分重合的情况（但可能出现端点相交）。小蓝想知道有多少条线段能被太阳照亮（一条线段有长度大于 $0$ 的部分被照亮就算）。