题解 P6148 【[USACO20FEB]Swapity Swapity Swap S】

· · 题解

前言

考场上没想到用倍增，呜呜呜~，只写了个找循环节，然后就 30 分。

正文

分析

考虑用倍增，其实这道题和这道题是有异曲同工之处的。

我们 f_{ij} 记录第 j 个元素，经过 2^i 次翻转后，这个元素的值。

求 f_{0,j}

好，那么显然，我们要先求出 f_{0,j}。

read(n);read(m);read(k);//读入
for(int i=1;i<=m;i++)read(a[i]),read(b[i]);//读入
for(int i=1;i<=n;i++)c[i]=i;//给c数组赋初值
for(int i=1;i<=m;i++)reverse(c+a[i],c+b[i]+1);//模拟
for(int i=1;i<=n;i++)f[0][i]=c[i];//经过1次翻转第i个元素的值为c[i]

写倍增

因为 2^i=2^{i-1}+2^{i-1}

所以，f_{i,j}=f_{i-1,f_{i-1,j}}

给第 j 个元素操作 2^{i-1} 次，再操作 2^{i-1} 次，就相当于直接操作 2^i 次。

学过 LCA 的应该都会。

for(int i=1;i<=30;i++)
    for(int j=1;j<=n;j++)
        f[i][j]=f[i-1][f[i-1][j]];//就是之前的公式

得到答案

我们知道，任何一个十进制整数都是可以转成二进制形式

这里的话，我们就拆分 k。这里的步骤也很像 LCA。

for(int i=1;i<=n;i++){
    int x=i,m=k;
    for(int j=30;j>=0;j--)
        if(m>=(1ll<<j)){
            m-=(1ll<<j);//拆
            x=f[j][x];//操作
        }
    writen(x);//输出
}

复杂度

时间复杂度 O(nm+n \log k)。这是一个不错的复杂度。

总代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>inline void read(T &FF){
    T RR=1;FF=0;char CH=getchar();
    for(;!isdigit(CH);CH=getchar())if(CH=='-')RR=-1;
    for(;isdigit(CH);CH=getchar())FF=(FF<<1)+(FF<<3)+(CH^48);
    FF*=RR;
}
template<typename T>inline void write(T x){
    if(x<0)putchar('-'),x*=-1;
    if(x>9)write(x/10);
    putchar(x%10+48);
}
template<typename T>inline void writen(T x){
    write(x);
    puts("");
}
const int MAXM=1e2+10,MAXN=1e5+10;
int n,m,k,a[MAXM],b[MAXM],c[MAXN],f[35][MAXN];
int main(){
    read(n);read(m);read(k);
    for(int i=1;i<=m;i++)read(a[i]),read(b[i]);
    for(int i=1;i<=n;i++)c[i]=i;
    for(int i=1;i<=m;i++)reverse(c+a[i],c+b[i]+1);
    for(int i=1;i<=n;i++)f[0][i]=c[i];
    for(int i=1;i<=30;i++)
        for(int j=1;j<=n;j++)
            f[i][j]=f[i-1][f[i-1][j]];
    for(int i=1;i<=n;i++){
        int x=i,m=k;
        for(int j=30;j>=0;j--)
            if(m>=(1ll<<j)){
                m-=(1ll<<j);
                x=f[j][x];
            }
        writen(x);
    }
    return 0;
}

后记

感谢 @LightningUZ 帮我调了这道题的代码，帮我调出了一个小错误。

如果题解有误，欢迎在下面评论或私信我，使得这篇题解更好。