第十六届蓝桥杯复盘

省赛过去一段时间了，现在复盘下，省赛报完名后一直没准备所以没打算参赛，直到比赛前两天才决定参加，赛前两天匆匆忙忙下载安装了比赛要用的编译器eclipse，当时连编译和运行怎么操作都不知道，平时用的都是idea，就简单熟悉了下输入输出就去比赛了，比赛那天天还没亮，早早出发就去赛点了，赛后也不知ac了多少，结果出来省一等奖进入国赛，这是第一次参加java赛道的，可以说完全没准备，能进国赛靠的是大学打比赛时的基础和运气好，不过大学参加的是cpp组别的，编程语言不一样，但算法思想感觉还是通用的，国赛不打算去参加了，这段时间日夜颠倒，打算出去玩几天缓缓，先去爬个衡山。

1.数位倍数

【问题描述】
 请问在 1 至 202504（含）中，有多少个数的各个数位之和是 5 的整数倍。例如：5、19、8025 都是这样的数。
 
思路：统计每个数字的数位总和，判断是否5的倍数进行累加。

代码

import java.util.*;public class Main {private static StreamTokenizer st =new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));private static PrintWriter out =new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));private static int Int() {try {st.nextToken();} catch (IOException e) {throw new RuntimeException(e);}return (int) st.nval;}private static Long Lon() {try {st.nextToken();} catch (IOException e) {throw new RuntimeException(e);}return (long) st.nval;}private static Double Dou() {try {st.nextToken();} catch (IOException e) {throw new RuntimeException(e);}return st.nval;}private static String Line() {String s = "";try {s = br.readLine();} catch (IOException e) {throw new RuntimeException(e);}return s;}public static void main(String[] args){int ans = 0;for (int i = 1; i <= 202504; i++) {int x = i;int cnt = 0;while (x != 0) {cnt += x % 10;x /= 10;}if (cnt % 5 == 0) {ans++;}}out.println(ans);out.flush();out.close();}
}

答案：40500

2.IPv6

【问题描述】
    小蓝最近在学习网络工程相关的知识。他最近学习到，IPv6 地址本质上是一个 128 位的二进制数，而字符串形式的 IPv6 地址是由被冒号分开的八段 16 进制数组成的，例如，下面每行是一个字符串形式的 IPv6 地址:

0000:0000:0000:0000:0000:0000:0000:0000
0000:0001:0000:0000:0000:0001:0000:0000
0000:0001:00ab:0000:0023:0000:0a00:0e00
0000:0000:00ab:0000:000a:0001:0a00:0e00
0000:0000:00ab:0000:0000:0001:0a00:0e00

其中，每一段最长 4 位，且每一段的前导零都可以去掉（如果 4 位都为 0 需要写成 0）。
另外，IPv6 地址还可以将其中相邻的值为 0 的段合并压缩起来，用两个冒号来表示，不过只能压缩一段。
例如上述地址最短的压缩后的形式分别为

::
0:1::1:0:0
0:1:ab:23:0:a00:e00
::ab:0:a:1:a00:e00
0:0:ab::1:a00:e00

小蓝想知道，所有 IPv6 地址的最短压缩形式的长度的和为多少？由于答案很大（甚至超过了 128 位二进制整数的范围），请填写答案时填写这个总和除以10^9+7的余数。
    
思路： dfs+组合数学，先通过dfs 生成段长度组合，每个段的长度a[i]可取0-4，再计算每段的种类数15×16^(len-1)（15表示非 0 首字符数，16^(len-1)为后面字符数），IPv6码总种类数等于所有段种类数的乘积，然后再计算IPV6码压缩后长度=不压缩前长度-压缩的0序列长度，最终将所有情况的长度进行累加。

代码

