链接:https://ac.nowcoder.com/acm/problem/13224
来源:牛客网

题目描述
n 个小区排成一列,编号为从 0 到 n-1 。一开始,美团外卖员在第0号小区,目标为位于第 n-1 个小区的配送站。
给定两个整数数列 a[0]~a[n-1] 和 b[0]~b[n-1] ,在每个小区 i 里你有两种选择:

  1. 选择a:向前 a[i] 个小区。
  2. 选择b:向前 b[i] 个小区。

把每步的选择写成一个关于字符 ‘a’ 和 ‘b’ 的字符串。求到达小区n-1的方案中,字典序最小的字符串。如果做出某个选择时,你跳出了这n个小区的范围,则这个选择不合法。
• 当没有合法的选择序列时,输出 “No solution!”。
• 当字典序最小的字符串无限长时,输出 “Infinity!”。
• 否则,输出这个选择字符串。

字典序定义如下:串s和串t,如果串 s 字典序比串 t 小,则
• 存在整数 i ≥ -1,使得∀j,0 ≤ j ≤ i,满足s[j] = t[j] 且 s[i+1] < t[i+1]。
• 其中,空字符 < ‘a’ < ‘b’。
输入描述:
输入有 3 行。

第一行输入一个整数 n (1 ≤ n ≤ 10^5)。

第二行输入 n 个整数,分别表示 a[i] 。

第三行输入 n 个整数,分别表示 b[i] 。

−n ≤ a[i], b[i] ≤ n
输出描述:
输出一行字符串表示答案。
示例1
输入
7
5 -3 6 5 -5 -1 6
-6 1 4 -2 0 -2 0
输出
abbbb
思路:
这题刚开始的时侯完全理解错了题种的字典序最小的序列,举个例子说明一下,如果一个点,选择a是死循环,但是选择b可以到达终点,那就还是输出“Infinity!”,因为到达终点的那条路不是字典序最小。所以我们应该维护一条字典序最小的路,如果选择a会越界就选b,b也越界就直接输出无解就可以了。如果能走,但是会回到之前走过的地方那就是“Infinity!”。但是你这样写会发现样例都是错的,它第二步选择的是a,但是走了a之后它要么是死循环要么是无法选择,是无法到达终点的。所以更严格的说明是在到达终点的这条路上,如果可以把一个b换成a,并且选择a是不会越界的,那么就是“Infinity!”。所以我们要先找出那些路它走,先用一个深搜从终点走一遍,沿路标记一下那些点是可以走的。
ac码:

#include<iostream>
#include<vector>
using namespace std;
const int N = 1e5+1;
int vis1[N], vis2[N], n, a[N], b[N];
vector<int>G[N];
inline bool pd(int m) {
	return m >= 0 && m < n;
}
void dfs(int u) {
	vis1[u] = 1;
	for (int i = 0; i < G[u].size(); i++) {
		if(!vis1[G[u][i]])
			dfs(G[u][i]);
	}
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		if(pd(i + a[i])) {
			G[i + a[i]].push_back(i);
		}
	}
	for (int i = 0; i < n; i++) {
		cin >> b[i];
		if(pd(i + b[i])) {
			G[i + b[i]].push_back(i);
		}
	}
	dfs(n-1);
	string s;
	int k = 0, flag = 0;
	vis2[0] = 1;
	while(pd(k) && !flag && k != n-1) {
		if(pd(k + a[k]) && vis1[k + a[k]]) {
			k += a[k];
			if(vis2[k]) {
				flag = 1;
				break;
			} else {
				s += 'a';
				vis2[k] = 1;
			}
		} else if(pd(k + b[k]) && vis1[k + b[k]]) {
			k += b[k];
			if(vis2[k]) {
				flag = 1;
				break;
			} else {
				s +='b';
				vis2[k] = 1;
			}
		} else {
			cout << "No solution!" << endl;
			return 0;
		}
	}
	if(flag)
		cout << "Infinity!" << endl;
	else
		cout << s << endl;
}