2021第12届蓝桥杯省赛c组java
4.2021c组java
https://blog.csdn.net/qq_43652327/article/details/115913757
https://blog.csdn.net/qq_43449564/article/details/115876990
https://zhuanlan.zhihu.com/p/368789485
https://ydlin.blog.csdn.net/article/details/116541595
https://blog.csdn.net/m0_46260869/article/details/115908148?spm=1001.2014.3001.5501
1.卡片
public class T3卡片 {
static int[] arr = new int[10];
public static void main(String[] args) {
for (int i = 0; i < arr.length; i++) {
arr[i] = 3;
}
for (int i = 1; i < 50000; i++) {
if (isZero(i)) {
System.out.println(--i);
break;
}
}
}
private static boolean isZero(int x) {
while (x>0) {
arr[x%10]--;
if (arr[x%10] < 0) {
return true;
}
x = x/10;
}
return false;
}
}
2.时间显示
import java.util.Scanner;
public class T6时间显示 {
static String check(long time) {
if (time<10) {
return "0"+time;
}else {
return time+"";
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 不算毫秒，先把毫秒去掉
long time = scanner.nextLong()/1000;
// 只算最后一天的时间
time%=(60*60*24);
// 剩余秒
long second = time%60;
// 剩余分钟,time/60:求出总共可以转化的分钟
long minute = (time/60)%60;
// 求出小时
long hour = time/60/60;
System.out.println(check(hour)+":"+check(minute)+":"+check(second));
// 46800999
}
}
3.*最小砝码
https://www.cnblogs.com/jalonjia/p/zuishaofamashu.html#/c/subject/p/zuishaofamashu.html
4.*杨辉三角
https://blog.csdn.net/qq_44901949/article/details/115862160
1.初始想法
30以下
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class 杨辉三角 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
long[][] arr = new long[n*n][n*n];
//特殊值判断
if (n == 1) {
System.out.println(1);
return;
}
arr[1][1] = 1;
List<Long> list = new ArrayList();
// 实现杨辉三角
for (int i = 2; i < arr.length; i++) {
for (int j = 1; j <= i; j++) {
arr[i][j] = arr[i-1][j-1]+arr[i-1][j];
}
}
// 拼接集合
for (int i = 1; i < arr.length; i++) {
for (int j = 1; j < arr.length; j++) {
// System.out.print(arr[i][j]+" ");
if(arr[i][j]!=0) {
list.add(arr[i][j]);
}
}
// System.out.println();
}
// 进行查找
for (int i = 0; i < list.size(); i++) {
if (list.get(i) == n) {
System.out.println(i+1);
break;
}
}
}
}
2.优化
- 一万以下
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class 杨辉三角 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
//n+2:代表这个数所在的行的长度
long[][] arr = new long[2][n+2];
int hang = 1;
//特殊值判断
if (n == 1) {
System.out.println(1);
return;
}
arr[0][1] = 1;
// 实现杨辉三角
while (true) {
hang++;//代表的行数增加,初始就在第二行了
for (int j = 1; j <= hang; j++) {
arr[1][j] = arr[0][j-1]+arr[0][j];
if(arr[1][j] == n) {
System.out.println(hang*(hang+1)/2-hang+j);
return;
}
//当前行没找到
}
// arr[0] = arr[1];//这样会指向同一个对象，二者会同步，赋值就用下面这个函数
for (int j = 1; j <= hang; j++) {
arr[0][j] = arr[1][j];
}
}
}
}
3.优化2
https://blog.csdn.net/qq_52184820/article/details/115915312
5.双向排序
1.初始想法
public class 双向排列 {
static int n;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
int m = scanner.nextInt();
int[] arr = new int[n+1];
for (int i = 1; i <= n; i++) {
arr[i] = i;
}
for (int i = 0; i < m; i++) {
int p = scanner.nextInt();
int q = scanner.nextInt();
if (p == 0) {//降序
//1-q,共执行q-1次
for (int j = 1; j < q; j++) {
int flag = 0;//flag是一个标志,是冒泡的优化
for (int j2 = 1; j2 <= q-j; j2++) {
//每次循环，就少比较一次
if (arr[j2] < arr[j2+1]) {
int temp = arr[j2];
arr[j2] = arr[j2+1];
arr[j2+1] = temp;
flag = 1;
}
}
if (flag == 0) {
break;
}
}
// print(arr);
}else {//升序
//q-n,共执行n-q-1次
for (int j = q; j < n; j++) {
int flag = 0;
for (int j2 = q; j2 < n; j2++) {
if (arr[j2] > arr[j2+1]) {
int temp = arr[j2];
arr[j2] = arr[j2+1];
arr[j2+1] = temp;
flag = 1;
}
}
if (flag == 0) {
break;
}
}
// print(arr);
}
}
print(arr);
}
public static void print(int[] arr) {
for (int i = 1; i <= n; i++) {
System.out.print(arr[i]+" ");
}
}
}
2.优化
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;
public class 双向排列 {
static int n;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
int m = scanner.nextInt();
Integer[] arr = new Integer[n+1];
for (int i = 1; i <= n; i++) {
arr[i] = i;
}
for (int i = 0; i < m; i++) {
int p = scanner.nextInt();
int q = scanner.nextInt();
if (p == 0) {//降序
//下标从0开始，[ )区间，默认升序，降序+Collections.reverseOrder()
//类型:包装类
Arrays.sort(arr,1,q+1,Collections.reverseOrder());
}else {//升序
Arrays.sort(arr,q,n+1);
}
}
print(arr);
}
public static void print(Integer[] arr) {
for (int i = 1; i <= n; i++) {
System.out.print(arr[i]+" ");
}
}
}
6.路径
https://blog.csdn.net/Veyne_/article/details/116211983
https://blog.csdn.net/weixin_44285683/article/details/115920289
https://blog.csdn.net/cgt2094634417/article/details/116140684?utm_medium=distribute.pc_relevant.none-task-blog-baidujs_title-0&spm=1001.2101.3001.4242
-
最短路径
https://blog.csdn.net/qibofang/article/details/51594673
https://blog.csdn.net/qq_38410730/article/details/79587768
https://www.cnblogs.com/of-fanruice/p/7670173.html
public class 路径 {
public static void main(String[] args) {
//定义一个邻接矩阵
int map[][] = new int[2050][2050];
for(int i=1;i<=2021;i++) {
//每个顶点到其他顶点的权值
for(int j=i;j<=i+21;j++) {
map[i][j] = lcm(j,i);
}
}
//是否被访问
boolean bj[] = new boolean[2050];
//原点到最短路径的存贮
int dis[] = new int[2050];
//最短路径的赋值,0就代表不可到达
for(int i=1;i<=2021;i++)dis[i]=map[1][i];
int min,minIdx=0;
//在没有到达终点，就一直循环
while(!bj[2021]) {
min = Integer.MAX_VALUE;
//从第二个顶点开始
for(int i=2;i<=2021;i++) {
//!bj[i]: 没有被访问
//dis[i]!=0 :不可到达
//dis[i]<min:找到所有可到达的值里面的最小值
if(!bj[i] && dis[i]!=0 && dis[i]<min) {
min = dis[i];
//记录这个中间点的坐标
minIdx = i;
}
}
//该中间已被访问
bj[minIdx]=true;
//在中间点所有的可选路径中，进行选择
for(int i=minIdx+1;i<=minIdx+21;i++) {
//dis[i]==0:代表原点不可到达终点，直接赋值
//原点到中间点+中间点到终点
if(dis[i]==0)dis[i] = dis[minIdx]+map[minIdx][i];
else{
//原点可到达终点,比较这二者距离
if(dis[minIdx]+map[minIdx][i] < dis[i])
dis[i]=dis[minIdx]+map[minIdx][i];
}
}
}
System.out.println(dis[2021]);
}
//最大公约数
public static int gcd(int x,int y) {
return x%y!=0 ? gcd(y, x % y) : y;
}
//最小公倍数数
public static int lcm(int x,int y) {
return x * y / gcd(x, y);
}
}
7.*左孩子右兄弟
http://www.voycn.com/article/dishierjielanqiaobei-ccazuzhenti-saihouhuigu
https://blog.csdn.net/weixin_46096297/article/details/112545956