jfmfoi.广搜和带有技巧的搜索-230703

· · 个人记录

今日小朋友训练题单

2 - 8 广度优先搜索：

https://www.luogu.com.cn/training/314140

2 - 9 带有技巧的搜索：

https://www.luogu.com.cn/training/314141

知识点

1. 队列（数据结构）

图示 https://www.cnblogs.com/bigsai/p/11363071.html

用数组表示队列，head 和 tail 表示头尾。

// 声明
int qx[1010], qy[1010];
int head = 0, tail = 0;

// 添加第一个元素
qx[head = tail = 1] = 2;
qy[1] = 3; 

while (head <= tail) {
    int x = qx[head];
    int y = qy[head];
    head++;

    for (...) {
        int tx = x + 1;
        int ty = y - 1;
        tail++;
        qx[tail] = tx;
        qy[tail] = ty;
    }

}

2. pair<int, int> 和 queue<pair<int, int>>

pair<int, int> 是一种数据类型，可以把两个 int 打包在一起，和结构很像。

// 声明
pair<int, int> u;

// 使用
u = make_pair(5, 5);
u.first = 1;
printf("%d\n", u.second);

queue<pair<int, int> > 则制作了一个存放 pair 的队列。用这种变量，我们就可以把上面的队列示例代码改写为：

// 声明
queue<pair<int, int> > q;

// 添加新元素到队列尾部
q.push(make_pair(2, 3));

while (!q.empty()) {
    // 提出队列的头部
    pair<int, int> u = q.front();
    // 删除队列的头部
    q.pop();

    int tx = u.first + 1;
    int ty = u.second - 1;
    // 把新元素加入到队列的尾部
    q.push(make_pair(tx, ty));   
}

一题回忆 https://www.luogu.com.cn/problem/P1443：在网格里，从起点出发，不断向四周搜索。

3. 用深度优先搜索枚举“n 选 k”的所有情况

一题回忆 https://www.luogu.com.cn/problem/P1036

这种算法的典型情况：你要在 n 个数里面选 k 个进行组合:

void dfs(int p, int num, int sum) {
    // p 表示枚举到了第几个数
    // num 表示已经选中了几个数
    // sum 存储已选的数的和
    if (num == k) {
        // 刚好选了 k 个，此时针对题目进行操作
        // do something
        return;
    }
    if (p == n + 1) {
        // 这说明 n 个数都枚举完了
        // 没进入上一个 if 就说明还没选 k 个数
        // 选法错误，所以直接抛弃
        return;
    }
    // 选中第 p 个数，并且继续往下搜索
    dfs(p + 1, num + 1, sum + a[p]);
    // 不选第 p 个数，往下搜索
    dfs(p + 1, num, sum);
}

int main() {
    ...
    dfs(1, 0, 0);
}