题目链接：https://ac.nowcoder.com/acm/contest/7225/A
题目描述
牛牛拿到了一个长度为N的排列和M个区间，一开始排列是1、2、3…N。
然后他将这些区间在按顺序在排列上翻转，全部翻转一遍称一次操作。
现在他要去搞文化课了…所以拜托你告诉他经过K次操作后的排列长什么样子。
输入描述:
第一行三个整数：N，M，K。
接下来M行，每行两个整数L和R描述一个区间。
输出描述:
输出一行N个数，表示经过K次操作后的排列。
基本思路
一开始，我认为对于任何的操作，只要操作两遍就等于没有操作，也就是说所有偶数次的操作都可以被忽略，然而……
事实证明，我这个方法是不对的，这题也不可能这么简单（实际上我到现在没有找到反例）
那么换种思路
记录变化量
一开始我想到的是，可以先翻转一次，记录这个数组的变化，也就是哪些位置发生了交换。
之后，就可以直接使用这个变化量来循环操作K次了，时间复杂度为O(NK)
但是按照这个数据规模，这个时间复杂度一定没有办法AC，怎么办呢？
倍增思想
众所周知，倍增是一个特别快的算法，时间复杂度可以降低到对数级，著名的快速幂算法和ST表使用的就是倍增思想。
稍加思考，很容易发现，求出2此操作后的变化量，可以把操作一次之后的结果在按照这个变化量变化，这样就可以得到操作2次的变化量。
然后，我们就可以利用操作2次之后的结果 来得出操作两次后 数组的变化量，进而得出操作4次之后的结果。
如此往复，可以通过递推的方式得到2^n次操作之后的变化量。
又因为任何一个数都可以拆分成2^a[i]的和（其中a[i]为自然数）。
比如5次操作可以通过先进行1此操作，再进行4次操作实现，这和快速幂算法是非常接近的。
于是，我们可以使用记录变化量和倍增的方式达到O(N log K)的时间复杂度。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| #include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
const int Max=100005;
int main(){
int n, m, k, pre[Max], tmp, l, r;
scanf("%d %d %d", &n, &m, &k);
for(int i=1; i<=n; i++) pre[i]=i;
for(int i=0; i<m; i++){
scanf("%d %d", &l, &r);
for(int j=l; j<=((l+r)>>1); j++){
tmp=pre[j];
pre[j]=pre[r-(j-l)];
pre[r-(j-l)]=tmp;
}
}
int now[Max], ans[Max], ansbak[Max];
for(int i=1; i<=n; i++) now[i]=pre[i];
for(int i=1; i<=n; i++) ans[i]=i;
while(k){
if(k&1){
for(int i=1; i<=n; i++){
ansbak[i]=ans[i];
}
for(int i=1; i<=n; i++){
ans[i]=ansbak[now[i]];
}
}
for(int i=1; i<=n; i++){
now[i]=pre[pre[i]];
}
for(int i=1; i<=n; i++) pre[i]=now[i];
k>>=1;
}
for(int i=1; i<=n; i++) printf("%d ", ans[i]);
return 0;
}
|