搜索专题

必备技能

• STL

• 队列
• 优先队列

那就可以了

---

fc(DFS&BFS)

相信大家都对搜索(深搜/款搜)有了一定程度上自己的理解了

然后据我所了解，可能大家对这两个东西的区分度可能不是特别高，然后请允许我来口胡(对比、分析？)一下这两个东西

先来一个小练习：

用搜索求斐波那契数列的第\(n\)项

可能在座的各位已经会了递推求解、矩阵快速幂求解、通项公式求解

但还是希望大家能拿起自己的草稿纸，画一画这个运行的大概的过

斐波那契数列

深度优先搜索(Depth First Search)

优势：

• 适合状态不易储存的情况
• 有时候对子问题的依赖很强
• 符合人类的思考习惯

劣势：

• 很容易超时
• 很容易爆栈

宽度优先搜索(Breadth First Search （Baidu First Search）)

优势：

• 适合状态容易储存的问题
• 不容易爆栈（搜索深度远大于\(\text{DFS}\)）
• 能够将父状态继承给子状态
• 可以跑最短路啊，各种最优化问题

劣势：

• 可能产生大量的无用状态导致\(MLE\)
• 对某些数据结构的要求有点高

接下来干嘛，练题？

太没意思了吧。。。

来点有意思的？

---

奇技淫巧一：记忆化搜索(伪dp)

先让大家用搜索求一求

斐波那契数列

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll maxn = 1e5 + 10;
const ll mod = 1e9 + 7;

ll n, Feb[105] = {0, 1, 1};

ll feb(ll x)
{
    if (x == 1 || x == 2) return 1;
    return (feb(x - 1) + feb(x -  2)) % mod;
}

int main()
{
    scanf ("%lld", &n);
    for (ll i = 3; i <= n; ++i) 
        Feb[i] = (Feb[i - 1] + Feb[i - 2]) % mod;
    printf ("%lld\n", Feb[n]);
    system("pause");
    printf ("%lld\n", feb(n));
    system("pause");
}

好像\(n\)从\(40\)开始，这两个方式跑出来的时间差距就越来越大了

咋搞？

嗯，如题：记忆化

code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll maxn = 1e5 + 10;
const ll mod = 1e9 + 7;

ll n, Feb[105] = {0, 1, 1};
ll ans[105];

ll feb(ll x)
{
    if (x == 1 || x == 2) return 1;
    if (ans[x]) return ans[x];
    return ans[x] = (feb(x - 1) + feb(x -  2)) % mod;
}

int main()
{
    scanf ("%lld", &n);
    for (ll i = 3; i <= n; ++i) 
        Feb[i] = (Feb[i - 1] + Feb[i - 2]) % mod;
    printf ("%lld\n", Feb[n]);
    system("pause");
    printf ("%lld\n", feb(n));
    system("pause");
}

其实这个没有什么不一样的

就是记忆化，请大家\(YY\)一下就好

来点例题？

SHOI2012滑雪

solution

那么就是用一个\(f[i][j]\)来记录在\((i,j)\)能往下滑的最大距离

那么转移的话就是 \[ f[i][j]=max(f[i-1][j], f[i+1][j],f[i][j-1],f[i][j+1])+1 \] 当然，这个方程并不完全正确，大家还需要判断一下边界条件和这个高度的大小

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;

int n, m, ans;
int f[105][105], h[105][105];
int mx[] = {1, -1, 0, 0};
int my[] = {0, 0, 1, -1};

int dfs(int x, int y)
{
    if (f[x][y]) return f[x][y];
    f[x][y] = 1;
    for (int i(0); i < 4; ++i) {
        int nx = x + mx[i];
        int ny = y + my[i];
        if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
        if (h[nx][ny] >= h[x][y]) continue;
        f[x][y] = max(f[x][y], dfs(nx, ny) + 1);
    }
    return f[x][y];
}

