P3083 [USACO13OPEN] Luxury River Cruise S
题目描述
农民约翰正带着贝西和其他奶牛们进行一次巡航！他们航行在一个有 \(N\) 个港口（\(1 \le N\le10^3\)）的河网中，港口编号为 \(1,2,3\dots N\)，贝西从港口 \(1\) 出发。每个港口恰好有两条流出的河道，直接通向其他港口，并且这些河道只能单向航行。
在每个港口，导游会选择走左边的河道或右边的河道继续向下游航行，但他们会一遍又一遍地重复相同的选择顺序。更具体地说，导游事先选定了一个长度为 \(M\) 的方向序列（\(1\le M\le500\)），每个方向要么是左，要么是右，然后将这个序列重复 \(K\) 次（\(1\le K\le10^9\)），请帮她计算出她最终会停在哪个港口。
输入格式
第 \(1\) 行：三个用空格隔开的整数 \(N,M,K\)。
第 \(2\) 行到第 \(N+1\) 行中，第 \(i+1\) 行包含两个用空格隔开的整数，分别表示港口 \(i\) 的左边河道和右边河道通向的港口编号。
第 \(N+2\) 行：\(M\) 个用空格隔开的字符，每个字符是 L 或 R。L 表示选择左边的河道，R 表示选择右边的河道。
输出格式
输出一个整数，表示贝西的巡航最终停靠的港口编号。
输入输出样例 #1
输入 #1
4 3 3
2 4
3 1
4 2
1 3
L L R 输出 #1
4 说明/提示
样例中在执行完第一遍方向序列后，贝西到达港口 \(2\)（路径：\(1 \to 2 \to 3 \to 2\)）；
第二遍结束后，她到达港口 \(3\)（路径：\(2 \to 3 \to 4 \to 3\)）；
最终结束时，她到达港口 \(4\)（路径：\(3 \to 4 \to 1 \to 4\)）。
感谢 @fkxr 提供翻译
思路概述
朴素解法就是暴力跑一遍。但是由于 \(k\) 的范围过大（\(1 \leq k \leq 10^9\)），所以考虑倍增解法。（其实还有一种解法是找环，但本蒟蒻没写）
设置 \(nxt[i][j]\) 数组，表示从 \(i\) 点出发，走过 \(2^j\) 次序列所到达的节点（注意预处理顺序）。因为所有数都能被二进制拆分，所以把 \(k\) 二进制分解，如果 \(k\) 右移 \(u\) 位后结尾是 \(1\) ，那么就把答案走到现在答案的后 \(2^u\) 个节点。
代码示例
#include <bits/stdc++.h>
#define N 1010
#define M 510
#define LOG 32
using namespace std;
int n,m,k;
int l[N],r[N];
char qs[M];
int nxt[N][LOG];
int main() {ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);cin>>n>>m>>k;for(int i=1;i<=n;i++) cin>>l[i]>>r[i];for(int i=1;i<=m;i++) cin>>qs[i];for(int i=1;i<=n;i++) {int now=i;for(int j=1;j<=m;j++) {if(qs[j]=='L') now=l[now];else now=r[now];}nxt[i][0]=now;}for(int j=1;j<=32;j++)for(int i=1;i<=n;i++)nxt[i][j]=nxt[nxt[i][j-1]][j-1];int ans=1;for(int i=0;k;i++) {if(k&1)ans=nxt[ans][i];k>>=1;}cout<<ans<<'\n';return 0;
}