P9185 [USACO23OPEN] Rotate and Shift B 题解

KidA · 2023-08-05 19:52:33 · 题解

首先，我们很容易就能得出一个显而易见的结论：

若令原数组为 order，K 个活跃位置分别为 A_1,A_2,...,A_K，则

order_{A_1} \to order_{A_2},order_{A_2} \to order_{A_3},...,order_{A_K} \to order_{A_1}

的操作就等价于将 order 数组顺时针旋转 x 次，即

order_1 \to order_2,order_2 \to order_3,...,order_N \to order_1

再进行上述操作，最后逆时针旋转 x 次转回来。

因为顺时针和逆时针的旋转方向是相反的，都旋转 x 次正好抵消，所以上述结论的正确性也是显然的。

根据上述结论，题目所说的操作流程可以如下：

1. \ R

2. \ +1,R,-1

3. \ +2,R,-2

\cdot \cdot \cdot

T. \ +(T-1),R,-(T-1)

（其中 R 表示将 order 数组按 A 数组轮换的操作，+x 和 -x表示顺时针 / 逆时针旋转 x 次 order 数组的操作，x. 表示第 x 分钟进行的操作。）

这个过程中的顺时针和逆时针可以抵消，于是化简后的结果如下：

1. \ R,+1

2. \ R,+1

3. \ R,+1

\cdot \cdot \cdot

T. \ R,+1,-T

这样化简之后，每分钟的操作都变成了 R,+1，我们称这样的一次操作为 S。

于是整个题目的操作流程变成了每分钟进行一次 S 操作，最后逆时针旋转 T 次即可。

但是每次 S 操作的时间都是 O(N) 的，总时间复杂度还是 O(TN)，和暴力并无区别。

那么如何加快 S 操作？既然朴素地旋转、轮换是不行的，那么我们就考虑使用倍增加快 S 操作的速度。

具体而言：

建立倍增数组数组 jmp，其中 jmp_{i,j} 表示用 2^j 次 S 操作能够把 i 挪到的位置。
首先预处理 jmp 数组，令 jmp_{b_i,0}=i，并令 jmp_{i,j}=jmp_{jmp_{i,j-1},j-1}（即从 i 用 2^{j-1} 次 S 操作挪到的位置开始再进行 2^{j-1} 次 S 操作。
接着枚举 2 的 k 次幂，若 2^k \le T 则进行 2^k 次 S 操作。

最后别忘了逆时针再旋转 T 次就可以了。

#include<bits/stdc++.h>
#define int long long
using namespace std;

int n,k,t,tt; //tt是t的备份
int jmp[200031][64]; //倍增数组
int sor1[200031],sor2[200031],rot[200031],tmp[200031]; //order 数组，order 数组备份、A 数组、旋转辅助数组

void rotate1(){ //R 操作
    memset(tmp,-1,sizeof(tmp));
    for(int i=1;i<k;i++) tmp[rot[i]]=sor2[rot[i-1]];
    tmp[rot[0]]=sor2[rot[k-1]];
    for(int i=0;i<n;i++)
        if(tmp[i]+1) sor2[i]=tmp[i];
}
void rotate2(){ //顺时针旋转
    memset(tmp,0,sizeof(tmp));
    for(int i=0;i<n-1;i++) tmp[i]=sor2[i+1];
    tmp[n-1]=sor2[0];
    memcpy(sor2,tmp,sizeof(tmp));
}
void rotate3(){ //逆时针旋转
    memset(tmp,0,sizeof(tmp));
    for(int i=0;i<n;i++) tmp[i]=sor1[(i-tt%n+n)%n];
    memcpy(sor1,tmp,sizeof(tmp));
}

signed main(){
    cin>>n>>k>>t;
    for(int i=0;i<k;i++) cin>>rot[i];
    for(int i=0;i<n;i++) sor1[i]=sor2[i]=i;
    tt=t;

    rotate1(); //进行一次 R 操作 + 逆时针旋转一次，避免特判
    rotate2();

    for(int i=0;i<n;i++) jmp[sor2[i]][0]=i; //预处理 jmp 数组
    for(int j=1;j<=40;j++) //递推 jmp 数组
        for(int i=0;i<n;i++)
            jmp[i][j]=jmp[jmp[i][j-1]][j-1];
    for(int i=40;i>=0;i--){ //枚举 2^i
        if((1ll<<i)<=t){
            t-=(1ll<<i);
            for(int j=0;j<n;j++) tmp[jmp[j][i]]=sor1[j]; //进行 2^i 次 S 操作
            memcpy(sor1,tmp,sizeof(tmp));
        }
    }

    rotate3(); //逆时针旋转 T 次
    for(int i=0;i<n;i++) cout<<sor1[i]<<' ';
    return 0;
}