第十四届蓝桥杯三月真题刷题训练——第 3 天
目录
题目1：门牌制作
题目描述
运行限制
代码：
题目2：货物摆放_long
题目描述
答案提交
运行限制
代码：
题目3：跳跃_dp
题目描述
输入描述
输出描述
输入输出样例
运行限制
代码：
题目4：重新排序_差分数组
问题描述
输入格式
输出格式
样例输入
样例输出
样例说明
评测用例规模与约定
运行限制
未满分代码：
差分数组满分代码：
题目1：门牌制作
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
小蓝要为一条街的住户制作门牌号。
这条街一共有 2020 位住户，门牌号从 1 到 2020 编号。
小蓝制作门牌的方法是先制作 0 到 9 这几个数字字符，最后根据需要将字符粘贴到门牌上，例如门牌 1017 需要依次粘贴字符 1、0、1、7，即需要 1 个字符 0，2 个字符 1，1 个字符 7。
请问要制作所有的 1 到 2020 号门牌，总共需要多少个字符 2？
运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
代码：
package 第十四届蓝桥杯三月真题刷题训练.day3;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
/**
* @author yx
* @date 2023-03-06 8:36
*/
public class 门牌制作 {
static PrintWriter out =new PrintWriter(System.out);
static BufferedReader ins=new BufferedReader(new InputStreamReader(System.in));
static StreamTokenizer in=new StreamTokenizer(ins);
/**
* 输入
* in.nextToken()
* int a= (int)in.nval;
*
* 输出
* out.print();
* out.flush();
*/
public static void main(String[] args) {
int sum=0;
for (int i = 1; i <= 2020 ; i++) {
sum+=numberTwo(i);
}
System.out.println(sum);
}
static int numberTwo(int n){
int temp=0;
while (n!=0){
if(n%10==2){
temp++;
}
n/=10;
}
return temp;
}
}
题目2：货物摆放_long
题目描述
小蓝有一个超大的仓库，可以摆放很多货物。
现在，小蓝有 n 箱货物要摆放在仓库，每箱货物都是规则的正方体。小蓝规定了长、宽、高三个互相垂直的方向，每箱货物的边都必须严格平行于长、宽、高。
小蓝希望所有的货物最终摆成一个大的长方体。即在长、宽、高的方向上分别堆 L、W、H 的货物,满足 n=L×W×H。
给定 nn，请问有多少种堆放货物的方案满足要求。
例如，当 n=4 时，有以下 6 种方案：1×1×4、1×2×2、1×4×1、2×1×2、2×2×1、4×1×1
请问，当 n=2021041820210418 （注意有 16 位数字）时，总共有多少种方案？
提示：建议使用计算机编程解决问题。
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
代码：
package 第十四届蓝桥杯三月真题刷题训练.day3;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Scanner;
/**
* @author yx
* @date 2023-03-06 8:43
*/
public class 货物摆放 {
static PrintWriter out =new PrintWriter(System.out);
static BufferedReader ins=new BufferedReader(new InputStreamReader(System.in));
static StreamTokenizer in=new StreamTokenizer(ins);
/**
* 输入
* in.nextToken()
* int a= (int)in.nval;
*
* 输出
* out.print();
* out.flush();
*/
// long类型是64位的也就是 ”-2^64“ 到”2^64 -1“
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
long n=scanner.nextLong();
HashSet<Long> set=new HashSet<>();
long ans=0;
for (long i = 1; i <= (long)Math.sqrt(n) ; i++) {
if(n%i==0){
set.add(i);
set.add(n/i);
}
}
ArrayList<Long> list=new ArrayList<>(set);
Collections.sort(list);
int length=list.size();
for (int i = 0; i <length ; i++) {
for (int j = 0; j <length ; j++) {
for (int k = 0; k <length ; k++) {
if(list.get(i)* list.get(j)*list.get(k)==n){
ans++;
}
}
}
}
System.out.println(ans);
}
}
题目3：跳跃_dp
题目描述
小蓝在一个 nn 行 mm 列的方格图中玩一个游戏。
开始时，小蓝站在方格图的左上角，即第 11 行第 11 列。
小蓝可以在方格图上走动，走动时，如果当前在第 rr 行第 cc 列，他不能走到行号比 rr 小的行，也不能走到列号比 cc 小的列。同时，他一步走的直线距离不超过 33。
例如，如果当前小蓝在第 33 行第 55 列，他下一步可以走到第 33 行第 66 列、第 33 行第 77 列、第 33 行第 88 列、第 44 行第 55 列、第 44 行第 66 列、第 44 行第 77 列、第 55 行第 55 列、第 55 行第 66 列、第 66 行第 55 列之一。
小蓝最终要走到第 nn 行第 mm 列。
在图中，有的位置有奖励，走上去即可获得，有的位置有惩罚，走上去就要接受惩罚。奖励和惩罚最终抽象成一个权值，奖励为正，惩罚为负。
小蓝希望，从第 11 行第 11 列走到第 nn 行第 mm 列后，总的权值和最大。请问最大是多少？
输入描述
输入的第一行包含两个整数 n,m，表示图的大小。
接下来 n 行，每行 m 个整数，表示方格图中每个点的权值。
其中，1≤n≤100，−104≤权值≤104
输出描述
输出一个整数，表示最大权值和。
输入输出样例
示例 1
输入
3 5 -4 -5 -10 -3 1 7 5 -9 3 -10 10 -2 6 -10 -4输出
15运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
代码：
package 第十四届蓝桥杯三月真题刷题训练.day3;
import java.io.*;
import java.util.Arrays;
import java.util.Scanner;
/**
* @author yx
* @date 2023-03-06 9:22
*/
public class 跳跃_dp {
static PrintWriter out =new PrintWriter(System.out);
static BufferedReader ins=new BufferedReader(new InputStreamReader(System.in));
static StreamTokenizer in=new StreamTokenizer(ins);
/**
* 输入
* in.nextToken()
* int a= (int)in.nval;
*
* 输出
* out.print();
* out.flush();
*/
public static void main(String[] args) throws IOException {
Scanner scanner = new Scanner(System.in);
int[] newX={-1,-2,-3,0,0,0,-1,-2,-1};//X操作
int[] newY={0,0,0,-1,-2,-3,-1,-1,-2};//Y操作
int m=scanner.nextInt();
int n=scanner.nextInt();
int dp[][]=new int[m][n];
int nums[][]=new int[m][n];
for (int i = 0; i <m ; i++) {
for (int j = 0; j < n; j++) {
nums[i][j]=scanner.nextInt();
}
}
for (int i = 0; i < m; i++) {
Arrays.fill(dp[i],Integer.MIN_VALUE);//赋值成最小值,也就是-int（-2*10^9）
}
dp[0][0]=nums[0][0];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < newX.length; k++) {
if (i + newX[k] >= 0 && j + newY[k] >= 0) {//设置数组界限
//采用逆向思维，这个点的最大值等于Max(这一步的dp值,上一步的dp值+这个点的nums值)
dp[i][j] = Math.max(dp[i][j], nums[i][j] + dp[i+newX[k]][j+newY[k]]);//更新dp数组的最大值
}
}
}
}
System.out.println(dp[m-1][n-1]);
}
}
题目4：重新排序_差分数组
问题描述
给定一个数组 A 和一些查询 Li,Ri 求数组中第 Li 至第 Ri个元素之和。
小蓝觉得这个问题很无聊, 于是他想重新排列一下数组, 使得最终每个查询结果的和尽可能地大。小蓝想知道相比原数组, 所有查询结果的总和最多可以增加多少?
输入格式
输入第一行包含一个整数 n 。
第二行包含 n 个整数 A1,A2,⋯ ,An相邻两个整数之间用一个空格分隔。
第三行包含一个整数 m 表示查询的数目。
接下来 m 行, 每行包含两个整数 Li、Ri相邻两个整数之间用一个空格分 隔。
输出格式
输出一行包含一个整数表示答案。
样例输入
5 1 2 3 4 5 2 1 3 2 5样例输出
4样例说明
原来的和为 6+14=20, 重新排列为 (1,4,5,2,3) 后和为 10+14=24, 增加了4。
评测用例规模与约定
对于 30%的评测用例， n,m≤50
对于 50%的评测用例, n,m≤500
对于 70% 的评测用例, n,m≤5000
对于所有评测用例, 1≤n,m≤105,1≤Ai≤106,1≤Li≤Ri≤106。
运行限制
- 最大运行时间：1s
- 最大运行内存: 512M
未满分代码：
package 第十四届蓝桥杯三月真题刷题训练.day3;
import java.io.*;
import java.util.Arrays;
/**
* @author yx
* @date 2023-03-06 10:08
*/
public class 重新排序_差分数组_前缀和_贪心 {
static PrintWriter out =new PrintWriter(System.out);
static BufferedReader ins=new BufferedReader(new InputStreamReader(System.in));
static StreamTokenizer in=new StreamTokenizer(ins);
/**
* 输入
* in.nextToken()
* int a= (int)in.nval;
*
* 输出
* out.print();
* out.flush();
*/
/*
十年IO一场空，不开long long见祖宗
*/
// 非常棒的博客思路：https://blog.csdn.net/qq_42487122/article/details/124081313
public static void main(String[] args) throws IOException {
// Scanner scanner = new Scanner(System.in);
in.nextToken();
// int n=scanner.nextInt();
int n=(int) in.nval;
long[] num=new long[n+1];
long[] nums1=new long[n+1];
long[] chaFen=new long[n+1];
long sum1=0;//原始和
long sum2=0;//更新和
String[] s1=ins.readLine().split(" ");
for (int i = 1; i <=n ; i++) {
// in.nextToken();
// nums1[i]=scanner.nextInt();
// nums1[i]=(int)in.nval;
num[i]=Integer.parseInt(s1[i-1]);
nums1[i]=nums1[i-1]+num[i];
}
in.nextToken();
// int m=scanner.nextInt();
int m=(int) in.nval;
for (int i = 0; i < m; i++) {
String[] s2=ins.readLine().split(" ");
// in.nextToken();
int l =scanner.nextInt();
// int l=(int) in.nval;
int r =scanner.nextInt();
// in.nextToken();
// int r=(int) in.nval;
int l=Integer.parseInt(s2[0]);
int r=Integer.parseInt(s2[1]);
sum1+=nums1[r]-nums1[l-1];
if((r-l)%2==0){
chaFen[(r+l)/2]++;
}
while (l<r){
chaFen[l]++;
chaFen[r]++;
l++;
r--;
}
}
Arrays.sort(num);
Arrays.sort(chaFen);
for (int i = 1; i <= n; i++) {
sum2 += chaFen[i]*num[i];//更新后的和
}
// System.out.println(sum2-sum1);
out.println(sum2-sum1);
out.flush();
}
}
差分数组满分代码：
关于差分：
- 因为我们确定从[l,r]区间，那么这个区间里面使用次数都+1
- 普通做法就是每个都+1，复杂度O(n*m)
- 通过前缀和，让l=1，r+1=-1，这样子就可以让[l,r]区间内的值统一+1
- 1 0 0 0 0 0 0 0 -1
前缀和为
1 1 1 1 1 1 1 1 0- 前缀和最后一个for循环计算即可，复杂度O(n+m)
- 复杂度从O(n*m)提升到O(m+n)，解决最后两个点超时的问题
package 第十四届蓝桥杯三月真题刷题训练.day3;
import java.io.*;
import java.util.Arrays;
/**
* @author yx
* @date 2023-03-06 12:37
*/
public class 重新排序_差分数组_100分 {
static PrintWriter out =new PrintWriter(System.out);
static BufferedReader ins=new BufferedReader(new InputStreamReader(System.in));
static StreamTokenizer in=new StreamTokenizer(ins);
/**
* 输入
* in.nextToken()
* int a= (int)in.nval;
*
* 输出
* out.print();
* out.flush();
*/
/*
十年IO一场空，不开long long见祖宗
*/
// 非常棒的博客思路：https://blog.csdn.net/qq_42487122/article/details/124081313
static int N=100010;
static long[] num=new long[N];
static long[] nums1=new long[N];
static long[] chaFen=new long[N];
public static void main(String[] args) throws IOException {
in.nextToken();
int n=(int) in.nval;
long sum1=0;//原始和
long sum2=0;//更新和
String[] s1=ins.readLine().split(" ");
for (int i = 1; i <=n ; i++) {
num[i]=Integer.parseInt(s1[i-1]);
nums1[i]=nums1[i-1]+num[i];
}
in.nextToken();
int m=(int) in.nval;
for (int i = 0; i < m; i++) {
String[] s2=ins.readLine().split(" ");
int l=Integer.parseInt(s2[0]);
int r=Integer.parseInt(s2[1]);
sum1+=nums1[r]-nums1[l-1];
//差分前缀和思想
chaFen[l]++;//左端点+1
chaFen[r+1]--;//右一端点-1
}
for (int i = 1; i <= n ; i++) {
chaFen[i]+=chaFen[i-1];
}
Arrays.sort(num);
Arrays.sort(chaFen);
int p=N-1;
while (chaFen[p]!=0){
sum2 += chaFen[p]*num[p];//更新后的和
p--;
}
out.println(sum2-sum1);
out.flush();
}
}
贴一个思路很棒的一篇博客，再结合差分就完美了
【2022年 第十三届蓝桥杯 Java】试题 G: 重新排序_蓝桥杯java排序_蒋丞选手！的博客-CSDN博客纪录一下昨天考场上“才思敏捷”的思路试题 G: 重新排序【问题描述】给定一个数组 A 和一些查询 L**i, R**i，求数组中第 L**i 至第 R**i 个元素之和。 小蓝觉得这个问题很无聊，于是他想重新排列一下数组，使得最终每个查询结果的和尽可能地大。小蓝想知道相比原数组，所有查询结果的总和最多可以增加多少?【输入格式】输入第一行包含一个整数 n。第二行包含 n 个整数 A1, A2, · · · , A**n，相邻两个整数之间用一个空格分隔。第三行包含一个整数 m 表示查
https://blog.csdn.net/qq_42487122/article/details/124081313