2023年第十四届蓝桥杯省赛JavaB组个人题解(AK)

---

之前在dotcpp上发了几个单独题解，现在补一篇完整的吧
P.S. 当天比完，一回去被室友感染甲流发烧躺了一周，。。（喜
今年相较去年，难度有提升（特别是C++），签到题不怎么签到了。脱离捞钱杯？

2023.4.27：更新 H、J；
2023.4.28：更新 F 正确题解；

---

A: 阶乘求和

本题总分：5分

---

【问题描述】

令 $S=1!+2!+3!+...+202320232023!$，求 $S$ 的末尾 9 位数字。 提示：答案首位不为 0。

【答案提交】

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

---

420940313

---

大于$39$后的阶乘都大于$1e9$，遍历即可

    static void solve() {ans=1;long res=1;for(int i=2;i<=39;i++) {res=res*i%(long)1e9;ans =ans+ res;ans%=(long)1e9;System.out.println(ans);}}

---

B: 幸运数字

本题总分：5分

---

【问题描述】

哈沙德数是指在某个固定的进位制当中，可以被各位数字之和整除的正整 数。例如 $126$ 是十进制下的一个哈沙德数，因为 $(126{)}_{10}mod(1+2+6)=0$；$126$ 也是八进制下的哈沙德数，因为 $(126{)}_{10}=(176{)}_8，(126{)}_{10}mod(1+7+6)=0$； 同时 $126$ 也是 $16$ 进制下的哈沙德数，因为 $(126{)}_{10}=(7e{)}_{16}，(126{)}_{10}mod(7+e)=0$。小蓝认为，如果一个整数在二进制、八进制、十进制、十六进制下均为 哈沙德数，那么这个数字就是幸运数字，第 1 至第 10 个幸运数字的十进制表示 为：$1,2,4,6,8,40,48,72,120,\mathrm{126...}$ 。现在他想知道第 2023 个幸运数 字是多少？你只需要告诉小蓝这个整数的十进制表示即可。

【答案提交】

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

---

215040

---

模拟。遍历判断即可

	static boolean check(int i) {int x = i;int mod = 0;while(x>0) {mod+= x%2;x>>=1;}if(i%mod !=0) return false;x=i;mod=0;while(x>0) {mod += x%8;x/=8;}if(i%mod !=0) return false;x=i;mod=0;while(x>0) {mod += x%10;x/=10;}if(i%mod !=0) return false;x=i;mod=0;while(x>0) {mod += x%16;x/=16;}if(i%mod !=0) return false;return true;}static void solve() throws IOException{for(int i=1,cnt=0;;i++) {if(check(i)) cnt++;if(cnt==2023) {System.out.println(i);break;}}}

---

C: 数组分割

时间限制: $1.0s$ 内存限制: $512.0MB$ 本题总分: $10$ 分

---

【问题描述】

小蓝有一个长度为 $N$ 的数组 $A=[A_0,A_1,...,A_{N-1}]$。现在小蓝想要从 $A$ 对应的数组下标所构成的集合 I = { 0 , 1 , 2 , . . . , N − 1 } I = \{0, 1, 2, . . . , N − 1\} I={0,1,2,...,N−1} 中找出一个子集 $R_1$，那么 $R_1$在 $I$ 中的补集为 $R_2$。记 $S_1={\sum }_{r\in R_1}{A}_r，S_2={\sum }_{r\in R2}{A}_r$，我们要求 $S_1$ 和 $S_2$ 均为偶数，请问在这种情况下共有多少种不同的 $R_1$。当 $R_1$ 或 $R_2$ 为空集时我们将 $S_1$ 或 $S_2$ 视为 0。

【输入格式】

第一行一个整数 $T$，表示有 $T$ 组数据。
接下来输入 $T$ 组数据，每组数据包含两行：第一行一个整数 $N$，表示数组 $A$ 的长度；第二行输入 $N$ 个整数从左至右依次为 $A_0,A_1,...,A_{N-1}$，相邻元素之间用空格分隔。

【输出格式】

对于每组数据，输出一行，包含一个整数表示答案，答案可能会很大，你需要将答案对 $1000000007$ 进行取模后输出。

【样例输入】

2
2
6 6
2
1 6

【样例输出】

4
0

【提示】

对于第一组数据，答案为 $4$。（注意：大括号内的数字表示元素在数组中的下标。）
R 1 = { 0 } , R 2 = { 1 } R_1 = \{0\}, R_2 = \{1\} R1​={0},R2​={1}；此时 $S_1=A_0=6$ 为偶数, $S_2=A_1=6$ 为偶数。
R 1 = { 1 } , R 2 = { 0 } R_1 = \{1\}, R_2 = \{0\} R1​={1},R2​={0}；此时 $S_1=A_1=6$ 为偶数, $S_2=A_0=6$ 为偶数。
R 1 = { 0 , 1 } , R 2 = { } R_1 = \{0, 1\}, R_2 = \{\} R1​={0,1},R2​={}；此时 $S_1=A_0+A_1=12$ 为偶数, $S_2=0$ 为偶数。
R 1 = { } , R 2 = { 0 , 1 } R_1 = \{\}, R_2 = \{0, 1\} R1​={},R2​={0,1}；此时 $S_1=0$ 为偶数, $S_2=A_0+A_1=12$ 为偶数。

