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

Tangninghaha · 2025-01-09 22:39:40 · 题解

做的第一道通信题。

题面：JOI 官网上的 PDF

提交：AtCoder

题意

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

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

数组下标从 0 开始。

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，所以是足够的。

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