题目描述
农夫约翰正带领着他的奶牛们去旅行。他们漂流在一个有N个港口的河流网络中,每个港口的标号分别是从1到N。开始的时候,他们在第一个港口,每个港口有且仅有两条可以开到其他港口的河流,并且河流的方向是单向的,船只能沿着河流的方向开。
在每一个港口,约翰可以选择向左边的河流或者向右边的河流开,约翰制定了一个长度为M的方向序列,序列中的字母或者是’L’或者是‘R’,‘L’表示向开向左边的港口,‘R’表示开向右边的港口。令人感觉奇怪的是,约翰执行这个长度为M的方向序列执行了K次。
问题描述:
请帮助约翰计算在执行了K次这种长度为M的序列之后,他最后在哪个港口。
输入
第一行三个整数,N,M和K。
接下来第2行到第N+1行,每行两个正整数,第i+1的两个整数表示第i个港口左边和右边的河流所去的其他港口的序号。
接下来一行,表示长度为M的方向序列,每个字母之间用空格隔开,字母只可能是‘L’或者‘R’。
输出
输出最后所在的港口的序号。
样例输入
4 3 3
2 4
3 1
4 2
1 3
L L R
样例输出
4
提示
数据范围:
1<=N<=1000,1<=M<=500,1<=K<=1000000000。
样例说明:
样例中,第一次序列执行完是在港口2(1-2-3-2),第二次序列执行完是在港口3(2-3-4-3),第三次序列执行完是在港口4(3-4-1-4)。所以最后的位置是在港口4。
说明:
注意这是一个有向图。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,k,j,x,i,net[900010],f[900010];
char ch[900010];
struct no{
int l,r;
}a[900010];
main(){
cin>>n>>m>>k;
for(i=1;i<=n;i++)
cin>>a[i].l>>a[i].r;
for(i=1;i<=m;i++)cin>>ch[i];
for(i=1;i<=n;i++){
x=i;
for(j=1;j<=m;j++)
if(ch[j]=='L')x=a[x].l;
else x=a[x].r;
net[i]=x;
}
for(i=2;i<=n;i++)f[i]=-1;x=1;f[1]=0;
for(i=1;i<=n+1;i++){
x=net[x];
if(f[x]<0)f[x]=i;
else{k=k-f[x];i=i-f[x];break;}
}
k=k%i;
for(i=1;i<=k;i++)x=net[x];
cout<<x;
}
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,k,j,x,i,net[900010],f[900010];
char ch[900010];
struct no{
int l,r;
}a[900010];
main(){
cin>>n>>m>>k;
for(i=1;i<=n;i++)
cin>>a[i].l>>a[i].r;
for(i=1;i<=m;i++)cin>>ch[i];
for(i=1;i<=n;i++){
x=i;
for(j=1;j<=m;j++)
if(ch[j]=='L')x=a[x].l;
else x=a[x].r;
net[i]=x;
}
for(i=2;i<=n;i++)f[i]=-1;x=1;f[1]=0;
for(i=1;i<=n+1;i++){
x=net[x];
if(f[x]<0)f[x]=i;
else{k=k-f[x];i=i-f[x];break;}
}
k=k%i;
for(i=1;i<=k;i++)x=net[x];
cout<<x;
}