import java.io.*;public class Main{private static StreamTokenizer st =new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));private static PrintWriter out =new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));private static int Int() {try {st.nextToken();} catch (IOException e) {throw new RuntimeException(e);}return (int) st.nval;}private static Long Lon() {try {st.nextToken();} catch (IOException e) {throw new RuntimeException(e);}return (long) st.nval;}private static Double Dou() {try {st.nextToken();} catch (IOException e) {throw new RuntimeException(e);}return st.nval;}private static String Line() {String s = "";try {s = br.readLine();} catch (IOException e) {throw new RuntimeException(e);}return s;}private static final int MOD = 1000000007;private static final int N = 8;private static int[] a = new int[N + 1];private static long[] fact = new long[5];private static long ans = 0;public static void main(String[] args) {// 初始化16的幂次数组fact[0] = 1;for (int i = 1; i < 5; i++) {fact[i] = fact[i - 1] * 16 % MOD;}dfs(1);System.out.println(ans);}//dfs生成所有可能的段长度组合private static void dfs(int x) {if (x == N + 1) {// 计算当前组合的总种类数和长度long sum = 1;for (int i = 1; i <= N; i++) {int len = a[i];if (len != 0) {// 计算当前段的种类数：(16-1) * 16^(len-1)sum = sum * fact[len - 1] % MOD;sum = sum * 15 % MOD;}}// 计算当前组合的长度int currentLength = getLength();sum = sum * currentLength % MOD;ans = (ans + sum) % MOD;return;}// 枚举当前段的长度（0-4）for (int i = 0; i <= 4; i++) {a[x] = i;dfs(x + 1);}}//计算当前段组合压缩后的IPv6码长度private static int getLength() {int len = 0; for (int i = 1; i <= N; i++) {if (a[i] == 0) {len++; // 0段计为1个字符} else {len += a[i]; // 非0段计为实际长度}}len += 7; int maxCompress = 0;int left = -1; // 连续0段的左边界for (int right = 1; right <= N; right++) {if (a[right] == 0) {if (left == -1) {left = right; }// 计算当前连续0段的可压缩长度int currentCompress;if (right == N) { if (left == 1) { // 全0压缩currentCompress = 2 * (right - left) - 1;} else {currentCompress = 2 * (right - left);}} else if (left == 1) {currentCompress = 2 * (right - left);} else { // 中间位置的连续0段currentCompress = 2 * (right - left) + 1;}maxCompress = Math.max(maxCompress, currentCompress);} else {left = -1; // 遇到非0段，重置左边界}}return len - maxCompress; // 总长度减去最大压缩长度}
}

答案：905307083

3.变换数组

【问题描述】
    输入一个数组 a ，包含有 n 个元素 a1,a2,…,an。对这个数组进行 m 次变换，每次变换会将数组 a 中的每个元素 ai 转换为 ai · bitCount(ai)。其中 bitCount(x) 表示数字 x 的二进制表示中 1 出现的次数，例如 bitCount(3)=2，因为 3 的二进制表示为 11，其中 1 出现了两次。
    请输出变换之后的数组内容。
【输入格式】
    输入的第一行包含一个正整数 n ，表示数组 a 中的元素个数。
    第二行包含 n 个整数 a1,a2,…,an，相邻整数之间使用一个空格分隔。
    第三行包含一个整数 m，表示变换次数。
【输出格式】
    输出一行，包含 n 个整数，相邻整数之间使用一个空格分隔，表示变换之后得到的数组 a。
【样例输入】

2
5 7
2

【样例输出】

20 63

思路：计算每个元素对应二进制中1的个数，进行相乘即可。

代码

