题解 | #送外卖#

思路：深度代表到达的小区编号，每一个小区都有走a，走b两种选择，走a一定先于走b，因为要确保输出的是最小字典序，在搜索的过程中，如果搜索到了一个曾经访问过的小区，那么一定就陷入了死循环，flag标记为1,为了模拟进入死循环的情况，如果在返回的过程中发现有一个小区曾经访问过，那么当前状态的字符串一定是无限长的。

#include<bits/stdc++.h>
using namespace std;
int n;
const int M=1e5+5;
int a[M];
int b[M];
int vis[M];
int f[M];
int flag;
char ans[M];
int dfs(int dep,int step){
	if(dep<1||dep>n){
		return 0;
	}
	if(dep==n){
		ans[step]='\0';
		return 1;
	}	
	if(vis[dep]){
		f[dep]=1;
		return 0;
	}
	vis[dep]=1;
	if(dfs(dep+a[dep],step+1)){
		ans[step]='a';
		if(f[dep])	flag=1;
		return true;
	}
	if(dfs(dep+b[dep],step+1)){
		ans[step]='b';
		if(f[dep])	flag=1;
		return true;
	}
	return false;
}

int main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); 
	cin>>n;
	for(int i=1;i<=n;i++)	cin>>a[i];
	for(int i=1;i<=n;i++)	cin>>b[i];
	if(dfs(1,0)){
		if(flag)	cout<<"Infinity!"<<endl;
		else	cout<<ans<<endl;
	}
	else	cout<<"No solution!"<<endl;
	
	return 0; 
}