你想裸考？不可能！蓝桥杯三天速成

废话不多说，直接实战，2个填空6个编程。
  第一天：省三我来了

   目标：把握基础算法和填空题套路，快速拿下省三保底分。
  

• 进制转换
  
• 日期盘算
  
• 数学头脑题
  

  握手问题

组合数学
   小蓝组织了一场算法交流会议，总共有 5050 人参加了本次会议。在会议上，各人进行了握手交流。按照惯例他们每个人都要与除自己以外的其他全部人进行一次握手 (且仅有一次)。但有 77 个人，这 77 人彼此之间没有进行握手 (但这 77 人与除这 77 人以外的全部人进行了握手)。叨教这些人之间一共进行了多少次握手?
  注意 AA 和 BB 握手的同时也意味着 BB 和 AA 握手了，以是算作是一次握手。

1. import java.util.Scanner;
2. // 1:无需package
3. // 2: 类名必须Main, 不可修改
4. public class Main {
5.     public static void main(String[] args) {
6.         Scanner scan = new Scanner(System.in);
7.         //在此输入您的代码...
8.         int ans = 50 * 49 / 2 - 7 * 6 / 2; //是不是很简单，那我们继续
9.         System.out.print(ans);
10.         scan.close();
11.     }
12. }

复制代码

 门牌制作

暴力枚举法
   小蓝要为一条街的住户制作门牌号。
  这条街一共有 20202020 位住户，门牌号从 11 到 20202020 编号。
  小蓝制作门牌的方法是先制作 00 到 99 这几个数字字符，最后根据必要将字符粘贴到门牌上，例如门牌 1017 必要依次粘贴字符 1、0、1、71、0、1、7，即必要 11 个字符 00，22 个字符 11，11 个字符 77。
  叨教要制作全部的 11 到 20202020 号门牌，总共必要多少个字符 22？

1. import java.util.Scanner;
2. // 1:无需package
3. // 2: 类名必须Main, 不可修改
4. public class Main {
5.     public static void main(String[] args) {
6.         Scanner scan = new Scanner(System.in);
7.         //在此输入您的代码...
8.         int n = 2,ans = 0;
9.         while(n <= 2020){
10.           int k = n;
11.           while(k > 0){
12.             if(k%10 == 2){
13.               ans++;
14.             }
15.             k /= 10;
16.           }
17.           n++;
18.         }
19.         System.out.print(ans);
20.         scan.close();
21.     }
22. }

复制代码

 小球反弹

数学
   根据上面的题目信赖你对模拟有一点的了解了吧，来看看这个！
  有一长方形，长为 343720343720 单元长度，宽为 233333233333 单元长度。在其内部左上角顶点有一小球 (无视其体积)，其初速率如图所示且保持运动速率不变，分解到长宽两个方向上的速率之比为 dx:dy=15:17。小球碰到长方形的边框时会发生反弹，每次反弹的入射角与反射角相称，因此小球会改变方向且保持速率不变（如果小球刚好射向角落，则按入射方向原路返回）。从小球出发到其第一次回到左上角顶点这段时间里，小球运动的路程为多少单元长度？答案四舍五入保存两位小数。
  假设从出发入射角，知道长和宽，怎样算出入射角，没错勾股定理。哪反射角怎么算了？把格局打开直接穿过，直线一直走算出长和宽就知道了吧，又有新问题了，什么时间回到开始点？剩下的自己想吧。

1. import java.util.Scanner;
2. // 1:无需package
3. // 2: 类名必须Main, 不可修改
4. public class Main {
5.     public static void main(String[] args) {
6.         Scanner scan = new Scanner(System.in);
7.         //在此输入您的代码...
8.         long c = 343720,k = 233333;
9.         long dx = 15,dy = 17;
10.         long count = 1;
11.         while(true){
12.           if((dx*count)%c == 0 && (dy*count)%k == 0){
13.             break;
14.           }
15.           count++;
16.         }
17.         double ans = 2*Math.sqrt((dx*count)*(dx*count) + (dy*count)*(dy*count));
18.         System.out.printf("%.2f",ans);
19.         scan.close();
20.     }
21. }

复制代码

九进制转十进制

