题解：P12509 【模板】通信题

chenxi2009 · 2025-05-12 22:19:51 · 题解

思路

发现把 S 压成哈希值直接传导是不可行的，期望 2^{10} 次左右会产生哈希冲突，而 Bob 可以通过 T 得出的可能的 S 有 N+1 种，故不可行。期望得分 50 分左右。

所以，我们需要用 X 传递一些 S 的特征。容易想到传递 S_i=1 的 i 的和，和 T_i=1 的 i 的和作差可以得出哪一位并不相同，但是差值的存在值域为 [-N,N]，故不可行，但已经和正解很接近了。期望得分 75。

考虑把差值为负的情况压掉，我们传递 S_i=1 的 i 的异或和，对 T 同样求然后作异或就可以找出不同的那个坐标了。期望得分 100。

代码

#include<bits/stdc++.h>
using namespace std;
int Alice(string s){
  int sum = 0;
  for(int i = 0;i < s.size();i ++) sum ^= (i + 1) * (s[i] - '0');
  return sum;
}
int Bob(string t,int x){
  for(int i = 0;i < t.size();i ++) x ^= (i + 1) * (t[i] - '0');
  return x;
}