Note：

什么是暴力方法

没有准确定义。一般指拿到问题之后，我们第一时间能想到的朴素方法。

暴力算法一般复杂度较高，很多优秀算法是在朴素算法之上改进而来的。

就直接硬写，写出来后再进行各种优化。

什么是模拟

「模拟」，顾名思义，把出题人描述的场景用代码实现。
一般不需要我们的算法作决策。只需要模拟即可。

模拟是一类题目的统称，有难有易,简单的有A+B problem，难的有猪国杀，一般考察代码能力。

用代码把题目里的场景重现一遍。
可能有些模拟算法需要优化。

模拟 - OI Wiki (oi-wiki.org)

基本枚举方法

所谓枚举，即不重不漏地列举出所有情况。
常用手段：循环、递归

尝试每一种情况。当然，一些不可能的情况可以不去枚举，以此优化时间复杂度。

现代cpu的运算速度一般达到了2000w/s，所以只要预估不超过2000w的运算，那么这个算法就是可行的。

因为时间复杂度是预估的，实际可能更大或者更小

Learned：

递归枚举——深度优先搜索（Depth-first search）

枚举子集

今有 nn 位同学，可以从中选出任意名同学参加合唱。

对于每一个同学，我们都有去，或者不去2种选择，所以我们只需要枚举去或者不去即可

1
2
3
4
5
6
7
8
9
10
11
12
void dfs(int pos) 
{
    if(pos == n+1) 
    {
		/*处理*/
        return;
    }
    a[pos] = 0;
    dfs(pos + 1);
    a[pos] = 1;
    dfs(pos + 1);
}

枚举元组

给定 n 和 k，请按字典序输出全体 n 元组，其中元组内的元素是在 [1,k] 之间的整数。

1
2
3
4
5
6
7
8
9
10
11
12
void dfs(int pos) {
    if(pos == n+1) {//边界条件与输出
        for(int i=1; i<=n; i++)
            printf("%d ", a[i]);
        printf("\n");
        return;
    }
    for(int i=1; i<=k; i++) {//边界条件与输出
        a[pos] = i;
        dfs(pos + 1);
    }
}

枚举排列

今有 n 名学生，要从中选出 k 人排成一列拍照。按照字典序输出排列。

与枚举元组十分相似，很多枚举题都是从枚举元组和枚举子集魔改而来，这题也不例外。只需判断一个人是否出现2次即可。

定义used数组确保一个人只去了一次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const int MAXN = 15;
bool used[MAXN];
void dfs(int pos) {
    if(pos == k+1) {//边界条件与输出
        for(int i=1; i<=k; i++)
            printf("%d ", a[i]);
        printf("\n");
        return;
	}
    for(int i=1; i<=n; i++)//边界条件与输出
        if(!used[i]) {
        a[pos] = i;//使用
        used[i] = true;//标记
        dfs(pos + 1);
        used[i] = false;//如果不标记回来，下一次枚举就不会枚举这个人
    }
}

剪枝

一般的枚举遵循先枚举、再检验的过程。但如果我们可以在枚举中途就发现某条
路不可行，直接不去走这条路，就能节省时间。
这便是剪枝，一个dfs能剪枝就减，不然可能会造成TLE（Time Limit Enough）

gcd辗转相除法的学习

我们有36和24

36%24得到12现在是[12,24],24%12得到[0,12]返回即可，他的模板是:

1
2
3
4
int gcd(int a,int b){
	if(b==0)return 0;
	gcd(b,a%b);
}

date: 2022-07-16 12:22:45