进制转换
   九进制正整数 (2022)9转换成十进制等于多少？

1. import java.util.Scanner;
2. // 1:无需package
3. // 2: 类名必须Main, 不可修改
4. public class Main {
5.     public static void main(String[] args) {
6.         Scanner scan = new Scanner(System.in);
7.         //在此输入您的代码...
8.         int n = 2022,k = 1;
9.         int ans = 0;
10.         while(n > 0){
11.           ans += n%10 * k;
12.           n /= 10;
13.           k *= 9;
14.         }
15.         System.out.print(ans);
16.         scan.close();
17.     }
18. }

复制代码

 艺术与篮球

日期枚举
   小蓝出生在一个艺术与运动并重的家庭中。
  妈妈是位书法家，她盼望小蓝能通过练习书法，继承她的艺术天赋，并练就一手好字。爸爸是一名篮球锻练，他盼望小蓝能通过篮球锻炼身体，培养运动的豪情和团队合作的精力。
  为了既满足妈妈的期望，又不辜负爸爸的心意，小蓝决定根据日期的笔画数来安排自己的练习。首先，他会将当天的日期按照 “YYYYMMDD” 的格式转换成一个8位数，然后将这8位数对应到汉字上，盘算这些汉字的总笔画数。如果总笔画数凌驾50，他就去练习篮球；如果总笔画数不凌驾 50，他就去练习书法。
  例如，在 20242024 年 11 月 11 日这天，日期可表示为一个 8 位数字 20240101，其转换为汉字是“二零二四零一零一”。日期的总笔画数为 2+13+2+5+13+1+13+1=50，因此在这天，小蓝会去练习书法。
  以下是汉字的笔画数对照表：
  汉字笔画数零13一1二2三3四5五4六4七2八2九2  现在，请你帮助小蓝统计一下，在 2000年 11 月 11 日到 2024 年 4 月 13 日这段时间内，小蓝有多少天是在练习篮球？
  怎么啊？看我干嘛，我不会自己写。
   第二天：省二稳一手

   目标：攻克高频算法+暴力骗分本事，暴力出古迹，DFS保平安。
  你先记着模板再说dfs和bfs。
  五子棋对弈 

DFS
    在五子棋的对弈中，友爱的小船说翻就翻？" 不！对小蓝和小桥来说，五子棋不仅是棋盘上的较量，更是心与心之间的沟通。这两位挚友承袭着"友爱第一，比赛第二"的宗旨，决定在一块 5×55×5 的棋盘上，用黑白两色的棋子来决出胜负。但他们又都不忍心让对方失落，于是决定用一场和棋（平手）作为彼此友爱的见证。
  比赛遵循以下规则：
  

• 棋盘规模：比赛在一个 5×5 的方格棋盘上进行，共有 25 个格子供下棋使用。
  
• 棋子类型：两种棋子，黑棋与白棋，代表两边。小蓝持白棋，小桥持黑棋。
  
• 先手规则：白棋（小蓝）具有先手优势，即在棋盘空缺时率先落子（下棋）。
  
• 轮漂泊子：玩家们瓜代在棋盘上放置各自的棋子，每次仅放置一枚。
  
• 胜利条件：率先在横线、竖线或斜线上形成连续的五个同色棋子的一方获胜。
  
• 平手条件：当全部 2525 个棋盘格都被下满棋子，而未决出胜负时，游戏以平手告终。
  

  在这一设定下，小蓝和小桥想知道，有多少种不同的棋局情况，既确保棋盘下满又保证比赛效果为平手。

