头像

Aigrl

欢迎您的到来




离线:8小时前


最近来访(405)
用户头像
我行其野
用户头像
1000减7是
用户头像
海星派大双
用户头像
有恒
用户头像
俗世奇人
用户头像
赣一中的曾宇浩
用户头像
迟少柯
用户头像
朵橙阿丶
用户头像
chaser.
用户头像
亚斯特拉格雷
用户头像
lchlchlch123
用户头像
lyktes
用户头像
shaoxuan
用户头像
大鼻孔
用户头像
cdm
用户头像
一天不A浑身难受
用户头像
余火
用户头像
妮可_4
用户头像
acwing_9052
用户头像
彬腾


Aigrl
8天前

最好是有很多语法高亮的



新鲜事 原文

Aigrl
9天前
祝大家 Rp ++


新鲜事 原文

Aigrl
15天前
怎么才能进 清华姚班 = OI 国家队 = OI 国集 + 天赋/运气 = OI 省队高分 + 一年时间 + 天赋/运气 怎么才能进省队= NOIP 高分 + 春令营 高分 + (地方OI 高分) + WC 中等分 NOIP 高分 = CSP 一等 + 3个月集训 春令营高分 = NOIP 高分 + 稳定考试状态 地方OI 高分 = NOIP 高分 + 省队知识积累 CSP 一等 = 1年时间 + 合格教练 + 努力 1年时间 = 是个人都有 合格教练 = 一个好的中学 = 不错的文化课 由于 y总 > 合格教练 所以 CSP 一等 < 1年时间 + y 总 所以 省队 < 进阶课精刷 + y 总 + ... 所以 是个人 + ... = 清华姚班



Aigrl
15天前

正文篇



第二章 DFS 题目的状态空间与转换


$2.1$ DFS 在地图类问题的转换

* DFS 维护连通块

在一个平面的地图上,仅用 $x、y$ 这两个坐标就可以描述地图上任意一个点。

起点 看作 起点可走到的格子 看作往外延伸的 子节点,在搜索过程中维护当前答案。

通常在每次递归时,我们会 新建一个变量(或在全局开一个数组)来累计答案。

但经过仔细分析之后,可以得出,这类问题的 搜索答案往往与路径相关,所以,可以用记忆化搜索解决。

下一步,就是如何处理状态。

下面这个程序所解决的题目,只需要知道 第$x, y$个格子是否被遍历过,由于此题的数据是一张图,所以不需要回溯。

只需要用一个数组的值就可以精准记录了。

int dfs(int x, int y)
{
    int cnt = 1;

    st[x][y] = true;
    for (int i = 0; i < 4; i ++ )
    {
        int a = x + dx[i], b = y + dy[i];

        if (a < 0 || a >= h || b < 0 || b >= w) continue;

        if (g[a][b] != '.') continue;
        if (st[a][b]) continue;

        cnt +=  dfs(a, b);  // 相加
    }

    return cnt;
}

* DFS 有约束的跑图问题

往往一道 $DFS$ 的题目会给你加上各式各样的约束,如何将这些约束合适的表达出来。

就是一门值得深究的学问了。

【例题 1】 滑雪

这是一道非常经典的题目,也是作者在 3个月前,初学 $DFS$ 的时候印象极为深刻的题目之一。

