P9185 [USACO23OPEN] Rotate and Shift B
题目描述
注意：本题的时间限制为 4 秒，是默认时间限制的 2 倍。
为了庆祝春天的到来，Farmer John 的NNN头奶牛发明了一种有趣的舞蹈，她们围成一个圆圈，并以一种可预测的方式重新排列自己。
具体来说，圆圈上有NNN个位置，编号从000到N−1N-1N−1，其中位置000紧接着位置N−1N-1N−1。每个位置上有一头奶牛。奶牛的编号也从000到N−1N-1N−1。初始时，奶牛iii位于位置iii。你会被告知一组KKK个“活跃”位置0=A1<A2<⋯<AK<N0 = A_1 < A_2 < \dots < A_K < N0=A1<A2<⋯<AK<N，这意味着这些位置上的奶牛是下一批要移动的。
在舞蹈的每一分钟，会发生两件事。首先，活跃位置上的奶牛会旋转：位置A1A_1A1的奶牛移动到位置A2A_2A2，位置A2A_2A2的奶牛移动到位置A3A_3A3，依此类推，位置AKA_KAK的奶牛移动到位置A1A_1A1。所有这些KKK次移动同时发生，因此在旋转完成后，所有活跃位置仍然恰好有一头奶牛。接下来，活跃位置本身会移动：A1A_1A1变为A1+1A_1 + 1A1+1，A2A_2A2变为A2+1A_2 + 1A2+1，依此类推（如果某个活跃位置Ai=N−1A_i = N-1Ai=N−1，则AiA_iAi会循环回到000）。
请计算舞蹈进行TTT分钟后奶牛的顺序。
输入格式
第一行包含三个整数NNN、KKK和TTT。
第二行包含KKK个整数，表示初始的活跃位置A1,A2,…,AKA_1, A_2, \dots, A_KA1,A2,…,AK。注意A1=0A_1 = 0A1=0，并且这些位置是按递增顺序给出的。
输出格式
输出TTT分钟后奶牛的顺序，从位置000的奶牛开始，用空格分隔。
输入输出样例 #1
输入 #1
5 3 4 0 2 3输出 #1
1 2 3 4 0说明/提示
对于上述样例，以下是前四个时间步的奶牛顺序和活跃位置AAA：
初始，T = 0：顺序 = [0 1 2 3 4]，A = [0 2 3] T = 1：顺序 = [3 1 0 2 4] T = 1：A = [1 3 4] T = 2：顺序 = [3 4 0 1 2] T = 2：A = [2 4 0] T = 3：顺序 = [2 4 3 1 0] T = 3：A = [3 0 1] T = 4：顺序 = [1 2 3 4 0]1≤K≤N≤2⋅1051 \leq K \leq N \leq 2 \cdot 10^51≤K≤N≤2⋅105，1≤T≤1091 \leq T \leq 10^91≤T≤109。
- 输入 2-7：N≤1000N \leq 1000N≤1000，T≤10000T \leq 10000T≤10000。
- 输入 8-13：没有额外限制。
C++实现
#include<bits/stdc++.h>usingnamespacestd;intn,k,t,a[200005][3],b[200005],c[200005];intmain(){cin>>n>>k>>t;for(inti=1;i<=k;i++)cin>>b[i];intx=b[2]-b[1],k1=2;for(inti=0;i<n;i++){if(i==b[k1]){if(k1==k)x=n-b[k1];else{k1++;x=b[k1]-b[k1-1];}}a[i][1]=x;}k1=1;for(inti=0;i<n;i++,x++){if(i==b[k1]){x=0;k1++;}a[i][2]=x;}for(inti=0;i<n;i++){inty;if(a[i][2]==0)y=i+int(ceil(t*1.0/a[i][1]))*a[i][1];elsey=i+int(ceil((t-a[i][2])*1.0/a[i][1]))*a[i][1];c[y%n]=i;}for(inti=0;i<n;i++)cout<<c[i]<<" ";return0;}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
