【深基5.习5】开灯

解题思路

同一盏灯每按两次会恢复关闭，因此只需知道每个编号出现次数的奇偶。把所有被按编号异或起来，偶数次相互抵消，结果就是唯一开灯编号。a 固定六位小数，可转为放大一百万的整数精确计算向下取整。

正确性说明

异或满足 x^x=0，所有偶数次编号抵消。最终仅一盏开灯，其编号出现奇数次，故保留为异或结果。固定精度整数计算 floor(k*a) 与数学定义一致。

易错点

不要直接截断浮点乘积导致整数边界误差；用 long long 计算放大后的乘积。

复杂度

总操作次数 T，时间 O(T)，空间 O(1)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    long long ans = 0;
    while (n--) {
        string s;
        int t;
        cin >> s >> t;
        size_t p = s.find('.');
        string whole = p == string::npos ? s : s.substr(0, p),
               frac = p == string::npos ? "" : s.substr(p + 1);
        while (frac.size() < 6)
            frac += '0';
        long long a = stoll(whole) * 1000000 + stoll(frac);
        for (int k = 1; k <= t; k++)
            ans ^= a * k / 1000000;
    }
    cout << ans << "\n";
    return 0;
}