当前位置：首页 > news >正文

蓝桥杯C++AB算法辅导

news 来源：原创 2024/5/19 0:33:46

文章目录

1.1 教学计划与递归
- 92. 递归实现指数型枚举
- 94. 递归实现排列型枚举
- 717. 简单斐波那契
- 95. 费解的开关
1.2 递推与递归——习题课
- 93. 递归实现组合型枚举
- 1209. 带分数
- 116. 飞行员兄弟
- 1208. 翻硬币
2.1 二分与前缀和
2.2 二分与前缀和——习题课
3.1 数学与简单DP
3.2 数学与简单DP——习题课
4.1 枚举、模拟与排序
4.2 枚举、模拟与排序——习题课
5.1 树状数组和线段树
5.2 树状数组和线段树——习题课
6.1 双指针、BFS和图论
6.2 双指针、BFS和图论——习题课
7.1 贪心
7.2 贪心——习题课
8.1 数论
8.2 数论——习题课
9.1 复杂DP
9.2 复杂DP——习题课
10.1 疑难杂题
10.2 疑难杂题——习题课
11 第十一届蓝桥杯省赛C++B组真题（7月）
12 第十二届蓝桥杯省赛C++B组真题（4月）
13 第十三届蓝桥杯C++ B组真题

1.1 教学计划与递归

在这里插入图片描述

92. 递归实现指数型枚举

94. 递归实现排列型枚举

在这里插入图片描述

全排列满足字典序最小，根据递归第一轮满足字典序最小之后也最小

全排列：dfs基础

#include<iostream>

using namespace std;

const int N = 10;
int path[N];
bool st[N];
int n;
void dfs(int u)//当前位u
{
    if(u == n)
    {
        for(int i = 0;i < n;i++)printf("%d ",path[i]);
        puts("");
    }
    
    for(int i = 1;i <= n;i++)
    {
        if(!st[i])
        {
            st[i] = true;
            path[u] = i;
            dfs(u + 1);
            path[u] = 0;//恢复现场，但其实path因为会被覆盖，所以这步可以省略【简单理解：全排列枚举所有结果就要恢复现场】
            st[i] =false;
        }
    }
}

int main()
{
    
    cin >> n;
    
    dfs(0);
        
    return 0;
}

717. 简单斐波那契

存储Fib版

#include<iostream>
using namespace std;

const int N = 50;
int f[N];
int n;
int main()
{
    cin >> n;
    f[1] = 0 ,f[2] = 1;//下标从1开始 (也可以从0开始)
    for(int i = 3;i <= n;i++)f[i] = f[i - 1] + f[i - 2];
    
    for(int i = 1 ;i <= n;i ++)printf("%d ",f[i]);
    
    return 0;
}

不开数组版:滚动数组 - dp雏形
注意Fib当n超过46就需要开高精度了



#include<stdio.h>
typedef long long LL;
LL n,a = 0, b = 1, c;//a第一项，b第二项，下一项c = a + b ， a，b位置再往后移动
int main()
{
    scanf("%d",&n);
    while(n--)
    {
        printf("%d ",a); //a每轮表示第i项  从1开始
        c=a+b;
        a=b,b=c;
    }
}

95. 费解的开关

1.2 递推与递归——习题课

93. 递归实现组合型枚举

在这里插入图片描述

1209. 带分数

116. 飞行员兄弟

1208. 翻硬币

初始状态变化到目标状态：常用BFS
仅限定一次翻转即为最优解

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n;
char start[N], aim[N]; //记录初始 -->目标状态  ，【不能用end 或 y : 库函数重名】


void turn(int i)
{
    if (start[i] == '*') start[i] = 'o';
    else start[i] = '*';
}

int main()
{
    cin >> start >> aim;//输入字符串 [一维char数组]
    n = strlen(start);//char数组长度

    int res = 0;
    for (int i = 0; i < n - 1; i ++ )//翻转到倒二个，包含倒一
        if (start[i] != aim[i])
        {
            turn(i), turn(i + 1);//依题意翻转
            res ++ ;//翻转次数
        }

    cout << res << endl;
    return 0;
}