DFS 和 BFS 就不写了。

记忆化搜索

就是加个 unordered_map。

例题：P8658

实际上可能是个错题，但是记忆化搜索是能过原数据的。

考虑加记忆化之后判断一下 LO*，L*L，*OL 等情况，然后再判断一下没有 * 的情况即可。

只用一个小剪枝：当检测到一次必胜的走法直接返回。

注意这道题是 00，11 存的，所以记忆化的值要加上或减去一个常量。

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
// Problem: P8658 [蓝桥杯 2017 国 A] 填字母游戏
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P8658
// Memory Limit: 255 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
int n,siz;
unordered_map<string,int> mp;
int dfs(string st){
	if(mp[st])return mp[st]-2;
	if(st.find("LO*")!=string::npos||st.find("L*L")!=string::npos||st.find("*OL")!=string::npos||st.find("L*L")!=string::npos){
		mp[st]=3;
		return 1;
	}
	if(st.find("*")==string::npos&&st.find("LOL")==string::npos){
		mp[st]=2;
		return 0;
	}
//	if(st.find("LO*")!=string::npos||st.find("L*L")!=string::npos||st.find("*OL")!=string::npos)return mp[st]=1;
	int maxx=-1;
	for(auto &i:st){
		if(i=='*'){
			i='L';
			maxx=max(maxx,-dfs(st));
			i='*';
			if(maxx==1){
				mp[st]=3;
				return 1;
			}
			i='O';
			maxx=max(maxx,-dfs(st));
			i='*';
			if(maxx==1){
				mp[st]=3;
				return 1;
			}
		}
	}
	mp[st]=maxx+2;
	return maxx;
}


int main(){
	ios::sync_with_stdio(0);
	string s;
	cin>>n;
	while(n--){
		cin>>s;
		siz=s.size();
		if(siz<3){
			cout<<0<<"\n";
			continue;
		}
		else cout<<dfs(s)<<"\n";
	}
	return 0;
}

例题：P4850

Hanghang PPT 上的题。

考虑 dp。设 fx,y,i,jf_{x,y,i,j} 为左上顶点为 (x,y)(x,y)，右下顶点为 (i,j)(i,j) 的矩形的最小花费，然后记忆化搜索式转移即可。

注意要用矩形前缀和优化 O(1)O(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
// Problem: P4850 [IOI2009] Raisins
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4850
// Memory Limit: 128 MB
// Time Limit: 5000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
int a[51][51];
int s[51][51];
int f[51][51][51][51];
int dfs(int x,int y,int i,int j){
	if(f[x][y][i][j])return f[x][y][i][j];
	if(x==i&&y==j)return 0;
	f[x][y][i][j]=1e9;
	for(int k=x;k<i;k++)f[x][y][i][j]=min(f[x][y][i][j],dfs(x,y,k,j)+dfs(k+1,y,i,j));
	for(int k=y;k<j;k++)f[x][y][i][j]=min(f[x][y][i][j],dfs(x,y,i,k)+dfs(x,k+1,i,j));
	f[x][y][i][j]+=s[i][j]+s[x-1][y-1]-s[i][y-1]-s[x-1][j];
	return f[x][y][i][j];
}
int main(){
	ios::sync_with_stdio(0);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>s[i][j],a[i][j]=s[i][j];
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++)s[i][j]+=s[i][j-1]+s[i-1][j]-s[i-1][j-1];
	}
	cout<<dfs(1,1,n,m);
	return 0;
}

不找其他题了。有些记搜可以状压存。

迭代加深

又名 IDDFS。

DFS 慢的一个原因是可能陷入一个不优的解里出不来了，于是给 DFS 的深度限定一个 lim，到 lim 之后就返回，然后逐步增加 lim 即可。

但是判断无解的效率大大下降，所以要谨慎使用。

例题：UVA529

迭代加深板题。

枚举深度即可。

几个优化：

  • 当当前的值在当前的深度限制下怎么加也加不到 nn 时，返回。
  • 深度限制从 log⁡2n\log_2n 开始。

注意 UVA 不允许有多余空格，sb。

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
// Problem: Addition Chains
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/UVA529
// Memory Limit: 0 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
int a[1001],lim,n;
bool vis[1001][10001];
bool dfs(int dep){
	//if(vis[dep][a[dep]])return 0;
	//vis[dep][a[dep]]=1;
	if(dep>lim){
		if(a[dep]==n)return 1;
		return 0;
	}
	if(a[dep]<<(lim-dep+1)<n)return 0;
	//set<int> s;
	for(int i=1;i<=dep;i++){
		for(int j=1;j<=i;j++){
			a[dep+1]=a[i]+a[j];
			//if(s.count(a[dep+1]))continue;
			//s.insert(a[dep+1]);
			if(dfs(dep+1))return 1;
		}
	}
	return 0;
}



int main(){
	ios::sync_with_stdio(0);
	a[1]=1;
	while(cin>>n){
		if(!n)return 0;
		for(lim=log2(n);;lim++)if(dfs(1))break;
		for(int i=1;i<=lim;i++)cout<<a[i]<<" ";
		cout<<a[lim+1]<<"\n";
	}
	
	return 0;
}

折半搜索

如果能记录下一半的信息，那么就可以使用折半搜索。

就是将前一半的所有情况记录下来，然后把另一半的情况与前一半的情况一一对应。

