按位异或解题技巧「建议收藏」

全栈程序员-站长 • 2022年6月4日下午4:36 • 未分类 • 阅读 38

大家好，又见面了，我是你们的朋友全栈君。

按位异或可以解决类似开灯问题一类的问题。
首先了解下什么是按位异或：
异或运算：

首先异或表示当两个数的二进制表示，进行异或运算时，当前位的两个二进制表示不同则为1相同则为0.该方法被广泛推广用来统计一个数的1的位数！

参与运算的两个值，如果两个相应bit位相同，则结果为0，否则为1。
即：
　　0^0 = 0，
　　1^0 = 1，
　　0^1 = 1，
　　1^1 = 0
按位异或的3个特点:
(1) 0^0=0,01=1 0异或任何数＝任何数
(2) 1^0=1,11=0 1异或任何数－任何数取反
(3) 任何数异或自己＝把自己置0
按位异或的几个常见用途:
(1) 使某些特定的位翻转
例如对数10100001的第2位和第3位翻转，则可以将该数与00000110进行按位异或运算。
　　　　　 10100001^00000110 = 10100111

(2) 实现两个值的交换，而不必使用临时变量。
例如交换两个整数a=10100001，b=00000110的值，可通过下列语句实现：
　　　　a = a^b；　　//a=10100111
　　　　b = b^a；　　//b=10100001
　　　　a = a^b；　　//a=00000110

了解之后，我们就可以利用他的特点来解题。
举个例子，开灯问题：
在一条无限长的路上，有一排无限长的路灯，编号为1,2,3,4,…1,2,3,4,…。

每一盏灯只有两种可能的状态，开或者关。如果按一下某一盏灯的开关，那么这盏灯的状态将发生改变。如果原来是开，将变成关。如果原来是关，将变成开。

在刚开始的时候，所有的灯都是关的。小明每次可以进行如下的操作：

指定两个数，a,ta,t（aa为实数，tt为正整数）。将编号为[a],[2 \times a],[3 \times a],…,[t \times a][a],[2×a],[3×a],…,[t×a]的灯的开关各按一次。其中[k][k]表示实数kk的整数部分。

在小明进行了nn次操作后，小明突然发现，这个时候只有一盏灯是开的，小明很想知道这盏灯的编号，可是这盏灯离小明太远了，小明看不清编号是多少。

幸好，小明还记得之前的nn次操作。于是小明找到了你，你能帮他计算出这盏开着的灯的编号吗？

输入输出格式
输入格式：
第一行一个正整数nn，表示nn次操作。

接下来有nn行，每行两个数，a_i,t_ia
i
,t
i
。其中a_ia
i
是实数，小数点后一定有66位，t_it
i
是正整数。

输出格式：
仅一个正整数，那盏开着的灯的编号。

输入输出样例
输入样例#1：复制
3
1.618034 13
2.618034 7
1.000000 21
输出样例#1：复制
20
说明
记T=t_1+t_2+t_3+…+t_nT=t
1
+t
2
+t
3
+…+t
n
。

对于30%30%的数据，满足T \le 1000T≤1000
对于80%80%的数据，满足T \le 200000T≤200000
对于100%100%的数据，满足T \le 2000000T≤2000000
对于100%100%的数据，满足n \le 5000,1 \le a_i<1000,1 \le t_i \le Tn≤5000,1≤a
i
<1000,1≤t
i
≤T
数据保证，在经过nn次操作后，有且只有一盏灯是开的，不必判错。

思路：
第一想法，我觉得是开数组暴力模拟，但是当你了解了按位异或之后，你就会…大吃一惊。
AC代码：

#include<bits/stdc++.h>
#include<iostream>
using namespace std;
int main()
{ 
   
	ios::sync_with_stdio(false);
	int n , t , i ,j;
	int res = 0;
	double a;
	cin >> n;
	for(i = 0 ; i < n ; i++)
	{ 
   
		cin >> a >> t;
		for(j = 1 ; j <= t ; j++)
		{ 
   
			res^=int(j*a);
		}
	}
	cout << res << endl;
	return 0;
}