1. import java.util.*;
2. // 1:无需package
3. // 2: 类名必须Main, 不可修改
4. public class Main {
5.     static int[][] mp = new int[5][5]; //棋盘
6.     static int ans = 0; //平局的结果
7.     public static void main(String[] args) {
8.         //初始化棋盘
9.         for (int i = 0; i < 5; i++) {
10.             Arrays.fill(mp[i], -1);
11.         }
12.         dfs(0,13,12);//白13，黑12
13.         System.out.println(ans); //3126376
14.     }
15.     // cnt 表示当前处理的格子编号（0 到 24），b 表示剩余的黑棋数量，h 表示剩余的白棋数量
16.     private static void dfs(int cnt, int b, int h) {
17.         if (cnt == 25) { // 如果所有格子都已处理
18.             if (chk()) { // 检查当前棋盘是否满足平局条件
19.                 ans++; // 如果满足，平局数量加 1
20.             }
21.             return;
22.         }
23.         //计算当前格子坐标
24.         int x = cnt / 5; //行
25.         int y = cnt % 5; //列
26.         //尝试放置白棋
27.         if (b > 0) {
28.             mp[x][y] = 1; //放白
29.             dfs(cnt + 1, b - 1, h); //下一个格子
30.             mp[x][y] = -1; // 回溯，恢复格子状态
31.         }
32.         //尝试放置黑棋
33.         if (h > 0) {
34.             mp[x][y] = 0; //放黑
35.             dfs(cnt + 1, b, h - 1); //下一个格子
36.             mp[x][y] = -1; // 回溯，恢复格子状态
37.         }
38.         
39.     }
40.     // 检查当前棋盘是否满足平局条件
41.     private static boolean chk() {
42.         for (int i = 0; i < 5; i++) {
43.             int sum1 = 0, sum2 = 0; //棋子状态和
44.             for (int j = 0; j < 5; j++) {
45.                 sum1 += mp[i][j];  //行
46.                 sum2 += mp[j][i];  //列
47.             }
48.             // 如果某一行或某一列全为 0（白棋）或全为 1（黑棋），则不满足平局条件
49.             if (sum1 == 0 || sum1 == 5 || sum2 == 0 || sum2 == 5) {
50.                 return false;
51.             }
52.         }
53.         // 检查两条对角线是否满足平局条
54.         int sum3 = 0, sum4 = 0;
55.         for (int i = 0; i < 5; i++) {
56.             sum3 += mp[i][i];
57.             sum4 += mp[4 - i][i];
58.         }
59.         // 如果某条对角线全为 0（白棋）或全为 1（黑棋），则不满足平局条件
60.         if (sum3 == 0 || sum3 == 5 || sum4 == 0 || sum4 == 5) {
61.             return false;
62.         }
63.         // 如果所有行、列和对角线都满足平局条件，返回 true
64.         return true;
65.     }
67. }

复制代码

 跳跃

DFS、动态规划
   小蓝在一个 n 行 m 列的方格图中玩一个游戏。
  开始时，小蓝站在方格图的左上角，即第 1 行第 1 列。
  小蓝可以在方格图上走动，走动时，如果当前在第 r 行第 c 列，他不能走到行号比 r 小的行，也不能走到列号比 c 小的列。同时，他一步走的直线距离不凌驾 3。
  例如，如果当前小蓝在第 3 行第 5 列，他下一步可以走到第 3 行第 6 列、第 3 行第 7 列、第 3 行第 8 列、第 4 行第 5 列、第 4 行第 6 列、第 4 行第 7 列、第 5 行第 5 列、第 5 行第 6 列、第 6 行第 5 列之一。
  小蓝终极要走到第 n 行第 m 列。
  在图中，有的位置有奖励，走上去即可得到，有的位置有惩罚，走上去就要接受惩罚。奖励和惩罚终极抽象成一个权值，奖励为正，惩罚为负。
  小蓝盼望，从第 1 行第 1 列走到第 n 行第 m 列后，总的权值和最大。叨教最大是多少？
  输入描述
  输入的第一行包罗两个整数 n,m 表示图的巨细。
  接下来 n 行，每行 m 个整数，表示方格图中每个点的权值。
  输出描述
  输出一个整数，表示最大权值和。
  输入输出样例
     输入
   3 5
   -4 -5 -10 -3 1
   7 5 -9 3 -10 10
   -2 6 -10 -4
   
     输出
   15
    方向是向前3个和向下3个，直接dfs

