P9741 「KDOI-06-J」翻转与反转 题解

· · 题解

数学题。

可以发现，反转偶数次相当于没有反转，而 a_i 反转的次数为 n-i+1，所以我们不用模拟反转过程，一步到位即可。

再来说说翻转。手推柿子可以发现位置 1 变化的规律：

i= 位置 1 当前位置
1 1
2 2
3 2
4 3
5 3
6 4
7 4
8 5

好像并看不出什么，那再来看看 2,3 的变化规律：

（把 1 的也放在旁边做个对比看我多善良）

i= 位置 1 当前位置 位置 2 当前位置 位置 3 当前位置
1 1 2 3
2 2 1 3
3 2 3 1
4 3 2 4
5 3 4 2
6 4 3 5
7 4 5 3
8 5 4 6

（恍然大雾状）

可以发现：位置 j 在 i<j 时位置是不变的。

虽然好像题目已经告诉我们是这样的。

还可以发现，设位置 j 在参与了 i 回反转的回合数为 x：当 x\bmod 2=1 时，位置 j 的位置是 \frac{x}{2}+1 ；当 x\bmod 2=0 时，位置 j 的位置是位置 j 反转 i-1 次后的位置加上 j，也就是 \frac{x}{2}+j 。

而在此基础上，还可以从表里发现：x=i-j+1。

而题目告诉了我们要反转 n 次，所以 i=n。

综上，我们可以得出如下结论：要判断位置 i 最终的位置，若 (n-i+1)\bmod 2=1，那么最终位置就是 \frac{n-i+1}{2}+1，否则就是 \frac{n-i+1}{2}+i。

最后可别只翻转忘了反转。

代码：

#include<bits/stdc++.h>
using namespace std;
int a[2000005];
int main(){int n;cin>>n;
    for(int i=1,x;i<=n;i++)cin>>x,a[(n-i+1)/2+((n-i+1)%2?1:i)/*翻转*/]=((n-i+1)%2?!x:x)/*反转*/;
    for(int i=1,x;i<=n;i++)cout<<a[i]<<' ';//一行输入一行输出搞定/jy
    return 0;
}