面对一道陌生的问题,我们需要对它进行合理的转化(至少在联赛难度的时候这个方法是适用的

很明显,我们可以从图上任意一点出发,搜索可以滑的最大距离,维护最大值即可。

但这样的复杂度是 $O((nm)^2)$, 显然超时。

结合 池塘计数 一题, 我们知道,并不是每一次搜索的时候都要将所有点都搜一遍。

回到此题,由于每一个点的 最大滑行距离固定,而对任意一个点而言,其最大滑行距离等价于

他能滑到的点中滑行距离最大的点 加 $1$。

所以,我们可以用 $f$ 数组记忆化维护每个点的最大滑行距离,在搜到这个点时,直接返回 $f$ 中储存的数即可。

【例题 2】 方格取数

无疑,这是一道经典模型的加强,让我们先为它划定状态空间。

即对于此图上的任意一点都有 三个变量,它的 $x, y$ 坐标和它上一步的方向 $k$。

这三类变量都可以用一个 $f$ 的三维数组来储存,设 $a, b, p$ 意义分别对应上面的 $x, y, k$。

若 $f[a][b][p]$ 被更新过,有知,$f[a][b][p]$ 储存的是 $a, b$ 坐标,上一步为 $p$ 的最大值,所以不用继续搜。

同时,我们还不能 重复经过一个格子,所以,需要用 $st$ 来判断格子是否已经经过,

需要注意的是,$st$ 并不是记忆化搜索,因为 到达一个格子的状态可能有很多个,不能以一概全。

所以我们还要在 延伸后回溯

值得注意的是,以上操作都是在默认从终点出发为前提的,那么,其递归边界就是 起点

状态转移,由于数据的特殊,我们将数据 逆时针转 90度 来看,那么三个转移过程是:

0. 向左转移

LL Left(int x, int y)
{
    int a, b;
    LL ans = -INF;
    a = x - 1;
    b = y;
    if (check(a, b) && !st[a][b]) 
    {
        LL res = max(dfs(a, b, 1) + g[x][y], dfs(a, b, 2) + g[x][y]);
        ans = max(ans, res);
    }
    return ans;
}

1. 向上转移

LL Up(int x, int y)
{
    int a, b;
    LL ans = -INF;
    a = x;
    b = y - 1;
    if (check(a, b) && !st[a][b]) 
    {
        LL res = max(max(dfs(a, b, 0) + g[x][y], dfs(a, b, 2) + g[x][y]), dfs(a, b, 1) + g[x][y]);
        ans = max(ans, res);
    }
    return ans;
}

2. 向右转移

LL Right(int x, int y)
{
    int a, b;
    LL ans = -INF;
    a = x + 1;
    b = y;
    if (check(a, b) && !st[a][b]) 
    {
        LL res = max(dfs(a, b, 1) + g[x][y], dfs(a, b, 0) + g[x][y]);
        ans = max(ans, res);
    }
    return ans;
}

递归代码:

inline bool check(int x, int y)
{
    return x >= 1 && x <= n && y >= 1 && y <= m;
}
inline LL dfs(int x, int y, int k)
{
    LL &ans = f[x][y][k];
    if (ans != -INF)
    {
        return ans;
    }

    st[x][y] = true;

    if (k == 0) ans = max(ans, Right(x, y));
    if (k == 1) ans = max(ans, Up(x, y));
    if (k == 2) ans = max(ans, Left(x, y));

    st[x][y] = false;
    return ans;
}

* DFS 解决棋盘类问题

我们在研究深搜算法时经常能碰到这一类问题:

在某个棋盘上有一种棋子,问最多放下几个棋子,使得剩下来的棋子两两不攻击。

这就是 棋盘类问题

或者,也可以广义的理解为,在一张图上放上一些满足一定规律的点,让你输出其中的 放点方案 或者是 方案数

常考题型有 八皇后问题、数独问题、多米诺骨牌(块状覆盖问题)。

下面我会教大家解决这些问题的变种,难度按递增顺序排列

【例题 1】 棋盘问题

这是一道经典问题的变形,同样也是方案数类问题的基础题,看似简单,却往往能将你折磨得怀疑人生。

让我们从头分析吧!

首先,确定搜索方式,显然是一个排列型枚举。

但如果这样,它的时间复杂度会飙升到 $64!$, 不能接受,所以,我们需要根据题意进行简化。

通常,可以用两个数组来记录 这一行或者这一列 是否有了棋子。

或者,也可以直接 按行枚举,提升效率。

然后,就要确定搜索边界,通常有两个:越出边界枚举完所有数字

其实,还是挺简单的,那就稍微加深点难度吧!

【例题 2】 数独

非常经典的问题,也是一道用来练习码力的入门题,在做完猪国杀之前,一度是我调试代码的噩梦。

这道问题涉及的内容很多,如果你不知道怎么剪枝来提升效率,可以先学习一下我之后分享的内容。

话不多说,让我们先来看一下搜索方式,显然,每个位置都有很多种填数的方案,是 排列型枚举

在想一下有哪些需维护的信息,首先,枚举的空格数空肯定是其中之一而且只有没有数字的格子才能去填。

数独问题是一道典型的 $NPC$ 问题,所以还需要我们进行回溯,通常使用二进制 $hash$表的方式来储存数独问题的状态。

边界就很显然了,在它的所有空格都正确填完之后,返回输出即可,一般是保证了唯一解的。

如果你觉得简单的话,也可以试一下这道题,无疑是对自己程序设计的一个挑战。

【习题 1】 数独2

让我们来看一道算法竞赛题真正的难度吧!

即使是身经百战的老手也很难快速解决这种问题,但也是你迈向更高道路上必经之路。

【例题 3】 多米诺骨牌

好吧,



活动打卡代码 AcWing 178. 第K短路

Aigrl
15天前
#include <bits/stdc++.h>
using namespace std;

const int N = 1010, M = 100010;

int n, m;
int S, T, K;
int f[N], h[N], e[M], ne[M], w[M], idx;

int dist[N], cnt[N];
bool st[N];

struct Ver
{
    int x, dist;
    bool operator < (const Ver &t) const
    {
        return dist > t.dist;
    }
};

struct Aver
{
    int x, dist, Af;
    bool operator < (const Aver &t) const
    {
        return Af > t.Af;
    }
};

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

void fadd(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = f[a], f[a] = idx ++;
}

void init(int Start)    // 反向边预处理
{
    memset(dist, 0x3f, sizeof dist);
    priority_queue<Ver> heap;
    heap.push({Start, dist[Start]});
    dist[Start] = 0;    

    while (heap.size())
    {
        Ver t = heap.top();
        heap.pop();

        int ver = t.x;

        if (st[ver]) continue;
        st[ver] = true;

        for (int i = f[ver]; i != -1; i = ne[i])    
        {
            int j = e[i];

            if (dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                heap.push({j, dist[j]});    
            }
        }
    }
}

int Astar(int start)    // A*版 Dijkstra
{
    priority_queue<Aver> heap;  
    heap.push({start, 0, dist[start]}); // 点的编号, 到源点的距离, 全程估计距离 = 实际距离 + 估价距离

    while (heap.size())
    {
        Aver t = heap.top();
        heap.pop();

        int ver = t.x;
        cnt[ver] ++;    // 经过次数 ++
        if (cnt[T] == K) return t.dist; // 此时经过 K 次终点, 直接返回到源点的距离

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            /* 
            如果走到一个中间点都cnt[j]>=K,则说明j已经出队k次了,且astar()并没有return distance,
            说明从j出发找不到第k短路(让终点出队k次),
            即继续让j入队的话依然无解,
            那么就没必要让j继续入队了
            */
            if (cnt[j] < K) // 出队次数小于 K
            {
                heap.push({j, t.dist + w[i], t.dist + w[i] + dist[j]});
            }
        }
    }
    return -1;
}