对于第二组数据，无论怎么选择，都不满足条件，所以答案为 0。

对于 20% 的评测用例，$1\le N\le 10$。
对于 40% 的评测用例，$1\le N\le 10^2$。
对于 100% 的评测用例，$1\le T\le 10,1\le N\le 10^3,0\le A_i\le 10^9$。

---

逆元 + 组合数

---

显然总和为奇的答案为0.
总和为偶数的，统计奇数、偶数个数为ji、ou，预处理组合数按式子计算即可.

化简也是可以的。

    public class Main {static int n,m,mod=(int)1e9+7,maxn=200010;static long ans=0,INF=(long)1e18;static Scanner sc = new Scanner (System.in);public static void main(String[]args) throws IOException{int T = 1;T = sc.nextInt();pre();while(T-->0) solve();}static long fac[] = new long[1002];static long inv[] = new long[1002];static long qpow(long a,long b) {long res = 1;a%=mod;while(b>0) {if(b%2==1) res = res*a%mod;a = a*a%mod;b/=2;}return res;}static void pre() {fac[0] = inv[0] =1;for(int i=1;i<=1000;i++) {fac[i] = fac[i-1]*i%mod;inv[i] = qpow(fac[i],mod-2);}}static void solve() throws IOException{n = sc.nextInt();int a[] = new int [n+1];int ji=0,ou=0, sum=0;for(int i=1;i<=n;i++) {a[i] = sc.nextInt()%2;if(a[i]%2==0) ou++;else ji++;sum+=a[i];}if(sum%2==1) {System.out.println(0);return;}ans = 0;for(int i=0;i<= ji ; i+=2)ans = (ans + fac[ji]*inv[i]%mod *inv[ji-i]%mod)%mod;long res = 0;for(int i=0;i<= ou ; i++) res = (res + fac[ou]*inv[i]%mod *inv[ou-i]%mod)%mod;System.out.println(ans*res%mod);}}

可能写复杂了。。

---

D: 矩形总面积

时间限制: $1.0s$ 内存限制: $512.0MB$ 本题总分: $10$ 分

---

【问题描述】

平面上有个两个矩形 $R_1$ 和 $R_2$，它们各边都与坐标轴平行。设 $(x_1,y_1)$ 和$(x_2,y_2)$ 依次是 $R_1$ 的左下角和右上角坐标，$(x_3,y_3)$ 和 $(x_4,y_4)$ 依次是 $R_2$ 的左下角和右上角坐标，请你计算 $R_1$ 和 $R_2$ 的总面积是多少？
注意：如果 $R_1$ 和 $R_2$ 有重叠区域，重叠区域的面积只计算一次。

【输入格式】

输入只有一行，包含 8 个整数，依次是：$x_1,y_1,x_2,y_2,x_3,y_3,x_4$ 和 $y_4.$

【输出格式】

一个整数，代表答案。

【样例输入】

2 1 7 4 5 3 8 6

【样例输出】

22

【提示】

对于 20% 的数据，$R_1$ 和 $R_2$ 没有重叠区域。
对于 20% 的数据，其中一个矩形完全在另一个矩形内部。
对于 50% 的数据，所有坐标的取值范围是 $[0,10^3]$。
对于 100% 的数据，所有坐标的取值范围是 $[0,10^5]$。

---

分类讨论 or 推结论

---

两种重合讨论，一种是矩形A至少一个角在矩形B内部；另一种是角都不在互相内部，但是中间部分重合了。注意判断完一次后再交换判断一次。
力扣好像有原题，正解是推结论，c++9行好像就写完了（悲

