啥是双向搜索
两种双向搜索算法：「双向同时搜索」和「Meet in the middle」
双向广搜的步骤：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| 将开始结点和目标结点加入队列 q
标记开始结点为 1
标记目标结点为 2
while (队列 q 不为空)
{
从 q.front() 扩展出新的 s 个结点
如果 新扩展出的结点已经被其他数字标记过
那么 表示搜索的两端碰撞
那么 循环结束
如果 新的 s 个结点是从开始结点扩展来的
那么 将这个 s 个结点标记为 1 并且入队 q
如果 新的 s 个结点是从目标结点扩展来的
那么 将这个 s 个结点标记为 2 并且入队 q
}
|
Meet in the middle
算法的主要思想是将整个搜索过程分成两半，分别搜索，最后将两半的结果合并。暴力搜索的复杂度往往是指数级的，而改用 meet in the middle 算法后复杂度的指数可以减半
[USACO2.2] 集合 Subset Sums
题目描述
对于从 $1\sim n$ 的连续整数集合，能划分成两个子集合，且保证每个集合的数字和是相等的。举个例子，如果 $n=3$，对于 ${1,2,3}$ 能划分成两个子集合，每个子集合的所有数字和是相等的：
${3}$ 和 ${1,2}$ 是唯一一种分法（交换集合位置被认为是同一种划分方案，因此不会增加划分方案总数）
如果 $n=7$，有四种方法能划分集合 ${1,2,3,4,5,6,7 }$，每一种分法的子集合各数字和是相等的:
${1,6,7}$ 和 ${2,3,4,5}$
${2,5,7}$ 和 ${1,3,4,6}$
${3,4,7}$ 和 ${1,2,5,6}$
${1,2,4,7}$ 和 ${3,5,6}$
给出 $n$，你的程序应该输出划分方案总数。
输入格式
输入文件只有一行，且只有一个整数 $n$
输出格式
输出划分方案总数。
样例 #1
样例输入 #1
样例输出 #1
提示
【数据范围】
对于 $100\%$ 的数据，$1\le n \le 39$。
分析
爆搜子集排列是$O(2^N)$ 的，而$O(2^N)$的时间复杂度在OI中一般跑N=20是没有问题的。
n<=39的数据范围想到的是meet-in-the-middle 这个小技巧。
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
| #include<cstdio>
typedef long long LL;
const int M=1e3+5;
LL b[M];
int n;
LL ans;
int main(){
scanf("%d",&n);
if(((1+n)*n/2)&1)puts("0");
else{
for(int i=0;i<(1<<(n/2));++i){
int cur=0;
for(int j=0;(i>>j)>0;++j)if((i>>j)&1)cur+=(j+1);
b[cur]++;
}
for(int i=0;i<(1<<(n-n/2));++i){
int cur=0;
for(int j=0;(i>>j)>0;++j)if((i>>j)&1)cur+=j+n/2+1;
if((1+n)*n/4>=cur)
ans+=b[(1+n)*n/4-cur];
}
printf("%lld\n",ans/2);
}
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
| #define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int sum, n;
int f[40][800];
int i, j;
int main() {
cin >> n;
sum = ((1 + n) * n / 2);
if (sum & 1) cout << "0";
else {
f[1][1] = 1;
f[1][0] = 1;
for (int i = 2; i <= n; i++) {
for (j = 0; j <= sum; j++) {
if (j > i) {
f[i][j] = f[i - 1][j] + f[i - 1][j - i];
}
else {
f[i][j] = f[i - 1][j];
}
}
}
cout << f[n][sum >> 1];
}
return 0;
}
|