1. import java.util.Scanner;
2. // 1:无需package
3. // 2: 类名必须Main, 不可修改
4. public class Main {
5.   static int dx[] = new int[]{1,2,3,0,0,0,1,2,1};
6.   static int dy[] = new int[]{0,0,0,1,2,3,1,1,2};
7.   static int n,m;
8.   static int g[][];
9.   static int ans = Integer.MIN_VALUE;
10.     public static void main(String[] args) {
11.         Scanner scan = new Scanner(System.in);
12.         //在此输入您的代码...
13.         n = scan.nextInt();
14.         m = scan.nextInt();
15.         g = new int[n][m];
16.         for(int i = 0;i < n;i++){
17.           for(int j = 0;j < m;j++){
18.             g[i][j] = scan.nextInt();
19.           }
20.         }
21.         dfs(0,0,g[0][0]);
22.         System.out.print(ans);
23.         scan.close();
24.     }
25.     public static void dfs(int x,int y,int count){
26.       if(x+1 == n && y+1 == m){
27.         ans = Math.max(count,ans);
28.       }
29.       for(int i = 0;i < 9;i++){
30.         int nx = x + dx[i];
31.         int ny = y + dy[i];
32.         if(nx >= 0 && ny >= 0 && nx < n && ny < m){
33.           dfs(nx,ny,count+g[nx][ny]);
34.         }
35.       }
36.     }
37. }

复制代码

 岛屿个数

BFS
   小蓝得到了一副巨细为 M×N 的格子地图，可以将其视作一个只包罗字符 '0'（代表海水）和 '1'（代表陆地）的二维数组，地图之外可以视作全部是海水，每个岛屿由在上/下/左/右四个方向上相邻的 '1' 相毗连而形成。
  叨教这个地图上共有多少个岛屿？在进行统计时不必要统计子岛屿的数目。
  输入格式
  第一行一个整数 T，表示有 T 组测试数据。
  接下来输入 T 组数据。对于每组数据，第一行包罗两个用空格分隔的整数 M、N 表示地图巨细；接下来输入 M 行，每行包罗 N 个字符，字符只可能是 '0' 或 '1'。
  输出格式
  对于每组数据，输出一行，包罗一个整数表示答案。
  样例输入
  2 5 5
  01111
  11001
  10101
  10001
  11111
  5 6
  111111
  100001
  010101
  100001
  111111
  样例输出
  1
  3