int main()
{
    cin >> n >> m;
    for (int i(1); i <= n; ++i)
        for (int j(1); j <= m; ++j)
            cin >> h[i][j];
    
    for (int i(1); i <= n; ++i)
        for (int j(1); j <= m; ++j)
            ans = max(ans, dfs(i, j));
    
    cout << ans << endl;
    system("pause");
}

​

Achen

solution

手动模拟一下

会发现，其实\(A/B\)左右是否是空的，对于这道题没有本质的影响

因为要走遍所有的点的话，这只有一种方案

然后\(A/B\)的顺序对于本题也没有本质影响

来两张图？

好像就是如果\(A\)不是最靠左的点，那么\(A\)的实际位置应该是再往右走一格的位置，\(B\)也同理

那么所有的问题都可以转化为\(A,B\)分别为端点的问题了

再想，这个又能怎么考虑呢？

这啥意思？

就是到最右端点的两种方案

如果我们用一个数组\(f[i]\)来表示经过了\(i\)点左边的所有点后，最后到达\(i\)这样的情况的方案数

那么它可以写成这样\(f[i] = f[i - 1] + f[i - 3]\)

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
inline ll Read()
{
	ll X(0);
	char O(getchar());
	while (O < '0' || O > '9') O = getchar();
	for (; O >= '0' && O <= '9'; O = getchar()) X = (X << 1) + (X << 3) + (O ^ 48);
	return X;
}

const ll Maxn = 1e6 + 10, Mod = 998244353;
ll Feb[Maxn] = {1};
ll T, N, A, B;

int dfs(int x)
{
	if (x < 3) return 1;
	if (Feb[x]) return Feb[x];
	return Feb[x] = (dfs(x - 1) + dfs(x - 3)) % Mod;
}

int main()
{
	T = Read();
	while (T--)
	{
		N = Read(), A = Read(), B = Read();
		if (A > B) swap(A, B);
		if (A > 1) A += 1;
		if (B < N) B -= 1;
		if (B < A) puts("0");
		else printf ("%lld\n", dfs(B - A));
	}
	return 0;
}

就可以了

其实递推更简单，但是没有这个记搜快

过河卒

solution

个人觉得这是一个板子题水题

极其无脑的模拟就可以了

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 50 + 10;
const int mod = 1e9 + 7;

inline int __read()
{
    int x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) x = (x << 1) + (x << 3) + (o ^ 48);
    return x * t;
}

int n, m, x, y;
ll f[maxn][maxn];
int mx[] = {1, 1, -1, -1, 2, 2, -2, -2, 0};
int my[] = {2, -2, 2, -2, 1, -1, 1, -1, 0};

ll dfs(int x, int y)
{
    if (x > n || y > m) return 0;
    if (f[x][y] == -1) return 0;
    if (f[x][y]) return f[x][y];
    return f[x][y] = dfs(x + 1, y) + dfs(x, y + 1);
}

int main()
{
    n = __read(), m = __read();
    x = __read(), y = __read();
    f[n][m] = 1;
    for (int i(0); i < 9; ++i) {
        int nx = x + mx[i];
        int ny = y + my[i];
        if (nx < 0 || nx > n || ny < 0 || ny > m) continue;
        f[nx][ny] = -1;
    }
    cout << dfs(0, 0) << endl;
    system("pause");
}

嗯，记得开\(long\;long\)我失算了，因为没开，交了三次。。。

难受。。。

奇技淫巧二：疯狂剪枝

那就是遇见不可能有贡献的答案可以直接返回

来点例题？

数的划分(加强版)

solution

我们可以先写一个暴力，康康它可以怎么记忆化

\(DFS\)的时候，我们就记录三个参数

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;

inline int __read()
{
    int x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) x = (x << 1) + (x << 3) + (o ^ 48);
    return x * t;
}

int n, k;
int f[205][10][205];