int main()
{
    memset(h, -1, sizeof h);
    memset(f, -1, sizeof f);

    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i ++ )
    {
        int a, b, L;
        scanf("%d %d %d", &a, &b, &L);
        add(a, b, L), fadd(b, a, L); // 建反向边
    }

    scanf("%d %d %d", &S, &T, &K);
    if (S == T) K ++;   // 源点等于汇点

    init(T);
    int ans = Astar(S);
    printf("%d", ans);

    return 0;
}



Aigrl
21天前

题目描述

阿福是一名经验丰富的大盗。趁着月黑风高,阿福打算今晚洗劫一条街上的店铺。

这条街上一共有 $N$ 家店铺,每家店中都有一些现金。

阿福事先调查得知,只有当他同时洗劫了两家相邻的店铺时,街上的报警系统才会启动,然后警察就会蜂拥而至。

作为一向谨慎作案的大盗,阿福不愿意冒着被警察追捕的风险行窃。

他想知道,在不惊动警察的情况下,他今晚最多可以得到多少现金?

输入格式

输入的第一行是一个整数 $T$,表示一共有 $T$ 组数据。

接下来的每组数据,第一行是一个整数 $N$ ,表示一共有 $N$ 家店铺。

第二行是 $N$ 个被空格分开的正整数,表示每一家店铺中的现金数量。