1. import java.util.*;
2. // 1:无需package
3. // 2: 类名必须Main, 不可修改
4. public class Main {
5. //解题思路 ： 海水连通8个方向，陆地连通4个方向，通过8个方向的海水可以访问到不是环的外岛内的海水和内岛（说明此时外岛不是环）
6. //使用bfs搜索外岛海水，碰到海水继续搜索其他连通海水，碰到陆地，此时岛数量+1，使用陆地的bfs，搜索找出这个岛
7. //为了防止重复搜索死循环，需要给海水和陆地都加上访问数组判断是否访问
8.    static int N = 51;
9.    static char[][] map;//存储地图
10.    static boolean[][] sea;//存储访问的海水
11.    static boolean[][] island;//存储访问的陆地
12.    static int m;
13.    static int n;
14.    static int[] seaDx = {-1,-1,-1,0,0,1,1,1};
15.    static int[] seaDy = {-1,0,1,-1,1,-1,0,1};//海的八个方向
16.    static int[] landDx = {-1,1,0,0};
17.    static int[] landDy = {0,0,-1,1};//陆地的四个方向
18.    static int ans;
19.    public static void main(String[] args) {
20.        Scanner sc = new Scanner(System.in);
21.        int T = sc.nextInt();
22.        while(T -- > 0) {
23.            boolean flag = false;
24.            m = sc.nextInt();
25.            n = sc.nextInt();
26.            map = new char[m][n];
27.            sea = new boolean[m][n];
28.            island = new boolean[m][n];
29.            for(int i = 0 ; i < m ; i ++) {
30.                map[i] = sc.next().toCharArray();
31.            }
32.            ans = 0;
33.            for(int i = 0 ; i < m ; i++) {
34.                for(int j = 0 ; j < n ; j++) {
35.                    if(i == 0 || i == m - 1 || j == 0 || j == n - 1) {//从外海开始找，如果外面一周都是陆地，那肯定就只有一个岛了
36.                        if(map[i][j] == '0' && !sea[i][j]) {
37.                            flag = true;//不是只有一个岛
38.                            bfsSea(i, j);
39.                        }
40.                    }
41.                }
42.            }
43.            System.out.println(flag ? ans : 1);
44.        }
45.    }
46.    public static boolean check(int i , int j) {//边缘检测
47.        return (i >= 0 && i < m && j >= 0 && j < n);   
48.    }
49.     public static void bfsLand(int i, int j) {
50. //陆地的bfs，作用是找到岛，把其在对应的boolean数组里标注为true
51.         Queue<int[]> list = new LinkedList<>();
52.         island[i][j] = true;
53.         list.offer(new int[]{i,j});//通过这个数组存储当前的x,y坐标
54.         while (!list.isEmpty()) {
55.             int[] poll = list.poll();
56.             for (int k = 0; k < 4; k++) {
57.                 int nx = poll[0] + landDx[k];
58.                 int ny = poll[1] + landDy[k];
59.                 if (check(nx, ny) && map[nx][ny] == '1' && !island[nx][ny]) {
60.                     island[nx][ny] = true;
61.                     list.offer(new int[] {nx,ny});
62.                 }
63.             }
64.         }
65.     }
66.     public static void bfsSea(int i, int j) {
67. //海的bfs，作用是寻找连通的海和岛，8个方向使其可以访问到内岛的海，如果八个方向都访问不到海，说明只有一个岛
68. //如果能找到岛，就把答案+1，用陆地bfs把这个岛标注出来
69.         Queue<int[]> list = new LinkedList<>();
70.         sea[i][j] = true;
71.         list.offer(new int[] {i,j});
72.         
73.         while(!list.isEmpty()) {
74.             int[] poll = list.poll();
75.             for(int k = 0 ; k < 8 ; k++) {
76.                 int nx = poll[0] + seaDx[k];
77.                 int ny = poll[1] + seaDy[k];
78.                 if(check(nx, ny) && map[nx][ny] == '0' && !sea[nx][ny]) {
79.                     sea[nx][ny] = true;
80.                     list.offer(new int[] {nx,ny});
81.                 }
82.                 if(check(nx, ny) && map[nx][ny] == '1' && !island[nx][ny]) {
83.                     ans++;
84.                     bfsLand(nx, ny);
85.                 }
86.                
87.             }
88.         }
89.     }
90. }

复制代码

 买瓜

前缀和DFS
   
  小蓝正在一个瓜摊上买瓜。瓜摊上共有 n 个瓜，每个瓜的重量为 AiA。
  小蓝刀功了得，他可以把任何瓜劈成完全等重的两份，不过每个瓜只能劈一刀。
  小蓝盼望买到的瓜的重量的和恰好为 m。
  叨教小蓝至少要劈多少个瓜才能买到重量恰好为 m 的瓜。如果无论怎样小蓝都无法得到总重恰好为 m 的瓜，请输出 −1。
  输入格式
  输入的第一行包罗两个整数 n，m，用一个空格分隔，分别表示瓜的个数和小蓝想买到的瓜的总重量。
  第二行包罗 n 个整数 Ai​，相邻整数之间使用一个空格分隔，分别表示每个瓜的重量。
  输出格式
  输出一行包罗一个整数表示答案。
  样例输入
  3 10
  1 3 13
  
  样例输出
  2
  

