2021年第十二届蓝桥杯省赛JAVA B组 省赛题解
目录
试题A.空间
试题B.卡片
试题C.直线
试题D.货物摆放
试题E.路径
试题F.时间显示
试题G.砝码称重
试题H.杨辉三角形
试题I.双向排序
试题J.括号序列
总结：
试题A.空间
1 b=8 Byte （1位即为1Byte）
1Kb=1024b
1Mb=1024Kb
public class lanqiao {
public static void main(String[] args) {
long Mb=256;
long Kb=1024;
long b=1024;
long Byte=8;
System.out.println(Mb*Kb*b*Byte/32);
}
}答案：67108864
试题B.卡片
比较简单，记得测试样例
import java.util.Arrays;
public class lanqiao {
private int[] a;
public static void main(String[] args) {
int a[]=new int[10];
Arrays.fill(a,2021);
for(int i=1;;i++)
{
int t=i;
while(t>0)
{
int temp=t%10;
t=t/10;
a[temp]--;
if(a[temp]==0)
{
System.out.println(i);
return ;
}
}
}
}
}答案：3181
试题C.直线
import java.util.*;
public class lanqiao {
public static void main(String[] args) {
HashSet<String> kb=new HashSet<String>();
int x=0;//横坐标
int y=0;//纵坐标
HashSet<Integer> a1=new HashSet<>();
for(x=0;x<20;x++)
{
for(y=0;y<21;y++)
{
a1.add(x*100+y);// (x*100+y)/100即为横坐标 (x*100+y)%100即为纵坐标 想
} // x,y皆未小于100的数
}
List<Integer> arr=new ArrayList<>(a1);
for(int i=0;i<x*y;i++) //共x*y个数
{
//获得横纵坐标
int x1=arr.get(i)/100;
int y1=arr.get(i)%100;
for(int j=i+1;j<x*y;j++)
{
int x2=arr.get(j)/100;
int y2=arr.get(j)%100;
int kup=y1-y2; //k的分子
int kdown=x1-x2;//k的分母
if(kdown==0) //分母为0 平行于x轴的直线
{
String s="y="+x1;
kb.add(s);
}
else
{
int kgcd=gcd(kup,kdown);
kup=kup/kgcd;
kdown=kdown/kgcd;
int bup=y1*kdown-kup*x1;//b的分子
int bdown=kdown;//b的分母
int bgcd=gcd(bup,bdown);
bup=bup/bgcd;
bdown=bdown/bgcd;
String s=kup+" "+kdown+" "+bup+" "+bdown;
kb.add(s);
}
}
}
System.out.println(kb.size());
}
static int gcd(int a,int b)
{
if(b==0)
{
return a;
}
return gcd(b,a%b);
}
}1.利用 z=x*100+y 来存储x,y x=z/100,y=z%100
2.java中用double类型存小数不准确，此题用分数形式存储
3.将多个数据组合用String类型存储，再利用set去重。String类型进行比较时，只有每个字符都相同时，才会默认为相同，所以不用再考虑其中的分子分母是否相等等问题
4.注意要约分，利用最大公因数函数
答案：40257
试题D.货物摆放
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.*;
public class lanqiao {
public static void main(String[] args) {
long n=2021041820210418l;
long a[]=new long[1000000];
int ans=0;
long temp=n;
for(long i=1l;i<temp;i++)
{
if(n%i==0)
{
temp=n/i;
a[ans++]=i;
a[ans++]=temp;
}
}
int result=0;
for(int i=0;i<ans;i++)
{
for(int j=0;j<ans;j++)
{
if(n%(a[i]*a[j])==0)
{
result++;
}
}
}
System.out.println(result);
}
}1.题目中给的大数在java中用long即可存储，不必使用BigInteger
2.若直接使用暴力三重循环，计算量太大，算不出结果
正确思路为将因子保存下来，二重循环计算
3.在寻找因子时要进行优化 若x为n的因子，则n/x也为x的因子
答案：2430
试题E.路径
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.*;
public class lanqiao {
public static void main(String[] args) {
int n=2021;
int g[][]=new int[2510][2510];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i!=j)
{
if(Math.abs(i-j)<=21)
{
g[i][j]=lcm(i,j);
g[j][i]=lcm(i,j);
}
else
{
g[i][j]=g[j][i]=100000000;
}
}
}
}
System.out.println(dis(g));
}
static int gcd(int a,int b)
{
return b>0? gcd(b,a%b):a;
}
static int lcm(int a,int b)
{
return a*b/gcd(a,b);
}
static int dis(int g[][])
{
int N=2510;
int dist[]=new int[N];
int st[]=new int[N];
int n=2021;
Arrays.fill(dist,1000000000);
dist[1]=0;
for(int i=1;i<=n;i++)
{
int t=-1;
for(int j=1;j<=n;j++)
{
if(st[j]==0&&(t==-1||dist[j]<dist[t]))
{
t=j;
}
}
st[t]=1;
for(int j=1;j<=n;j++)
{
if(dist[j]>(dist[t]+g[t][j]))
{
dist[j]=dist[t]+g[t][j];
}
}
}
return dist[n];
}
}迪杰斯特拉模板题
答案：10266837
试题F.时间显示
【样例输入 1】
46800999
【样例输出 1】
13:00:00
【样例输入 2】
1618708103123
【样例输出 2】
01:08:23
【评测用例规模与约定】
对于所有评测用例，给定的时间为不超过 1018 的正整数。
答案：
import java.math.BigDecimal;
import java.math.BigInteger;
import java.text.DecimalFormat;
import java.util.*;
public class lanqiao {
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
long n=in.nextLong();
n=(n/1000)%86400;
int hour= (int) (n/3600);
int minute= (int) ((n%3600)/60);
int second= (int) (n-hour*3600-minute*60);
DecimalFormat df=new DecimalFormat("00");
System.out.println(df.format(hour)+":"+df.format(minute)+":"+df.format(second));
}
}java中long的范围为：-9223372036854775808到9223372036854775807
所以此题用long即可
试题G.砝码称重
【样例输入】
3
1 4 6
【样例输出】
10
【样例说明】
能称出的 10 种重量是：1、2、3、4、5、6、7、9、10、11。
1 = 1；
2 = 6 6 4 (天平一边放 6，另一边放 4)；
3 = 4 1；
4 = 4；
5 = 6 1；
6 = 6；
7 = 1 + 6；
9 = 4 + 6 1；
10 = 4 + 6；
11 = 1 + 4 + 6。【评测用例规模与约定】
对于 50% 的评测用例，1 ≤ N ≤ 15。
对于所有评测用例，1 ≤ N ≤ 100，N 个砝码总重不超过 100000。
闫氏dp分析法
答案：
import java.math.BigDecimal;
import java.math.BigInteger;
import java.text.DecimalFormat;
import java.util.*;
public class lanqiao {
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
int n=in.nextInt();
//dp[i][j]表示前i个砝码，称出j的集合，值为bool值，能称出j就true
boolean dp[][]=new boolean[110][1000000];
int a[]=new int[101];
int m=0;
for(int i=1;i<=n;i++)
{
a[i]=in.nextInt();
m+=a[i];
}
dp[0][0]=true;
for(int i=1;i<=n;i++)//前i个
{
for(int j=0;j<=m;j++)//称出j
{
dp[i][j]=dp[i-1][j]||dp[i-1][j+a[i]]||dp[i-1][Math.abs(j-a[i])];
//只要有一种情况为真，那么dp[i][j]就真
}
}
int ans=0;
for(int i=1;i<=m;i++)
{
if(dp[n][i])
{
ans++;
}
}
System.out.println(ans);
}
}试题H.杨辉三角形
【样例输入】
6
【样例输出】
13
【评测用例规模与约定】
对于 20% 的评测用例，1 ≤ N ≤ 10；
对于所有评测用例，1 ≤ N ≤ 1000000000。
遍历：数据达不到，骗分来的，没找到好的解决办法~~~
节省时间的话，直接枚举1-10
import java.math.BigDecimal;
import java.math.BigInteger;
import java.text.DecimalFormat;
import java.util.*;
public class lanqiao {
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
int n=in.nextInt();
long arr[][]=new long[100000][100000];
for(int i=0;i<arr.length;i++)
{
for(int j=0;j<=i;j++)
{
if(j==0||i==j)
{
arr[i][j]=1;
}
else
{
arr[i][j]=arr[i-1][j-1]+arr[i-1][j];
}
}
}
int count=1;
for(int i=0;i<arr.length;i++)
{
for(int j=0;j<=i;j++)
{
if(n==arr[i][j])
{
System.out.println(count);
return;
}
else
{
count++;
}
}
}
}
}试题I.双向排序
【样例输入】
3 3
0 3
1 2
0 2
【样例输出】
3 1 2
【样例说明】
原数列为 (1, 2, 3)。 第 1 步后为 (3, 2, 1)。 第 2 步后为 (3, 1, 2)。 第 3 步后为 (3, 1, 2)。与第 2 步操作后相同，因为前两个数已经是降序了。【评测用例规模与约定】
对于 30% 的评测用例，n, m ≤ 1000；
对于 60% 的评测用例，n, m ≤ 5000；
对于所有评测用例，1 ≤ n, m ≤ 100000，0 ≤ ai ≤ 1，1 ≤ bi ≤ n。
直接用sort函数排序可得到一部分分数。
完整实现可看y总的讲解 。
试题J.括号序列
【样例输入】
((()
【样例输出】
5
【评测用例规模与约定】
对于 40% 的评测用例，|s| ≤ 200。
对于所有评测用例，1 ≤ |s| ≤ 5000。
答案：
dfs暴力骗分版本：
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class J括号序列 {
/***
dfs暴力骗分
()()()
10. 这个set容器可以不需要,直接在dfs中计数,count设置为全局变量
*/
static Set<String> set = new HashSet<>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.next();
int left = 0;
int right = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
left++;
} else {
right++;
}
}
//int count = Math.max(left, right);
int count;//最多的括号数量
int sub;//插入的括号不能超过sub个,也就是不一样的括号数量
if (left > right) {
count = left;
sub = left - right;
} else {
count = right;
sub = right - left;
}
String temp = "";
for (int i = 0; i < count; i++) {
temp += "()";
}
dfs(temp);
System.out.println(set);
int resCount = 0;
for (String s1 : set) {
int i = 0;
int j = 0;
boolean isMatch = true;
while (i < s.length() && j < s1.length()) {
int tempCount = sub;
if (s.charAt(i) == s1.charAt(j)) {
i++;
j++;
} else {
j++;
tempCount--;
}
if (tempCount < 0) {
isMatch = false;
break;
}
}
if (isMatch) {
resCount++;
}
}
System.out.println(resCount);
}
private static void dfs(String temp) {
set.add(temp);
for (int i = 0; i < temp.length() - 1; i++) {
if (temp.charAt(i) == ')' && temp.charAt(i + 1) == '(') {
String temps = temp.substring(0, i) + "()" + temp.substring(i + 2, temp.length());
dfs(temps);
}
}
}
}总结：
这次比赛更加注重算法和细节了
前面程序填空的直线题，最开始想保存扩大倍数的k,b，实现起来很多坑，后来看到x*100+y的保存方式，最终结果用字符串保存十分巧妙。
闫式背包一开始就没想出来，还是积累不够
后面的杨辉三角形和双向排序都是数据量比较大，用的简单方法蹭了一部分分数~~~
总之，难度感觉要比往年的大一些，还是要继续努力呀