P9741 「KDOI-06-J」翻转与反转题解
crz_2025
·
·
题解
题目简述
给定一个只有 0 和 1 构成，长度为 n 的序列 a，对这个序列 a 进行 n 次操作，第 i 次操作把 1\sim i 的子序列翻转，再把翻转后的 1\sim i 每位数取反，求最终的序列 a。
思路
对于这种和题目，暴力肯定会 TLE，可以先打表找找规律，我用 !x 表示取反 x，如下：
结果：$!a_1$。
$n=2$，
结果：$!a_2,a_1$。
$n=3$，
结果：$!a_3,!a_1,a_2$。
$n=4$，
结果：$!a_4,!a_2,a_1,a_3$。
$n=5$，
结果：$!a_5,!a_3,!a_1,a_2,a_4$。
可以发现，如果 $n$ 为奇数，前 $\lceil \dfrac{n}{2} \rceil$ 个数都被取反，且下标从 $n$ 开始，逐次减 $2$ 到 $1$。后 $\lfloor \dfrac{n}{2} \rfloor$ 个数没有被取反，下标从 $2$ 开始，逐次加 $2$ 到 $n-1$。
如果 $n$ 为偶数，前 $\dfrac{n}{2}$ 个数都被取反，且下标从 $n$ 开始，逐次减 $2$ 到 $2$。后 $\dfrac{n}{2}$ 个数没有被取反，下标从 $1$ 开始，逐次加 $2$ 到 $n-1$。
我们现在可以先算出前 $\lceil \dfrac{n}{2} \rceil$ 个数，在算出后 $\lfloor \dfrac{n}{2} \rfloor$ 个数，时间复杂度为 $O(n)$，不会 TLE。
## Code
```
#include<bits/stdc++.h>
using namespace std;
int n,a[2000010];
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];//输入
if(n&1){//如果 n为奇数
for(int i=n;i>=1;i-=2){// 从 n开始，到 1
cout<<(a[i]^1)<<' ';// 异或 1等于取反
}
for(int i=2;i<n;i+=2){// 从 2开始，到 n-1
cout<<a[i]<<' ';
}
}else{//否则为偶数
for(int i=n;i>=2;i-=2){// 从 n开始，到 2
cout<<(a[i]^1)<<' ';
}
for(int i=1;i<n;i+=2){// 从 1开始，到 n-1
cout<<a[i]<<' ';
}
}
return 0;
}
```