提交链接

题目描述
在一条无限长的路上，有一排无限长的路灯，编号为 1,2,3,4,…。
每一盏灯只有两种可能的状态，开或者关。如果按一下某一盏灯的开关，那么这盏灯的状态将发生改变。如果原来是开，将变成关。如果原来是关，将变成开。
在刚开始的时候，所有的灯都是关的。小明每次可以进行如下的操作：
指定两个数，a,t（a 为实数，t 为正整数）。将编号为 ⌊a⌋,⌊2×a⌋,⌊3×a⌋,…,⌊t×a⌋ 的灯的开关各按一次。其中 ⌊k⌋ 表示实数 k 的整数部分。
在小明进行了 n 次操作后，小明突然发现，这个时候只有一盏灯是开的，小明很想知道这盏灯的编号，可是这盏灯离小明太远了，小明看不清编号是多少。幸好，小明还记得之前的 n 次操作。于是小明找到了你，你能帮他计算出这盏开着的灯的编号吗？

这道题，采用模拟算法，模拟开关灯的操作过程，然后从第一个编号开始向后找第一个开着的等即可。但是数组要开的足够大，不然容易出现RE错误！！

#include <bits/stdc++.h>
using namespace std;
#define N 1000000
bool x[N];  //false关闭，true开

int main()
{
	int n, t;
	double a;

	cin >> n;
	while (n--)
	{
		cin >> a >> t;

		for (int i = 1; i <= t; i++)
		{
			int da = (int)(a * i);
			x[da] = !x[da];
		}
	}

	int p = 1;
	while (x[p] == false)
		p++;
	cout << p << endl;

	return 0;
}

其他思路：由于最终只有一盏灯是开的，这意味着这盏灯被按了奇数次，而其他所有灯都被按了偶数次。这里可以利用异或运算的特性：
(1)任何数与 0 异或结果是它本身。
(2)任何数与自身异或结果是 0。
因此，我们可以将每次操作涉及的灯的编号进行异或运算，最终得到的结果就是唯一开着的灯的编号。

#include <bits/stdc++.h>
using namespace std;
long long n, t, ans, x;
double a;

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a >> t;
		for (int i = 1; i <= t; i++)
		{
			x = (int)floor(a * i); //a*i为当前灯的编号
			ans ^= x;
		}
	}
	cout << ans;
	return 0;
}

关键理解：通过不断的异或操作被按偶数次的灯编号在ans中相互抵消为0，被按奇数次的灯编号保留在ans中。假设操作序列是：操作灯1、2、3、2、1。
初始：ans = 0
操作1：ans = 0 ^ 1 = 1
操作2：ans = 1 ^ 2 = 3
操作3：ans = 3 ^ 3 = 0
操作4：ans = 0 ^ 2 = 2
操作5：ans = 2 ^ 1 = 3