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

· · 题解

模拟可得 O(n) 的做法。

根据题意可知，共有 n 个元素，进行 n 次操作，每一次操作的范围是 [1],[1,2],[1,2,3],[1,2,3,4] .....，那么第 1 个元素操作 n 次，第 2 个元素操作 n-1 次，以此类推，第 i 个元素需要操作 n-i+1 次。

对于第 1 个变换，可以发现，第 i 位在进行它的第一次操作时向去前移动了 i-1 位，而它的第二次操作时向后移动 i 位，它的第三次操作时又向前移动 i-1 位，推理可知，操作两次共往后移动了 1 位，如果有剩余，那么就是再往前移动了 i-1 位。

对于第 2 个变换，现象就很明显了，操作奇数次时（例如 0 -> 1 -> 0 -> 1），这一位上会变换，反之，操作偶数次时，这一位上不会变换（例如 0 -> 1 -> 0）。

联合以上我们总结出的规律，可以写出 O(n) 的代码：

#include<bits/stdc++.h>
#define int long long //常开long long好习惯
using namespace std;
int n;
char s[2000010]; //s用来存储原序列
char ans[2000010]; //ans用来存储答案序列
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n;
    //对于1，每次往前0位往后1位 
    //对于2，每次往前1位往后2位 
    //对于n，每次往前n-1位往后n位，那么两次往后1位 
    //对于i，操作n-i+1次 
    //只需要判断操作次数的奇偶，以此类推 
    for(int i = 1; i<=n; i++){
        cin >> s[i];
    }
    int p; 
    for(int i = 1; i<=n; i++){
        int at = 0; //at代表移动后的位置
        p = n-i+1;//p代表第i位共计的操作次数
        if(p%2==0){ //如果操作次数是偶数
            at = p/2;//直接向后移动p/2位（两次操作前进一位）
            ans[i+at] = s[i];
        }else{
            p--; 
            at += p/2*i;//一共向后移动了p/2*i位（一次移动i位）
            at -= (p/2+1)*(i-1);//一共向后移动了(p/2+1)*(i-1)位（一次移动i-1位）
            if(s[i]=='0'){ //因为是奇数次操作，所以要改变原元素
                ans[i+at] = '1';
            }else{
                ans[i+at] = '0';
            }
        }

    }
    for(int i = 1; i<=n; i++){
        cout << ans[i] << " "; //输出答案即可
    }
    return 0;
}