每家店铺中的现金数量均不超过 $1000$。

输出格式

对于每组数据,输出一行。

该行包含一个整数,表示阿福在不惊动警察的情况下可以得到的现金数量。

数据范围

$1≤T≤50$,
$1≤N≤10^5$

输入样例:

2
3
1 8 2
4
10 7 6 14

输出样例:

8
24

算法1

(记忆化搜索) $O(n)$

状态转移方程是 前 i 个数 = max(前 i - 1 个数, 前 i - 2 个数 + 第 i 个数)

平时写一下搜索还是挺好的。 (比Dp还快 2ms)

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int T, n;

int a[N];
int f[N];
int ans;

int dfs(int u)
{
    if (u <= 0) return 0;
    if (f[u] != 0) return f[u]; // 计搜灵魂

    return f[u] = max(dfs(u - 1), dfs(u - 2) + a[u]);
}

int main()
{
    scanf("%d", &T);
    while (T -- )
    {
        scanf("%d", &n);
        memset(f, 0, sizeof f);
        for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

        printf("%d\n",dfs(n));
    }
    return 0;
}

算法2

(状态机) $O(n)$

把一个过程用一种确定的状态描述了出来

如 f[i][0] 表示没有偷第 i 个商店, f[i][1] 表示偷了第 i 个商店

则 f[i][0] 的入边(即过程)有两条 1. 偷了第 i - 1 个商店, 2. 没偷第 i - 1 个商店
而 f[i][1] 的入边仅有一条,即 没偷第 i - 1 个商店。

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int T, n;

int a[N];
int f[N][2];

int main()
{
    scanf("%d", &T);
    while (T -- )
    {
        scanf("%d", &n);
        memset(f, 0, sizeof f);
        for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

        for (int i = 1; i <= n; i ++ )
        {
            f[i][0] = max(f[i - 1][0], f[i - 1][1]);
            f[i][1] = f[i - 1][0] + a[i];
        }
        printf("%d\n", max(f[n][0], f[n][1]));
    }
    return 0;
}

算法3

(DP) $O(n)$

参照算法 1

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int T, n;

int a[N];
int f[N];

int main()
{
    scanf("%d", &T);
    while (T -- )
    {
        scanf("%d", &n);
        memset(f, 0, sizeof f);
        for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

        f[1] = a[1];
        for (int i = 2; i <= n; i ++ )
        {
            f[i] = max(f[i - 1], f[i - 2] + a[i]);
        }
        printf("%d\n",f[n]);
    }
    return 0;
}

算法4

(状态机的记忆化搜索) $O(n)$

参照算法 2

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int T, n;

int a[N];
int f[N][2];

int dfs(int u, int state)
{
    if (u <= 0) return 0;
    if (f[u][state]) return f[u][state];

    if (!state) return f[u][0] = max(dfs(u - 1, 0), dfs(u - 1, 1));
    else return f[u][1] = dfs(u - 1, 0) + a[u];
}

int main()
{
    scanf("%d", &T);
    while (T -- )
    {
        scanf("%d", &n);
        for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

        memset(f, 0, sizeof f);
        int x = dfs(n, 0);
        memset(f, 0, sizeof f);
        int y = dfs(n, 1);

        printf("%d\n", max(x, y));
    }
    return 0;
}

效率排名(由快到慢)

算法 1(517 ms) > 算法 3(519 ms) > 算法 2(523 ms)> 算法 4 (804 ms)

还有一个来自彩铅大佬的滚动数组优化

