基础算法集合:思想

1.枚举

人话：挨个挨个试
举个例子
问题：给定10个数，给定一个数k，在这10个数中查找数k。
枚举法答案：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a[10];
    int k;
    cin>>k;
    for(int i=0;i<=10;i++)//循环挨个尝试
    {
        cin>>a[i];
        if(a[i]==k)
            cout<<i<<endl;
    }
    return 0;

枚举技巧：一定记住找到等量关系！

2.模拟

人话：题目牵着你鼻子走
例子：
首先计算a+b
然后加上a-b
模拟法答案：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b;
    cin>>a,b;
    int sum=0;
    sum=a+b;//step1
    sum-=a+b;//step2
    //lots of steps...
    return 0;
}

大模拟技巧：一步一步 流程图
复杂的大模拟就当我没说

3.分治

人话：1生2 2生3 3生万物
例子：
线段树
算了说人话
给出一个长度为 \(n\)的序列 \(a\)，选出其中连续且非空的一段使得这段和最大。
思路：
第一个数为一个有效序列
如果一个数加上上一个有效序列得到的结果比这个数大，那么该数也属于这个有效序列。
如果一个数加上上一个有效序列得到的结果比这个数小，那么这个数单独成为一个新的有效序列
在执行上述处理的过程中实时更新当前有效序列的所有元素之和并取最大值。
技巧：找到这个问题的最小单位去解（类似递归）

4.贪心

人话：只看眼前的，就近原则
举个例子，你只顾雪糕好吃，吃了\(10^9\)根
然后你就没了
这个例子说明什么？
不能吃太多雪糕
我们在使用贪心前要证明其正确性
例题：lg P1090 合并果子
关键：不断取最小的两堆合并成较大的一堆是最优的
证明：题中有类似我们每次都取 XXX 中最大/小的东西，并更新 XXX的东西。
技巧：题中有我们每次都取 XXX 中最大/小的东西，并更新 XXX。/我们将 XXX 按照某某顺序排序，然后按某种顺序（例如从小到大）选择大概率是贪心！！

来源链接：https://www.cnblogs.com/Doraemon-Blog/p/18671701