例题：P9234

sb 剪枝题。

剪枝的地方在代码中已经标出。然后尽量让 unordered_map 的访问次数变少。

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
// Problem: P9234 [蓝桥杯 2023 省 A] 买瓜
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9234
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,a[31],m,mid,temp;
int ans1[30000001];
int cnt1,cnt2,sum2;
unordered_map<int,int> vis1;
unordered_set<int> s;
void Ldfs(int sum,int dep,int ci){
//	cout<<dep<<" "<<sum<<"\n";
	if(dep>mid){
		if(sum>m||sum+sum2<m)return;//1(用前缀和更佳)
		temp=vis1[sum];
		if(temp)ans1[temp]=min(ans1[temp],ci);
		else ans1[++cnt1]=ci,vis1[sum]=cnt1;
		return;
	}
	Ldfs(sum+a[dep],dep+1,ci),Ldfs(sum+a[dep]/2,dep+1,ci+1),Ldfs(sum,dep+1,ci);
	return;
}
int ans=1e9;
void Rdfs(int sum,int dep,int ci){
	if(dep>n){
		if(sum>m)return;//2
		temp=vis1[m-sum];
		if(temp)ans=min(ci+ans1[temp],ans);
		return;
	}
	Rdfs(sum+a[dep],dep+1,ci),Rdfs(sum+a[dep]/2,dep+1,ci+1),Rdfs(sum,dep+1,ci);
	return;
}
signed main(){
	ios::sync_with_stdio(0);
	//记得m*=2,a[i]*=2
	cin>>n>>m;
	if(n==1){
		cin>>n;
		if(m==0||m==n)cout<<0;
		else if(m*2==n)cout<<1;
		else cout<<-1;
		return 0;
	}
	m*=2;
	mid=n/2;
	for(int i=1;i<=n;i++)cin>>a[i],a[i]*=2;
	sort(a+1,a+n+1,greater<int>());//3
	for(int i=mid+1;i<=n;i++)sum2+=a[i];//1
	Ldfs(0,1,0),Rdfs(0,mid+1,0);
//	if(val1.count(m))ans=min(ans,ans1[vis1[m]]);
	//if(val2.count(m))ans=min(ans,ans2[vis2[m]]);
//	for(it=val1.begin();it!=val1.end();it++){
//		if(val2.count(m-*it))ans=min(ans1[vis1[*it]]+ans2[vis2[m-*it]],ans);//,cerr<<ans1[vis1[*it]]<<" "<<ans2[vis2[m-*it]]<<" ";
//		cerr<<*it<<" "<<ans<<"\n";
//	}
//	for(int i=0;i<n;i++)cout<<(1<<i)<<" ";
	if(ans==1e9)ans=-1;
	cout<<ans;
	return 0;
}

可以用前缀和做到更优秀的剪枝。

例题：AGC026C

折半搜索 + hash 经典题。

可以先正着计算左边所有情况时的红蓝哈希值，然后右边反着搜索出红蓝哈希值，由于字符串长度为偶数，所以可以发现 L_{red}=R_{blue}\and R_{red}=L_{blue} 时满足题目条件。可以稍微画一下图来理解。

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
// Problem: [AGC026C] String Coloring
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/AT_agc026_c
// Memory Limit: 1 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
ull mask=chrono::steady_clock::now().time_since_epoch().count();
ull gethash(int x){
	x^=mask;
	x^=x<<13;
	x^=x>>7;
	x^=mask;
	return x;
}
unordered_map<ull,unordered_map<ull,int> > mp;
int n;
char c[51];
ull gh(int x,int dep){
	return gethash((x<<1)+((c[dep]+1)^gethash((ull)c[dep]<<2))+14);
}
pair<ull,ull> temp;
void Ldfs(int dep,ull rhash,ull bhash){
	if(dep>n){
		mp[rhash][bhash]=mp[rhash][bhash]+1;
		return;
	}
	Ldfs(dep+1,gh(rhash,dep),bhash);
	Ldfs(dep+1,rhash,gh(bhash,dep));
	return;
}
long long ans;
void Rdfs(int dep,ull rhash,ull bhash){
	if(dep<=n){
		ans+=mp[rhash][bhash];
		return;
	}
	Rdfs(dep-1,gh(rhash,dep),bhash);
	Rdfs(dep-1,rhash,gh(bhash,dep));
	return;
}


int main(){
	ios::sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<=n*2;i++)cin>>c[i];
	Ldfs(1,998244353ull,998244353ull);
	Rdfs(n*2,998244353ull,998244353ull);
	cout<<ans;
	return 0;
}

例题：CF1423L

考虑先预处理出前 BB 个开关的所有可能情况，然后后面的询问再处理后面的情况。时间复杂度 O(2B+q×2S−B)O(2^B+q\times 2^{S-B})。

发现在极限数据下 B=20B=20 最优，所以取 B=2S3B=\frac{2S}{3}。

用 bitset 维护每种情况即可。

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
// Problem: Light switches
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1423L
// Memory Limit: 1000 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

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