import java.io.*;
import java.util.*;public class Main {private static StreamTokenizer st =new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));private static PrintWriter out =new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));private static int Int() {try {st.nextToken();} catch (IOException e) {throw new RuntimeException(e);}return (int) st.nval;}private static Long Lon() {try {st.nextToken();} catch (IOException e) {throw new RuntimeException(e);}return (long) st.nval;}private static Double Dou() {try {st.nextToken();} catch (IOException e) {throw new RuntimeException(e);}return st.nval;}private static String Line() {String s = "";try {s = br.readLine();} catch (IOException e) {throw new RuntimeException(e);}return s;}static final int N = 1010;static int n, m;static int[] a = new int[N];// 计算数字二进制中1的个数static int count(int x) {int cnt = 0;while (x != 0) {cnt += x % 2;x /= 2;}return cnt;}public static void main(String[] args) {n = Int();for (int i = 1; i <= n; i++) {a[i] = Int();}m = Int();while (m-- > 0) {for (int i = 1; i <= n; i++) {a[i] *= count(a[i]);}}for (int i = 1; i <= n; i++) {out.print(a[i] + " ");}out.flush();out.close();}
}

4.最大数字

【问题描述】
我们有 n 个连续的整数 1,2,3,…,n，可以自由排列它们的顺序。
然后，我们把这些数字转换成二进制表示，按照排列顺序拼接形成一个新的二进制数。
我们的目标是让这个二进制数的值最大，并输出这个二进制对应的十进制表示。
【输入格式】
    输入一行包含一个正整数 n 。
【输出格式】
    输出一行包含一个整数表示答案。
【样例输入】

3

【样例输出】

30

【样例说明】
1 的二进制为 1；2 的二进制为 10；3 的二进制为 11；其组成的最大的二进制数字为 11110，对应的十进制数字为 30。

思路：自定义排序+大数运算，将1 − n 所有数的二进制放入集合后进行排序，然后对排序后的二进制字符串从后往前进行运算转换成10进制。

代码

import java.io.*;
import java.math.BigInteger;
import java.util.*;public class Main {private static StreamTokenizer st =new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));private static PrintWriter out =new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));private static int Int() {try {st.nextToken();} catch (IOException e) {throw new RuntimeException(e);}return (int) st.nval;}private static Long Lon() {try {st.nextToken();} catch (IOException e) {throw new RuntimeException(e);}return (long) st.nval;}private static Double Dou() {try {st.nextToken();} catch (IOException e) {throw new RuntimeException(e);}return st.nval;}private static String Line() {String s = "";try {s = br.readLine();} catch (IOException e) {throw new RuntimeException(e);}return s;}public static void main(String[] args) {int n = Int();List<String> list = new ArrayList<>();for (int i = 1; i <= n; ++i) {list.add(itos(i));}Collections.sort(list,new Comparator<String>() {@Overridepublic int compare(String o1, String o2) {return (o1 + o2).compareTo(o2 + o1) > 0 ? 1 : -1;}});StringBuilder sb = new StringBuilder();for (int i = list.size() - 1; i >= 0; --i) {sb.append(list.get(i));}BigInteger sum = new BigInteger("0");BigInteger d = new BigInteger("1");int len = sb.length();for (int i = len - 1; i >= 0; --i) {if (sb.charAt(i) == '1') {sum = sum.add(d);}d = d.multiply(new BigInteger("2"));}out.println(sum);out.flush();out.close();}public static String itos(int n) {StringBuilder sb = new StringBuilder();while (n != 0) {sb.append(n % 2);n /= 2;}return sb.reverse().toString();}
}

5.小说

【问题描述】

小蓝是一位网络小说家。现在他正在撰写一部新的推理小说，这部小说有 n 个不同的人物。

小说的每一章都有以下三种情节的一种：

A 发现 B 不知道真相。
A 发现 B 知道真相。
A 知道了真相。

为了保证读者的协调和新鲜感，小蓝的小说还要满足以下要求：

“B 发现 A 不知道真相”不能在 “A 知道了真相”后。
“B 发现 A 知道真相”不能在 “A 知道了真相”前。
“B 发现 A 不知道真相”不能在 “B 发现 A 知道真相”后。
相邻的两章情节类型不同，例如如果第一章是 A 发现 B 不知道真相那么第二章就不能是 C 发现 D 不知道真相。
完全相同的情节不能出现两次。

