题解 | #送外卖#

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<stack>
#include<map>
#include<queue>
#include<set>
#include<unordered_map>
using namespace std;
int read()
{
    int x=0,y=1;char c=getchar();
    while(c>'9'||c<'0'){if(c=='0')y=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*y;
}

int N;
int A[100010],B[100010];
bool vis[100010],st[100010];//vis判断当前小区是否被选， st判断小区在经过一定步骤操作后是否回到该小区
//接上注释，设小区x在被选定后，经过某些步骤后再次选择x小区，构成死循环，即 vis[ x ]==true加上一些操作后，再次选择x小区
bool pan=false; 
char str[100010];//小区步骤的字符串存入
 
bool dfs(int xq,int step){//xq为当前位置小区，step为花费步骤//该方法为置顶向下，（可以理解为树根向树叶的方法） 
	if(xq>N||xq<1){
		return false;//非法步骤 
	}
	
	if(xq==N){
		str[step]='\0';//字符串截止，也是对之前字符串的覆盖 
		return true; 
	}
	
	//如果该小区之前已经被选择过
	if(vis[xq]){ 
		//陷入死循环,设置状态st，直接返回 
		st[xq]=true;
		return false; //之后没必要再循环下去 
	}
	vis[xq]=true;//该小区被第一次选择
	
	//因为要求字典序最小，其中'\0'<'a'<'b'  (如果要求字典序最大，先b再a即可)
	//1.先选择走a步骤
	if(dfs(xq+A[xq],step+1)){
		str[step]='a';//步骤字符填入
		if(st[xq]) pan=true;//标志为死循环
		return true; //大字典序字符无法覆盖的原因。
		//如果小字典序字符满足条件//在此处就已经输出 
	} 
	//2.后选择b步骤 
	if(dfs(xq+B[xq],step+1)){
		str[step]='b';
		if(st[xq]) pan=true;//标志为死循环
		return true;
	}
	return false;
}
//该方法剪枝//置顶向下剪树枝//简称不撞南墙不回头// 
 
int main(){
	scanf("%d",&N);
	
	
	for(int i=1;i<=N;i++){
		scanf("%d",&A[i]);
        //该代码中快读方法read()对负数的读入不稳定，不建议在有负数输入的时候使用
	}
	for(int i=1;i<=N;i++){
		scanf("%d",&B[i]);
	}
	if(dfs(1,0)){
		if(pan){
			puts("Infinity!");
		}
		else{
			puts(str);
		}
	}
	else{
		puts("No solution!");
	}
	return 0;
}