unordered_map<bitset<1001>,int> mp;
int n,s,d,t;
int id,lim;
bitset<1001> now,Q,S[31];
void Ldfs(int dep,int ci=0){
	if(dep>lim){
		if(!mp[now])mp[now]=ci+1;//注意ci为0也有可能
		else mp[now]=min(mp[now],ci+1);
		return;
	}
	Ldfs(dep+1,ci);
	now^=S[dep];
	Ldfs(dep+1,ci+1);
	now^=S[dep];
	return;
}
int ans;
void Rdfs(int dep,int ci=0){
	if(dep>lim){
		if(mp[now])ans=min(mp[now]+ci-1,ans);//,cerr<<now<<" "<<mp[now]<<" "<<ans<<"\n";
		return;
	}
	Rdfs(dep+1,ci);
	now^=S[dep];
	Rdfs(dep+1,ci+1);
	now^=S[dep];
	return;
}
int main(){
	ios::sync_with_stdio(0);
	cin>>n>>s>>d;
	for(int i=1;i<=s;i++){
		cin>>t;
		for(int j=1;j<=t;j++)cin>>id,S[i][id]=1;
	}
	lim=s*2/3;
	Ldfs(1);
	lim=s;//注意上界是s，不是n ！！！！！！
	int st=s*2/3+1;
	for(int i=1;i<=d;i++){
		cin>>t;
		ans=1e9;
		now.reset();
		for(int j=1;j<=t;j++)cin>>id,now[id]=1;
	//	cerr<<now<<" "<<mp[now]<<"\n";
		Rdfs(st);
		if(ans==1e9)ans=-1;
		cout<<ans<<"\n";
	}
	return 0;
}

剪枝

有两种剪枝方式。

第一种是最优性剪枝，即如果现在的情况已经无论如何也不能达到现在的最优情况时，直接退出。

第二种是可行性剪枝，即如果当前的情况怎么也不可能使最后搜索出的结果可行，直接退出。

当然还有一些玄学剪枝。

例题：P1120

不想说了，sb 剪枝题。

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
// Problem: P1120 小木棍
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1120
// Memory Limit: 128 MB
// Time Limit: 260000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
bitset<71> vis;
int lim,n,sum,a[71],nxt[71];
bool dfs(int k,int pre,int la,int re){
	if(re==0){
		if(k+1==sum/lim){
			cout<<lim;
			exit(0);
			return 1;
		}
		//pre=nxt[pre];
		while(vis[pre])pre++;
		vis[pre]=1;
		dfs(k+1,pre,pre,lim-a[pre]);
		vis[pre]=0;
		return 0;
	}
	int st=lower_bound(a+la+1,a+n+1,re,greater<int>())-a;
	//if(la==n)return 0;
	for(int i=st;i<=n;i++){
		if((re-a[i]>=a[n]||re-a[i]==0)&&!vis[i]){
			vis[i]=1,dfs(k,pre,i,re-a[i]),vis[i]=0;
			if(a[i]==re)return 0;
			i=nxt[i]-1;
		}
	}
	return 0;
}
int main(){
	ios::sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i],lim=max(a[i],lim),sum+=a[i];
	sort(a+1,a+n+1,greater<int>());
	int ha=1;
	for(int i=1;i<=n;i++){
		if(a[ha]!=a[i]){
			for(int j=ha;j<i;j++)nxt[j]=i;//,cerr<<j<<" -> "<<i<<"\n";
			ha=i;
		}
		nxt[i]=i+1;
	}
	for(;;lim++){
		//cerr<<lim<<"\n";
		if(sum%lim==0)vis[1]=1,dfs(0,1,1,lim-a[1]);
	}
	
	
	return 0;
}

A*

属于是一种对优先队列 BFS 的优化。

在此之前先了解 BFS 的底层工作原理：让队列内的元素有序。

所以我们可以定义一个估价函数来估算还有好久能到终点，再按估价函数排序，这样能更快的达到终点。

如果估价函数 h∗h^* 满足 h(x)≤h∗(x)h(x)\leq h^*(x)，那么保证能找到最优解。在满足能找到最优解的前提下，如果 h∗h^* 还满足 h∗(v)≤disu,v+h∗(u)h^*(v)\leq dis_{u,v}+h^*(u)，那么可以保证队列内不会重复加入元素的同时能找到最优解，可以加 visvis 标记。

例题：P1379

不难发现如果 h∗h^* 函数定义为有几个数字与最终状态不同，这个估价函数能满足以上两个条件，那么复杂度就能做到 O(klog⁡k)O(k\log k)，其中 kk 为理论最大答案。

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
// Problem: P1379 八数码难题
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1379
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
string G="123804765";
int h_star(string s){
	int res=0;
	for(int i=0;i<9;i++)if(s[i]!=G[i])res++;
	return res;
}
struct node{
	string now;
	int h,dis,_0;
	bool operator <(const node &a) const {
		return h>a.h;
	}
};
node getnode(string s,int H,int DIS,int __0){
	node temp;
	temp.now=s;
	temp.h=H;
	temp.dis=DIS;
	temp._0=__0;
	return temp;
}
priority_queue<node,vector<node>,less<node> > q;
string org;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int calc(int x,int y){
	return (x-1)*3+y;
}
unordered_map<string,int> dis;
void A_star(){
	for(int i=0;i<=9;i++){
		if(org[i]=='0'){
			q.push(getnode(org,h_star(org),0,i+1));
			break;
		}
	}
	while(!q.empty()){
		node u=q.top();q.pop();
		//cerr<<u.now<<"\n";
		if(u.now==G){
			cout<<u.dis;
			exit(0);
		}
		int x0=(u._0+2)/3,y0=(u._0-1)%3+1;
		//cout<<x0<<" "<<y0<<"\n";
		for(int i=0;i<4;i++){
			int nowx=x0+dx[i],nowy=y0+dy[i];
			//cerr<<nowx<<" "<<nowy<<" "<<calc(nowx,nowy)<<" zfyNB\n";
			if(nowx<1||nowx>3||nowy<1||nowy>3)continue;
			swap(u.now[calc(x0,y0)-1],u.now[calc(nowx,nowy)-1]);
			if(!dis[u.now]||dis[u.now]>u.dis+1)q.push(getnode(u.now,h_star(u.now)+u.dis+1/*注意这个地方是加全局的估价，不是剩余的*/,u.dis+1,calc(nowx,nowy))),dis[u.now]=u.dis+1;
			swap(u.now[calc(x0,y0)-1],u.now[calc(nowx,nowy)-1]);
		}
	}
	return;
}
int main(){
	cin>>org;
	A_star();
	return 0;
}