public class Main{static int maxn = 200005,n,m;static long INF = (long)2e18,ans = 0,mod = (int)1e9+7;static Scanner sc = new Scanner (System.in);public static void main(String[]args) throws IOException{int T = 1;while(T-->0) solve();pw.flush();}static long x1,x2,x3,x4,y1,y2,y3,y4;static boolean check1() { // 四角if(x3 <= x2 && x3 >= x1 && y3 <=y2 && y3 >= y1) {ans -= (Math.min(x2, x4)-x3) *(Math.min(y4, y2)-y3);return true;}if(x4 >= x1 && x4 <= x2 && y3 >=y1 && y3 <= y2) {ans -= (x4 - Math.max(x1, x3)) *(Math.min(y4, y2)-y3);return true;}if(x4 >= x1 && x4 <= x2 && y4 >=y1 && y4 <= y2) {ans -= (x4 - Math.max(x1, x3)) *(y4 - Math.max(y1, y3));return true;}if(x3 >= x1 && x3 <= x2 && y4 >=y1 && y4 <= y2) {ans -= (Math.min(x2, x4)-x3) *(y4 - Math.max(y1, y3));return true;}return false;}static void check2() { //四角都不重合在矩形内部if(x1<x3 && x3 <x2 && x4>x1 && x4 < x2) ans -= (x4-x3) *(y2-y1);if(x1>x3 && x1 <x4 && x2 > x3 && x2 < x4)ans -= (x2-x1)*(y4-y3);}static void solve() throws IOException{x1=sc.nextInt();y1=sc.nextInt();x2=sc.nextInt();y2=sc.nextInt();x3=sc.nextInt();y3=sc.nextInt();x4=sc.nextInt();y4=sc.nextInt();ans = (x2-x1)*(y2-y1) + (x4-x3) *(y4-y3);if(check1()) pw.println(ans);else {long t;t=x1;x1=x3;x3=t;t=x2;x2=x4;x4=t;t=y1;y1=y3;y3=t;t=y2;y2=y4;y4=t;if(check1()) pw.println(ans);else {check2();pw.println(ans);}}}
}

---

E: 蜗牛

时间限制: $1.0s$ 内存限制: $512.0MB$ 本题总分: $15$ 分

---

【问题描述】

这天，一只蜗牛来到了二维坐标系的原点。
在 $x$ 轴上长有 $n$ 根竹竿。它们平行于 $y$ 轴，底部纵坐标为 $0$，横坐标分别为 $x_1,x_2,...,x_n$。竹竿的高度均为无限高，宽度可忽略。蜗牛想要从原点走到第 $n$ 个竹竿的底部也就是坐标 $(x_n,0)$。它只能在 $x$ 轴上或者竹竿上爬行，在 $x$ 轴上爬行速度为 $1$ 单位每秒；由于受到引力影响，蜗牛在竹竿上向上和向下爬行的速度分别为 $0.7$ 单位每秒和 $1.3$ 单位每秒。
为了快速到达目的地，它施展了魔法，在第 $i$ 和 $i+1$ 根竹竿之间建立了传送门 $(0<i<n)$，如果蜗牛位于第 $i$ 根竹竿的高度为 $a_i$ 的位置 $(x_i,a_i)$，就可以瞬间到达第 $i+1$ 根竹竿的高度为 $b_{i+1}$ 的位置 $(x_{i+1},b_{i+1})$，请计算蜗牛最少需要多少秒才能到达目的地。

【输入格式】

输入共 $1+n$ 行，第一行为一个正整数 $n$；
第二行为 $n$ 个正整数 $x_1,x_2,...,x_n$；
后面 $n-1$ 行，每行两个正整数 $a_i,b_{i+1}$。

【输出格式】

输出共一行，一个浮点数表示答案（四舍五入保留两位小数）。

【样例输入】

3
1 10 11
1 1
2 1

【样例输出】

4.20

【提示】

蜗牛路线：$(0,0)\to (1,0)\to (1,1)\to (10,1)\to (10,0)\to (11,0)$，
花费时间为 $1+1/0.7+0+1/1.3+1\approx 4.20$

对于 20% 的数据，保证 $n\le 15$；
对于 100% 的数据，保证 $n\le 10^5，a_i,b_i\le 10^4，x_i\le 10^9$。

---

线性dp

---

$dp[i][j]$ 表示蜗牛走到第 $i$ 根杆子的最短用时，$j$ 表示状态。
$j=0$ : 走到杆子底部
$j=1$ ：走到杆子的传送门处
$P.S.$ 由于只与前一个杆子状态有关，其实用两个变量就行，用二维数组便于理解
时间复杂度: $O(n)$

---