现在小蓝希望知道，他最多能写多少章。
输入的第一行包含一个正整数 n，表示小说人数。
输入

2

输出

6

思路：对于 n 个角色，当 n=1 时，最多可写章节数为为 1；当 n≥2 时，答案为2n^2−3n+4.

分为以下几种情况：
相邻角色：假设角色甲刚知真相，下一个知真相的是角色乙
情况1：除乙外的n−1个角色发现乙不知道真相（共n−1次）
情况2：除甲外的n−1个角色发现甲知道真相（共n−1次）
每对相邻角色有2(n−1)种可能，共n−1对相邻角色，总共有2(n−1)2个情节。
知真相的情况：
情况3：每个角色知道真相对应1个情节，共n个情节
边界处理：
情况4
第一个角色知真相前：只能有情况1
最后一个角色知真相后：只能有情况2，所以边界总共2个情节，最终2n^2−3n+4

代码

import java.io.*;
import java.util.*;public class Test2 {private static StreamTokenizer st =new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));private static PrintWriter out =new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));private static int Int() {try {st.nextToken();} catch (IOException e) {throw new RuntimeException(e);}return (int) st.nval;}private static Long Lon() {try {st.nextToken();} catch (IOException e) {throw new RuntimeException(e);}return (long) st.nval;}private static Double Dou() {try {st.nextToken();} catch (IOException e) {throw new RuntimeException(e);}return st.nval;}private static String Line() {String s = "";try {s = br.readLine();} catch (IOException e) {throw new RuntimeException(e);}return s;}public static void main(String[] args) {long n= Lon();if(n==1){out.println(1);}else{out.println(2*n*n-3*n+4);}out.flush();out.close();}
}

6.01串

【问题描述】
    给定一个由 0,1,2,3…的二进制表示拼接而成的长度无限的 01 串。其前若干位形如 011011100101110111… 。请求出这个串的前 x 位里有多少个 1 。
【输入格式】
    输入的第一行包含一个正整数 x 。
【输出格式】
    输出一行包含一个整数表示答案。
【样例输入】

7

【样例输出】

5

思路：分段统计+位运算，将自然数（0,1,2,3,…）的二进制拼接而成的01 串分为两段处理，分别是前面的完整段和后面的不完整段，先计算有多少个完整的自然数段被完全包含在前x位中，再处理剩余部分，对最后一个不完整的自然数段，统计其中前mod位内的1的个数。

代码

import java.io.*;
import java.util.*;public class Test2 {private static StreamTokenizer st =new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));private static PrintWriter out =new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));private static int Int() {try {st.nextToken();} catch (IOException e) {throw new RuntimeException(e);}return (int) st.nval;}private static Long Lon() {try {st.nextToken();} catch (IOException e) {throw new RuntimeException(e);}return (long) st.nval;}private static Double Dou() {try {st.nextToken();} catch (IOException e) {throw new RuntimeException(e);}return st.nval;}private static String Line() {String s = "";try {s = br.readLine();} catch (IOException e) {throw new RuntimeException(e);}return s;}public static void main(String[] args) {long x = Lon();x--;long res = 0;long i;for (i = 0; ; i++) {long term = (i + 1) * (1L << i);if (x < term) break;x -= term;res += (1L << i);}res += x / (i + 1);long mod = x % (i + 1);long sumResult = getSum(res);long popResult = popCount(res + 1 >> (int) (Math.log(res + 1) / Math.log(2)) - (int) mod + 1);out.println(sumResult + popResult);out.flush();out.close();}//计算二进制中1的个数private static long popCount(long x) {long res = 0;while (x != 0) {res += x & 1;x >>>= 1;}return res;}// 计算所有自然数二进制中1的总个数private static long getSum(long x) {long res = 0;long cnt = 0;x++; // 转换为闭区间[1, x]while (x != 0) {if ((x & 1) != 0) {// 计算当前位为1时的贡献res += (cnt * (1L << (cnt - 1))) + ((1L << cnt) * popCount(x >> 1));}x >>>= 1;cnt++;}return res;}
}

