这是一个正在更新中的C++算法帖子

基本框架

#include<iostream>
using namespace std;
int main(){

    return 0;
}

一、枚举

简单的算法之一

枚举，就是暴力列出所有可能性

枚举一定要知道的两个要素:

1、枚举的对象和范围

2、判断条件

例如#4193. 因子问题

要求出最小的因子，首先要知道枚举的是什么

这道题很简单，枚举的就是最小的正整数a，范围为1~m(因为如果超过m就变成了负数)

for(int a=1;a<=m;a++)//枚举a 范围1~m

对象和范围知道了，那条件又是什么呢？

题目描述中清楚的说了:求一个最小的正整数a，使得a和(M-a)都是N的因子。

N肯定要被a整除，且N要被M-a整除

if(n%a==0&&n%(m-a)==0)//判断条件

判断后直接输出即可

二、递推

递推是按照一定的规律来计算序列中的每个项,思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复

递推通常使用数组，它的两个重点分别是:

1、初始值

2、递推关系式

例如斐波那契数列,它的规律是这个数等于前两个数的和

这道题用递推做的话，首先要知道至少要有几个初始值

因为第三个数等于前两个数的和，所以只需两个数就能推出所有数

而它的前两个数都是1

int a[1145]={0/*第0个数没有值*/,1,1};

而递推关系式可以通过题目获得

斐波那契数列的一个数等于前两个数的和

所以递推关系式为

a[i]=a[i-1]+a[i-2]

最后按照题意输出即可

提示:题目中如果让你取余，建议在计算时就取余，这样是不影响结果的

三、递归

3-1、递归

递归通常用于解决高难度的题

直接或间接调用自身函数称为递归函数，递归的核心是把一个规模较大的问题拆解为规模较小的问题来求解。

递归和递推有相似之处，因为递归自己调用自己就等于递推的循环，但是递归是从未知到已知，不需要初始值

递归必须有的东西:

递归边界，使用递归算法必须有明确的结束条件

举个例子，求阶乘，这道题用递归该怎么做呢?

如果要求n的阶乘，首先要知道它的边界

由于1的阶乘为1，所以暂定1为边界

if(n==1) return 1;

边界知道了，那该怎么求n!呢?

首先先思考能不能将这个问题化为小问题

假设n为5

5!是不是等于5*4!，那4!等于什么呢?等于4*3!

这样一步一步求到1的阶乘，最后返回阶乘就可以了

return n*f(n-1);//递归等式

3-2 记忆化递归

记忆化递归的原理是让函数计算问题的结果时，能够记住这个结果(用数组存储)，以后求相同问题的结果时，直接使用，不用重复计算。

你会发现，记忆化递归跟递推很相似，只不过没初始值而已

计算出结果后，直接返回数组的第n项就行

四、搜索

4-1 深度优先搜索(深搜)

深度优先搜索的思路是枚举，基础是递归，适用于要求所有解方案或判断是否能走到哪里的题目

深搜的步骤:

1 列出所有可能

2 判断是否满足题意

3 满足则记录当前可能

4 继续往下搜索

5 回溯

深搜的思想是能深就深，不能深则退。意思就是说先走一步到一个新的起点，然后继续走到满足条件的地方，如果不能继续走，则回退一步，一直反复。直到找到解或证明无解

深搜是有框架的，其算法框架如下:

void dfs(变量){
    if(满足结束条件){
        执行操作
        return;
    }
    else{
        for(int i=0;i<状态的可能扩展数;i++){
            枚举下一步走哪里(这个可以不要)
            if(判断这种可能是否可行){
                执行代码
                调用函数
                回溯(按题目需求写)
            }
        }
    }
}

但由于深搜的思想和枚举类似，在做一些数据量大的题目时会,所以深搜只适合于数据小的题目

如果你想更快的TLE的话可以在调用时加个循环

4-2 广度优先搜索(广搜)

广搜的实现涉及到队列的相关知识，篇幅受限，建议看这个

五、前缀和与差分

5-1 前缀和

1.前缀和是什么?

前缀和就是用一个数组s去存数组a的前n项的和。

原数组:a[1],a[2],a[3],a[4]……

前缀和数组:s[i]=a[1]+a[2]+a[3]+……+a[i]

这样s[n]对应的就是a[1]—a[n]的和，s的每一项都这样对应，就构成了前缀和。

2.暴力前缀和

在做数据量小的题目时，可以直接用for/while循环遍历数组，用sum加a[i]就可以了

int l,r;
cin>>l>>r;
for(int i=l;i<=r;i++){
    sum+=a[i];
}

这种暴力的方法也能求出[L,R]的前缀和，但时间复杂度为O(n),当数据过于强大时就会牺牲

3.前缀和

如何利用前缀和去求区间大小呢？

假设我们要求a[3]-a[6]的区间大小

s[3]=a[1]+a[2]+a[3];

s[6]=a[1]+a[2]+a[3]+a[4]+a[5]+a[6];

a[3,6]的前缀和就是a[3]+a[4]+a[5]+a[6];

只需要减去a[1]+a[2]就行了

可得公式为:

[L,R]=s[r]-s[l-1]

4.如何求前缀和

这个很好理解，举个例子就知道了

s[1]=s[0]+a[1]求的是第一个数的前缀和，而由于s[1]存储的是a[1]-a[1]的和，所以求s[2]的时候只需要加上a[2]就行了

s[2]=s[1]+a[2];

s[3]=s[2]+a[3]

……

s[i]=s[i-1]+a[i];

代码:

for(int i=1;i<=n;i++){
    cin>>a[i];
    s[i]=s[i-1]+a[i];
}

5.练习题

5-1 入门

3205.前缀和去探险

5-2 进阶

3900. 区间最大和去探险

6655. 7区间去探险

5-2 差分

剩下的有时间更新~