自动搬运

查看原文

来自洛谷，原作者为

	0x3F Wir müssen wissen, wir werden wissen.

搬运于2025-08-24 22:29:54，当前版本为作者最后更新于2021-03-24 22:34:02，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

最开始时由于某些原因这题是第一题。

我做了半个小时才做出来，心想第一题都这么难，第二题肯定做不出来了。

结果只花了 $5$ 分钟就做出了 “第二题”。

进入正题：

先考虑 $1$ 操作。

以长度为 $2^3 = 8$ 的序列为例。

初始序列：

操作后：

再次操作：

观察它们的二进制有什么规律？

我们发现一次操作相当于将二进制首位移到末位，其他位向左移一格。

也就是说，将二进制的各位按顺时针连成一个环，并将该环逆时针旋转一格。

开一个变量记一下旋转的次数即可。

如果旋转了整整一圈，一定记得要归零！！！

再来看一下 $2$ 操作： | $1$ 操作 | 二进制 | $2$ 操作 | 二进制 | | :-----------: | :-----------: | :-----------: | :-----------: | | $0$ | $000$ | $1$ | $001$ | | $2$ | $010$ | $3$ | $011$ | | $4$ | $100$ | $5$ | $101$ | | $6$ | $110$ | $7$ | $111$ | | $1$ | $001$ | $0$ | $000$ | | $3$ | $011$ | $2$ | $010$ | | $5$ | $101$ | $4$ | $100$ | | $7$ | $111$ | $6$ | $110$ |

不就是 $\operatorname{xor}$ 一下 $1$ 吗？

另开一个变量记一下要 $\bold{xor}$ 的数即可。

用位运算，$\Theta(m)$，比大伙们的 $\Theta(nm)$ 快多了。

还有：

unsigned int

因为：

而 int 的表示范围为

你用 long long 没人拦着你

#include <bits/stdc++.h>
using namespace std;
int n, m, o;
unsigned x, y;

inline unsigned read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}

inline void write(unsigned x)
{
    if(x>9) write(x/10);
    putchar(x%10+48);
}

int cnt;
int main() {
	n = read();
	m = read();
	while (m--) {
		o = read();
		x = read();
		if (o == 1) {
			if (x) {
				y = y ^ (1<<cnt);
			}
			cnt++;
			if (cnt == n) cnt = 0;
		} else {
			if (cnt) write(((x>>(n-cnt))|((x&((1<<(n-cnt))-1))<<cnt))^y);
			else write(x^y);
			putchar(10);
		}
	}
	return 0;
}