意外

LYinMX · 2023-03-23 15:34:32 · 个人记录

开全局变量把每个数据存下来，这样的非通信方法被卡了内存。

考虑 Hack 交互库，您会发现交互库输出 Don't print anymore! 来警告。

因为值域非常大，所以在修改后可以直接视为和其他数不同。

而数学分析和实际测试有较大差距，所以解式子的精度显得没那么重要。

非常暴力的将每个数复制 len 次，有大概率它们的众数是原数。

正确概率为 (1-(1+len)(\frac{1}{2})^{len})^{100 \times 10^4}，当达到 0.999 时，len 为 29 左右，可以得到 25 左右的分。

考虑对上述做法优化，我们不一定每次只将一个数操作，如果我们将 k 个数压在一起传，具体的，求出 len 个点值，然后用其中 k 个数插值回去。

只要保留了大于等于 k 个原数，这一位就是对的，这样正确概率为 (1-(\frac{1}{2})^{len}\sum_{i=0}^{k}\binom{len}{i})^{100 \times 10^4}。

很遗憾 k 大于 2 就跑不动了，所以取 len 为 30，k 为 2，可以得到 50 左右的分。

如果我们知道那里的数是错的就可以更好的解码，绝对众数是很好的载体，考虑将一个数复制多次后，随机修改后，将绝对众数视为原数，不存在则直接丢弃，而用插值可以在一位储存多位的信息，所以最后只要保留下 100 个数就可以用拉格朗日插值解码。

当存储了 len 个点值，每位保留概率为 p 时，正确概率为 (\sum_{i=100}^{len}\binom{len}{i}p^{i}(1-p)^{len-i}))^{(10^4)}。

当 k=3 时存在绝对众数的概率为 \frac{1}{2}，实测当 len 为 283，k 为 3 时，可以得到 88 分，当 len 为 266，k 为 3 时，有一定概率可以得到 93 分。

上一个做法中 k=4 时存在绝对众数的概率为 \frac{11}{16}，虽然复制 4 次比复制 3 次长，但是在指数层面有所减小。

实测当 len 为 187，k 为 4 时，可以得到 100 分。

我好像只考虑了~~一发入魂~~的实现，赛时多次提交会得到较高的分数。