JOISC2017 E - 壊れた機器 (Broken Device)

做的第一道通信题。

题面：JOI 官网上的 PDF

提交：AtCoder

题意 ​

有一个长度为 $N$ 的空白数组，其中有 $K$ 个位置是坏的，分别是 $P_{0},P_{1},\cdots,P_{K-1}$。

现在 Anna 需要使用这个空白数组向 Bruno 发送一个数字 $X$，要求空白数组损坏的位置只能填 $0$，其它位置可以填 $0$ 或 $1$。而 Bruno 将会得到这个填好的数组（并不知道哪里是损坏的），需要还原出 Anna 想要发送的数字 $X$。

数组下标从 $0$ 开始。

$N=150,0\le X\le 10^{18},1\le K\le 40$

WTC 的 Hard Version：$N=120$。

需要实现两个函数：

• void Anna( int N, long long X, int K, int P[] )

  给定空白数组长度 $N$，需要发送的数字 $X$，坏位置的数量 $K$，坏位置下标 $P$。

  在这个函数中需要调用 $N$ 次 void Set( int pos, int bit ) 函数，将空白数组 $pos$ 位置赋值为 $bit$。

• long long Bruno( int N, int A[] )

  将会给出一个长度为 $N$ 的数组 $A$，需要返回 Anna 发送的数字 $X$。

做法 ​

注意到 Bruno 难以知道哪个位置是好的，哪个位置是坏的。

提示 ​

将 150 个位置两两分一组，分为 75 组。

解法 1 ​

有了提示后容易想到：如果一组中，有一个位置是坏的，将两个位置都设置为 $0$，这样，Bruno 就可以跳过这些位置。否则，这两个位置有 3 种不同的状态，可以对应三进制下的 0，1 和 2。这样，最坏情况下，每一组中恰好有一个位置是坏的，这样只有 35 组是可用的，然而 $3^{35}\approx 5\times 10^{16}$，表示范围不足。

一种想法是：将数组下标进行随机打乱，这样出现最坏情况的概率很小。

解法 2 ​

WTC 说观察了 maspy 的提交记录得到的做法。

给每一个位随机赋一个权值 $p_i$，用线性基找到一组 $\oplus_{i=1}^{N}x_ip_i$ 为 $X$，如果一位是坏的，那么这一位 $x_i$ 必须为 $0$。

WTC 说期望需要 $\log_{2} X+O(1)$ 个位置才能表示出所有可能的 $X$，此题中 $\log_{2}X=60$，所以是足够的。

随机化只要在两个函数中使用相同的随机种子，得到的结果就是相同的了。