P12509

035966_L3 · 2025-05-12 22:22:04 · 题解

Update 2025/12/29：修复了第一行的一个 typo。

感谢 xyz123 对本题的加强建议，原版题目中只要求 X <2^{31}。

说句闲话：我设计这题的初衷是【模板】哈希 2，而不是【模板】通信题。

如果 A 程序可以向 B 程序传递一个不大于 2^{31}-1 的非负整数，那么这就是一个 Hash 模板题。弱化后的题目随便用什么 Hash 函数都能过，比如「所有 \texttt{1} 的位置编号之和 \text{mod } 12345678」。

然而，这道题目只允许 A 程序向 B 程序传递一个不大于 2^{20}-1 的非负整数，因此我们要优化 Hash 函数——把 Hash 函数改为「所有 \texttt{1} 的位置编号之异或和」就可以通过此题了。

（可以发现，对于不变动的 N-1 位，设所有 \texttt{1} 的位置编号之异或和为 Q，则第 P 位为 \texttt{0} 的字符串的最终 Hash 值为 Q，而另一个为 Q \text{ xor } P，二者的异或和恰好为 P。当 P=0 时，两个 Hash 值都是 Q，异或和恰好也为 P=0。）

#include <bits/stdc++.h>
using namespace std;
int Alice(string S)
{
    int X = 0;
    int n = S.size();
    S = ' ' + S;
    for (int i = 1; i <= n; i++)
        if (S[i] == '1') X ^= i;
    return X;
}
int Bob(string T, int X)
{
    int D = 0;
    int n = T.size();
    T = ' ' + T;
    for (int i = 1; i <= n; i++)
        if (T[i] == '1') X ^= i;
    return X;
}

那么这题数据是怎么造的？

1. 首先均匀随机一个 [0, 1] 范围内的实数 r 表示 \tt 1 出现的比例。
2. 按比例 r 逐位（不均匀）随机生成 S。
3. 根据测试点编号，均匀随机选定一个修改位置并生成 T：
   • 测试点 1, 2, 6, 7, 11, 12, 16, 17 保证 S_P = \tt 1。
   • 测试点 3, 4, 8, 9, 13, 14, 18, 19 保证 S_P = \tt 0。
   • 测试点 5, 10, 15, 20 保证 P = 0。

最后，欢迎大家来题目来源处打卡！