蓝桥杯刷题总结-合集(持续更新)_蓝桥杯前端刷题

作者：凡人多烦事01 | 2024-04-16 00:26:53

踩

蓝桥杯前端刷题

蓝桥杯刷题总结

待办：

0. 刷题前须知
1. 递归与递推
2. 二分
3. 前缀和
4. 数学
5. 枚举
6. 模拟
7. 排序
8. 双指针
9. BFS
10. 图论
11. 树状数组
12. 线段树
13. 贪心
14. 数论
15. 简单DP
16. 复杂DP
17. 杂题
18. 十一届蓝桥杯真题
19. 十二届蓝桥杯真题

BaseOn ： https://www.acwing.com

0、刷提前的须知

1、输入

in.next()和in.nextLine()

package com.caopeng.zero;

import java.util.Scanner;

/**
 * @author Crescent_P
 * @date 2021-12-02 19:41
 */
public class InputOutput1 {
   
    public static void main(String[] args) {
   
        // Scanner类输入
        Scanner in = new Scanner(System.in);
        // 整数
//        int a = in.nextInt();
        // 浮点数
//        double v = in.nextDouble();
        // 长整数
//        long c = in.nextLong();
        // short
//        short d = in.nextShort();
        // 字符串
        String s1 = in.next();          // c++ 中的 cin/scanf 遇到空格结束
        String s2 = in.nextLine();      // c++ 中的 gets      遇到回车结束
        // 输入 abc def g
        System.out.println("s1 :" + s1);    // s1 :abc
        System.out.println("s2 :" + s2);    // s2 : def g
    }
}
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

hasNext()

package com.caopeng.zero;

import java.util.Scanner;

/**
 * @author Crescent_P
 * @date 2021-12-02 19:41
 */
public class InputOutput2 {
   
    public static void main(String[] args) {
   
        // Scanner类输入
        Scanner in = new Scanner(System.in);
        // hasNext()
        // hasNext()返回的是bool类型、当缓冲区有数据返回true
        // 当缓冲区没有数据会发生阻塞、等待数据的输入
        // 遇到多组输入，不知道什么时候能结束输入可以使用
        // while(in.hasNext()) 相当于 while(scanf())
        int a,b,c;
        while(in.hasNext()){
   
            a = in.nextInt();
            b = in.nextInt();
            c = in.nextInt();
            System.out.printf("%d\n",a+b+c);    // 模式化输出
        }

    }
}

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

2、输出

// 常见的输出
System.out.println();       // 带换行的
System.out.print();         // 不带换行的
System.out.printf();        // 格式化输出，相当于c/c++ 的 printf
1
2
3
4

3、快速输出输出

BufferedReader和BufferedWriter实现

4、集合容器

1、递归与递推

递归实现指数型枚举

java

import java.util.*;

public class Main{
   