    public class Main{static int maxn = 200005,n,m;static long INF = (long)2e18,ans = 0,mod = (int)1e9+7;static Scanner sc = new Scanner (System.in);static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));public static void main(String[]args) throws IOException{int T = 1;//T = Integer.parseInt(S());while(T-->0) solve();pw.flush();}static final int I() throws IOException {st.nextToken();return (int)st.nval;}static void solve() throws IOException{n = sc.nextInt();long x[] = new long [n+1];for(int i=1;i<=n;i++) x[i] = sc.nextInt();int []a = new int [n+1];int []b = new int [n+1];for(int i=1;i<n;i++) {a[i] = sc.nextInt();;b[i] = sc.nextInt();}double dp[][] = new double[n+1][2];dp[1][0] = x[1]; //底端最小用时dp[1][1] = x[1] + a[1] / 0.7;  //传送门用时for(int i=2; i<=n ; i++) {dp[i][0] = Math.min(dp[i-1][0]+x[i]-x[i-1], dp[i-1][1] + b[i-1]/1.3);dp[i][1] = Math.min(dp[i][0] + a[i] / 0.7, dp[i-1][1] + ((b[i-1]>a[i])?(b[i-1]-a[i])/1.3: (a[i]-b[i-1])/0.7));}pw.printf("%.2f",dp[n][0]);}}

---

F: 合并区域

时间限制: $2.0s$ 内存限制: $512.0MB$ 本题总分: $15$ 分

---

【问题描述】

小蓝在玩一款种地游戏。现在他被分配给了两块大小均为 $N\times N$ 的正方形区域。这两块区域都按照 $N\times N$ 的规格进行了均等划分，划分成了若干块面积相同的小区域，其中每块小区域要么是岩石，要么就是土壤，在垂直或者水平方向上相邻的土壤可以组成一块土地。现在小蓝想要对这两块区域沿着边缘进行合并，他想知道合并以后可以得到的最大的一块土地的面积是多少（土地的面积就是土地中土壤小区域的块数）？
在进行合并时，小区域之间必须对齐。可以在两块方形区域的任何一条边上进行合并，可以对两块方形区域进行 $90$ 度、$180$ 度、$270$ 度、$360$ 度的旋转，但不可以进行上下或左右翻转，并且两块方形区域不可以发生重叠。

【输入格式】

第一行一个整数 $N$ 表示区域大小。
接下来 $N$ 行表示第一块区域，每行 $N$ 个值为 $0$ 或 $1$ 的整数，相邻的整数之间用空格进行分隔。值为 $0$ 表示这块小区域是岩石，值为 $1$ 表示这块小区域是土壤。
再接下来 $N$ 行表示第二块区域，每行 $N$ 个值为 $0$ 或 $1$ 的整数，相邻的整数之间用空格进行分隔。值为 $0$ 表示这块小区域是岩石，值为 $1$ 表示这块小区域是土壤。

【输出格式】

一个整数表示将两块区域合并之后可以产生的最大的土地面积。

【样例输入】

4
0 1 1 0
1 0 1 1
1 0 1 0
1 1 1 0
0 0 1 0
0 1 1 0
1 0 0 0
1 1 1 1

【样例输出】

15

【提示】

第一张图展示了样例中的两块区域的布局。第二张图展示了其中一种最佳的合并方式，此时最大的土地面积为 $15$。

对于 30% 的数据，$1\le N\le 5$。
对于 60% 的数据，$1\le N\le 15$。
对于 100% 的数据，$1\le N\le 50$。

---

搜索

---

dotcpp上已更新std。
原先错误std以为只能合并两块，殊不知可以有不止两块合并。

考虑暴力bfs。围绕一块地建图，另一块地在其周围旋转并移动，遍历bfs。遍历至多$4\ast 4\ast 100=1600$次，每次bfs复杂度$O(100\ast 100)$，总复杂度$O(1600\ast 10000)=O(16e6)$.

$2s$内足够了。

import java.io.*;
import java.util.*;public class Main {static int maxn = 200005,n,m;static long INF = (long)2e18,ans = 0,mod = (int)1e9+7;static Scanner sc = new Scanner (System.in);static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer st  =new StreamTokenizer(bf);static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));public static void main(String[]args) throws IOException{int T = 1;while(T-->0) solve();pw.flush();}static final int I() throws IOException {st.nextToken();return (int)st.nval;}static int [][]g = new int [500][500];static int w[][] = new int [55][55];static boolean f[][] = new boolean [500][500];static int x1,x2,y1,y2;static void clear(int a,int b) {for(int i=a;i<a+n ; i++)for(int j=b;j<b+n;j++) g[i][j]=0;}static void add(int a,int b,int op) {if(op == 0) {for(int i=a;i<a+n ; i++)for(int j=b;j<b+n;j++) g[i][j]=w[i-a][j-b];}else if(op == 1) { //逆时针1次for(int j = b,u = 0 ; j <b+n ; j++,u++)for(int i = a+n-1,v=0 ; i>=a ; i--,v++) g[i][j] = w[u][v];}else if(op == 2) { //顺时针1次for(int j = b+n-1,u = 0 ; j>=b ; j--,u++)for(int i = a,v=0 ; i<a+n ; i++,v++) g[i][j] = w[u][v];}else { //倒置for(int i = a+n-1,u = 0 ; i >=a ; i--,u++)for(int j = b+n-1,v=0 ; j>=b ; j--,v++) g[i][j] = w[u][v];}}static void ppp() {System.out.println("graph:");for(int i=x1;i<=x2 ; i++) {for(int j=y1;j<=y2 ; j++) {System.out.print(g[i][j]+" ");}System.out.println();}}static int x[] = {1,-1,0,0};static int y[] = {0,0,1,-1};static int bfs(int aa,int bb) {Queue<Integer> q = new LinkedList<>();q.add(aa*1000+bb);int res=0;while(!q.isEmpty()) {int k = q.poll();int a = k/1000,b=k%1000;if(f[a][b]) continue;res++;f[a][b]=true;for(int i=0;i<4;i++) {int xx = a+x[i],yy = y[i]+b;if(xx>=x1 && xx<=x2 && yy>=y1 && yy <=y2 && !f[xx][yy] && g[xx][yy] == 1)q.add(xx*1000+yy);}}return res;}static void work() {int res = 0;for(int u = x1 ; u <= x2 ; u++)for(int v=y1;v<=y2 ; v++) f[u][v]=false;for(int u = x1 ; u <= x2 ; u++)for(int v=y1;v<=y2 ; v++)if(g[u][v] == 1 && !f[u][v]) {res = Math.max(res, bfs(u,v));}m=res;ans = Math.max(ans, res);}static void solve() throws IOException{n = I();for(int i = 60 ; i<60+n ; i++) //第一块区域固定，左上角为 (60,60)for(int j = 60 ; j<60+n ; j++)g[i][j] = I();for(int i = 0;i<n ; i++)for(int j = 0 ; j <n ; j++)w[i][j] = I();for(int i = 60-n+1 ; i <= 60+n-1 ; i++) { //上for(int j=0;j<4;j++) {add(60-n,i,j);x1 =60-n;y1 = Math.min(60, i); x2 = 60+n-1; y2 = Math.max(60+n-1, i+n-1);//ppp();work();//System.out.println(m);clear(60-n,i);}}for(int i = 60-n+1 ; i <= 60+n-1 ; i++) { //下for(int j=0;j<4;j++) {add(60+n,i,j);x1 =60;y1 = Math.min(60, i); x2 = 60+2*n-1; y2 = Math.max(60+n-1, i+n-1);//ppp();work();//System.out.println(m);clear(60+n,i);}}for(int i = 60-n+1 ; i <= 60+n-1 ; i++) { //左for(int j=0;j<4;j++) {add(i,60-n,j);x1 =Math.min(i, 60);y1 = 60-n; x2 = Math.max(i+n-1, 60+n-1); y2 = 60+n-1;//ppp();work();//System.out.println(m);clear(i,60-n);}}for(int i = 60-n+1 ; i <= 60+n-1 ; i++) { //右for(int j=0;j<4;j++) {add(i,60+n,j);x1 =Math.min(i, 60);y1 = 60; x2 = Math.max(i+n-1, 60+n-1); y2 = 60+2*n-1;//ppp();work();//System.out.println(m);clear(i,60+n);}}pw.println(ans);}
}

恶心人的题。

---

G: 买二赠一

时间限制: $1.0s$ 内存限制: $512.0MB$ 本题总分: $20$ 分

---

【问题描述】

某商场有 $N$ 件商品，其中第 $i$ 件的价格是 $A_i$。现在该商场正在进行 “买二赠一” 的优惠活动，具体规则是：
每购买 $2$ 件商品，假设其中较便宜的价格是 $P$（如果两件商品价格一样，则 $P$ 等于其中一件商品的价格），就可以从剩余商品中任选一件价格不超过 $P/2$ 的商品，免费获得这一件商品。可以通过反复购买 $2$ 件商品来获得多件免费商品，但是每件商品只能被购买或免费获得一次。

小明想知道如果要拿下所有商品（包含购买和免费获得），至少要花费多少钱？

【输入格式】

第一行包含一个整数 $N$。
第二行包含 $N$ 个整数，代表 $A_1,A_2,A_3,...,A_N$。

【输出格式】

输出一个整数，代表答案。

【样例输入】

7
1 4 2 8 5 7 1

【样例输出】

25

【提示】

小明可以先购买价格 $4$ 和 $8$ 的商品，免费获得一件价格为 $1$ 的商品；再后买价格为 $5$ 和 $7$ 的商品，免费获得价格为 $2$ 的商品；最后单独购买剩下的一件价格为 $1$ 的商品。总计花费 $4+8+5+7+1=25$。不存在花费更低的方案。
对于 30% 的数据，$1\le N\le 20$。
对于 100% 的数据，$1\le N\le 5\times 10^5，1\le Ai\le 10^9$

---

贪心+二分

---

先排序，每次贪心地选最大的没买/赠的物品$a,b$，然后选剩下的的最大不超过$min(a/2,b/2)$的物品，赠送的物品的价值显然不会增大，故可以二分。

    import java.util.*;import java.io.*;public class Main {static int n,m,mod=(int)1e9+7,maxn=500010;static long ans=0,INF=(long)1e18;static Scanner sc = new Scanner (System.in);static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer st = new StreamTokenizer(bf);static PrintWriter pw = new PrintWriter(System.out);public static void main(String[]args) throws IOException{int T = 1;//T = I();while(T-->0) solve();pw.flush();}static int I() throws IOException{st.nextToken();return (int)st.nval;}static int a[] = new int [maxn];static boolean f[] = new boolean [maxn];static int find(int x) {int l=1,r=n;int res =0;while(l<=r) {int mid = (l+r)/2;if(f[mid]) { //先前赠送过，跳到左边r=mid-1;continue;}if(a[mid] <= x) {res = Math.max(res, mid);l = mid+1;}else r = mid-1; }return res;}static void solve() throws IOException{n = I();for(int i=1 ;i<=n;i++) a[i]  =I();Arrays.sort(a,1,n+1);int t = 0;for(int i=n;i>=1;i--) {if(f[i]) continue;//赠送过，跳过ans += a[i];t++;if(t == 2) {t=0;int id = find(a[i]/2);if(id>0) f[id]=true;}}pw.println(ans);}}

---

H: 合并石子

时间限制: $1.0s$ 内存限制: $512.0MB$ 本题总分: $20$ 分

---

【问题描述】

在桌面从左至右横向摆放着 $N$ 堆石子。每一堆石子都有着相同的颜色，颜色可能是颜色 $0$，颜色 $1$ 或者颜色 $2$ 中的其中一种。
现在要对石子进行合并，规定每次只能选择位置相邻并且颜色相同的两堆石子进行合并。合并后新堆的相对位置保持不变，新堆的石子数目为所选择的两堆石子数目之和，并且新堆石子的颜色也会发生循环式的变化。具体来说：两堆颜色 $0$ 的石子合并后的石子堆为颜色 $1$，两堆颜色 $1$ 的石子合并后的石子堆为颜色 $2$，两堆颜色 $2$ 的石子合并后的石子堆为颜色 $0$。本次合并的花费为所选择的两堆石子的数目之和。
给出 $N$ 堆石子以及他们的初始颜色，请问最少可以将它们合并为多少堆石子？如果有多种答案，选择其中合并总花费最小的一种，合并总花费指的是在所有的合并操作中产生的合并花费的总和。

【输入格式】

第一行一个正整数 $N$ 表示石子堆数。
第二行包含 $N$ 个用空格分隔的正整数，表示从左至右每一堆石子的数目。
第三行包含 $N$ 个值为 $0$ 或 $1$ 或 $2$ 的整数表示每堆石头的颜色。

【输出格式】

一行包含两个整数，用空格分隔。其中第一个整数表示合并后数目最少的石头堆数，第二个整数表示对应的最小花费。

【样例输入】

5
5 10 1 8 6
1 1 0 2 2

【样例输出】

2 44

【提示】
上图显示了两种不同的合并方式。其中节点中标明了每一堆的石子数目，在方括号中标注了当前堆石子的颜色属性。左图的这种合并方式最终剩下了两堆石子，所产生的合并总花费为 $15+14+15=44$；右图的这种合并方式最终也剩下了两堆石子，但产生的合并总花费为 $14+15+25=54$。综上所述，我们选择合并花费为 $44$ 的这种方式作为答案。
对于 30% 的评测用例，$1\le N\le 10$。
对于 50% 的评测用例，$1\le N\le 50$。
对于 100% 的评测用例，$1\le N\le 300,1\le$ 每堆石子的数目 $\le 1000$。

---

区间dp

---

石子合并裸题。

设 $dp[i][j][col]$ 为 合并区间 $[i,j]$ 为一堆，且颜色为 $col$ 的最小花费，有转移式：
$$dp[i][j][(col+1)\%3]=min(dp[i][j][(col+1)\%3],dp[i][k][col]+dp[k+1][j][col]+sum[i][j])$$ 其中 $sum[i][j]$ 为区间 $[i,j]$ 内石子总数。

为统计最小堆数，设$num[i][j]$为操作合并区间$[i,j]$后的最小堆数，初始化为区间长度；更新$dp[i][j]$的同时，更新$num[i][j]=1$，即合并为1堆。

为统计总共最小花费，设为$cost[i][j]$，初始化 $[i,j]$区间能合并为一堆的花费为$min(dp[i][j][col])$，其他不能合并为1堆的花费初始化为0（因为没有合并，就不用花费），然后用类似$floyd$的算法转移即可。
复杂度：$O(3\ast n^3)$

import java.io.*;
import java.util.*;
public class Main{static int maxn = 200005,n,m,inf=(int)1e9;static long INF = (long)2e18,ans = 0,mod = (int)1e9+7;static Scanner sc = new Scanner (System.in);static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer st  =new StreamTokenizer(bf);static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));public static void main(String[]args) throws IOException{int T = 1;while(T-->0) solve();pw.flush();}static final int I() throws IOException {st.nextToken();return (int)st.nval;}static int dp[][][] = new int [303][303][3];static int num[][] = new int [303][303];static int a[] = new int [301];static int sum[] = new int [301]; //前缀和static int c[] = new int [301];static int cost[][] = new int [303][303];static void solve() throws IOException{n= I();for(int i=1;i<=n;i++)for(int j=i;j<=n;j++) {num[i][j]=j-i+1;for(int k=0;k<3;k++) dp[i][j][k]=inf;}for(int i=1;i<=n;i++) {a[i] = I();sum[i]=a[i]+sum[i-1]; //前缀和，方便统计区间}for(int i=1;i<=n;i++) {c[i] = I();//颜色dp[i][i][c[i]] = 0; //初始石子堆花费显然为0}for(int len=1;len<=n;len++)for(int i=1;i+len-1<=n;i++) {int j=i+len-1;for(int col=0;col<3;col++) {int min = inf;for(int k=i;k<j;k++) {if(dp[i][k][col]!=inf && dp[k+1][j][col]!=inf) {min = Math.min(min, dp[i][k][col] + dp[k+1][j][col]);}}if(min==inf) continue;num[i][j]=1;dp[i][j][(col+1)%3] = Math.min(dp[i][j][(col+1)%3], min+sum[j]-sum[i-1]);cost[i][j] = Math.min(dp[i][j][0], Math.min(dp[i][j][1], dp[i][j][2]));}}for(int k=1;k<=n;k++) for(int i=1;i<=k;i++)for(int j=k+1;j<=n;j++) {if(num[i][j] > num[i][k] + num[k+1][j]) {num[i][j] = num[i][k] + num[k+1][j];cost[i][j] = cost[i][k]+cost[k+1][j];}else if(num[i][j] == num[i][k] + num[k+1][j]) {cost[i][j] = Math.min(cost[i][j], cost[i][k]+cost[k+1][j]);}}pw.println(num[1][n]+" "+cost[1][n]);}
}

---

I: 最大开支

时间限制: $1.0s$ 内存限制: $512.0MB$ 本题总分: $25$ 分

---

【问题描述】

小蓝所在学校周边新开业了一家游乐园，小蓝作为班长，打算组织大家去游乐园玩。已知一共有 $N$ 个人参加这次活动，游乐园有 $M$ 个娱乐项目，每个项目都需要买门票后才可进去游玩。门票的价格并不是固定的，团购的人越多单价越便宜，当团购的人数大于某个阈值时，这些团购的人便可以免费进入项目进行游玩。这 $M$ 个娱乐项目是独立的，所以只有选择了同一个项目的人才可
以参与这个项目的团购。第 i 个项目的门票价格 $H_i$ 与团购的人数 $X$ 的关系可以看作是一个函数：$H_i(X)=max(K_i\times X+B_i,0)$
$max$ 表示取二者之中的最大值。当 $H_i=0$ 时说明团购人数达到了此项目的免单阈值。
这 $N$ 个人可以根据自己的喜好选择 $M$ 个娱乐项目中的一种，或者有些人对这些娱乐项目都没有兴趣，也可以选择不去任何一个项目。每个人最多只会选择一个娱乐项目，如果多个人选择了同一个娱乐项目，那么他们都将享受对应的团购价格。小蓝想知道他至少需要准备多少钱，使得无论大家如何选择，他都有能力支付得起所有 $N$ 个人购买娱乐项目的门票钱。

【输入格式】

第一行两个整数 $N$、$M$，分别表示参加活动的人数和娱乐项目的个数。
接下来 $M$ 行，每行两个整数，其中第 $i$ 行为 $K_i、B_i$，表示第 i 个游乐地点的门票函数中的参数。

【输出格式】

一个整数，表示小蓝至少需要准备多少钱，使得大家无论如何选择项目，自己都支付得起。

【样例输入】

4 2
-4 10
-2 7

【样例输出】

12

【提示】

样例中有 $4$ 个人，$2$ 个娱乐项目，我们用一个二元组 $(a,b)$ 表示 $a$ 个人选择了第一个娱乐项目，$b$ 个人选择了第二个娱乐项目，那么就有 $4-a-b$ 个人没有选择任何项目，方案 $(a,b)$ 对应的门票花费为 $max(-4\times a+10,0)\times a+max(-2\times b+7,0)\times b$，所有的可能如下所示：

a	b	花费
0	0	0
0	1	5
0	2	6
0	3	3
0	4	0
1	0	6
1	1	11
1	2	12
1	3	9
2	0	4
2	1	9
2	2	10
3	0	0
3	1	5
4	0	0

其中当 $a=1$, $b=2$ 时花费最大，为 $12$。此时 $1$ 个人去第一个项目，所以第一个项目的单价为 $10-4=6$，在这个项目上的花费为 $6\times 1=6$；$2$ 个人去第二个项目，所以第二个项目得单价为 $7-2\times 2=3$，在这个项目上的花费为$2\times 3=6$；还有 $1$ 个人没去任何项目，不用统计；总花费为 $12$，这是花费最大的一种方案，所以答案为 $12$。
对于 30% 的评测用例，$1\le N,M\le 10$。
对于 50% 的评测用例，$1\le N,M\le 1000$。
对于 100% 的评测用例，$1\le N,M,B_i\le 10^5，-10^5\le K_i<0。$

---

贪心 + 优先队列

---

将所有项目扔到堆里，按项目游玩人数＋1 的开支变化量降序排序，贪心取变化最大的即可。
变化量小于等于 0 时退出循环。

import java.io.*;
import java.util.*;
public class Main{static int maxn = 200005,n,m;static long INF = (long)2e18,ans = 0,mod = (int)1e9+7;static Scanner sc = new Scanner (System.in);static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer st  =new StreamTokenizer(bf);static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));public static void main(String[]args) throws IOException{int T = 1;while(T-->0) solve();pw.flush();}static final int I() throws IOException {st.nextToken();return (int)st.nval;}static class node implements Comparable<node>{long k=0,b=0;int num=0;public node(long a,long bb) {k=a;b=bb;}@Overridepublic int compareTo(node o) {// TODO Auto-generated method stublong x = (this.num+1)*Math.max(0, k*(num+1)+b) - num*Math.max(0, k*num+b);long y =  (o.num+1)*Math.max(0, o.k*(o.num+1)+o.b) - o.num*Math.max(0, o.k*o.num+o.b);return x<y?1:-1;}}static void solve() throws IOException{n=I();m=I();PriorityQueue<node> q = new PriorityQueue<>();for(int i=0;i<m;i++) {long k=I(),b=I();q.add(new node(k,b));}while(n-->0) {node o = q.poll();if((o.num+1)*Math.max(0, o.k*(o.num+1)+o.b) - o.num*Math.max(0, o.k*o.num+o.b)<=0) {q.add(o);break;}o.num++;q.add(o);}while(!q.isEmpty()) {node o = q.poll();ans += o.num*Math.max(0, o.k*o.num+o.b);}pw.println(ans);}
}

借用肖哥一句话：为什么就不能把贪心从考纲里划掉呢？(滑稽

---

J: 魔法阵

时间限制: $1.0s$ 内存限制: $512.0MB$ 本题总分: $25$ 分

---

【问题描述】

魔法师小蓝为了营救自己的朋友小 $Q$，来到了敌人布置的魔法阵。魔法阵可以看作是一幅具有 $N$ 个结点 $M$ 条边的无向图，结点编号为 $0,1,2,...,N-1$，图中没有重边和自环。敌人在每条边上都布置了陷阱，每条边都有一个伤害属性 $w$，每当小蓝经过一条边时就会受到这条边对应的 $w$ 的伤害。小蓝从结点 0出发，沿着边行走，想要到达结点 $N-1$ 营救小 $Q$。
小蓝有一种特殊的魔法可以使用，假设一条路径按照顺序依次经过了以下 $L$ 条边：$e_1,e_2,...,e_L$（可以出现重复的边），那么期间小蓝受到的总伤害就是 $P={\sum }_{i=1}^{L}w(e_i)$，$w(e_i)$ 表示边 $e_i$ 的伤害属性。如果 $L\ge K$，那么小蓝就可以从这 $L$条边当中选出连续出现的$K$条边 $e_c,e_{c+1},...,e_{c+K-1}$ 并免去在这 $K$ 条边行走期间所受到的伤害，即使用魔法之后路径总伤害变为 $P^{\prime }=P-{\sum }_{i=c}^{c+K-1}w(e_i)$。
注意必须恰好选出连续出现的 $K$ 条边，所以当 $L<K$ 时无法使用魔法。
小蓝最多只可以使用一次上述的魔法，请问从结点 $0$ 出发到结点 $N-1$ 受到的最小伤害是多少？题目保证至少存在一条从结点 $0$ 到 $N-1$ 的路径。

【输入格式】

第一行输入三个整数，$N$, $K$, $M$，用空格分隔。
接下来 $M$ 行，每行包含三个整数 $u,v,w$，表示结点 $u$ 与结点 $v$ 之间存在一条伤害属性为 $w$ 的无向边。

【输出格式】

输出一行，包含一个整数，表示小蓝从结点 $0$ 到结点 $N-1$ 受到的最小伤害。

【样例输入】

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

【样例输出】

2

【提示】

样例 1，存在路径：$0\to 1\to 2\to 3，K=2$，如果在 $0\to 1\to 2$ 上使用魔法，那么答案就是 $0+0+4=4$；如果在 $1\to 2\to 3$ 上使用魔法，那么答案就是 $2+0+0=2$。再也找不到比 $2$ 还小的答案了，所以答案就是 $2$。

对于 30% 的评测用例，$1\le N\le 20$。
对于 50% 的评测用例，$1\le N\le 100$。
对于 100% 的评测用例，$1\le N\le 1000,1\le M\le N\times (N-1)/2，1\le K\le 10，0\le u,v\le N-1，1\le w\le 1000$

---

最短路+简单dp

---

同比C++压轴题，似乎容易了些。（至少比去年好，超级大模拟，哪里来的天才出题人）

设$dp[i][j]$ 表示从 $0$ 跑到 $i$ ，且消除 $j$ 条连续边伤害的最小伤害。显然 $j=0$ 时，表示不使用魔法。

在 $Dijkstra$ 算法中，每次从未确定最短路的结点中选择距离起点最近的结点 $u$，然后更新与 $u$ 相邻的结点的最短路，总复杂度差不多为 $O(n^2)$。对于每个相邻结点 $v$，我们需要考虑三种情况：

(1) 如果不使用魔法，显然是普通最短路算法。若当前路径长度 $dp[u][0]+w(u,v)<dp[v][0]$，那么更新 $dp[v][0]=dp[u][0]+w(u,v)$，表示不使用魔法的最小伤害。
(2) 使用魔法，有转移式：$dp[v][j]=min(dp[v][j],dp[u][j-1])$;
(3) 已经连续消除 $k$ 条边的伤害，正常转移：$dp[v][k]=min(dp[v][k],dp[u][k]+w(u,v))$;

小蓝继续努力吧。

import java.io.*;
import java.util.*;
public class Main{static int maxn = 200005,n,m,inf=(int)1e9;static long INF = (long)2e18,ans = 0,mod = (int)1e9+7;static Scanner sc = new Scanner (System.in);static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer st  =new StreamTokenizer(bf);static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));public static void main(String[]args) throws IOException{int T = 1;while(T-->0) solve();pw.flush();}static final int I() throws IOException {st.nextToken();return (int)st.nval;}static class node{int to;int w;public node(int a,int b) {to=a;w=b;}}static Vector<Vector<node>> g =new Vector<>();static int k=0;static int d[][] = new int [1001][11];static int cnt=0;static void dij() {for(int i=0;i<n;i++)for(int j=0;j<=k;j++) d[i][j] = inf;d[0][0]=0;Queue<Integer> q = new LinkedList<>();q.add(0);while(!q.isEmpty()) {int x = q.poll();for(node o:g.get(x)) {int y = o.to,w = o.w;boolean f = false;if(d[y][0] > d[x][0]+w) {d[y][0] = d[x][0]+w;f=true;}for(int j=1;j<=k;j++) {if(d[y][j] > d[x][j-1]) {d[y][j] = d[x][j-1];f=true;}}if(d[y][k] > d[x][k]+w) {f=true;d[y][k] = d[x][k]+w;}if(f) q.add(y);}}}static void solve() throws IOException{n=I();k=I();m=I();for(int i=0;i<n;i++) g.add(new Vector<>());while(m-->0) {int u=I(),v=I(),w=I();g.get(u).add(new node(v,w));g.get(v).add(new node(u,w));}dij();pw.println(Math.min(d[n-1][0], d[n-1][k]));}
}

---

制作不易，喜欢的话点个赞吧！谢谢~