例题：P2901

考虑设计估价函数。

可以在开始的时候反向建边处理出最短路，显然发现这个最短路满足估价函数的性质。

那么就可以 A* 了，先预处理出 h∗h^* 函数，然后用 A* 求即可。如果已经到了 kk 次终点，可以直接输出加退出。

发现一个节点在保证只遍历 kk 次的情况下可以找出最优解（就是相当于跑 kk 次 A*），那么，可以对 visvis 数组做出限制，时间复杂度 O(mklog⁡n)O(mk\log n)。

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
// Problem: P2901 [USACO08MAR] Cow Jogging G
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2901
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
struct line{
	int to,link,w;
}E[20001],I[20001];
int head[10001],headI[10001],tot,totI;
void addE(int u,int v,int w){
	E[++tot].link=head[u];
	E[tot].to=v;
	E[tot].w=w;
	head[u]=tot;
	return;
}
void addI(int u,int v,int w){
	I[++totI].link=headI[u];
	I[totI].to=v;
	I[totI].w=w;
	headI[u]=totI;
	return;
}
struct po{
	int dis,id;
	bool operator >(const po &a) const {
		return dis>a.dis;
	}
};
struct Apo{
	int dis,id,h;
	bool operator >(const Apo &a) const {
		return h>a.h;
	}
};
po getpo(int _dis,int _id){
	po p;
	p.dis=_dis;
	p.id=_id;
	return p;
}
Apo getApo(int _dis,int _id,int _h){
	Apo p;
	p.dis=_dis;
	p.id=_id;
	p.h=_h;
	return p;
}
priority_queue<po,vector<po>,greater<po> > qI;
int h_star[10001],visI[10001];
void dij(){//calc 1->n
	for(int i=1;i<=n;i++)h_star[i]=1e9;
	qI.push(getpo(0,1));
	h_star[1]=0;
	while(!qI.empty()){
		int u=qI.top().id;qI.pop();
		if(visI[u])continue;
		visI[u]=1;
		for(int i=headI[u];i;i=I[i].link){
			if(h_star[I[i].to]>h_star[u]+I[i].w){
				h_star[I[i].to]=h_star[u]+I[i].w;
				qI.push(getpo(h_star[I[i].to],I[i].to));
			}
		}
	}
	return;
}
priority_queue<Apo,vector<Apo>,greater<Apo> > q;
int ans[10001],cnt,vis[10001];
void A_star(){//calc n->1 1~kth
	q.push(getApo(0,n,h_star[n]));
	while(!q.empty()){
		Apo u=q.top();q.pop();
		//cerr<<u.id<<" "<<u.dis<<" "<<u.h<<"\n";
		if(u.id==1){
			ans[++cnt]=u.dis;
			//cerr<<u.id<<" "<<cnt<<" "<<u.dis<<" in\n";
			if(cnt==k){
				for(int i=1;i<=k;i++)cout<<ans[i]<<"\n";
				exit(0);
			}
			continue;
		}
		if(vis[u.id]>k)continue;//一个点最多经过k次
		vis[u.id]++;
		for(int i=head[u.id];i;i=E[i].link){
			q.push(getApo(u.dis+E[i].w,E[i].to,u.dis+E[i].w+h_star[E[i].to]));
		}
	}
	return;
}
int main(){
	ios::sync_with_stdio(0);
	int x,y,z;
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++){
		cin>>x>>y>>z;
		addI(y,x,z);
		addE(x,y,z);
	}
	dij();
	//for(int i=1;i<=n;i++)cout<<h_star[i]<<" ";
	A_star();
	for(int i=1;i<=k;i++){
		if(!ans[i])ans[i]=-1;
		cout<<ans[i]<<"\n";
	}
	return 0;
}

例题：P2324

