题解 P6148 【[USACO20FEB]Swapity Swapity Swap S】
kradcigam
2020-03-05 10:03:28
# 前言
考场上没想到用倍增，呜呜呜~，只写了个找循环节，然后就 $30$ 分。
# 正文
## 分析
考虑用倍增，其实这道题和[这道题](https://www.luogu.com.cn/problem/P3083)是有异曲同工之处的。
我们 $f_{ij}$ 记录第 $j$ 个元素，经过 $2^i$ 次翻转后，这个元素的值。
### 求 $f_{0,j}$
好，那么显然，我们要先求出 $f_{0,j}$。
```cpp
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$ 的应该都会。
```cpp
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$。
```cpp
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(n \log k)$ 是一个不错的复杂度。
## 总代码
```cpp
#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 帮我调了这道题的代码，帮我调出了一个小错误。
如果题解有误，欢迎在下面评论或私信我，使得这篇题解更好。