7.甘蔗

【问题描述】
    小蓝种了一排甘蔗，甘蔗共 n 根，第 i 根甘蔗的高度为 ai 。小蓝想砍一些甘蔗下来品尝，但是他有强迫症，不希望甘蔗的高度显得乱糟糟的。具体来说，他给出了一个大小为 m 的整数集合 B = {b1,b2,…,bm} ，他希望在砍完甘蔗后，任意两根相邻的甘蔗之间的高度差 |ai - ai+1| 都要在这个集合 B 中。小蓝想知道他最少需要砍多少根甘蔗（对于高度为 h 的甘蔗，他可以将其砍成 x 高度的甘蔗，x ∈{0,1,2,…,h - 1}）。
【输入格式】
    输入的第一行包含两个正整数 n,m，用一个空格分隔。
    第二行包含 n 个正整数 a1,a2,…,an ，相邻整数之间使用一个空格分隔。
    第三行包含 m 个正整数 b1,b2,…,bm ，相邻整数之间使用一个空格分隔。
【输出格式】
    输出一行包含一个整数表示答案。如果不能满足条件，输出 -1 。
【样例输入】

6 3
6 7 3 4 9 12
2 3 5

【样例输出】

2

【样例说明】

其中一种方案：将 a2 砍为 3，再将 a3 砍为 1。

思路：动态规划，先确定dp表达式， dp[i][j]表示第i根甘蔗在高度为 j时，符合条件时最少需要砍多少根甘蔗，然后确定状态转移方程式，对于每根甘蔗的高度 j 是由前一根甘蔗的 j-b[k] 和 j+b[k] 转移过来，但需要注意这两个状态的高度必须在前一根甘蔗的高度范围内，然后进行初始化，当第一根甘蔗高度为a[1]时dp[1][a[1]] = 0，高度为i (i<a[1])时 dp[1][i] = 1，其余初始化为无穷大。

代码

import java.io.*;
import java.util.*;public class Test2 {private static StreamTokenizer st =new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));private static PrintWriter out =new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));private static int Int() {try {st.nextToken();} catch (IOException e) {throw new RuntimeException(e);}return (int) st.nval;}private static Long Lon() {try {st.nextToken();} catch (IOException e) {throw new RuntimeException(e);}return (long) st.nval;}private static Double Dou() {try {st.nextToken();} catch (IOException e) {throw new RuntimeException(e);}return st.nval;}private static String Line() {String s = "";try {s = br.readLine();} catch (IOException e) {throw new RuntimeException(e);}return s;}public static void main(String[] args) {int n =Int();int m =Int();int[] a = new int[n + 1];int[] b = new int[m + 1];for (int i = 1; i <= n; i++) {a[i] = Int();}for (int i = 1; i <= m; i++) {b[i] = Int();}int[][] dp = new int[n + 1][1001];for(int i = 0;i <= n; ++i){for(int j = 0; j <= 1000; ++j){dp[i][j] = Integer.MAX_VALUE/2;}}dp[1][a[1]] = 0;for (int i = 0; i < a[1]; ++i) {dp[1][i] = 1;}for (int i = 2; i <= n; ++i) {for (int j = 0; j <= a[i]; ++j) {for (int k = 1; k <= m; ++k) {if (j == a[i]) {if (j - b[k] >= 0) dp[i][j] = Math.min(dp[i - 1][j - b[k]], dp[i][j]);if (j + b[k] <= a[i - 1]) dp[i][j] = Math.min(dp[i - 1][j + b[k]], dp[i][j]);} else {if (j - b[k] >= 0) dp[i][j] = Math.min(dp[i - 1][j - b[k]]+1, dp[i][j]);if (j + b[k] <= a[i - 1]) dp[i][j] = Math.min(dp[i - 1][j + b[k]] + 1, dp[i][j]);}}}}int res = dp[n][0];for (int i = 1; i <= a[n]; ++i) {res = Math.min(res, dp[n][i]);}out.println(res == Integer.MAX_VALUE/2 ? -1 : res);out.flush();out.close();}
}

