别看他简单，但是代码打起来特别容易红温，而且容易想不到漏洞。特别是大模拟题……
本文简要总结一下常用的搜索算法：
二分搜索
使用二分搜索的前提条件是每种情况的答案具有二分性————即大于某一点符合某一性质，小于等于某一点则不符合某一性质。一般常和排序一起用。
例题：2020 ICPC Shanghai Site D.Walker
首先把特殊情况处理一下：一个人走完全程、两人相对走到终点。
其次列举某点，某一人走完1到某点的距离，另外人走剩下部分。某点向用时较长的人方向偏移。
代码：
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
| #ifndef VLSMB_VS
#include <bits/stdc++.h>
#else
#include <iostream>
#include <iomanip>
#include <set>
#include <algorithm>
#include <map>
#include <vector>
#include <stack>
#endif
#define int long long
#define pii pair<int,int>
#define endl '\n'
#define veci vector<int>
#define vecpi vector<pii >
#define mpi map<int,int>
#define mpc map<char,int>
#define inf 0x7fffffffffffffff
#define eps 1e-8
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define seti set<int>
#define mulseti multiset<int>
#define setpi set<pii >
#define priqli priority_queue<int,veci,less<int> >
#define priqgi priority_queue<int,veci,greater<int> >
using namespace std;
const int N = 1000000;
void solve();
void init();
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t=1;
init();
cin>>t;
while(t--)solve();
cout.flush();
return 0;
}
void solve()
{
double n,p1,v1,p2,v2;
cin>>n>>p1>>v1>>p2>>v2;
if(p1>p2)swap(p1,p2),swap(v1,v2);
double ans=min((min(n-p1,p1)+n)/v1,(min(n-p2,p2)+n)/v2);
ans=min(ans,max((n-p1)/v1,p2/v2));
double l=p1,r=p2;
while(r-l>eps)
{
double mid=(l+r)/2;
double t1=(min(p1,mid-p1)+mid)/v1;
double t2=(min(n-p2,p2-mid)+(n-mid))/v2;
if(t1>t2)r=mid;
else l=mid;
ans=min(ans,max(t1,t2));
}
cout<<setprecision(10)<<ans<<endl;
}
void init()
{
}
|
二进制枚举
常用于个数较少（N<=20）时直接用，i的每一二进制位代表选择或者不选择某一操作。
POJ1753
思路：直接翻
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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
| #ifdef VLSMB_VS
#else
#include <iostream>
#include <iomanip>
#include <set>
#include <algorithm>
#include <map>
#include <vector>
#include <stack>
#endif
#define int long long
#define pii pair<int,int>
#define endl '\n'
#define veci vector<int>
#define vecpi vector<pii >
#define mpi map<int,int>
#define mpc map<char,int>
#define inf 0x7fffffffffffffff
#define eps 1e-8
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define seti set<int>
#define mulseti multiset<int>
#define setpi set<pii >
#define priqli priority_queue<int,veci,less<int> >
#define priqgi priority_queue<int,veci,greater<int> >
using namespace std;
const int N = 1000000;
void solve();
void init();
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t=1;
init();
while(t--)solve();
cout.flush();
return 0;
}
char tab[10][10];
char tmp[10][10];
int d[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
void solve()
{
int ans=200;
for(int i=0;i<4;i++)for(int j=0;j<4;j++)cin>>tab[i][j];
for(int s=0;s<(1<<16);s++)
{
for(int i=0;i<4;i++)for(int j=0;j<4;j++)tmp[i][j]=tab[i][j];
for(int i=0;i<4;i++)
{
for(int j=0;j<4;j++)
{
if(s&(1ull<<(4*i+j)))
{
if(tmp[i][j]=='b')tmp[i][j]='w';
else tmp[i][j]='b';
for(int k=0;k<4;k++)
{
if(i+d[k][0]>=0&&i+d[k][0]<4&&j+d[k][1]>=0&&j+d[k][1]<4)
{
if(tmp[i+d[k][0]][j+d[k][1]]=='b')tmp[i+d[k][0]][j+d[k][1]]='w';
else tmp[i+d[k][0]][j+d[k][1]]='b';
}
}
}
}
}
bool flag=true;
for(int i=0;i<4&&flag;i++)for(int j=0;j<4&&flag;j++)flag=tmp[i][j]==tmp[0][0];
if(flag)
{
int cnt=0;
int tx=s;
while(tx)
{
if(tx&1)cnt++;
tx>>=1;
}
ans=min(ans,cnt);
}
}
if(ans!=200)cout<<ans<<endl;
else cout<<"Impossible"<<endl;
}
void init()
{
}
|
DFS深度优先搜索
用于可能需要回溯剪枝的，注意需要一个vis辅助数组代表上一层所选的元素。
HD1016 Prime Ring Problem
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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
| #ifndef VLSMB_VS
#include <bits/stdc++.h>
#else
#include <iostream>
#include <iomanip>
#include <set>
#include <algorithm>
#include <map>
#include <vector>
#include <stack>
#endif
#define int long long
#define pii pair<int,int>
#define endl '\n'
#define veci vector<int>
#define vecpi vector<pii >
#define mpi map<int,int>
#define mpc map<char,int>
#define inf 0x7fffffffffffffff
#define eps 1e-8
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define seti set<int>
#define mulseti multiset<int>
#define setpi set<pii >
#define priqli priority_queue<int,veci,less<int> >
#define priqgi priority_queue<int,veci,greater<int> >
using namespace std;
const int N = 1000000;
void solve();
void init();
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t=1;
init();
while(t--)solve();
cout.flush();
return 0;
}
mpi prime;
void dfs(veci&ans,veci&vis,int n,int d)
{
if(d==n)
{
if(!prime[ans[0]+ans[n-1]])return;
for(const auto&x:ans)cout<<x<<' ';
cout<<endl;
return;
}
for(int i=2;i<=n;i++)
{
if(!vis[i]&&prime[ans[d-1]+i])
{
ans.push_back(i);
vis[i]=1;
dfs(ans,vis,n,d+1);
ans.pop_back();
vis[i]=0;
}
}
}
void solve()
{
int t=1;
int n;
while(cin>>n)
{
cout<<"Case "<<t<<':'<<endl;
t++;
veci ans;
veci vis(n+1);
vis[1]=1;
ans.push_back(1);
dfs(ans,vis,n,1);
cout<<endl;
}
}
void init()
{
prime[2]++;
prime[3]++;
prime[5]++;
prime[7]++;
prime[11]++;
prime[13]++;
prime[17]++;
prime[19]++;
prime[23]++;
prime[29]++;
prime[31]++;
prime[37]++;
prime[41]++;
prime[43]++;
}
|
BFS广度优先搜索
常见于走迷宫问题，一样需要一个vis辅助数组标记已经访问过的节点。注意有多组数据的时候要对vis数组进行清空处理。常用队列模拟每个节点走过的途径。题目越ex队列要存的东西越复杂。有些题可能需要一个状态辅助参数，有些节点需要某种状态才能进入之类的，如果状态较少可以直接用二进制数字保存。
HD1429 胜利大逃亡(续)
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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
| #ifdef VLSMB_VS
#include <bits/stdc++.h>
#else
#include <iostream>
#include <iomanip>
#include <set>
#include <algorithm>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#endif
#define int long long
#define pii pair<int,int>
#define endl '\n'
#define veci vector<int>
#define vecpi vector<pii >
#define mpi map<int,int>
#define mpc map<char,int>
#define inf 0x7fffffffffffffff
#define eps 1e-8
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define seti set<int>
#define mulseti multiset<int>
#define setpi set<pii >
#define priqli priority_queue<int,veci,less<int> >
#define priqgi priority_queue<int,veci,greater<int> >
using namespace std;
const int N = 1000000;
void solve();
void init();
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t=1;
init();
while(t--)solve();
cout.flush();
return 0;
}
char table[25][25];
int d[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int vis[25][25][2000];
void solve()
{
int n,m,t;
while(cin>>n>>m>>t)
{
for(int i=0;i<25;i++)for(int j=0;j<25;j++)for(int k=0;k<2000;k++)vis[i][j][k]=0;
pii org;
int has=0;
map<pii, int>h1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>table[i][j];
if(table[i][j]=='@')org.first=i,org.second=j;
if(table[i][j]=='*')has++,h1[{i,j}]++;
}
}
queue<pair<pii,pii > >q;
q.push({org,{0,0}});
while(!q.empty())
{
if(has==n*m)break;
pii tmp1=q.front().first;
pii tmp2=q.front().second;
q.pop();
if(table[tmp1.first][tmp1.second]=='^')
{
cout<<tmp2.first<<endl;
goto succ;
}
if(!h1[tmp1])h1[tmp1]++,has++;
if(table[tmp1.first][tmp1.second]>='a'&&table[tmp1.first][tmp1.second]<='j')
{
int off=table[tmp1.first][tmp1.second]-'a';
tmp2.second |= (1ull<<off);
}
tmp2.first++;
if(tmp2.first==t)continue;
for(int i=0;i<4;i++)
{
if(!(tmp1.first+d[i][0]>=1&&tmp1.first+d[i][0]<=n&&tmp1.second+d[i][1]>=1&&tmp1.second+d[i][1]<=m))
continue;
if(table[tmp1.first+d[i][0]][tmp1.second+d[i][1]]=='*')continue;
if(table[tmp1.first+d[i][0]][tmp1.second+d[i][1]]=='^'||table[tmp1.first+d[i][0]][tmp1.second+d[i][1]]=='@'||table[tmp1.first+d[i][0]][tmp1.second+d[i][1]]=='.' || (table[tmp1.first+d[i][0]][tmp1.second+d[i][1]]>='a'&&table[tmp1.first+d[i][0]][tmp1.second+d[i][1]]<='j')
|| (table[tmp1.first+d[i][0]][tmp1.second+d[i][1]]>='A'&&table[tmp1.first+d[i][0]][tmp1.second+d[i][1]]<='J'&&(tmp2.second&(1ull<<(table[tmp1.first+d[i][0]][tmp1.second+d[i][1]]-'A'))) ) )
{
if(!vis[tmp1.first+d[i][0]][tmp1.second+d[i][1]][tmp2.second])
{
q.push({{tmp1.first+d[i][0],tmp1.second+d[i][1]},tmp2});
vis[tmp1.first+d[i][0]][tmp1.second+d[i][1]][tmp2.second]++;
}
}
}
}
cout<<-1<<endl;
succ:
continue;
}
}
void init()
{
}
|
双向搜索
对于数据量较大的BFS，可以考虑从起点和终点双向搜索，或分区间搜索。每一次处理一般的数据，最后再将答案合并。
ATCoder abc271F XOR on Grid Path
这题思路为从起点到终点进行dfs，以i+j==n+1为界限，看两次dfs的结果。在边界线上的每一个点，值相等的记录数相乘。对每个点求和即为答案。
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
81
82
83
84
85
86
87
88
89
90
| #ifndef VLSMB_VS
#include <bits/stdc++.h>
#else
#include <iostream>
#include <iomanip>
#include <set>
#include <algorithm>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <cstdio>
#include <cmath>
#endif
#define int long long
#define pii pair<int,int>
#define endl '\n'
#define veci vector<int>
#define vecpi vector<pii >
#define mpi map<int,int>
#define mpc map<char,int>
#define inf 0x7fffffffffffffff
#define eps 1e-8
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define seti set<int>
#define mulseti multiset<int>
#define setpi set<pii >
#define priqli priority_queue<int,veci,less<int> >
#define priqgi priority_queue<int,veci,greater<int> >
using namespace std;
const int N = 1000000;
void solve();
void init();
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t=1;
init();
while(t--)solve();
cout.flush();
return 0;
}
int a[30][30];
mpi h1[30][30],h2[30][30];
void dfs1(int i,int j,int n,int val)
{
if(i+j==n+1)
{
h1[i][j][val]++;
return;
}
if(i<n)dfs1(i+1,j,n,val^a[i][j]);
if(j<n)dfs1(i,j+1,n,val^a[i][j]);
}
void dfs2(int i,int j,int n,int val)
{
if(i+j==n+1)
{
h2[i][j][val]++;
return;
}
if(i>1)dfs2(i-1,j,n,val^a[i-1][j]);
if(j>1)dfs2(i,j-1,n,val^a[i][j-1]);
}
void solve()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>a[i][j];
int ans=0;
dfs1(1,1,n,0);
dfs2(n,n,n,a[n][n]);
for(int i=1;i<=n;i++)
{
for(const auto&p:h1[i][n+1-i])ans+=p.second*h2[i][n+1-i][p.first];
}
cout<<ans<<endl;
}
void init()
{
}
|
暴力循环
其实有的题写三个for就能过……但一般都要对表达式进行变形，你才能看出来。
SPOJ ABCDEF
比如说这题，写5个循环肯定寄，写4个循环也会被卡。我们变形一下，可以把e移到右面，再将d乘过去。注意枚举的时候d不能为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
| #ifndef VLSMB_VS
#include <bits/stdc++.h>
#else
#include <iostream>
#include <iomanip>
#include <set>
#include <algorithm>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <cstdio>
#include <cmath>
#endif
#define int long long
#define pii pair<int,int>
#define endl '\n'
#define veci vector<int>
#define vecpi vector<pii >
#define mpi map<int,int>
#define mpc map<char,int>
#define inf 0x7fffffffffffffff
#define eps 1e-8
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define seti set<int>
#define mulseti multiset<int>
#define setpi set<pii >
#define priqli priority_queue<int,veci,less<int> >
#define priqgi priority_queue<int,veci,greater<int> >
using namespace std;
const int N = 1000000;
void solve();
void init();
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t=1;
init();
while(t--)solve();
cout.flush();
return 0;
}
void solve()
{
int n;
cin>>n;
veci s(n);
int ans=0;
for(auto&x:s)cin>>x;
mpi h1,h2;
for(int i=0;i<n;i++)for(int j=0;j<n;j++)for(int k=0;k<n;k++)
{
h1[s[i]*s[j]+s[k]]++;
if(s[i])h2[s[i]*(s[j]+s[k])]++;
}
for(const auto&p:h1)ans+=p.second*h2[p.first];
cout<<ans<<endl;
}
void init()
{
}
|
BFS + 优先队列
POJ2908 Quantum
有的时候直接BFS队列取出来的第一个答案不一定是最优解。如POJ2908，测试点为
1
2
3
4
5
6
| 1
4 3 1
CCCC 10
NNSS 1
SSNN 1
0000 1111
|
正确答案应该是2，但是使用普通队列的话，取出第一轮的答案之后我们直接输出答案10是错误的，等队列为空取最小值还会超时。因此我们可以用优先队列，让价值最小的优先出队，不管它现在是第几轮的操作。
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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
| #ifdef VLSMB_VS
#else
#include <iostream>
#include <iomanip>
#include <set>
#include <algorithm>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <cstdio>
#include <cmath>
#endif
#define int unsigned long long
#define pii pair<int,int>
#define endl '\n'
#define veci vector<int>
#define vecpi vector<pii >
#define mpi map<int,int>
#define mpc map<char,int>
#define inf 0x7fffffffffffffff
#define inf3f 0x3f3f3f3f3f3f3f3f
#define eps 1e-8
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define seti set<int>
#define mulseti multiset<int>
#define setpi set<pii >
#define priqli priority_queue<int,veci,less<int> >
#define priqgi priority_queue<int,veci,greater<int> >
#define priqlpi priority_queue<pii,vecpi,less<pii> >
#define priqgpi priority_queue<pii,vecpi,greater<pii > >
using namespace std;
const int N = 1000000;
void solve();
void init();
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t=1;
init();
cin>>t;
while(t--)solve();
cout.flush();
return 0;
}
int vis[1ull<<20],dis[1ull<<20];
bool operator<(const pair<int,string>&a,const pair<int,string>&b)
{
return a.first<b.first;
}
struct node
{
int first,second;
node(int x,int y):first(x),second(y){}
};
bool operator<(const node&a,const node&b)
{
return a.first>b.first;
}
void solve()
{
int l,n,m;
cin>>l>>n>>m;
vector<pair<int,string> >op(n);
for(int i=0;i<n;i++)cin>>op[i].second>>op[i].first;
while(m--)
{
for(int i=0;i<(1ull<<l);i++)vis[i]=0,dis[i]=inf3f;
string src,dest;
cin>>src>>dest;
int s=0,t=0;
for(int i=0;i<l;i++)
{
if(src[i]=='1')s|=1ull<<(l-1-i);
if(dest[i]=='1')t|=1ull<<(l-1-i);
}
priority_queue<node > q;
node tmp(0,s);
q.push(tmp);
dis[s]=0;
int ans=inf;
while(!q.empty())
{
int cost=q.top().first;
int cur=q.top().second;
const int sub=cur;
q.pop();
vis[cur]++;
if(cur==t)
{
cout<<cost;
if(m)cout<<' ';
goto succ;
}
for(vector<pair<int,string> >::iterator p=op.begin();p!=op.end();p++)
{
cur=sub;
const string&chg=p->second;
for(int i=0;i<l;i++)
{
if(chg[i]=='F')cur^=1ull<<(l-i-1);
else if(chg[i]=='S')cur|=1ull<<(l-i-1);
else if(chg[i]=='C'&&(cur&(1ull<<(l-i-1))))cur^=1ull<<(l-i-1);
}
node tmp2(cost+p->first,cur);
if(!vis[cur]&&dis[cur]>cost+p->first)dis[cur]=cost+p->first,q.push(tmp2);
}
}
cout<<"NP";
if(m)cout<<' ';
succ:
continue;
}
cout<<endl;
}
void init()
{
}
|