int dfs(int rest, int num, int last)//rest -> 还剩多少， 还应该分几次， last -> 保证枚举出来时单调的
{
    if (!num) {
        if (rest) return 0;
        return 1;
    }
    int ans(0);
    for (int i = last; i <= rest; ++i)
        ans += dfs(rest - i, num - 1, i);
    return ans;
}

int main()
{
    memset (f, -1, sizeof f);
    cin >> n >> k;
    cout << dfs(n, k, 1) << endl;
    system("pause");
}

记忆化一下，代码没怎么变

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;

inline int __read()
{
    int x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) x = (x << 1) + (x << 3) + (o ^ 48);
    return x * t;
}

int n, k;
int f[205][10][205];

int dfs(int rest, int num, int last)
{
    if (~f[rest][num][last]) return f[rest][num][last];
    if (!num) {
        if (rest) return f[rest][num][last] = 0;
        return f[rest][num][last] = 1;
    }
    if (rest < num * last) return f[rest][num][last] = 0;
    f[rest][num][last] = 0;
    for (int i = last; i <= rest; ++i)
        f[rest][num][last] += dfs(rest - i, num - 1, i);
    return f[rest][num][last];
}

int main()
{
    memset (f, -1, sizeof f);
    cin >> n >> k;
    cout << dfs(n, k, 1) << endl;
    system("pause");
}

看看题解，惊艳了，这种吊打我代码神仙写法都有

当然，我将这种写法呢，只是为了让大家深刻理解一下这的记忆化搜索还有剪枝优化

奇技淫巧三：双向BFS、折半搜索

怎么说？如题！

八数码难题

solution

双向\(BFS\)嘛，对吧？

那就从首尾两端分别搜一次呗

这有什么好处呢？

简单的说，这个东西它及大幅度的剪掉了无用的状态

上图？

如果要把这个搜索树给遍历完，那么这个的时间复杂度就是\(O(2^{n+1})\)

那么如果\(n\)的数量级在\(30、40\)左右，那么恭喜你，完了！绝对\(TLE\)！

但是\(CJ\)我表示不服，我就只会搜索。。。

那么我们稍微修改一下这棵树

怎么讲？

有很多叶子节点时没有用的！！！

那么我们让这棵树有两个根，看看那些叶子结点的信息重合了

重合了就可以更新答案

那么时间复杂度？\(O(\sqrt{2^{n+1}})\)，很可以！

如果原来是\(1e12\)的复杂度

根号一下就是\(1e6\)，随便跑啊！！！

#include <bits/stdc++.h>

using namespace std;

int mx[4] = {1, -1, 0, 0};
int my[4] = {0, 0, 1, -1};
int Now, Next, Ans = 123804765;

map <int, int> en[2];
queue <int> q[2];

void mswap(char &a, char &b){a ^= b ^= a ^= b;}

int Get(int state,int k,int w){
	char a[3][3];
	short x, y, l = en[w][state];

	for(int i = 2; i >= 0; --i)
		for(int j = 2; j >= 0; --j){
			if(state % 10 == 0) x = i,y = j;
			a[i][j] = char((state % 10 - 0) + '0'), state /= 10;
		}

	short nx = x + mx[k];
	short ny = y + my[k];
	if(nx < 0 || ny < 0 || nx > 2 || ny > 2) return 0;
	mswap(a[x][y], a[nx][ny]);
	for(int i = 0; i < 3; ++i){
		for(int j = 0; j < 3; ++j){
			state = state * 10 + int(a[i][j] - '0');
		}
	}
    
	if(en[w].count(state)) return 0;
	en[w][state] = l + 1;
	return state;
}

void work(int x){
	Now = q[x].front();
		q[x].pop();
		for(int i = 0; i < 4; ++i){
			Next = Get(Now, i, x);
			if(!Next)continue;
			if(en[!x].count(Next)){
				printf("%d\n", en[0][Next] + en[1][Next]);
				exit(0); 
			}
			q[x].push(Next);
		}
}

