题意:一共n个节点,下标从0开始,两个数组a[n],b[n],每个节点i从a[i],b[i]中选择一个步数,从0节点开始,最终要走到n-1节点,答案是每次选择所组成的字符串,要求该字符串字典序最小,如果该字符串无穷就输出“IN”,无解则输出NO
样例
INPUT
7
5 -3 6 5 -5 -1 6
-6 1 4 -2 0 -2 0
OUTPUT
abbbb
思路:每个点两个选择两个可以想到与图论相关,首先建图。接下来想:如何找到所有答案?就是如何找到一条能从0到n-1的路径。所以想到BFS找到路径。接下来想:如何在BFS过程中找到字典序最小的路径并且输出?在BFS的过程中很难同时处理出答案,因为每个节点所存的选择都有可能被下一个选择覆盖掉。答案用到了一个我没想到的方法:
先逆着求出路径,从n-1开始,用BFS求出从n-1到0的路径,并且把走过的节点标记(st1)(注意是所有走过的节点)。这里建图必须使用单向图(n-1->0)。然后从0开始,如果节点被st1标记过,证明这是一条路径上的点(妙啊),然后优先选择a,从0正向往n-1再走一遍,记录走的选择,标记走的节点(st2),如果重复走过同一个节点,证明字典序最小的字符串无限长。
code:
#include<iostream>
#include<queue>
#include<cstring>
#include<string>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N];
int n; string s="";
int e[N], ne[N], idx,h[N];
bool st1[N], st2[N];
void add(int a,int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
void bfs()
{
queue<int>q;
q.push(n - 1);
st1[n - 1] = true;
while (q.size()) {
int t = q.front();
q.pop();
for (int i = h[t]; i != -1; i = ne[i])
{
if (!st1[e[i]])
{
q.push(e[i]);
st1[e[i]] = true;
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
memset(h, -1, sizeof h);
for (int i = 0; i < n; i++)
{
cin >> a[i];
if (i + a[i] >= 0 && i + a[i] < n)
{
add(i + a[i], i);
}
}
for (int i = 0; i < n; i++)
{
cin >> b[i];
if (i + b[i] >= 0 && i + b[i] < n)
{
add(i + b[i], i);//建立有向图,因为如果建立无向图,非路径上的点也会被st1标记
}
}
bfs();
if (st1[0] == false)cout << "No solution!";//没能走到0
else {
bool IN = false;
int x = 0;//从0开始走
// st2[0] = true;
while (x != n - 1)
{
int nx = x + a[x];//优先选择a
if (nx >= 0 && nx < n && st1[nx])//这个走法符合条件
{
if (!st2[nx])//没走过该点
{
s += "a";
st2[nx] = true;
x = nx;
}
else {
IN = true;//走过该点,则证明答案无限长
}
}
else {
nx = x + b[x];
if (nx >= 0 && nx < n && st1[nx])
{
if (!st2[nx]) {
s += "b";
st2[nx] = true;
x = nx;
}
else {
IN = true;
}
}
}
// cout<<s<<endl;
if (IN == true)break;
}
if (IN)cout << "Infinity!";
else cout << s;
}
return 0;
}