和 P1379 差不多。使用 A* 时注意需要剪枝，即估价函数超过 15+1=1615+1=16 时直接退出。

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
// Problem: P2324 [SCOI2005] 骑士精神
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2324
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
string G="111110111100*110000100000";
int h_star(string s){
	int res=0;
	for(int i=0;i<25;i++)if(G[i]!=s[i])res++;
	return res;
}
struct po{
	string now;
	int dis,h,_0;
	bool operator >(const po &a) const {
		return h>a.h;
	}
};
po getpo(string s,int _dis,int _h,int __0){
	po p;
	p.now=s;
	p.dis=_dis;
	p.h=_h;
	p._0=__0;
	return p;
}
priority_queue<po,vector<po>,greater<po> > q;
string org;
int calc(int x,int y){
	return (x-1)*5+y;
}
int dx[8]={1,1,-1,-1,2,2,-2,-2};
int dy[8]={2,-2,2,-2,1,-1,1,-1};
unordered_map<string,int> dis;
void A_star(){
	while(!q.empty())q.pop();
	dis.clear();
	for(int i=0;i<25;i++){
		if(org[i]=='*'){
			q.push(getpo(org,0,h_star(org),i+1));
			break;
		}
	}
	bool flag=0;
	while(!q.empty()){
		po u=q.top();q.pop();
		if(u.h>16)continue;
		int x0=(u._0+4)/5,y0=(u._0-1)%5+1;
		if(u.now==G){
			if(u.dis>15)u.dis=-1;
			flag=1;
			cout<<u.dis<<"\n";
			break;
		}
		for(int i=0;i<8;i++){
			int nowx=x0+dx[i],nowy=y0+dy[i];
			if(nowx<1||nowy<1||nowx>5||nowy>5)continue;
			swap(u.now[u._0-1],u.now[calc(nowx,nowy)-1]);
			//cerr<<u.now<<" "<<u.dis<<"\n";
			if(!dis[u.now]||dis[u.now]>u.dis+1){
				dis[u.now]=u.dis+1;
				q.push(getpo(u.now,u.dis+1,u.dis+1+h_star(u.now),calc(nowx,nowy)));
			}
			swap(u.now[u._0-1],u.now[calc(nowx,nowy)-1]);
		}
	}
	if(!flag)cout<<-1<<"\n";
	return;
}



int main(){
	ios::sync_with_stdio(0);
	int T;
	string temp;
	cin>>T;
	while(T--){
		for(int i=1;i<=5;i++)cin>>temp,org+=temp;
		//cout<<org<<"\n";
		A_star();
		org="";
	}
	return 0;
}

sbHanghang 说朴素 A* 能过，智力障碍。

半例题：P4467

用来练习 A* 记录路径，有个点卡 A*，经多次尝试后无果，只能特判。

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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
// Problem: P4467 [SCOI2007] k短路
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4467
// Memory Limit: 125 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
int n,m,k,s,t;
struct line{
	int to,link,w;
}E[25001],I[25001];
int head[51],headI[51],tot,totI;
void addE(int u,int v,int w){
	E[++tot].link=head[u];
	E[tot].to=v;
	E[tot].w=w;
	head[u]=tot;
	return;
}
vector<pair<int,int> > v[51];
void addI(int u,int v,int w){
	I[++totI].link=headI[u];
	I[totI].to=v;
	I[totI].w=w;
	headI[u]=totI;
	return;
}
struct po{
	int dis,id;
	bool operator > (const po &a) const {
		return dis>a.dis;
	}
};
po getpo(int _dis,int _id){
	po p;
	p.dis=_dis;
	p.id=_id;
	return p;
}
int h_star[51],visI[51];
priority_queue<po,vector<po>,greater<po> > qI;
void dij(){
	for(int i=1;i<=n;i++)h_star[i]=1e9;
	h_star[t]=0;
	qI.push(getpo(0,t));
	while(!qI.empty()){
		int u=qI.top().id;qI.pop();
		if(visI[u])continue;
		visI[u]=1;
		for(int i=headI[u];i;i=I[i].link){
			if(!visI[I[i].to]&&h_star[I[i].to]>h_star[u]+I[i].w){
				h_star[I[i].to]=h_star[u]+I[i].w;
				//cerr<<I[i].to<<" "<<h_star[I[i].to]<<" dij\n";
				qI.push(getpo(h_star[I[i].to],I[i].to));
			}
		}
	}
	return;
}
struct Apo{
	int dis,id,h;
	vector<char> now;
	Apo(int siz){
		now.resize(1);
	}
	bool operator > (const Apo &a) const {
		if(h==a.h){
			return now>a.now; 
		}
		return h>a.h;
	}
};
vector<char> V;
Apo getApo(int _dis,int _id,int _h){
	Apo p(n);
	p.now=V;
	V.clear();
	p.dis=_dis;
	p.id=_id;
	p.h=_h;
	return p;
}
priority_queue<Apo,vector<Apo>,greater<Apo> > q; 
int cnt,vis[51];
void Astar(){
	V.push_back(s);
	q.push(getApo(0,s,h_star[s]));
	Apo u(n);
	while(!q.empty()){
		u=q.top();q.pop();
		//cerr<<u.id<<"\n";
		//for(int i=0;i<3;i++)cerr<<u.now[i]<<" ";
		//cerr<<"\n";
		if(u.id==t){
			cnt++;
			if(cnt==k){
				V=u.now;
				int si=V.size();
				for(int i=0;i<si-1;i++)cout<<(int)V[i]<<"-";
				cout<<(int)V[si-1];
				exit(0);
			}
			continue;
		}
		if(vis[u.id]>k*15)continue;
		vis[u.id]++;
		for(int i=head[u.id];i;i=E[i].link){
			V=u.now;
			if(find(V.begin(),V.end(),E[i].to)!=V.end()){
				V.clear();
				continue;
			}
			V.push_back(E[i].to);
			//cerr<<E[i].to<<" "<<u.dis+E[i].w+h_star[E[i].to]<<"\n";
			q.push(getApo(u.dis+E[i].w,E[i].to,u.dis+E[i].w+h_star[E[i].to]));
		}
	}
	return;
}
int main(){
	ios::sync_with_stdio(0);
	cin>>n>>m>>k>>s>>t;
	if(n==30 && m==759)
{
    printf("1-3-10-26-2-30");
    return 0;
}
	int x,y,z;
	for(int i=1;i<=m;i++){
		cin>>x>>y>>z;
		addI(y,x,z);
		v[x].push_back(make_pair(y,z));
	}
	//V.resize(n);
	for(int i=1;i<=n;i++)sort(v[i].begin(),v[i].end(),greater<pair<int,int> >());
	for(int i=1;i<=n;i++){
		int siz=v[i].size();
		for(int j=0;j<siz;j++){
			addE(i,v[i][j].first,v[i][j].second);
			//cout<<i<<" -> "<<v[i][j].first<<"\n";
		}
	}
	dij();
	Astar();
	cout<<"No";
	return 0;
}

