当前位置:   article > 正文

【算法】蓝桥杯历年真题 2021 十二届_蓝桥杯官方网站算法题目

蓝桥杯官方网站算法题目

蓝桥杯历年真题 http://lx.lanqiao.cn/problemset.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]--; // 去掉第一个1
		res++; 
		while (true) {
			num++; // 数字加1,然后下面看看剩余的卡片能不能拼成num
			int 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	
	}

}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
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']--;
            }
        }
    }
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

直线 *

在这里插入图片描述
蓝桥杯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 x
                int 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);
    }

}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74

货物摆放

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);

	}

}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47

路径

【参考: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);		
	}

}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52

时间显示

签到题
注意格式

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;
	}

}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39

砝码称重 **

【参考: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;  // 回溯
			}

		}

	}

}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44

【参考:[无聊君]蓝桥杯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博客


  • 1

双向排序 不会

纯暴力 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]+" ");
        }
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42

括号序列 不会

暴力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); // 加)
		
	}
		
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41

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]);
		}
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Cpp五条/article/detail/606368
推荐阅读
相关标签
  

闽ICP备14008679号