void bfs(){
	q[0].push(Now);
	q[1].push(Ans);
	while(q[0].size() || q[1].size()){
		if(q[0].size())work(0);
		if(q[1].size())work(1);
	}
}

int main(){
	scanf("%d", &Now);
	if(Now == Ans)puts("0");
	else bfs();
	return 0;
}

是吧，挺简单的

奇技淫巧四：IDA*

来到例题？

铁盘整理

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;

inline int __read()
{
    int x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) x = (x << 1) + (x << 3) + (o ^ 48);
    return x * t;
}

int n, a[maxn], f[maxn], limit;

inline int _abs(int x)
{
    if (x < 0) return -x;
    return x;
} 

inline int Check() 
{
    int res(0);
    for (int i(1); i <= n; ++i)
        res += (_abs(a[i] - a[i + 1]) != 1);
    return res;
}

void bdfs(int dep, int pre)
{
    int g = Check();
    if (dep + g > limit) return ;
    if (dep > limit) return ;
    if (g == 0) {
        printf ("%d\n", dep);
        system("pause");
        exit(0);
    }
    for (int i = 2; i <= n; ++i)
        if (i != pre) {
            reverse (a + 1, a + i + 1);
            bdfs(dep + 1, i);
            reverse (a + 1, a + i + 1);
        }
}

int main()
{
    n = __read();
    for (int i = 1; i <= n; ++i) a[i] = __read(), f[i] = a[i];
    sort (f + 1, f + n + 1);
    for (int i = 1; i <= n; ++i) a[i] = lower_bound(f + 1, f + n + 1, a[i]) - f;
    a[n + 1] = n + 1;
    for (; limit <= (n << 1) - 2; ++limit) bdfs(0, 0);
    system("pause");
}

骑士精神

Code

#include <cstdio>

int T, X, Y, Get;
const int mx[] = {1, 1, -2, -2, 2, 2, -1, -1};
const int my[] = {2, -2, 1, -1, 1, -1, 2, -2};
char Now[10][10];
char Goal[10][10] = {
    {'1','1','1','1','1'},
    {'0','1','1','1','1'},
    {'0','0','*','1','1'},
    {'0','0','0','0','1'},
    {'0','0','0','0','0'},
};

inline void Swap(char &x,char &y){x ^= y ^= x ^= y;}

int G()
{
    int Cnt = 0;
    for (int i = 0; i < 5; ++i)
        for(int j = 0; j < 5;++j)if (Now[i][j] != Goal[i][j])++Cnt;
    return Cnt;
}

void IDA_STAR(int x, int y, int Dep, int Limit, int Dir)
{
    if (Get)return;
    if (Dep > Limit)return;
    if (!G())
    {
        printf("%d\n", Dep);
        Get = 1;
        return;
    }
    for (int i = 0; i < 8; ++i)
    {
        int nx = x + mx[i];
        int ny = y + my[i];
        if(nx < 0 || nx >= 5 || nx <0 || ny >= 5)continue;
        if(i + Dir == 7)continue;
        Swap(Now[x][y], Now[nx][ny]);
        if (G() + Dep <= Limit)IDA_STAR(nx, ny, Dep + 1, Limit, i);
        Swap(Now[x][y], Now[nx][ny]);
    }
}

int main()
{
    scanf("%d",&T);
    while(T--)
    {
        Get = 0;
        for (int i = 0; i < 5; ++i)
        {
            char Ch = getchar();
            while((Ch != '0') && (Ch != '1') && (Ch != '*'))Ch = getchar();
            Now[i][0] = Ch;
            for(int j = 1; j < 5; ++j)Now[i][j] = getchar();
            for(int j = 0; j < 5; ++j)
                if(Now[i][j] == '*') X = i, Y = j;
        }
        for (int i = 0; i <= 15; ++i)IDA_STAR(X, Y, 0, i, 8);
        if (!Get)puts("-1");
    }
    return 0;
}

我可能没时间写了，好网站