当前位置：首页 > news >正文

USACO历年白银组真题解析 | 2013年3月Luxury River Cruise

news 2026/5/12 4:20:18

欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
希望系统学习C++/Python编程的初学者
想要提升算法与编程能力的编程爱好者

附上汇总贴：USACO历年白银组真题解析 | 汇总-CSDN博客

【题目来源】

洛谷：[P3083 USACO13OPEN] Luxury River Cruise S - 洛谷

【题目描述】

农民约翰正带着贝西和其他奶牛们进行一次巡航！他们航行在一个有N NN个港口（1 ≤ N ≤ 10 3 1 \le N\le10^31≤N≤103）的河网中，港口编号为1 , 2 , 3 … N 1,2,3\dots N1,2,3…N，贝西从港口1 11出发。每个港口恰好有两条流出的河道，直接通向其他港口，并且这些河道只能单向航行。

在每个港口，导游会选择走左边的河道或右边的河道继续向下游航行，但他们会一遍又一遍地重复相同的选择顺序。更具体地说，导游事先选定了一个长度为M MM的方向序列（1 ≤ M ≤ 500 1\le M\le5001≤M≤500），每个方向要么是左，要么是右，然后将这个序列重复K KK次（1 ≤ k ≤ 10 9 1\le k\le10^91≤k≤109），请帮她计算出她最终会停在哪个港口。

【输入】

第1 11行：三个用空格隔开的整数N , M , K N,M,KN,M,K。

第2 22行到第N + 1 N+1N+1行中，第i + 1 i+1i+1行包含两个用空格隔开的整数，分别表示港口i ii的左边河道和右边河道通向的港口编号。

第N + 2 N+2N+2行：M 个用空格隔开的字符，每个字符是 L 或 R。L 表示选择左边的河道，R 表示选择右边的河道。

【输出】

输出一个整数，表示贝西的巡航最终停靠的港口编号。

【输入样例】

4 3 3 2 4 3 1 4 2 1 3 L L R

【输出样例】

【算法标签】

《洛谷 P3083 Luxury River Cruise》 #模拟# #倍增# #USACO# #2013#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=1005;intn,m,k;// n: 位置数, m: 操作序列长度, k: 操作轮数inta[N][2];// a[i][0/1]表示在位置i，选择左/右后到达的位置boolflag[N];// flag[i]表示第i个操作是L(0)还是R(1)intf[N][30];// f[i][j]表示从位置i开始，执行2^j轮操作后到达的位置intmain(){// 输入cin>>n>>m>>k;// 读入位置转移表for(inti=1;i<=n;i++)cin>>a[i][0]>>a[i][1];// a[i][0]是左选择，a[i][1]是右选择// 读入操作序列for(inti=1;i<=m;i++){charopt;cin>>opt;if(opt=='R')// 右操作flag[i]=1;// 标记为1elseflag[i]=0;// 标记为0（左操作）}// 预处理：计算每个位置执行一轮(m个操作)后到达的位置for(inti=1;i<=n;i++){intpos=i;// 从位置i开始for(intj=1;j<=m;j++)// 执行一轮m个操作{// 根据操作类型选择左或右pos=a[pos][flag[j]];}f[i][0]=pos;// 记录执行一轮后的位置}// 倍增预处理：计算执行2^j轮后的位置for(intj=1;j<30;j++)// 2^30 > 1e9，足够大{for(inti=1;i<=n;i++){// 执行2^j轮 = 先执行2^(j-1)轮，再执行2^(j-1)轮f[i][j]=f[f[i][j-1]][j-1];}}// 模拟执行k轮操作intpos=1;// 起始位置是1for(inti=29;i>=0;i--)// 从高位到低位处理k的二进制{if(k&(1<<i))// 如果k的第i位是1{// 从当前位置执行2^i轮pos=f[pos][i];}}cout<<pos<<endl;// 输出最终位置return0;}