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

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

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

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

参与运算的两个值，如果两个相应bit位相同，则结果为0，否则为1。 即： 　　0^0 = 0， 　　1^0 = 1， 　　0^1 = 1， 　　1^1 = 0 按位异或的3个特点: (1) 00=0,01=1 0异或任何数＝任何数 (2) 10=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;
}

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/135802.html原文链接：https://javaforall.cn