牛客网--送外卖

链接：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;
}