2023年第十四届蓝桥杯省赛JavaB组个人题解(AK)_\。1\.m.?n...? )b9.? b9b;.i bm?bo bbb jj. .. !\。 ?\

---

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

2023.4.27：更新 H、J；
2023.4.28：更新 F 正确题解；
2024.2.03：G题hacked，思考ing

---

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);
    	}
    }
1
2
3
4
5
6
7
8
9
10

---

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

---

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
1
2
3
4
5

【样例输出】

4
0
1
2

【提示】

对于第一组数据，答案为 $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);
        }
    }
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

可能写复杂了。。

---

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
1

【样例输出】

22
1

【提示】

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

---

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
1
2
3
4

【样例输出】

4.20
1

【提示】

蜗牛路线：$(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]);
        }
    }
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: 合并区域

时间限制: $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
1
2
3
4
5
6
7
8
9

【样例输出】

15
1

【提示】

第一张图展示了样例中的两块区域的布局。第二张图展示了其中一种最佳的合并方式，此时最大的土地面积为 $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);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149

恶心人的题。

---

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$。

【输出格式】

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

【样例输入1】

7
1 4 2 8 5 7 1
1
2

【样例输出1】

25
1

【样例输入2】

6
12 23 25 25 50 50
1
2

【样例输出2】

150
1

【提示】

小明可以先购买价格 $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$

---

Hacked，以下是原贪心做法

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

---

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
1
2
3

【样例输出】

2 44
1

【提示】
上图显示了两种不同的合并方式。其中节点中标明了每一堆的石子数目，在方括号中标注了当前堆石子的颜色属性。左图的这种合并方式最终剩下了两堆石子，所产生的合并总花费为 $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]);
    }
}
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

---

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
1
2
3

【样例输出】

12
1

【提示】

样例中有 $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=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;
    	}
		@Override
		public int compareTo(node o) {
			// TODO Auto-generated method stub
			long 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);
    }
}

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

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

---

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
1
2
3
4

【样例输出】

2
1

【提示】

样例 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$ 时，表示不使用魔法。

(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))$;
复杂度： $O(n^2)$

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<int[]> q = new LinkedList<>();
    	q.add(new int[]{0,0});
    	while(!q.isEmpty()) {
    		int []p = q.poll();
    		int x=p[0],j=p[1];
    		for(node o:g.get(x)) {
    			int y = o.to,w = o.w;
    			if(j<k){
    			    if(d[y][j+1] > d[x][j]){
    			    d[y][j+1] = d[x][j];
    			    q.add(new int[]{y,j+1});
    			    }
    			}
    			if(j==0||j==k){
    		    	if(d[y][j] > d[x][j]+w){
    			    d[y][j] = d[x][j]+w;
    			    q.add(new int[]{y,j});
    		    	}
    			}
    		}
    	}
    }
    
    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]));
    }
}



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

---

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