【算法】蓝桥杯历年真题 2021 十二届

算法】蓝桥杯历年真题 2021 十二届"/>

【算法】蓝桥杯历年真题 2021 十二届

蓝桥杯历年真题 .page?code=PREV

研究生/大学A组、大学B组、大学C组很多题目都是一样，只有个别题目不一样，每个组各自排名

第二场是部分省份因为时间冲突等原因不能按时比省赛，所以蓝桥杯给他们单独办了一场，比完第一场的不用管这场。决赛是5.8，获得省一的才有资格。

历年合集

【参考：【算法】蓝桥杯历年真题 2020 十一届_myaijarvis的博客-CSDN博客】

2021第十二届

【参考：蓝桥杯ACM训练系统 - C语言网 第十二届】

省赛 大学B组

【参考：2021年第十二届蓝桥杯省赛B组（C/C++）个人题解_雪岩ding的博客-CSDN博客】

【参考：2021第十二届蓝桥杯省赛java b组 题目+答案_en_oc的博客-CSDN博客】

卡片

import java.util.HashMap;public class Main {public static void main(String[] args) {// 0-9各2021张// arr[i] 就是数字i有多少张int[] arr={2021,2021,2021,2021,2021,2021,2021,2021,2021,2021};int res=0;int num=1; // 从 1 拼到多少boolean flag=false;arr[1]--; // 去掉第一个1res++; while (true) {num++; // 数字加1，然后下面看看剩余的卡片能不能拼成numint temp=num;// 取temp每位数字，看看对应卡片是否还有剩余，如果没有剩余，说明无法拼成，此时num-1是能拼成的最大值while (temp>0) {int i=temp%10; // 取最低位arr[i]--;if(arr[i]<0) { // 数字i用完了flag=true;break;}temp=temp/10;}if(flag) {break;}res++;	}System.out.println(res); // 3181	}}

import java.util.Arrays;public class Main {public static void main(String[] args) {int[] chs = new int[10];Arrays.fill(chs, 2021);for (int i = 1; ; i++) { // i就是现在正在拼的数字for (char c : String.valueOf(i).toCharArray()) {if (chs[c - '0'] == 0) { // 数字c用完了System.out.println(i-1);return;}chs[c - '0']--;}}}
}

直线 *

【蓝桥杯2021年真题演练——2、直线（JavaA组）】

答案 40257

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;public class Main {public static void main(String[] args) {//存k和b（kup kdown bup bdown）HashSet<String> set = new HashSet<String>();ArrayList<Integer> list = new ArrayList<Integer>();for (int x = 0; x < 20;x++) {for (int y = 0; y < 21; y++) {list.add(x*100+y);	/*把坐标以x*100+y的形式存入ArrayList*/		}}int len=list.size();for (int i = 0; i < len; i++) {int x1=list.get(i)/100;//点一横坐标int y1=list.get(i)%100;//点一纵坐标for (int j = i+1; j < len; j++) {int x2=list.get(j)/100;//点二横坐标int y2=list.get(j)%100;//点二纵坐标// 计算斜率（用分数（kup/kdown）表示）int kup=y1-y2;int kdown=x1-x2;if (kdown==0) {// kdown=0说明斜率不存在String s="x="+x1;set.add(s);continue;}int kgcd=gcd(kup,kdown);kup/=kgcd;kdown/=kgcd;// k = kup/kdown 此时为最简分数//计算截距（用分数（bup/bdown）表示）// bup/bdown=b=y-kx=y- kup/kdown xint bdown=kdown;int bup=y1*bdown-kup*x1;int bgcd=gcd(bup,bdown);bup/=bgcd;bdown/=bgcd;// b=bup/bdown	此时为最简分数String s=kup+" "+kdown+" "+bup+" "+bdown;set.add(s);                             }}//kb中的元素是不重复的，有重复也只会存储其中一个，因此kb的大小就是直线的个数System.out.println(set.size());}//辗转相除求最大公约数static int gcd(int a, int b) {if(b==0){return a;}return gcd(b,a%b);}}

货物摆放

n = 2021041820210418 （注意有 16 位数字）要用 long类型
【参考：蓝桥杯货物摆放思路分析_RonaldDong的博客-CSDN博客】

思路：遍历这个大数的所有因数，然后对这些因数进行全排序，找到所有三个相乘为大数的排序

【参考：2021年第十二届蓝桥杯省赛B组（C/C++）个人题解_雪岩ding的博客-CSDN博客】
由于要拆解成因子，拆解的三个因子（设为a，b，c），把a，b，c放到一个集合里s；
始终要a<=b<=c（不然超时！）
【（1，1，4）包括了1×1×4，1×4×1，4 × 1 × 1，即包括了（1，4，1），（4，1，1）】
如果s.size()==1，ans+=1;//abc三者相等，为一种情况
如果s.size()==2，ans+=3;//abc三个有两个相等，则独立的有三种放法
如果s.size()==3，ans+=6；//abc互不相等，全排列3 * 2 *1种
循环一定要两层，不要三层，必须使用sqrt降低复杂度

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;public class Main {public static void main(String[] args) {long n = 2021041820210418L, n2;long i = 0, j, k; // 三个因子int res = 0;for (i = 1; i < Math.sqrt(n); i++) {if (n % i != 0) {continue;}n2 = n / i;for (j = 1; j < Math.sqrt(n2); j++) {if (n2 % j != 0) {continue;}k = n2 / j;if (i <= j && j <= k) {HashSet<Long> set = new HashSet<>();set.add(i);set.add(j);set.add(k);int len = set.size();if (len == 1)res++;else if (len == 2)res += 3;else if (len == 3)res += 6;}}}System.out.println(res);}}

路径

【参考：2021年第十二届蓝桥杯省赛B组（C/C++）个人题解_雪岩ding的博客-CSDN博客】

Floyd 弗洛伊德算法 求图的两点最短路径

public class Main {public static void main(String[] args) {int n = 2022;int INF = Integer.MAX_VALUE / 2;int[][] map = new int[n][n];for (int i = 1; i < n; i++) {for (int j = 1; j < n; j++) {if (i == j) {map[i][j] = map[j][i] = 0;} else if (Math.abs(i - j) > 21) {map[i][j] =map[j][i] = INF;} else {map[i][j] = map[j][i] = i * j / gcd(i, j);					}}}int[][] dist = new int[n][n];for (int i = 1; i < n; i++) {for (int j = 1; j < n; j++) {dist[i][j] = map[i][j];}}for (int k = 1; k < n; k++) {for (int i = 1; i < n; i++) {for (int j = 1; j < n; j++) {if (dist[i][k] + dist[k][j] < dist[i][j]) {dist[i][j] = dist[i][k] + dist[k][j];}}}}System.out.println(dist[1][n-1]);}static int gcd(int a,int b) { if(b==0) return a;return gcd(b, a%b);		}}

时间显示

签到题
注意格式

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);long n = sc.nextLong();long ms=1;long s=ms*1000;long m=s*60;long h=m*60;long ht_y=n%(24*h)%h;// 余数long ht=n%(24*h)/h; // 小时if(ht_y!=0) { // 还有分钟long mt=ht_y/m;long mt_y=ht_y%m;if(mt_y!=0) { // 还有秒long st=mt_y/s;System.out.printf("%02d:%02d:%02d",ht,mt,st);return;}System.out.printf("%02d:%02d:00",ht,mt);return;}// %02d:默认情况下，数据数据宽度不够2位是用空格填补的，// 但是因为2d前面有0，表示，数据宽度不足时用0填补。System.out.printf("%02d:00:00",ht);return;}}

砝码称重 **

【参考：2021年第十二届蓝桥杯省赛B组（C/C++）个人题解_雪岩ding的博客-CSDN博客】

测试样例范围 50%的样例在1<=n<=15,果断dfs深搜骗分

import java.util.HashSet;
import java.util.Scanner;public class Main {static int n=3;static int[] w;static int[] v; static HashSet<Integer> set=new HashSet<>();public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();w = new int[n];v = new int[n];for (int i = 0; i < n; i++) {w[i] = sc.nextInt();}dfs(0, 0);System.out.println(set.size());}static void dfs(int sum1, int sum2) {if (sum1 < sum2)return;if (sum1 > sum2) {set.add(sum1 - sum2);}for (int i = 0; i < n; i++) {if (v[i] != 1) { // 未使用v[i] = 1; // 标记使用dfs(w[i] + sum1, sum2); // 放在左边dfs(sum1, w[i] + sum2); // 放在右边v[i] = 0;  // 回溯}}}}

【参考：[无聊君]蓝桥杯2021年第十二届省赛真题-最少砝码 推公式-Dotcpp编程社区】
题目询问的是称出N重量的最少砝码 那就根据砝码个数跟重量来推公式即可

称1 需要1个砝码 砝码重量1

称2 需要2个砝码 砝码重量1 2

称3 需要2个砝码 砝码重量1 2

称4 需要2个砝码 砝码重量1 3

称5 需要3个砝码 砝码重量1 2 3

称6 需要3个砝码 砝码重量1 2 3

称7 需要3个砝码 砝码重量1 3 6

称8 需要3个砝码 砝码重量1 5 7

称9 需要3个砝码 砝码重量1 3 8

称10 需要3个砝码 砝码重量1 3 8

称11 需要3个砝码 砝码重量1 3 8

称12 需要3个砝码 砝码重量1 3 8

称13 需要3个砝码 砝码重量1 3 9

当需要称重14时3个砝码就不够了 就到了4个砝码

1个砝码最大称到1

2个砝码最大称到4

3个砝码最大称到13

看最大可称重的正整数找到规律

新一级的砝码最大称称重到：

上一级砝码上限 × 3 + 1

用代码实现即可

杨辉三角形 不会

【评测用例规模与约定】
对于 20% 的评测用例，1 ≤ N ≤ 10；
对于所有评测用例，1 ≤ N ≤ 1000000000。10亿

暴力不得行 暴力枚举只能得50分

【参考：去年的蓝桥杯H题杨辉三角形你满分了吗？_小怂很怂的博客-CSDN博客】

双向排序 不会

纯暴力 64分

import java.util.Arrays;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n=sc.nextInt();int m=sc.nextInt();int[] p=new int[m];int[] q=new int[m];for (int i = 0; i < n; i++) {p[i] = sc.nextInt();q[i] = sc.nextInt();}Integer[] a=new Integer[n+1];for (int i = 1; i <= n; i++) {a[i]=i;}for (int i = 0; i < m; i++) {if(p[i]==1) {// 升序Arrays.sort(a, q[i],a.length);}else if(p[i]==0) {// 降序Arrays.sort(a, 1, q[i]+1,(Integer o1,Integer o2)->{return o2 - o1;});}}for (int i =1; i <= n; i++) {System.out.print(a[i]+" ");}}
}

括号序列 不会

暴力dfs 只能拿几分

import java.util.Scanner;public class Main {static int res=0;static int n=0;public static void main(String[] args) {Scanner scanner=new Scanner(System.in);String s=scanner.nextLine().trim();char[] sc=s.toCharArray();int p=0,q=0;for (int i = 0; i < sc.length; i++) {if(sc[i]=='(') p++;if(sc[i]==')') q++;}n=sc.length+Math.abs(p-q); // 需要的括号总数dfs(0, 0, 0);System.out.println(res%1000000007);}// i （的数量 // j ）的数量static void dfs(int num,int i,int j) {if(num>n) {return;}// 左括号优先if(i<j || i> n/2 || j> n/2) return;if(num==n) { // 括号总数达到要求res++;}dfs(num+1, i+1, j); // 加（dfs(num+1, i, j+1); // 加）}}

2012

天干地支

【参考：[蓝桥杯]天干地支（c++详解）_kano_s的博客-CSDN博客】

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n=sc.nextInt();String[] t={"geng","xin","ren","gui","jia","yi","bing","ding","wu","ji"};String[] d={"zi","chou","yin","mao","chen","si","wu","wei","shen","you","xu","hai"};int t1=0,d1=0,y=0;if(n>=1900) {y=n-1900;t1=y%10;d1=y%12;System.out.println(t[t1]+d[d1]);}else {y=1900-n;t1=y%10;d1=y%12;System.out.println(t[10-t1]+d[12-d1]);}}
}