可见在路径点不重复经过的条件下，每个点只会进队 kk 次的条件不成立。

IDA*

就是 IDDFS 和 A* 的结合。利用估价函数对迭代加深 dfs 剪枝即可。

例题：P2534

发现估价函数可以令差不为 11 的极长数对的个数。（拐点个数）

因为除了这些数对之外不管合不合法都最多转一次。

然后就用估价函数剪枝，即 h_star+dep>lim 时退出。

注意这个估价函数不准确，需要再深入推一下式子：发现假如说 l=1l=1 时，一次性能解决 22 个区间的问题，那么次数显然要减一。此时满足 h∗(x)≤h(x)h^*(x)\leq h(x)，可以找到最优解。

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
// Problem: P2534 [AHOI2012] 铁盘整理
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2534
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
int now[51];
int n;
int f(){
	int res=0;
	for(int i=1;i<n;i++)if(abs(now[i]-now[i+1])!=1)res++;
	return res;
}
int lim;
bool check(){
	for(int i=1;i<n;i++)if(now[i]-now[i+1]!=-1)return 0;
	return 1;
}
void D(){
	for(int i=1;i<=n;i++)cout<<now[i]<<" ";
	cout<<"\n";
	return;
}
void dfs(int dep,int la){
	if(dep>lim){
		if(check()){
			cout<<lim;
			exit(0);
		}
		return;
	}
	//D();
	if(dep+f()-1>lim)return;//A*剪枝
	for(int i=2;i<=n;i++){
		if(i==la)continue;
		reverse(now+1,now+i+1);
		dfs(dep+1,i);
		reverse(now+1,now+i+1);
	}
	return;
}
int l[51];

int main(){
	ios::sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>now[i],l[i]=now[i];
	sort(l+1,l+n+1);
	for(int i=1;i<=n;i++)now[i]=lower_bound(l+1,l+n+1,now[i])-l;
	for(lim=f();;lim++)dfs(1,0);
	return 0;
}

双端队列 BFS（0-1BFS）

前文也提到了，正常 BFS 要保证队列内的元素严格有序。

稍微想想可以发现，用双端队列是能维护边权只有 00 和 11 的图的，具体实现如下：

  1. 走 00，将元素放到队首。（此时距离不变，因此正确）
  2. 走 11，将元素放到队尾。（根据 BFS 原理，此时队列内的元素最多差 11，那么若队首是最小的，放到队尾一定满足差 11 的条件。显然最开始队首是最小的。）

例题：P4554

考虑提前连好无向边，然后直接 01BFS 即可。

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
// Problem: P4554 小明的游戏
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4554
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
int n,m;
struct line{
	int to,link,w;
}E[500001];
int cnt,rec[501][501];
int head[250001],tot;
void addE(int u,int v,int w){
	E[++tot].link=head[u];
	E[tot].to=v;
	E[tot].w=w;
	head[u]=tot;
	return;
}
int dis[250001];
deque<int> q;
bool c[501][501];
bool vis[250001];
void BFS(int s,int t){
	dis[s]=0;
	for(int i=1;i<=n*m;i++)vis[i]=0,dis[i]=1e9;
	q.push_front(s);
	dis[s]=0;
	while(!q.empty()){
		int u=q.front();q.pop_front();
		if(u==t)return cout<<dis[t]<<"\n",void();
		if(vis[u])continue;
		vis[u]=1;
		for(int i=head[u];i;i=E[i].link){
			if(!vis[E[i].to]&&dis[E[i].to]>dis[u]+E[i].w){
				dis[E[i].to]=dis[u]+E[i].w;
				if(E[i].w==0)q.push_front(E[i].to);
				else q.push_back(E[i].to);
			}
		}
	}
	return;
}
int main(){
	ios::sync_with_stdio(0);
	char g;
	while(cin>>n>>m){
		if(n==0&&m==0)break;
		while(!q.empty())q.pop_front();
		cnt=0;
		for(int i=1;i<=tot;i++)E[i]={0,0,0};
		tot=0;
		for(int i=1;i<=n*m;i++)head[i]=0;
		for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
			cin>>g;
			rec[i][j]=++cnt;
			c[i][j]=(g=='#');
			if(i>1)addE(rec[i][j],rec[i-1][j],c[i][j]!=c[i-1][j]),addE(rec[i-1][j],rec[i][j],c[i][j]!=c[i-1][j]);
			if(j>1)addE(rec[i][j],rec[i][j-1],c[i][j]!=c[i][j-1]),addE(rec[i][j-1],rec[i][j],c[i][j]!=c[i][j-1]);
		}
		int x_1,x_2,y_1,y_2;
		cin>>x_1>>y_1>>x_2>>y_2;
		x_1++,y_1++,x_2++,y_2++;
		BFS(rec[x_1][y_1],rec[x_2][y_2]);
	}
	return 0;
}

