Today is the second day of the course.
Note:
什么是暴力方法
没有准确定义。一般指拿到问题之后,我们第一时间能想到的朴素方法。
暴力算法一般复杂度较高,很多优秀算法是在朴素算法之上改进而来的。
就直接硬写,写出来后再进行各种优化。
什么是模拟
「模拟」,顾名思义,把出题人描述的场景用代码实现。
一般不需要我们的算法作决策。只需要模拟即可。
模拟是一类题目的统称,有难有易,简单的有A+B problem,难的有猪国杀,一般考察代码能力。
用代码把题目里的场景重现一遍。
可能有些模拟算法需要优化。
模拟 - OI Wiki (oi-wiki.org)
基本枚举方法
所谓枚举,即不重不漏地列举出所有情况。
常用手段:循环、递归
尝试每一种情况。当然,一些不可能的情况可以不去枚举,以此优化时间复杂度。
现代cpu的运算速度一般达到了2000w/s,所以只要预估不超过2000w的运算,那么这个算法就是可行的。
O(n^{2})一般可以跑5000的数据
O(n^{3})一般可以跑500的数据
O(n!)只能跑到10
因为时间复杂度是预估的,实际可能更大或者更小
Learned:
递归枚举——深度优先搜索(Depth-first search)
枚举子集
今有 nn 位同学,可以从中选出任意名同学参加合唱。
对于每一个同学,我们都有去,或者不去2种选择,所以我们只需要枚举去或者不去即可
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] 之间的整数。
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数组确保一个人只去了一次
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)