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

tder · 2023-10-17 21:24:51 · 题解

\Large\color{black}\textbf{P9741 「KDOI-06-J」翻转与反转} \Large\textbf{题解}

\textbf{题目传送门}

\textbf{更好的阅读体验}

看了一眼题解好像没一个跟我一样的（

先考虑第 2 种按值翻转，a_i 会经历当 x\in[i,n] 时共 n-i+1 次按值翻转，所以如果经历奇数次翻转则等于经历 1 次翻转，即当 n-i+1\equiv1\pmod{2} 时令 a_i\leftarrow {(\sim a_i)}，其中 \sim 表示按值翻转。否则，经历偶数次翻转则等于不经历翻转。

再考虑第 1 种按下标翻转，简单模拟一下。下面除 a 表示翻转后的答案外，各数均表示下标：

发现规律，当 n 为奇数时，a=\{n,n-2,\dotsm,3,1,2,4,\dotsm,n-3,n-1\}，即先有 n\rightarrow1 中的所有奇数下标，后 2\rightarrow n-1 中的所有偶数下标。当 n 为偶数时，a=\{n,n-2,\dotsm,4,2,1,3,\dotsm,n-3,n-1\}，即先有 n\rightarrow2 中的所有偶数下标，后 1\rightarrow n-1 中的所有即数下标。

总复杂度 O(n) 实现。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e6 + 5;
int n, a[N], f[N];
signed main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n;
    for(int i = 1; i <= n; i++) cin>>a[i];
    for(int i = 1; i <= n; i++)
        if((n - i + 1) % 2) a[i] = !a[i]; // 按值翻转
    if(n % 2) { // n 为奇数
        for(int i = n; i >= 1; i -= 2) cout<<a[i]<<" ";
        for(int i = 2; i <= n - 1; i += 2) cout<<a[i]<<" ";
    } else { // n 为偶数
        for(int i = n; i >= 2; i -= 2) cout<<a[i]<<" ";
        for(int i = 1; i <= n - 1; i += 2) cout<<a[i]<<" ";
    }
    return 0;
}