2021年蓝桥杯java A组真题及解决
前言一、试题A 相乘二、试题B 直线三、试题C 货物摆放二、试题D 路径
前言
刷一些蓝桥杯的真题，把自己的解决方法记录在此。其中有一些也是借鉴了其他优秀答主的做法。
一、试题A 相乘
【问题描述】
【解决思路】
遍历即可，注意设置数据类型为long
【代码】
public class T1_12_2021 {
public static void main(String args[])
{
long res;
for(long i=1;i<1000000007;i++)
{
res=(i*2021)%1000000007;
if(res==999999999)
{
System.out.println("这个数字是"+i);
}
}
}
}
【答案】
17812964
【问题描述】
在平面直角坐标系中，两点可以确定一条直线。如果有多点在一条直线上，那么这些点中任意两点确定的直线是同一条。
给定平面上2×3个整点{(x, y)0 ≤x <2,0 ≤y<3,x ∈ Z,y ∈ Z)，即横坐标是0到1(包含0和1)之间的整数、纵坐标是0到2(包含0和2)之间的整数的点。这些点一共确定了11条不同的直线。
给定平面上20× 21个整点{(x, y)|0 ≤x <20,0 ≤y < 21,x ∈ 'Z,y ∈ Z)，即横坐标是0到19(包含0和 19)之间的整数、纵坐标是0到20(包含0和20)之间的整数的点。请问这些点一共确定了多少条不同的直线。
【解决思路】
由y=kx+b可以知道，只需要k和b两个变量就可以确定一条直线。但是，在java中，通过暴力解出k、b来确定直线是不能解决这个问题的。因为可能计算出来的两条直线的斜率k过于相近，导致被认为是同一条直线。
因此，可以将k、b保留分数形式（化简成最简分数）。用k、b两个分数（实际上是两个分子、两个分母，即四个整数）表示一条直线，用Set集合存放直线，ArrayList存放点。
set集合：无序、不重复；arraylist：有序、可以重复；
注意：有一些直线是垂直于x轴的，这些直线不存在k，需要被单独计入总数
【代码】
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class T1_12_2021 {
//答案：40257
public static void main(String args[]) {
Set answer=new HashSet<>(); //存储答案
ArrayList dot=new ArrayList<>(); //存储点对的集合
int x=20,y=21; //x坐标20个点,y坐标21个点
for(int i=0;i0&&b>0)
{
sign="+";
}
else if(a>0&&b<0)
{
sign="-";
b=-b;
}
else if(a<0&&b>0)
{
sign="-";
a=-a;
}
else if(a<0&&b<0)
{
sign="+";
a=-a;
b=-b;
}
else if(a==0)
{
return(0+" ");
}
int gcd=Getgcd(a,b);
a1=a/gcd; //a1是化简后的分子
b1=b/gcd; //b1是化简后的分母
return(sign+a1+"/"+b1+" ");
}
public static int Getgcd(int a,int b)
{//假设a是分子，b是分母
int gcd; //gcd是两个数字a、b的最大公约数
//寻找最大公约数
int min= a > b ? b : a;//在a,b中找出较小的一个数字
while(min>1)
{
if(a%min==0 && b%min==0)
{//如果a和b都能被min整除，那么就找到了最大公约数
gcd=min;
return gcd;
}
else
{//否则min减一
min--;
}
}
gcd=min;
return gcd;
}
}
【答案】40257
三、试题C 货物摆放【问题描述】
【解决思路】
一开始，尝试使用两层循环从1到n暴力枚举，但是发现程序跑了很久都没跑出答案来。
后来发现这其实是一个求约数的问题，思路如下：
Step1：求该数字的所有约数Step2：枚举所有约数，判断成立的方案数量
注意：如果希望向集合ArrayList当中存储基本类型数据，必须使用基本类型对应的"包装类"。
基本类型 包装类(引用类型，包装类都位于Java.lang包下)
byte Byte
short Short
int Integer 【特殊】
long Long
float Float
double Double
char Character 【特殊】
boolean Boolean
从JDK 1.5+开始，支持自动装箱、自动拆箱。
自动装箱:基本类型 --> 包装类
自动拆箱:包装类型 --> 基本类型
【代码】
public class T1_12_2021 {
public static void main(String args[])
{
int answer=0;
long n = 2021041820210418L;
ArrayList yueshu=new ArrayList();
//求n的所有约数
for(long i=1;i*i<=n;i++)
{
if(n%i==0)
{
yueshu.add(i);
//System.out.println(i);
if(n/i!=i)
{
yueshu.add(n/i);
//System.out.println(n/i);
}
}
}
for(int i=0;i
【答案】2430
二、试题D 路径
【问题描述】
【解决思路】
这是一条很经典的用Dijkstra算法解决最短路径问题的题目。我首先复习了一下Dijkstra算法，具体可见笔记：https://blog.csdn.net/rellvera/article/details/122839964
然后再看题目，发现与一般题目的不同之处在于，这条题目中路径的权重是两个结点的最小公倍数。因此只要再计算一下最大公约数即可。在这里，我利用了公式“最小公倍数×最大公约数=两个数的乘积”，通过求出最大公约数，来计算出最小公倍数。
【代码】
//答案10266837
public class exercise {
public int nodeNum; //结点数量
public int edgeNum; //边的数量
public int node[]=new int[2021]; //邻接矩阵的点
public int edge[][]=new int[2021][2021];//邻接矩阵的边的集合
public exercise()
{
nodeNum=2021;
edgeNum=0;
for(int i=0;i b ? b : a;//在a,b中找出较小的一个数字
while(min>1)
{
if(a%min==0 && b%min==0)
{//如果a和b都能被min整除，那么就找到了最大公约数
gcd=min;
return gcd;
}
else
{//否则min减一
min--;
}
}
gcd=min;
return gcd;
}
//输出图
public void printGraph()
{
System.out.print("该图输出为：n ");
for(int i=0;i
【答案】10266837