时间(1460ms) (应该是 cin 拖累的

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;

int n;
int w[N];
int f[2][2];

void solve()
{
    memset(f, -0x3f, sizeof f);
    f[0][0] = 0;

    cin >> n;
    for (int i = 1; i <= n; ++ i) cin >> w[i];
    for (int i = 1; i <= n; ++ i)
    {
        f[i & 1][0] = max(f[(i - 1) & 1][1], f[(i - 1) & 1][0]);
        f[i & 1][1] = f[(i - 1) & 1][0] + w[i];
    }
    cout << max(f[n & 1][0], f[n & 1][1]) << endl;
}
int main()
{
    int T = 1;
    cin >> T;
    while (T -- ) solve();
    return 0;
}


空间仅有其它算法的 20/1




Aigrl
22天前

算法1

(模拟) $O(nlogn)$

主要是排序的时间较大。

将数据读入并排序,再用 hash表判重就可以过掉了。

不幸的是,我中途有事离开了一会,提交时,比赛已经结束了emm

C++ 代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 200010;


int n, m;

int p[N];
int a, b;
int c;

vector<int> mp[4];
unordered_map<int, bool> pth;

signed main()
{
    cin >> n;

    for (int i = 0; i < n; i ++ ) 
    {
        cin >>p[i];
        pth[p[i]] = true;
    }

    for (int i = 0; i < n; i ++ ) 
    {
        cin >> a;
        mp[a].push_back(p[i]);
    }
    for (int i = 0; i < n; i ++ ) 
    {
        cin >> b;
        mp[b].push_back(p[i]);
    }

    for (int i = 1; i <= 3; i ++ ) 
    {
        sort(mp[i].begin(), mp[i].end());
        reverse(mp[i].begin(), mp[i].end());
    }

    cin >> m;
    for (int i = 0; i < m; i ++ ) 
    {
        cin >> c;
        while (mp[c].size() && pth[mp[c].back()] == false) mp[c].pop_back();
        if (mp[c].size()) 
        {
            printf("%lld ", mp[c].back());
            pth[mp[c].back()] = false;
            mp[c].pop_back();
        }
        else printf("-1 ");
    }

}



Aigrl
22天前

时隔至今,发现时间流逝的速度愈加凶猛,距上一次 CSP 已过十余天,更别提期中考将至。

可是,堆积如山的任务却不见减少。

一来,记录生活, 二来,勉励自己(不要咕咕咕),下定决心开始坚持写日记周记,以此勉励自己。

那么,开始吧!

【第一周】

最近一篇周记:

买了一本 《离散数学》,打算带到学校去啃。

咕了四天,到星期五才想起来(bushi

听老师评讲“过程性评价” 卷子,对了一下答案,发现英语还是那么砸(主要是听力,表格阅读,作文 扣的较多),其它还好

电脑课决定开始码天天爱跑步,卡在 70分之后就一直调不过去。

周末疫情严重差点回不去了qwq

周六早上,写了会博客,将作业补了一点,然后就中午了(起的太晚..

中午,写了一道模拟 P1686 ,感觉还是挺简单的。

1个多小时就调完了qwq

代码在这里

发了会呆,一看时间 ? 这么晚了!

晚上的时候应该会去打一下周赛,顺带将之前提高组的题补了(本来是上周就打算做的

然后,明天就认真卷文化课吧(毕竟每次期中我都要考砸

记录时间: 2021/11/6

【第二周】

期中考延迟到下周二了。

写了一份地理思维导图,感觉这学期跟没上过地理课一样。

卷了会文化课,然后写了道 A* ,似乎就没什么别的了。



活动打卡代码 AcWing 16. 替换空格

Aigrl
22天前
#include <bits/stdc++.h>
using namespace std;

const int N = 260000, INF = 1e9;

typedef pair<int, int> PII;

int n;
char str[N];
map<char, PII> mp;

struct Edge
{
    int x, y;
    int num;
}R[N];

int S, E, ans = INF;
char st;

bool C1(Edge a, Edge b) {return a.x < b.x || (a.x == b.x && a.y < b.y);}
bool C2(Edge a, Edge b) {return a.y < b.y || (a.y == b.y && a.x < b.x);}

bool check(int d, int l, int r)
{
    if (d == ans && S == l) return E < r;
    return d == ans ? S > l : d < ans;
}

void work1()
{
    int f, l;
    for (int i = 1; i < n; i ++ )
    {
        if (R[i].x == R[i + 1].x)
        {
            int dist = R[i + 1].y - R[i].y;
            int a = R[i].num, b = R[i + 1].num;
            char std = a > b ? 'S' : 'N';
            if (a > b) swap(a, b);
            f = a, l = b;

            if (f + 1 == l) continue;
            if (check(dist, f, l)) {ans = dist, S = f, E = l; st = std;}
        }
    }
}

void work2()
{
    int f, l;
    for (int i = 1; i < n; i ++ )
    {
        if (R[i].y == R[i + 1].y)
        {
            int dist = R[i + 1].x - R[i].x;
            int a = R[i].num, b = R[i + 1].num;
            char std = a > b ? 'W' : 'E';
            if (a > b) swap(a, b);

            f = a, l = b;

            if (f + 1 == l) continue;
            if (check(dist, f, l)) {ans = dist, S = f, E = l; st = std;}
        }
    }
}

int main()
{
    scanf("%d\n%s", &n, str + 1);

    mp['N'] = {0, 1}, mp['S'] = {0, -1}, mp['W'] = {-1, 0}, mp['E'] = {1, 0};
    for (int i = 1; i <= n; i ++ )
    {
        R[i] = R[i - 1], R[i].num = i;
        R[i].x += mp[str[i]].first;
        R[i].y += mp[str[i]].second;
    }
    sort(R + 1, R + n + 1, C1); work1();
    sort(R + 1, R + n + 1, C2); work2();

    printf("%d %d %d %c", ans, S, E, st);
    return 0;
}



Aigrl
22天前

正文篇



第一章 引言


$1.1$ DFS 的定义

* DFS 的基层实现原理

$DFS$ 即 深度优先搜索,在程序中是以 栈的形式 实现,符合 的先进先出的原理,当栈不为空时,就会一直弹出栈顶元素

这也是 $DFS$ 在实现时,会一直往一条道上搜, 直到搜完才返回的原因。

但是,如果 $DFS$ 在第一次搜完之后就结束了, 那么作用不大,但是如果在 每一次递归 (即压栈) 的时候

同时递归其它值, 由于递归其它值的操作只有在 上一条道搜完之后 才会执行,所以会在一些深度上形成分叉。

只要能够 确认问题的搜索框架,就可以 穷举所有方案,也就是 一切皆可搜 的由来。

* DFS 的实现场景

$DFS$ 是一种用递归实现的算法,但本质上完全可以借助栈来解决。

常见的深度优先搜索的应用分别是 图的连通性模型、枚举方案数、枚举所有可能性、 树的自底向上维护信息 等等,

这些都会在后文作详细介绍。

* DFS 的实现方式

那 $DFS$ 又应该如何实现呢?

其中的难点在于对题目要求的转换和对无用的状态空间的排除,

在此,给出一些最基本的 $DFS$ 代码实现和最基本的思想讲解。

设计一个 $DFS$ 代码,你要确定在你的搜索树中你要 维护那些信息,以及你往下搜索的扩展方式。

一定要尽量吝啬于你 往外延伸的分支数量,不然时间复杂度会以一个极为恐怖的方式增长。

void dfs(变化的参数, 如深度、方案数、枚举到第几个方案、横纵坐标等等)
{
    if 问题边界                 // 必备的, 只有有限的空间才可以搜索
    {
        维护答案;
        return;
    }

    往不同方向搜索延伸          // 搜索分支
    {
        dfs(参数发生不同的变化);   // 往下搜索 
    }
}

这是一个最基本的框架,也是后文延伸的一个基础,抱着循序渐进的想法,更多内容就留给下文阐述。

* 回溯法的原理

回溯法 是系统地搜索问题状态的方法。

某个问题的 所有可能状态 称为问题的 状态空间,若 状态空间是有限的,便可将状态空间映射成 树结构

请记住,任何状态空间可以映射成树结构的问题,都可以使用回溯法。

也就是说,回溯法是能够在树结构里搜索到 通往特定终点 的一条或者多条特定路径。

回溯算法的基本思想是:

"从一条路往前走,能进则进,不能进则退回来,换一条路再试,从而搜索到抵达特定终点的一条或者多条特定路径。"

值得注意,回溯法以深度优先搜索的方式搜索 状态空间,并且在搜索过程中 用剪枝函数避免无效搜索

那么,它可以解决哪些题目呢?

  1. 【组合问题】:N个数里面按一定规则找出k个数的集合

  2. 【排列问题】:N个数按一定规则全排列,有几种排列方式

  3. 【切割问题】:一个字符串按一定规则有几种切割方式

  4. 【子集问题】:一个N个数的集合里有多少符合条件的子集

  5. 【棋盘问题】:N皇后,解数独等等

在回溯法的题目里,我们的模板也有了一些变化。

void dfs(变化的参数, 如深度、方案数、枚举到第几个方案、横纵坐标等等)
{
    if 问题边界                 // 必备的, 只有有限的空间才可以搜索
    {
        维护答案;
        return;
    }

    往不同方向搜索延伸          // 搜索分支
    {
        处理此节点信息
        dfs(参数发生不同的变化);    // 往下搜索
        复原此节点信息, 才可以进行对分支的正确搜索。    // 回溯
    }
}

为什么这样就可以遍历整个搜索树呢?

感性的理解是:for循环可以理解是横向遍历,dfs(递归)就是纵向遍历

同样,也可以画图体会。

多数问题都需要靠回溯法来求解,但必须要强调的是

深度优先搜索 不等于 回溯法

正如上文所述,回溯法解决的是 树形结构 问题,

而深度优先搜索同样也可以用于 图结构 问题

当问题不在只是一棵树的时候,可能会存在 例如 环、重边 等更复杂的结构。

更重要的是这类问题 一个节点需要且只需访问一次。

为了解决重复遍历的问题,我们往往会用一个 $st$ 数组来储存图的某个节点是否重复遍历的问题。

而不再继续使用回溯法了,毕竟你要走的路径已经给出了呀。


$1.2$ DFS 的可传递信息

*DFS 自底向上的信息维护

深搜作为一种实用的算法,可以维护几乎所有的信息,但笔者能力有限,故此,仅列举几种常用信息的维护方式。

$【sum$ 值的维护】 :

我们用一个 $sum$ 数组储存 以这个节点为根的子树之和,同时用一个 $st$ 数组储存 树的某个节点是否被重复遍历

然后,我们就可以遍历整棵树了。

可以看出,从一个节点出发往下的所有节点都是它的子树。

因此,我们仅需要在往下搜索时,储存一个变量 $sum$, 在返回的过程中维护以它为根的子树之和,往上传递时,其父节点仅需要加上它的值就可以了。

这也是一个名为 打包 的重要思想。

【树的最小字典序维护】 :

给定你一颗树,让你求出在可以重复经过同一个节点的情况下,遍历所有节点的字典序最小的方案是什么?

字典序仅会在第一次到达此节点时累计。

我们用一个 $path$ 数组储存方案,先将每一个点的出边排序,从字典序小的边开始搜,并维护第一次搜到的点的方案。

同样用 $st$ 数组判重,由于 DFS 一次搜到底的性质,在不存在环的情况下满足

运用贪心的思想,由字典序从小到大遍历整棵树,一点是最优的。

【树的重心】 :

重心是指树中的一个结点,如果将这个点删除后,剩余各个连通块中子节点数的最大值最小,那么这个节点被称为树的重心。

将一颗树的一个节点删掉后,树会被分成两个部分,可维护的值有两个。

一个是以它为根的下一层子树中最大的一颗的子节点数,一个是除去以它为根的子树后剩余节点数。

根据容斥原理,直接维护最大联通子图的节点数即可。


$1.3$ DFS 的铺垫知识

*前提条件

原问题问题边界 之间的 每个变换步骤具有相似性时 就可以考虑用 递归递推 来求解

*变换步骤(递归)

对于递归算法,可以通过以下三个操作来求解


1. 【自身调用自身】

缩小问题规模空间

这意味着程序尝试寻找在 原问题问题边界 之间的 变化路线,并向 正在探索 的路线上迈出一步

2. 【回溯时还原现场(搜索失败)】

尝试求解 规模缩小以后的问题

如果失败,程序需要 重新回到当前问题 去寻找 其它的变换路线

因此把 当前问题 缩小为 子问题 时所做的 对当前问题状态产生影响的事情全部失效

3. 【扩展(搜索成功)】

找到了 规模缩小以后的问题 的答案, 那么将答案 扩展到当前问题

如果失败,就 重新返回 当前问题,继续寻找 当前答案其它变换路线,直至 确定当前问题无法求解


总结

简洁的说,就是 缩小,求解,扩展


*DFS 的三种枚举方式

【指数型枚举】 :

对于序列中每个整数都有两种可能, 或者 不选

也就是说,这颗搜索树上的每一个节点都有两个分支

每次将尚未确定的整数减少 $1$,从而转换成一个更小的同类问题。

注意:指数型枚举不考虑顺序

时间复杂度 $O(k^n)$

注意:其中的 $k$ 为常数。

void dfs(int u){
    if (u == n + 1)
    {
        for (int i = 0; i < ch.size(); i ++ )
            printf("%d ", ch[i]);
        puts("");
        return;
    }

    dfs(u + 1);
    ch.push_back(u);

    dfs(u + 1);
    ch.pop_back();
}

【组合型枚举】 :

可以等价于上述枚举仅在 枚举数 $= m$ 的情况下有效。

注意:组合型枚举不考虑顺序

时间复杂度 $O(C_n^m)$

组合数的知识会在 数论 一章进行讲解

void dfs(int u){
    if (ch.size() > m || ch.size() + (n - u + 1) < m) return;
    if (u == n + 1)
    {
        for (int i = 0; i < ch.size(); i ++ )
            printf("%d ", ch[i]);
        puts("");
        return;
    }

    dfs(u + 1);
    ch.push_back(u);

    dfs(u + 1);
    ch.pop_back();
}

【排列型枚举】 :

它与组合型枚举的最大不同在于它考虑搜索顺序。

它的搜索树分支是这样的 :

可以看出,第一层每个数有三个分支,第二层每个数有两个分支,第三层每个数有一个分支。

也就是说,这个搜索树的分支具有收敛性。

这中枚举的功能是 其中的每个分支都是在当前未选择的数中挑选一个,具体可以看图。

时间复杂度 $O(P_n^m)$

int st[N];//存储方案
bool used[N];//标记数字是否被用过,true表示被用过,false表示没被用过
int n;

void dfs(int u) {   //当前枚举第u位
    if (u > n) {
        for (int i = 1; i <= n; i ++ ) 
            printf("%d ", st[i]);   //打印方案
        puts("");
        return ;
    }

    for (int i = 1; i <= n; i ++ ) {    //依次枚举每个数
        if (!used[i]) {                 //当前数可用
            st[u] = i;
            used[i] = true;
            dfs(u + 1);

                            //恢复现场
            st[u] = 0;      //可省略
            used[i] = false;//不可省
        }
    }
}

int main() {
    scanf("%d", &n);

    dfs(1);

    return 0;
}

$1.4$ 记忆化搜索初步

1.记忆化搜索的思想

在搜索过程中,会有很多重复计算,如果我们能记录一些状态的答案,就可以减少重复搜索量

2、记忆化搜索的适用范围

根据记忆化搜索的思想,它是 解决重复计算,而不是重复生成

也就是说,这些搜索必须是在 搜索 扩展路径的过程中分步计算的题目,也就是“搜索答案与路径相关”的题目,而不能是 搜索一个路径之后才能进行计算的题目

必须要分步计算,并且搜索过程中,一个搜索结果必须可以建立在 同类型问题 的结果上,也就是类似于动态规划解决的那种。

也就是说,他的问题表达,不是 单纯生成一个走步方案,而是生成一个走步方案的代价等,而且每走一步,在 搜索树/图 中生成一个新状态,都可以精确计算出到此为止的费用

也就是,可以分步计算,这样才可以 套用已经得到的答案

3、记忆化搜索的核心实现

$a.$ 首先,要通过一个表 记录已经存储下的搜索结果,一般用 哈希表 实现

$b.$ 状态表示,由于是要用 哈希表 实现,所以状态最好可以用数字表示,常用的方法是把一个状态连写成一个 $p$ 进制数字,然后把这个数字对应的十进制数字作为状态

$c.$ 在每一状态搜索的开始,高效的使用哈希表搜索这个状态是否出现过,如果已经做过,直接调用答案,回溯

$d.$ 如果没有,则按正常方法搜索

4、记忆化搜索是类似于动态规划的,不同的是,它是倒做的“递归式动态规划”。