自动搬运

查看原文

来自洛谷，原作者为

	wjx38223 一！二！

搬运于2025-08-24 22:51:22，当前版本为作者最后更新于2023-10-14 18:31:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

模拟可得 $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;
}