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

做的第一道通信题。

题面:JOI 官网上的 PDF

提交:AtCoder

题意

有一个长度为 NN 的空白数组,其中有 KK 个位置是坏的,分别是 P0,P1,,PK1P_{0},P_{1},\cdots,P_{K-1}

现在 Anna 需要使用这个空白数组向 Bruno 发送一个数字 XX,要求空白数组损坏的位置只能填 00,其它位置可以填 0011。而 Bruno 将会得到这个填好的数组(并不知道哪里是损坏的),需要还原出 Anna 想要发送的数字 XX

数组下标从 00 开始。

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

WTC 的 Hard Version:N=120N=120

需要实现两个函数:

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

    给定空白数组长度 NN,需要发送的数字 XX,坏位置的数量 KK,坏位置下标 PP

    在这个函数中需要调用 NNvoid Set( int pos, int bit ) 函数,将空白数组 pospos 位置赋值为 bitbit

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

    将会给出一个长度为 NN 的数组 AA,需要返回 Anna 发送的数字 XX

做法

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

提示

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

解法 1

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

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

解法 2

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

给每一个位随机赋一个权值 pip_i,用线性基找到一组 i=1Nxipi\oplus_{i=1}^{N}x_ip_iXX,如果一位是坏的,那么这一位 xix_i 必须为 00

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

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

NOMURA2020 F - Sorting Game
高级数据结构常见套路