题解：CF2168C Intercepting Butterflies

· · 题解

题意

A 要给 B 发一个数字，但是他不能直接发，他只能给一个 1 到 20 中数字构成的一个集合，而且路上也有干扰，到达目的地后可能会增加或减少一个元素，如何发送信息才能免于干扰影响？

分析

这很像现实中的信息传递啊，路上会有各种各样的干扰。所以思路也应该相同，可以借鉴其奇偶验证，但我们还需要做的是复原信号，而不是像实际中发送失败还能再发一次。

考虑集合构造，观察数据范围，发现 1 \le x \le 2^{15} 即可以对 x 进行减一操作后用前 15 个数字表示，也就是用某个元素的是否存在表示二进制上 x 的某一位，这 15 位称为信息位。那么后 5 位表示什么呢？

由于在数据错误时需要复原，我们可以花 4 位来表示数据的奇偶性分布来进行复原，称为复原位，具体原理如下：

每层对应区间表示该位记录其覆盖位的奇偶性，与实际接收到的信息位的奇偶性进行比对，就可以找到错误位。

我们这时发现一个问题，这才 19 位啊，而题目给的是 20 位，该不会题目给选手留余地吧？？

然后带着这个疑问敲完代码，跑样例，发现根本过不了。经观察，发现如果错误位是复原位，那么上面的系统就会炸掉。

所以我们就需要用到最后一位，校验位。 其统计信息位的总奇偶性。实际收到数据时，若校验位与收到信息位奇偶性相同，则说明校验位和信息位都没错误，直接输出即可。

若不同，则说明校验位和信息位必然有一个错误，我们要找到这个错误，想起 4 位的复原位，其最高能复原的位数为 16 位而非 15 位。

此时一切都通了，将校验位置于第 16 位，复原位置于 17 到 20 位，并将校验位和信息位并在一起复原。

由于错误只有一个，所以如果信息位或校验位错了，则复原位一定正确。

代码：

#include <bits/stdc++.h>
// #define int long long
using namespace std;
void sol1()
{
  int _;
  cin >> _;
  while (_ --)
  {
    int n;
    cin >> n;
    bool b[21];
    memset(b, 0, sizeof(b));
    n --;
    for (int i = 15; i >= 1; i --)
    {
      b[i] = n & 1;
      n >>= 1;
      b[16] ^= b[i];
    }
    for (int i = 1; i <= 4; i ++)
    {
      for (int j = 1; j <= 16; j ++)
        if ((j - 1) % (1 << i) + 1 <= (1 << i - 1))
          b[i + 16] ^= b[j];
    }
    int cnt = 0;
    for (int i = 1; i <= 20; i ++) cnt += b[i];
    cout << cnt << endl;
    for (int i = 1; i <= 20; i ++) if (b[i]) cout << i << " ";
    cout << endl;
  }
}
void sol2()
{
  int _;
  cin >> _;
  while (_ --)
  {
    int n;
    cin >> n;
    bool b[21], ccb[5];
    memset(b, 0, sizeof(b));
    memset(ccb, 0, sizeof(ccb));
    for (int i = 1; i <= n; i ++){
      int x;
      cin >> x;
      b[x] = 1;
    }
    int chk1 = 0, sum = 0;
    for (int i = 1; i <= 15; i ++) chk1 ^= b[i], sum = (sum << 1 | b[i]);
    // cout << chk1 << endl;
    if (chk1 == b[16])
    {
      // cout << "K\n";
      cout << sum + 1 << endl;
      continue;
    }
    for (int i = 1; i <= 4; i ++)
    {
      for (int j = 1; j <= 16; j ++)
        if ((j - 1) % (1 << i) + 1 <= (1 << i - 1))
          ccb[i] ^= b[j];
      // cout << (bool)ccb[i] << " ";
    }
    // cout << endl;
    int l = 1, r = 16;
    for (int i = 4; i >= 1; i --)
    {
      if (ccb[i] == b[i + 16])
        l = l + (1 << i - 1);
      else
        r = l + (1 << i - 1) - 1;
      // cout << l << "->" << r << endl;
    }
    b[l] = !b[l];
    // cout << l << endl;
    sum = 0;
    for (int i = 1; i <= 15; i ++) sum = (sum << 1 | b[i]);
    cout << sum + 1 << endl;
  }
}
signed main()
{
  // cin.tie(0)->sync_with_stdio(0);
  string s;
  cin >> s;
  if (s == "first")
    sol1();
  else
    sol2();
  return 0;
}