YbtOJ「基础算法」第4章 深度搜索

YbtOJ 大全

【例题1】拔河比赛

我们在 $dfs$ 的过程中记录当前选了几个人，这些人的体重是多少，然后当遍历完所有人并且满足条件的时候，更新答案

#include 
#include 
#include 
#include 
#include 
#include 
#define re register
#define drep(a,b,c) for(re int a(b) ; a>=(c) ; --a)
#define rep(a,b,c) 	for(re int a(b) ; a<=(c) ; ++a)
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch == '-') f=-1 ; ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
const int M = 200;
int T,n,sum,ans = 1e9;
int a[M];
inline void dfs(int cur,int x,int tot){
	if(x == n/2){
		ans = min(ans,abs(tot*2-sum));
		return;
	}
	if(cur > n) return;
	dfs(cur+1,x+1,tot+a[cur]);
	dfs(cur+1,x,tot);
}
inline void work(){
	n = read();
	sum = 0,ans = 1e9;
	rep(i,1,n) a[i] = read(),sum += a[i];
	dfs(1,0,0);
	printf("%d\n",ans);
}
signed main(){
	T = read();
	while(T--) work();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

【例题2】数独游戏

$Ybt$ 书上讲的做法没看懂，就写了一个非常暴力的 $dfs$。用三个 $vis$ 数组分别记录行，列，宫是否有这个数字，在 $dfs$ 的过程中判断是否可行，往下搜索即可。

#include 
#include 
#include 
#include 
#include 
#include 
#define re register
#define drep(a,b,c) for(re int a(b) ; a>=(c) ; --a)
#define rep(a,b,c) 	for(re int a(b) ; a<=(c) ; ++a)
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch == '-') f=-1 ; ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
const int M = 10;
int a[M][M],vish[M][M],visl[M][M],vis[M][M];
int fl;
inline void pr(){
	rep(i,1,9) rep(j,1,9) printf("%d",a[i][j]);
	puts("");
}
inline void init(){
	memset(vish,0,sizeof(vish));
	memset(visl,0,sizeof(visl));
	memset(vis,0,sizeof(vis));
	memset(a,0,sizeof(a));
	fl = 0;
}
inline int pos(int x,int y){
	if(x <= 3 && y <= 3) return 1;
	if(x <= 3 && y <= 6) return 2;
	if(x <= 3 && y <= 9) return 3;
	if(x <= 6 && y <= 3) return 4;
	if(x <= 6 && y <= 6) return 5;
	if(x <= 6 && y <= 9) return 6;
	if(x <= 9 && y <= 3) return 7;
	if(x <= 9 && y <= 6) return 8;
	if(x <= 9 && y <= 9) return 9;
}
inline void dfs(int x,int y){
	if(fl == 1) return;
	if(x > 9) { pr(); fl = 1; return; }
	if(a[x][y] != 0){
		if(y == 9) dfs(x+1,1);
		else dfs(x,y+1);
	}
	else{
		int p = pos(x,y);
		rep(i,1,9){
			if(vish[x][i] || visl[y][i] || vis[p][i]) continue;
			vish[x][i] = visl[y][i] = vis[p][i] = 1;
			a[x][y] = i;
			if(y == 9) dfs(x+1,1);
			else dfs(x,y+1);
			vish[x][i] = visl[y][i] = vis[p][i] = 0;
			a[x][y] = 0;
		}
	}
}
signed main(){
	while(1){
		string s;
		cin >> s;
		if(s == "end") break;
		init();
		int l = 1,h = 0;
		rep(i,0,81){
			if(i%9 == 0) h++,l=1;
			if(s[i]>='1' && s[i]<='9'){
				a[h][l] = s[i] - '0';
				vish[h][a[h][l]] = visl[l][a[h][l]] = vis[pos(h,l)][a[h][l]] = 1;
			}
			l++;
		}
		dfs(1,1);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

【例题3】虫食算

这道题爆搜会 $TLE$，考虑如何进行剪枝。

由于是加法，进位最多只能是 $1$，记第一行的数为 $a$，第二行的数为 $b$，如果 $a+b\ne c$ 并且 $a+b+1\ne c$，说明当前方案不合法，可以直接返回。

如果这一列三个数字已经确定，记当前情况进位为 $jw$，如果 $a+b+jw\ne c$，同样也是不合法的，可以直接返回。

如果最高位有进位，显然也不合法，直接返回。

我们从右往左，从上往下枚举每一个字母可以填的数字，如果合法就继续往下填，最后判断即可。

注意，行和列别弄反了，由于是读入字符串，需要一行一行读，不能直接类似数组可以随意变 $x$ 和 $y$ 的位置。一开始传参的时候，行列传反了，导致 $debug$ 了很长时间。

#include 
#include 
#include 
#include 
#include 
#include 
#define re register
#define drep(a,b,c) for(re int a(b) ; a>=(c) ; --a)
#define rep(a,b,c) 	for(re int a(b) ; a<=(c) ; ++a)
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch == '-') f=-1 ; ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
const int M = 30;
int n;
char s[M][M];
int vis[M],mp[M];
inline int change(char a) { return a - 'A' + 1; }
inline void pr() { rep(i,1,n) printf("%d ",mp[i]); }
inline void dfs(int x,int y,int jw){
	if(x == 0){
		if(jw == 0) { pr(); exit(0); }
		return;
	}
	drep(i,x-1,1){
		int w1 = mp[change(s[1][i])],w2 = mp[change(s[2][i])],w3 = mp[change(s[3][i])];
		if(w1==-1 || w2==-1 || w3==-1) continue;
		if((w1+w2)%n != w3 && (w1+w2+1)%n != w3) return;
	}
	if(mp[change(s[y][x])] == -1){
		drep(i,n-1,0){
			if(!vis[i]){
				if(y != 3){
					mp[change(s[y][x])] = i;
					vis[i] = 1;
					dfs(x,y+1,jw);
					mp[change(s[y][x])] = -1;
					vis[i] = 0;
				}
				else{
					int w = mp[change(s[1][x])] + mp[change(s[2][x])] + jw;
					if(w%n != i) continue;
					mp[change(s[3][x])] = i;
					vis[i] = 1;
					dfs(x-1,1,w/n);
					mp[change(s[3][x])] = -1;
					vis[i] = 0;
				}
			}
		}
	}
	else{
		if(y != 3) dfs(x,y+1,jw);
		else{
			int w = mp[change(s[1][x])] + mp[change(s[2][x])] + jw;
			if(w%n != mp[change(s[3][x])]) return;
			dfs(x-1,1,w/n);
		}
	}
}
signed main(){
	n = read();
	rep(i,1,3) scanf("%s",s[i]+1);
	memset(mp,-1,sizeof(mp));
	dfs(n,1,0);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

$1.$ 生日蛋糕

一开始没太理解题目，看懂之后，就是一个搜索加上剪枝。

$(1)$ 当前体积 $v$ 加上前面层的最小体积 $>n$，可以直接返回。

$(2)$ 当前表面积 $s$ 加上前面层的最小侧面积 $>$ 已经搜到的答案，可以直接返回。

$(3)$ 倒着循环更快。

$(4)$ 我们每次枚举 $r$ 和 $h$，不需要从 $1$ 枚举到 $n$，由于要小于上一层，可以直接从一个区间内转移。

#include 
#include 
#include 
#include 
#include 
#include 
#define re register
#define drep(a,b,c) for(re int a(b) ; a>=(c) ; --a)
#define rep(a,b,c) 	for(re int a(b) ; a<=(c) ; ++a)
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch == '-') f=-1 ; ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
const int M = 1e4+10;
int n,m,ans = 1e9;
inline void dfs(int dep,int s,int v,int prer,int preh){
	if(s >= ans) return;
	if(dep == m+1 && v == n){
		ans = min(ans,s);
		return;
	}
	if(v >= n) return;
	int k = m-dep+1;
	if(k * prer * prer * preh + v < n) return;
	if(k * 2 + s > ans) return;
	if(dep == 1) { drep(r,prer,m) rep(h,m,preh) dfs(dep+1,s+r*r+2*r*h,v+r*r*h,r,h); }
	else { drep(r,prer-1,m-dep+1) rep(h,m-dep+1,preh-1) dfs(dep+1,s+2*r*h,v+r*r*h,r,h); }
}
signed main(){
	n = read(),m = read();
	dfs(1,0,0,(int)sqrt(n),n);
	printf("%d\n",ans);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

$2.$ 最大费用

如果 $n\le 20$，就是一个很简单的爆搜。但这道题 $n\le 40$，需要进行剪枝。我们注意到，选第 $i$ 个物品和选第 $j$ 个物品互不影响，所以我们可以进行分治。前 $\frac{n}{2}$ 个物品进行一次 $dfs$，后 $n-\frac{n}{2}$ 个物品进行一次 $dfs$，最后把两个数组拼凑成答案。

我们可以将两个数组从小到大排序。对于第一个数组 $f1$，从 $f2$ 中找到 $\le m$ 的最大位置，可以用 $upper$_$bound$ 实现，将这两个数加一起更新答案。

#include 
#include 
#include 
#include 
#include 
#include 
#define re register
#define drep(a,b,c) for(re int a(b) ; a>=(c) ; --a)
#define rep(a,b,c) 	for(re int a(b) ; a<=(c) ; ++a)
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch == '-') f=-1 ; ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
const int M = 1e5+10;
int a[M],b[M],f1[M],f2[M];
int n,m,n1,n2,ans,cnt1,cnt2;
inline void dfs1(int cur,int x,int sum){
	if(sum > m) return;
	if(cur == n1+1){
		f1[++cnt1] = sum;
		return;
	}
	dfs1(cur+1,x+1,sum+a[cur]);
	dfs1(cur+1,x,sum);
}
inline void dfs2(int cur,int x,int sum){
	if(sum > m) return;
	if(cur == n2+1){
		f2[++cnt2] = sum;
		return;
	}
	dfs2(cur+1,x+1,sum+b[cur]);
	dfs2(cur+1,x,sum);
}
signed main(){
	n = read(),m = read();
	n1 = n>>1,n2 = n-n1;
	rep(i,1,n1) a[i] = read();
	dfs1(1,0,0);
	rep(i,1,n2) b[i] = read();
	dfs2(1,0,0);
	sort(f1+1,f1+cnt1+1);
	sort(f2+1,f2+cnt2+1);
	rep(i,1,cnt1){
		int x = upper_bound(f2+1,f2+cnt2+1,m-f1[i])-f2-1;
		ans = max(ans,f1[i] + f2[x]);
	}
	printf("%d\n",ans);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

$3.$ 骑士精神

自己写的这篇博客讲的很详细

#include 
#include 
#include 
#include 
#include 
#include 
#define re register
#define drep(a,b,c) for(re int a(b) ; a>=(c) ; --a)
#define rep(a,b,c) 	for(re int a(b) ; a<=(c) ; ++a)
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch == '-') f=-1 ; ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
const int M = 10;
const int dx[] = {1,1,-1,-1,2,2,-2,-2};
const int dy[] = {2,-2,2,-2,1,-1,1,-1};
int mp[M][M];
int T,sx,sy,fl,success;
const int goal[7][7] = {
	{0,0,0,0,0,0},
	{0,1,1,1,1,1},
	{0,0,1,1,1,1},
	{0,0,0,2,1,1},
	{0,0,0,0,0,1},
	{0,0,0,0,0,0},
};
inline int evaluate(){
	int cnt = 0;
	rep(i,1,5) rep(j,1,5) if(mp[i][j] != goal[i][j]) cnt++;
	return cnt;
}
inline bool check(int x,int y){
	if(x<1 || y<1 || x>5 || y>5) return false;
	return true;
}
inline void dfs(int dep,int x,int y,int mx){
	if(dep == mx){
		if(!evaluate()) success = 1;
		return;
	}
	rep(i,0,7){
		int xx = x + dx[i];
		int yy = y + dy[i];
		if(!check(xx,yy)) continue;
		swap(mp[xx][yy],mp[x][y]);
		if(evaluate() + dep <= mx) dfs(dep+1,xx,yy,mx);
		swap(mp[xx][yy],mp[x][y]);
	}
}
inline void work(){
	fl = success = 0;
	rep(i,1,5) rep(j,1,5){
		char ch;
		cin >> ch;
		if(ch == '*') mp[i][j] = 2,sx = i,sy = j;
		else mp[i][j] = ch - '0';
	}
	if(!evaluate()) { puts("0"); return; }
	rep(step,1,15){
		dfs(0,sx,sy,step);
		if(success) { printf("%d\n",step); fl = 1; break; }
	}
	if(!fl) puts("-1");
}
signed main(){
	T = read();
	while(T--) work();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

$4.$ 折纸问题

由于有翻转和翻折操作，我们只需要枚举前半部分的折线，因为后半部分的折线可以通过先翻转再翻折达到同样的效果。

#include 
#include 
#include 
#include 
#include 
#include 
#define re register
#define int long long
#define drep(a,b,c) for(re int a(b) ; a>=(c) ; --a)
#define rep(a,b,c) 	for(re int a(b) ; a<=(c) ; ++a)
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch == '-') f=-1 ; ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
const int M = 30;
int T,n,m,pd;
int a[M],b[M],c[M];
inline void dfs(int len,int reverse){
	if(pd) return;
	if(len == m){
		bool f1=1,f2=1;
		rep(i,1,len){
			if(f1 || f2){
				if(a[i] != b[i]) f1 = false;
				if(a[i] != c[i]) f2 = false;
			}
			else break;
		}
		if(f1 || f2) pd = true;
		return;
	}
	int d[M];
	rep(i,1,len) d[i] = a[i];
	int mid = (len+1)>>1,p = (mid > m) ? mid : m;
	rep(i,p,len-1){
		int l = i,r = i+1;
		while(r<=len && l>=1) a[l--] += a[r++];
		dfs(i,0);
		rep(j,1,len) a[j] = d[j];
	}
	if(!reverse){
		rep(i,1,len) a[i] = d[len-i+1];
		dfs(len,1);
	}
}
inline void work(){
	pd = 0;
	rep(i,1,n) a[i] = read();
	m = read();
	rep(i,1,m) b[i] = read();
	rep(i,1,m) c[i] = b[m-i+1];
	dfs(n,0);
	if(pd) puts("S");
	else puts("N");
}
signed main(){
	while(scanf("%d",&n) != EOF) work();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

$5.$ 最多约数

如果不知道算数基本定理，做这道题可能有点困难。

具体的定理就是，一个正整数 $N$ 可以唯一分解为有限个质数的乘积 $N=p_1^{c_1}{p}_2^{c_2}\cdot \cdot \cdot p_m^{c_m}$，期中 $c_i$ 都是正整数，$p_i$ 都是质数。那么 $N$ 的约数个数为 ${\prod }_{i=1}^m(c_i+1)$。

这道题我们可以枚举质数，记录每一个质数选了几次，根据算数基本定理来求出因数个数。

#include 
#include 
#include 
#include 
#include 
#include 
#define re register
#define int long long
#define drep(a,b,c) for(re int a(b) ; a>=(c) ; --a)
#define rep(a,b,c) 	for(re int a(b) ; a<=(c) ; ++a)
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch == '-') f=-1 ; ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
int n,ans,cnt;
const int len = 15;
int a[len] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};
inline void dfs(int cur,int mul,int mx,int tot,int sum){
	int res = sum * (tot+1);
	if(res > cnt || (res == cnt && mul < ans)) ans = mul,cnt = res;
	if(cur+1 <= mx && a[cur] * mul <= n) dfs(cur,mul*a[cur],mx,tot+1,sum);
	if(a[cur+1] * mul <= n) dfs(cur+1,mul*a[cur+1],mx,1,sum*(tot+1));
}
signed main(){
	n = read();
	dfs(0,1,50,0,1);
	printf("%lld\n",ans);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32