蓝桥杯考前指导

时间复杂度

一秒钟10^8^对于不同的问日

一般ACM或者笔试题的时间限制是1秒或2秒。 在这种情况下，C++代码中的操作次数控制在 10^7^∼10^8^最佳

由此我们便可以通过时间复杂度倒推可能使用的算法

PS：此处的n指数据量（点数、边数），有些问题的数据量可能存在两个值（n、m）这时n^2^也可能表示为mn

遇事先暴力 再算复杂度 不过再说优化

更新: 12/19/2024 字数: 0 字 时长: 0 分钟

遇事别绕弯 先想自然语言能否直接转化成代码

更新: 12/19/2024 字数: 0 字 时长: 0 分钟

一：递归与递推

时间复杂度大于10^5^则使用scanf与printf，大概快一倍。

递归->dfs（暴力搜索）

核心在于顺序，即从1--n，依次考虑每个数选或是不选,由递归搜索树转译为代码

字典序最小->从小到大进行枚举

枚举分类

指数型枚举

每一个位置上的数字固定，对于该位置上的数只存在两种情况，选与不选

特点：对内容存在选与不选两种情况,数据排列数序已经固定，不需要在每次dfs中记录排序

#include <iostream>
using namespace std;
const int N=20;
int n;
bool st[N];  //此处的默认排序为从小到大排序，若存在其他排序形式，则应单独开一个path数组记录初始排序状态

void dfs(int t){
    if(t>n){  //如果遍历到最后一个数字，则输出
        for(int i=1;i<=n;i++)
            if(st[i])
                cout<<i<<' ';
        cout<<endl;
        return;
    }
    st[t]=true;   //第一种情况，该位置选
    dfs(t+1);
    st[t]=false;  //第二种情况，该位置不选
    dfs(t+1);
}

int main(){
    cin>>n;
    dfs(1);
}

**简介：**利用递归的特点，递归只有在走完本函数中调用的函数后才会向下走，即撞到南墙再回头。利用这一特点，我们便可以对所有有终点的数据进行排列

排列型枚举

不考虑顺序，对全部内容进行枚举

**特点：**需要状态数组对每个数据进行记忆

#include<iostream>

using namespace std;

const int N=10;
bool st[N];
int path[N];
int n;

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

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

最经典的dfs问题，不再多说

组合类型枚举

考虑顺序，对所有数字进行枚举

特点：不需要状态数组记录状态（顺序固定，即当并非每个数都可以按照任意顺序去放）

#include <iostream>

using namespace std;

const int N=30;
int way[N];
int n;

void dfs(int t,int start){
    if(u+n-start<m) return; //剪枝 
    if(t>n){
        for(int i=0;i<n;i++)
            cout<<way[i]<<' ';
        cout<<endl;
        return;
    }
    for(int i=start;i<=n;i++){
        way[t]=i;
        dfs(t+1,i);//每次都固定使用比前一个数大的数
    }
}

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

对于状压枚举所有可能性，仅限于小于16格的矩阵，再大会出现超时的可能性

最短->bfs/模拟

模拟->对于一个状态，找到起始点（该点变化方式及变化种类固定，且变换后后续状态可能性固定为一个区间），由此处开始递推，然后次次去找每层循环的起始点即可

数学知识：向上取整

对于a/b向上取整==（a+b-1）/b向下取整