大家好，又见面了，我是你们的朋友全栈君。
按位异或可以解决类似开灯问题一类的问题。
首先了解下什么是按位异或：
异或运算：
首先异或表示当两个数的二进制表示，进行异或运算时，当前位的两个二进制表示不同则为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.net/135802.html原文链接：https://javaforall.net
