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

· · 题解

题目

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

思路

我们先找个规律(因为直接打暴力就会TLE)：

n = 1 \color{red}!a_1 n = 2 !a_1,a_2 a_2,!a_1 \color{red}!a_2,a_1 n = 3 !a_1,a_2,a_3 a_2,!a_1,a_3 !a_2,a_1,a_3 a_3,a_1,!a_2 \color{red}!a_3,!a_1,a_2 n = 4 !a_1,a_2,a_3,a_4 a_2,!a_1,a_3,a_4 !a_2,a_1,a_3,a_4 a_3,a_1,!a_2,a_4 !a_3,!a_1,a_2,a_4 a_4,a_2,!a_1,!a_3 \color{red}!a_4,!a_2,a_1,a_3 n = 5 !a_1,a_2,a_3,a_4,a_5 a_2,!a_1,a_3,a_4,a_5 !a_2,a_1,a_3,a_4,a_5 a_3,a_1,!a_2,a_4,a_5 !a_3,!a_1,a_2,a_4,a_5 a_4,a_2,!a_1,!a_3a,_5 !a_4,!a_2,a_1,a_3,a_5 a_5,a_3,a_1,!a_2,!a_4 \color{red}!a_5,!a_3,!a_1,a_2,a_4

经过上面的举例，我们可以发现，

当 n 是奇数的时候，

for (int i = n; i >= 1; i -= 2) {
    a[i] = a[i] == 1 ? 0 : 1;
    cout << a[i] << " ";
}
for (int i = 2; i <= n; i += 2) {
    cout << a[i] << " ";
}

当 n 是偶数的时候，

for (int i = n; i >= 2; i -= 2) {
    a[i] = a[i] == 1 ? 0 : 1;
    cout << a[i] << " ";
}
for (int i = 1; i <= n; i += 2) {
    cout << a[i] << " ";
}

这时，时间复杂度是 O(n) ，根本不用担心 TLE 。

code

#include<bits/stdc++.h>
using namespace std;
const int _ = 2 * 1e6 + 5;
int n, a[_];
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    if (n % 2 == 1) {
        for (int i = n; i >= 1; i -= 2) {
            a[i] = a[i] == 1 ? 0 : 1;
            cout << a[i] << " ";
        }
        for (int i = 2; i <= n; i += 2) {
            cout << a[i] << " ";
        }
    } else {
        for (int i = n; i >= 2; i -= 2) {
            a[i] = a[i] == 1 ? 0 : 1;
            cout << a[i] << " ";
        }
        for (int i = 1; i <= n; i += 2) {
            cout << a[i] << " ";
        }
    }
}