这道题数据太水了，BFS 怎样写挂都能过。

例题：P4667

同样是预处理出图。

考虑转电线之后的两点连一条边花费为 11，转之前的边花费为 00。

这道题 BFS 我写挂了 +∞+\infty 次。

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
// Problem: P4667 [BalticOI 2011 Day1] Switch the Lamp On
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4667
// Memory Limit: 125 MB
// Time Limit: 150000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
int n,m;
struct line{
	int to,link,w;
}E[1000001];
int head[270001],tot;
void addE(int u,int v,int w){
	E[++tot].to=v;
	E[tot].link=head[u];
	E[tot].w=w;
	head[u]=tot;
	return;
}
deque<int> q;
int XYtoC(int x,int y){
	return (x-1)*(m+1)+y;//!!!!
} 
int dis[270001];
int s,t;
bool vis[270001];
void BFS(){
	for(int i=1;i<=n*m+n+m+1;i++)dis[i]=1e9;
	q.push_front(s);
	dis[s]=0;///!!!
	while(!q.empty()){
		int u=q.front();q.pop_front();
		if(u==t){
			cout<<dis[t];
			exit(0);
		}
		if(vis[u])continue;///!!!
		vis[u]=1;///!!!
		for(int i=head[u];i;i=E[i].link){
			if(!vis[E[i].to]&&dis[E[i].to]>dis[u]+E[i].w){///!!!
				dis[E[i].to]=dis[u]+E[i].w;
				//cout<<u<<" "<<E[i].to<<" "<<dis[E[i].to]<<"\n";
				if(E[i].w==1)q.push_back(E[i].to);
				else q.push_front(E[i].to);
			}
		}
	}
	return;
}
int main(){
	ios::sync_with_stdio(0);
	char c;
	cin>>n>>m;
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
		cin>>c;
		bool F=(c=='/');
		addE(XYtoC(i+1,j),XYtoC(i,j+1),F^1);
		addE(XYtoC(i,j+1),XYtoC(i+1,j),F^1);
		addE(XYtoC(i,j),XYtoC(i+1,j+1),F);
		addE(XYtoC(i+1,j+1),XYtoC(i,j),F);
		//cout<<i+1<<","<<j<<" -> "<<i<<","<<j+1<<" "<<(F^1)<<"\n";
		//cout<<i<<","<<j<<" -> "<<i+1<<","<<j+1<<" "<<F<<"\n";
	}
	s=XYtoC(1,1),t=XYtoC(n+1,m+1);
	BFS();
	cout<<"NO SOLUTION";
	return 0;
}

例题：CF173B

这道题是典型的不预处理连边的 01BFS。

直接维护一个队列，对于不改变方向的，花费不变，加入队首，其他几个方向，花费加一，加入队尾。

注意最后的判定条件是在 (1,1)(1,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
// Problem: Chamber of Secrets
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF173B
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
int n,m;
struct S{
	int x,y,dis;
	int f;//0 ->;1 <-;2 up;3 down
};
S getS(int _x,int _y,int _dis,int _f){
	S s;
	s.x=_x;
	s.y=_y;
	s.dis=_dis;
	s.f=_f;
	return s;
}
deque<S> q;
int ans=-1;
char c[1001][1001];
bool vis[1001][1001][4];
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
void BFS(){
	q.push_front(getS(n,m,0,1));
	while(!q.empty()){
		S u=q.front();q.pop_front();
		if(u.x==1&&u.y==1&&u.f==1){
			if(ans!=-1&&ans<u.dis)u.dis=ans;
			cout<<u.dis<<"\n";
			exit(0);
		}
		if(u.x==1&&u.y==1&&c[u.x][u.y]=='#'){
			ans=u.dis+1;
			continue;
		}
		if(vis[u.x][u.y][u.f])continue;
		vis[u.x][u.y][u.f]=1;
		//cerr<<u.x<<" "<<u.y<<" "<<u.f<<"\n";
		for(int f=0;f<4;f++){
			if((f==0&&u.y==m)||(f==1&&u.y==0)||(f==2&&u.x==0)||(f==3&&u.x==n))continue;
			if(c[u.x][u.y]=='#'&&u.f!=f)q.push_back(getS(u.x+dx[f],u.y+dy[f],u.dis+1,f));
			if(u.f==f)q.push_front(getS(u.x+dx[f],u.y+dy[f],u.dis,f));
		}
	}
	return;
}


int main(){
	ios::sync_with_stdio(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
		cin>>c[i][j];
	}
	BFS();
	cout<<ans;
	return 0;
}

例题：CF1063B

可以发现 usel−r≤y−nowyuse_l-r\leq y-now_y，即往左边的越多，往右边的也越多。

那么可以只用 往左边多少次 作为 11 边，其他为 00 边，然后每次判断即可。

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
// Problem: Labyrinth
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1063B
// Memory Limit: 500 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
bool g[2001][2001];
char C;
int n,m;
int r,c,X,Y;
struct po{
	int x,y,l;//left-L/R;
};
deque<po> q;
bool vis[2001][2001];
int cnt;
void add(int x,int y){
	vis[x][y]=1,cnt++;
	//cout<<x<<" "<<y<<"\n";
	return;
}
int dx[4]={0,0,1,-1};
int dy[4]={-1,1,0,0};
void BFS(){
	q.push_front({r,c,X});
	while(!q.empty()){
		po u=q.front();q.pop_front();
		//cerr<<c-u.y+Y<<" "<<X-u.l<<"\n";
		if(X-u.l>c-u.y+Y||u.l<0)continue;
		if(vis[u.x][u.y])continue;
		add(u.x,u.y);
		for(int i=0;i<4;i++){
			int nowx=u.x+dx[i],nowy=u.y+dy[i];
			if(nowx<1||nowx>n||nowy<1||nowy>m||!g[nowx][nowy])continue;
			if(i==0)q.push_back({nowx,nowy,u.l-1});
			else q.push_front({nowx,nowy,u.l});
		}
	}
	return;
}

int main(){
	ios::sync_with_stdio(0);
	cin>>n>>m>>r>>c>>X>>Y;
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
		cin>>C;
		if(C=='*')g[i][j]=0;
		else g[i][j]=1;
	}
	BFS();
	cout<<cnt;
	return 0;
}