    static Scanner in = new Scanner(System.in);		// 输入
    // 看题目范围 n是1到15，我们稍微把数组开大一点点、防止数组越界。
    static int max = 20,n;							
    // 判断每一位是否被用过
    static boolean[] st = new boolean[max];
    public static void main(String[] args){
   
        n = in.nextInt();
        dfs(0);
    }
    // dfs(深度优先搜索)
    private static void dfs(int u){
   
        // 搜索到最后一位
        if(u == n){
   
            // 打印输出
            for(int i = 0;i < n;i++){
   
                if(st[i]) System.out.printf("%d ",i+1);
            }
            System.out.println();
            return;
        }
        // 要第u位
        st[u] = true;
        dfs(u+1);
        // 不要第u位
        st[u] = false;
        dfs(u+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

C/C++

#include <bits/stdc++.h>

using namespace std;

const int N = 20;

bool st[N];

int n;

void dfs(int u){
    // 递归到了叶子节点
    if(u == n){
        for(int i = 0;i < n;i++){
            if(st[i]) cout << i + 1 << " ";
        }
        cout << endl;   // 换行
        return;
    }
    // 选
    st[u] = true;
    dfs(u+1);
    
    // 不选
    st[u] = false;
    dfs(u+1);
}

int main(){
    cin >> n;
    dfs(0);
    return 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

递归实现排列型枚举

Java

import java.util.*;
import java.io.*;
public class Main {
   
    static Scanner in = new Scanner(System.in);
    static int max = 10, n;
    static int[] path = new int[max];       // 存储路径
    static boolean[] st = new boolean[max]; // 记录每个数字是否被使用了
    static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args)throws Exception{
   
        n = in.nextInt();
        dfs(0);
        out.flush();
    }
    private static void dfs(int u) throws Exception{
   
        if(u == n){
   
            for(int i = 0;i < n;i++) out.write(path[i] + " ");	// 快速写出
            out.write("\n");       // 换行
            return;
        }
        for(int i = 0;i < n;i++){
   
            if(!st[i]){
   
                st[i] = true;
                path[u] = i+1;
                dfs(u+1);
                st[i] = false;
                path[u] = 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

C/C++

#include <bits/stdc++.h>

using namespace std;

const int N = 10;

int path[N];
bool st[N];
int n;

void dfs(int u){
    if(u == n){
        for(int i = 0;i < n;i++) cout << path[i] << " ";
        cout << endl;
        return;
    }
    for(int i = 0;i < n;i++){
        if(!st[i]){
            st[i] = true;
            path[u] = i+1;
            dfs(u+1);
            st[i] = false;
        }
    }
}

int main(){
    cin >> n;
    dfs(0);
    return 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

递归实现组合型枚举

Java

import java.util.*;
public class Main{
   
    static Scanner in = new Scanner(System.in);
    static int max = 30,n,m;
    static int[] path = new int[max];
    public static void main(String[] args){
   
        n = in.nextInt();
        m = in.nextInt();
        dfs(0);
        return;
    }
    public static void dfs(int u){
   
        if(u == m){
   
            for(int i = 0;i < m;i++) System.out.printf("%d ",path[i]);
            System.out.println();
            return;
        }
        for(int i = 1;i <= n;i++){
   
            if(u == 0) path[u] = i;
            else {
   
                if(path[u-1] < i) path[u] = i;
                else continue;
            }
            dfs(u+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

C/C++

#include <bits/stdc++.h>

using namespace std;

const int N = 30;

int path[N];

int n,m;

void dfs(int u){
    if(u == m){
        for(int i = 0;i < m;i++) cout << path[i] << " ";
        cout << endl;
        return;
    }
    for(int i = 1;i <= n;i++){
        if(u == 0) path[u] = i;
        else{
            // 前一位要比这一位小
            if(path[u-1] < i) path[u] = i;
            else continue;
        }
        dfs(u+1);
    }
}

int main(){
    cin >> n >> m;
    dfs(0);
    return 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

简单的斐波那契数列

java

import java.util.*;
public class Main{
   
    static Scanner in = new Scanner(System.in);
    static int n,a = 0,b  = 1;
    public static void main(String[] args){
   
        n = in.nextInt();
        for(int i = 0;i < n;i++){
   
            System.out.printf("%d ",a);
            int temp = a + b;
            a = b;
            b = temp;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

C/C++

#include <bits/stdc++.h>

using namespace std;

// 递推公式
// a[i] = a[i-1] + a[i-2]

int n;

int main(){
    int a = 0,b = 1;
    cin >> n;
    for(int i = 0;i < n;i++){
        cout << a << " ";
        int temp = a + b;
        b = a;
        a = temp;
    }
    cout << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

费解的开关

想写出这个题目，首先得分析出几个点：

每个灯泡只能被摁一次，因为摁两次不会有任何改变，并且还多了步数
摁的顺序是无所谓的，先摁哪个再摁哪个是没关系的。

依靠上面两个结论，我们来看这一题：

我们可以先只看第一行，第一行我们可以随意摁，但是每个灯泡只能被操作一次。
第一行被操作过了，轮到第二行，此时第一行如果还有灭的，只能通过第二行来将其熄灭。逻辑就是这样，下面的每一行的灯泡是否操作，都是看上一行灯灯泡的状态。

因此：

我们枚举第一行的所有状态
1. 怎么枚举，第一行一共5个灯泡、每个灯泡开或关有两种状态、那么就是2^5=32种状态
之后根据当前第一行的状态去操作后续的行
到最后一行、看是否有开的，如果有，说明不能全灭

C/C++

#include <bits/stdc++.h>

using namespace std;

const int N = 6;

char g[N][N],backup[N][N];

// 偏移量,用于遍历(x,y)的上下左右中
int dx[5] = {1,0,-1,0,0},dy[5] = {0,1,0,-1,0};

// 将(x,y)的上下左右摁一遍
void turn(int x,int y){
    for(int i = 0;i < 5;i++){
        int nx = x + dx[i],ny = y + dy[i];
        if(nx < 0 || nx > 5 || ny < 0 || ny > 5) continue;  // 外界不需要考虑
        if(g[nx][ny] == '0') g[nx][ny] = '1';
        else g[nx][ny] = '0';
    }
}

int main(){
    int T;
    cin >> T;
    while(T--){
        // 将图读入
        for(int i = 0;i < 5;i++) cin >> g[i];
        // 第一行一共5个按钮,每个按钮开或不开一共2种情况,2^5 = 32
        int ans = 10;
        for(int op = 0;op < 32;op++){
            memcpy(backup,g,sizeof g);  // 将 g的内容放入backup中备份
            int step = 0;   // 操作的步数
            // 第一行所有情况
            for(int i = 0;i < 5;i++){
                // 当前对应了1就操作
                if(op >> i & 1){
                    step++;
                    turn(0,i);
                }
            }
            // 每一行的每一个开关开或不开其实是受上一行的开关影响的
            for(int i = 0;i < 4;i++){
                for(int j = 0;j < 5;j++){
                    // 当前是关的,那么下一行对应的必须操作一次,这个才能打开
                    if(g[i][j] == '0'){
                        step++;
                        turn(i+1,j);
                    }
                }
            }
            // 最后一行是不能有关闭的,否则就是不能实现
            bool dark = false;
            for(int i = 0;i < 5;i++){
                if(g[4][i] == '0'){
                    dark = true;
                    break;
                }
            }
            if(!dark) ans = min(ans,step);
            memcpy(g,backup,sizeof g);  // 将 g的内容放入backup中备份
        }
        if(ans > 6) ans = -1;
        cout << ans << endl;
    }
    return 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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

java

import java.util.*;
public class Main{
   
    static Scanner in = new Scanner(System.in);
    static int max = 5;
    static char[][] g = new char[max][max];
    static char[][] backup = new char[max][max];
    static int[] dx = {
   1,0,-1,0,0},dy = {
   0,1,0,-1,0};
    public static void main(String[] args){
   
        int T = in.nextInt();
        // T个测试样例
        while(T-- > 0){
   
            // 读入图
            int res 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/凡人多烦事01/article/detail/431216