1. import java.util.Arrays;
2. import java.util.Scanner;
4. public class Main {
5.     static int n, ans = 50;
6.     static long m;
7.     static long[] a = new long[50];
8.     static long[] sum = new long[50];
10.     public static void main(String[] args) {
11.         Scanner scan = new Scanner(System.in);
12.         n = scan.nextInt();
13.         m = scan.nextLong() * 2; // 目标质量也要乘以2才能保证结果不受影响
14.         for (int i = 0; i < n; i++) {
15.             a[i] = scan.nextLong() * 2; // 为了防止劈瓜出现小数，将其左移一位乘以2倍
16.         }
17.         Arrays.sort(a, 0, n); // 根据题目要求，需要让质量大的在前面，争取最小劈瓜次数可以满足条件
18.         reverseArray(a, n);
20.         // 遍历所有的瓜
21.         for (int i = n - 1; i >= 0; i--) {
22.             sum[i] = sum[i + 1] + a[i]; // 当前瓜及其之后所有瓜的总质量=从1到下一个瓜的总质量+当前瓜的质量
23.         }
24.         dfs(0, 0, 0);
25.         if (ans != 50) // 最终 ans 不再是初始值 50，则表示找到了劈瓜的方式满足要求
26.             System.out.println(ans);
27.         else
28.             System.out.println(-1);
29.     }
31.     static void dfs(long S, int i, int cnt) {
32.         if (cnt >= ans)
33.             return;
34.         if (S == m)
35.             ans = cnt;
36.         if (i >= n || S > m || S + sum[i] < m)
37.             return; // 递归结束条件
38.         dfs(S, i + 1, cnt);
39.         dfs(S + a[i], i + 1, cnt);
40.         dfs(S + a[i] / 2, i + 1, cnt + 1);
41.     }
43.     // 反转数组
44.     static void reverseArray(long[] arr, int n) {
45.         int left = 0;
46.         int right = n - 1;
47.         while (left < right) {
48.             long temp = arr[left];
49.             arr[left] = arr[right];
50.             arr[right] = temp;
51.             left++;
52.             right--;
53.         }
54.     }
55. }

复制代码

数字三角形

动态规划DFS
   从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。
  路径上的每一步只能从一个数走到下一层和它近来的左边的那个数大概右 边的那个数。此外，向左下走的次数与向右下走的次数相差不能凌驾 1。
  输入描述
  输入的第一行包罗一个整数 N (1≤N≤100)，表示三角形的行数。
  下面的 N 行给出数字三角形。数字三角形上的数都是 0 至 100 之间的整数。
  输出描述
  输出一个整数，表示答案。
  输入输出样例
     输入
   5
   7
   3 8
   8 1 0
   2 7 4 4
   4 5 2 6 5
       输出
   27
     第三天：省一有盼望

   目标：把握 DP焦点模型 + 图论遍历与最短路 + 贪心策略，确保省二冲刺！ 
  

• DP定框架
  
• 贪心骗大分
  
• 图论暴力搜
  

  路径

动态规划
   小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，盼望找到图 中的最短路径。
  小蓝的图由 2021 个结点组成，依次编号 1 至 2021。
  对于两个不同的结点 a, b，如果 a 和 b 的差的绝对值大于 21，则两个结点 之间没有边相连；如果 a 和 b 的差的绝对值小于等于 21，则两个点之间有一条 长度为 a 和 b 的最小公倍数的无向边相连。
  例如：结点 1 和结点 23 之间没有边相连；结点 3 和结点 24 之间有一条无 向边，长度为 24；结点 15 和结点 25 之间有一条无向边，长度为 75。
  请盘算，结点 1 和结点 2021 之间的最短路径长度是多少。

1. import java.util.*;
3. public class Main {
5.     public static void main(String[] args) {
6.         //1.创建dp数组，dp[i]代表从1到这个位置的最短路径
7.         int[] dp =new int[2022];
8.         //2.初始化
9.         Arrays.fill(dp,Integer.MAX_VALUE);
10.         dp[1] = 0;
12.         for (int i = 1; i < dp.length; i++) {
13.             for (int j = i+1; j < dp.length && Math.abs(i-j)<=21; j++) {
14.                 //3.确定递推公式
15.                 //max(前一个点的路径总和+两个点的最小公倍数,当前的最短路径和)
16.                 dp[j] = Math.min(dp[j],lcm(i,j)+dp[i]);
17.             }
18.         }
19.         System.out.println(dp[2021]);
21.     }
23.     private static int lcm(int a,int b){
24.         return a*b / gcd(a,b);
25.     }
27.     private static int gcd(int a, int b) {
28.         return b == 0 ? a : gcd(b,a % b);
29.     }
30. }

复制代码

---

   好了本期内容，谢谢观看！记得多看加深印象，查漏补缺，例如本期没有提到的排序、前缀和、二分、差分等。
  如果考完没有理想的成绩不要紧，你要记着，只要你学到了，那就是最好的效果。
  工科我建议多实习，多做项目，多了解先进技能，无限进步，加油！

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。