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);
}

枚举元组

给定 nk,请按字典序输出全体 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