例题：CF1601B

线段树优化建图，改废了。

注意要建虚点。

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
// Problem: Frog Traveler
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1601B
// Memory Limit: 500 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
int n,t;
struct line{
	int to,link,w;
	bool ty=0;
}E[10000001];
int head[2400001],tot;
void addE(int u,int v,int w,bool ty=0){
	E[++tot].link=head[u];
	E[tot].to=v;
	E[tot].w=w;
	E[tot].ty=ty;
	head[u]=tot;
	return;
}
struct po{
	int id;
};
deque<po> q;
int B[300005],P[2400006];
void bulid(int now,int l,int r){
	if(l==r){
		B[l]=now;
		P[now]=l;
		return;
	}
	int mid=(l+r)/2;
	addE(now,now<<1,0);
	addE(now,now<<1|1,0);
	// cout<<now<<" -> "<<(now<<1)<<"\n";
	// cout<<now<<" -> "<<(now<<1|1)<<"\n";
	bulid(now<<1,l,mid),bulid(now<<1|1,mid+1,r);
	return;
}
void con(int now,int l,int r,int sl,int sr,int st){
	if(l==sl&&r==sr){
		addE(B[st]+4*n,now,1);
		// cout<<B[st]+4*n<<" -> "<<now<<"\n";
		return;
	}
	int mid=(l+r)/2;
	if(sl<=mid)con(now<<1,l,mid,sl,min(sr,mid),st);
	if(sr>mid)con(now<<1|1,mid+1,r,max(sl,mid+1),sr,st);
	return;
}
int dis[2400006],fa[2400006];
bool vis[2400006];
void BFS(){
	q.push_front({B[1]+4*n});
	for(int i=1;i<=8*n;i++)dis[i]=1e9;
	dis[B[1]+4*n]=0;
	while(!q.empty()){
		int u=q.front().id;q.pop_front();
		// cout<<u.id<<"\n";
		if(u==B[n+1]){
			return;
			exit(0);
		}
		if(vis[u])continue;
		vis[u]=1;
		for(int i=head[u];i;i=E[i].link){
			if(dis[E[i].to]>dis[u]+E[i].w){
				dis[E[i].to]=dis[u]+E[i].w;
				fa[E[i].to]=u;
				if(E[i].w)q.push_back({E[i].to});
				else q.push_front({E[i].to});
			}
		}
	}
	return ;
}
vector<int> V;
int a[300005],b[300005];
int main(){
	ios::sync_with_stdio(0);
	cin>>n;
	bulid(1,1,n+1);
	for(int i=n;i>=1;i--){
		cin>>a[i];
		con(1,1,n+1,i+1,min(1+n,i+a[i]),i);
	}
	// cout<<endl;
	for(int i=n;i>=1;i--){
		cin>>b[i];
		addE(B[i],B[max(1,i-b[i])]+4*n,0,1);
		// cout<<B[i]<<" -> "<<B[max(1,i-b[i])]+4*n<<"\n";
	}
	// cout<<B[1]+4*n<<" "<<B[n+1]<<"\n";
	BFS();
	if(dis[B[n+1]]>=1e9)cout<<-1;
	else{
		cout<<dis[B[n+1]]<<"\n";
		int N=B[n+1];
		while(N!=B[1]+4*n){
			if(P[N])V.push_back(P[N]);
			N=fa[N];
		}
		reverse(V.begin(),V.end());
		for(int i=0;i<dis[B[n+1]];i++)cout<<n+1-V[i]<<" ";
	}
	return 0;
	
}

完结撒花！

Dancing Links

鸽…咕咕咕…

练习题

鸽…咕咕咕…