8.原料采购

小蓝负责一家工厂的原料采购。

工厂有一辆运货卡车，其容量为 m。

工厂附近的采购点都在同一条路的同一方向上，一共有 n 个，每个采购点和工厂的距离各不相同。其中，第 i 个采购点的价格为 ai​, 库存为 bi​, 距离为 ci​。

卡车每行驶一单位长度的路径就需要额外花费 o。（返程没有花费，你也可以认为 o 实际是行驶两单位长度的花费）

请计算将卡车装满最少需要花费多少钱，如果没有任何方案可以装满请输出 −1。
输入格式

输入的第一行包含三个正整数 n,m,o，相邻整数之间使用一个空格分隔。

接下来 n 行，每行包含三个正整数 ai​,bi​,ci​ 表示一个采购点，相邻整数之间使用一个空格分隔。
输出格式

输出一行包含一个整数表示答案，即装满卡车所需的最小花费。
输入输出样例

输入

3 5 1
99 9 1
3 4 99
1 2 190

输出

201

思路:贪心+优先队列，使用最大堆将采购点的原料按价格从高到低排序，先从前到后遍历原料装入卡车，当卡车装满后，将遍历到原料的价格与最大堆中堆顶原料的最高价格进行比较，若当前价格低于堆顶原料，则替换堆顶原料，更新总费用，并记录以当前点为最远距离的总费用。

代码

import java.io.*;
import java.util.*;public class Main {private static StreamTokenizer st =new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));private static PrintWriter out =new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));private static int Int() {try {st.nextToken();} catch (IOException e) {throw new RuntimeException(e);}return (int) st.nval;}private static Long Lon() {try {st.nextToken();} catch (IOException e) {throw new RuntimeException(e);}return (long) st.nval;}private static Double Dou() {try {st.nextToken();} catch (IOException e) {throw new RuntimeException(e);}return st.nval;}private static String Line() {String s = "";try {s = br.readLine();} catch (IOException e) {throw new RuntimeException(e);}return s;}static final int MAXN = 1000005;static final long INF = (long) 3e18;static int n, m, o;static long[] a = new long[MAXN];static long[] b = new long[MAXN];static long[] c = new long[MAXN];static long cost, use, sum;static long ans = INF;static class Node implements Comparable<Node> {long price;long wei;public Node(long price, long wei) {this.price = price;this.wei = wei;}@Overridepublic int compareTo(Node x) {return Long.compare(x.price, this.price); // 大顶堆}}public static void main(String[] args) {n = Int();m = Int();o = Int();for (int i = 1; i <= n; i++) {a[i] = Lon();b[i] = Lon();c[i] = Lon();use += b[i];}if (use < m) {out.println(-1);return;}PriorityQueue<Node> q = new PriorityQueue<>();for (int i = 1; i <= n; i++) {if (cost + b[i] <= m) {q.offer(new Node(a[i], b[i]));cost += b[i];sum += (a[i] * b[i]);} else {if (cost < m) {long delta = m - cost;q.offer(new Node(a[i], delta));b[i] -= delta;sum += a[i] * delta;cost = m;}while (!q.isEmpty() && b[i] > 0) {Node u = q.poll();if (u.price <= a[i]) {q.offer(u);break;}if (b[i] >= u.wei) {q.offer(new Node(a[i], u.wei));b[i] -= u.wei;sum -= (u.price - a[i]) * u.wei;} else {q.offer(new Node(a[i], b[i]));q.offer(new Node(u.price, u.wei - b[i]));sum -= (u.price - a[i]) * b[i];b[i] = 0;}}ans = Math.min(ans, sum + c[i] * o);}}out.println(ans);out.flush();out.close();}
}