题解：P12509 【模板】通信题

· · 题解

思路分析

为洛谷第一道通信题庆生！

因为只改一个位置，所以我们考虑将二者是 1 的所有 p 异或起来，如果一样就是零，不一样就是两边的值异或起来。

正确性嘛，因为只换一个数，所以必定不会有改多个位置来构造的情况，只有改的那个位置造成异或值更改恰为那个位置的下标。

代码如下：

#include<string>
int Alice(std::string S) {
    long long ret = 0;
    for (int i = 1;i <= S.size();++i)
        if (S[i - 1] ^ 48) ret ^= i;
    return ret;
}
int Bob(std::string T, int x) {
    long long ret = 0;
    for (int i = 1;i <= T.size();++i)
        if (T[i - 1] ^ 48) ret ^= i;
    return x ^ ret;
}