最近在刷洛谷时遇到了 P1161 开灯 这道题，发现了一种非常巧妙的异或解法。本文从常规的数组模拟讲起，再到异或消去，并整理异或运算符的几条核心性质。

方法一：朴素算法 —— 数组模拟

思路

用一个巨大的 bool 数组记录每盏灯的状态，每经过一次就将对应位置取反（开灯 ↔ 关灯），最后遍历整个数组，找到唯一仍亮着的灯。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<vector>
using namespace std;
int main(){
	int n;
	double a,t;
	vector<bool> b(2000001,0);
	cin>>n;
	
	for(int i=0;i<n;i++){
		cin>>a>>t;
		for(int j=1;j<=t;j++){
			int tmp=a*j;
			b[tmp]=!b[tmp];
		}
	}
	
	for(int i=0;i<2000001;i++){
		if(b[i])cout<<i;
	}
	
	return 0;
}

这种算法简单粗暴，缺点是开了一个巨大的 bool 数组，内存占用较大。

方法二：异或消去

核心原理

异或反转操作的本质：奇数次保留，偶数次抵消。

异或运算符有如下特性：

1
2
1 ^ 1 ^ 2 ^ 2 ^ 3 = 3
a ^ b ^ b = a

因此不需要记录每盏灯的状态，只要把所有编号依次异或，出现偶数次的编号会自动抵消，最后剩下的就是答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
using namespace std;
int main(){
	int n,ans=0;
	double a,t;
	cin>>n;
	
	for(int i=0;i<n;i++){
		cin>>a>>t;
		for(int j=1;j<=t;j++){
			int tmp=a*j;
			ans ^= tmp;
		}
	}
	
	cout<<ans;
	
	return 0;
}

优点

  • 省去巨大的 bool 数组，内存占用极小；
  • 逻辑优雅，利用数学性质直接消去；
  • 时间复杂度与方法一相同，都是 O(Σt)。

深入理解异或运算符 ^

上面的例子只展示了异或的一个巧妙用法，想深入理解可以继续往下看。

异或运算符的性质

  1. 交换律：a ^ b = b ^ a
  2. 结合律：(a ^ b) ^ c = a ^ (b ^ c)
  3. 自反性：x ^ x = 0（同一个数异或自己直接清零）
  4. 单位元：x ^ 0 = x（异或 0，值不变）

常见经典应用

  • 找出只出现过一次的数字：数组中其他数字都出现两次，把所有数依次异或即可。
  • 不借助临时变量交换两个数：
1
2
3
a ^= b;
b ^= a;
a ^= b;

异或还有很多有趣的应用，暂时先不深入探究，以后遇到再补充。