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

USACO历年白银组真题解析 | 2026年1月

news 2026/3/31 10:15:37

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

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

适合人群：

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

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

P14977 Lineup Queries

【题目来源】

洛谷：[P14977 USACO26JAN1] Lineup Queries S - 洛谷

【题目描述】

有一队奶牛，初始时（即时刻t = 0 t = 0t=0）只有奶牛0 00在位置0 00（这里，一头奶牛在位置k kk表示它前面有k kk头奶牛）。在时刻t tt（t = 1 , 2 , 3 , … t=1,2,3,\dotst=1,2,3,…），位置0 00的奶牛移动到位置⌊ t / 2 ⌋ \lfloor t/2\rfloor⌊t/2⌋，位置1 … ⌊ t / 2 ⌋ 1\dots \lfloor t/2\rfloor1…⌊t/2⌋上的每头奶牛向前移动一个位置，并且奶牛t tt加入到队列的末尾（位置t tt）。

回答Q QQ（1 ≤ Q ≤ 10 5 1\le Q\le 10^51≤Q≤105）个独立的查询，每个查询属于以下两种类型之一：

在时刻t tt刚结束时，奶牛c cc在什么位置（0 ≤ c ≤ t ≤ 10 18 0\le c\le t\le 10^{18}0≤c≤t≤1018）？
在时刻t tt刚结束时，位置x xx上是哪头奶牛（0 ≤ x ≤ t ≤ 10 18 0\le x\le t\le 10^{18}0≤x≤t≤1018）？

【输入】

第一行包含Q QQ，表示查询的数量。

接下来的Q QQ行，每行包含三个整数，指定一个查询，格式为 “1 11c cct tt” 或 “2 22x xxt tt”。

【输出】

将每个查询的答案输出在单独一行。

【输入样例】

2 1 4 9 2 2 9

【输出样例】

2 4

【解题思路】

【算法标签】

《洛谷 P14977 Lineup Queries》 #模拟# #Ad-hoc# #USACO# #2026#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong// 将int定义为long long类型，避免大数溢出intq,type,a,t;// q: 查询次数，type: 操作类型，a: 初始值，t: 时间/目标值signedmain()// 使用signed main()替代int main()，因为int被重定义为long long{cin>>q;// 读入查询次数while(q--)// 处理每个查询{cin>>type>>a>>t;// 读入操作类型、初始值和时间参数if(type==1)// 类型1：正向模拟过程{intc=a;// 当前值intcur=c;// 当前状态变量intnow=c;// 当前时间// 模拟从时间now到时间t的过程while(now<t){if(cur==0)// 如果当前状态为0{now++;// 时间推进1单位cur=now/2;// 状态更新为当前时间的一半}else// 当前状态不为0{intlimit=(now+1)/2;// 计算当前时间的上限if(cur>limit)// 如果当前状态超过上限{// 计算目标状态和时间inttarget=2*cur-1;intjump=target-now;// 需要跳跃的时间// 如果跳跃会超过目标时间t，则调整跳跃量if(now+jump>t){jump=t-now;}now+=jump;// 时间跳跃}else// 当前状态未超过上限{intjump=cur;// 跳跃量为当前状态值// 如果跳跃会超过目标时间t，则调整跳跃量if(now+jump>t){jump=t-now;}cur-=jump;// 状态减少now+=jump;// 时间推进}}}cout<<cur<<endl;// 输出最终状态}else// 类型2：逆向推导过程{intx=a;// 目标状态intcur_t=t;// 当前时间intcur_x=x;// 当前状态// 逆向推导，从时间t向回推导while(cur_t>0){if(cur_x==cur_t)// 特殊情况：状态等于时间{cur_x=cur_t;break;}// 如果当前时间不足以支持当前状态if(cur_t<2*cur_x){break;// 停止推导}if(cur_x==cur_t/2)// 特殊规则：状态等于时间的一半{cur_x=0;// 状态归0cur_t--;// 时间回退1单位}else// 一般情况{// 计算回退步数kintk=(cur_t-2*cur_x)/3;if(k==0)// 如果计算为0，则至少回退1步{k=1;}cur_x+=k;// 状态增加cur_t-=k;// 时间回退}}cout<<cur_x<<endl;// 输出推导得到的初始状态}}return0;}