填问卷 解题报告

这是一道很简单的题目，前置知识：二进制、分类讨论。 约定：询问格式是 $1x2x3y$ 这样，其中数字代表题号，$x$ 表示选 $0$，$y$ 表示选 $1$，其中 $1x2x3y$ 的意义是 $1,2,3$ 三道题分别选 $0,0,1$。 ## 1 问 1 这个不说了，是个人都会做，直接暴力即可。 ## 1 问 k ($1<k<2$) 数据存在构造？你可以把每一题的答案异或上 $0,1$ 中随机的一个数，这样子就可以保证数据纯随机了。 我们可以先问 $1x2x$，如果答案为 $0$ 或 $2$，则直接询问下一组，不然询问 $1x$ 就可以得出，根据随机的理论，答案为偶数的概率是 $50\%$。 理论上是平均 $1$ 问 $1.5$。 ## 2 问 3 $1x2x$，$1x2y3x$，如果第一次结果为 $0$ 或 $2$ 可以直接得出第一题和第二题的答案，不然可以得出第一题和第二题答案不同。于是 $1x2y$ 的结果只有可能是 $0$ 或 $2$。 然后就可以推理出 $1x2y,3x$ 两者的结果了。 ## 打包操作 我们定义一种打包操作，假如我们 **已经知道** 某些数两两之间的关系，我们可以构造一个询问使得答案只有可能是 $0$ 或者该集合的元素个数，并且知道这个答案就可以轻松得出集合内的所有元素。 比如我们知道第一题和第二题答案不同，第二题和第三题答案相同，那么我们构造 $1x2y3y$，结果只有可能是 $0,3$，并且如果知道了结果，就能得出三道题的答案。 ## 4 问 7 $1x2x,3x4x$，考虑最坏情况，也就是两者结果均为 $1$，显然可以用2问3的思想，把 $1,2$ 打包成 $f$，$3,4$ 打包成 $g$，这时再询问 $fxgx5x6x$，如果 $5x6x$ 结果为 $1$，那么可以直接得出$1234$两两之间的关系，我们把 $f,g$ 打包成一个大包 $A$，显然 $A$ 只有可能是 $0,4$，$5,6$ 打成包 $h$，显然 $h$ 只有可能是 $0,2$，于是就用二进制的理论问一下最后一次就可以了。 如果不为 $1$，说明 $56$ 答案相同，我们再把 $5,6$ 打包成 $h$，这里就相当于是求出了 $fxgxhx$ 的值，是不是很眼熟？这是 $2$ 问 $3$ 中的第 $2$ 步，下一次我们再做一次第一步的操作即可，也就是 $fxgy7x$。 #### 启发：我们发现我们每次询问单独的两个的时候只关注其奇偶性，所以 4 问 7 显然是可以优化的。 ## 平均 1 问 2 第一次询问 $1x2x$，可以得出 $1,2$ 之间的关系。 第二次询问 $1x2y3x4x$，如果答案为 $1$ 或者 $3$，那么相当于我们已经知道了 $1,2$ 的答案，还知道了 $3,4$ 的关系，然后我们重复执行第二次的询问。如果结果为 $2$，那么我们可以知道 $3,4$ 的关系以及 $1234$ 四者的关系，构造一个询问使得答案只有可能是 $0,4$，询问下一组的时候只需要加上这个就行了。 #### 这两种方法实现的精细一点的话都可以获得90分。 ## 平均 1 问 k ( $2<k<4$，实测 $k\approx2.08$ ) 再次引入随机大法。 我们 1 问 2 时先问 $1x2x$，再问 $1x2y3x4x$，我们能不能调换一下呢？显然可以。 先问 $1x2y3x4x$，如果答案为 $0$ 或 $4$ 的话直接询问下一组，不然再执行刚才的步骤。 也就是说，我们先问 $1x2y3x4x$，如果不为 $0$ 或 $4$，再问 $1x2x$。 然后我们就可以根据 $1x2x$ 套路出 $1x2y$ 的奇偶性和 $3x4x$ 的奇偶性 如果一 $3x4x$ 为奇数，那么我们继续按照套路问下去。 如果两个均为偶数，那么我们把四个打包，然后下次询问加上。 打包之后，下一次询问我们一次问四个，并且加上这个包。 如果答案不为 $4$，那么我们可以得出这两次询问的结果。 如果答案为 $4$，我们可以再把再 $4$ 个的元素和这个包一起询问，以此类推。如果得出了原来那个包的值，就可以得出所有四个四个的值。 实测大约六万两千多，当然这个随机比较稳定，每次询问的次数波动不会很大，显然 $63000$ 是随便过的，$64000$ 是留给卡得不够细致的选手。 当然这一题的部分分还是很好拿的，随便 random_shuffle 一下就能拿六十多分，如果你用 2 问 3 和随机大法就可以拿到 $79$ 分的好成绩。 ### 题外话 本题的数据按照以下方式构造： 首先是一组全 $0$ 的数据和一组全 $1$ 的数据。 然后是两组 $01$ 交错的数据。 接下来是 $6$ 组随机数据。 欢迎各位大佬来碾标（如果询问次数低于 $62500$，就算是爆标，记得吱一声哦）。 然后如果你直接两个两个的问靠运气的话这题你的得分即为 $0$ 分，因为第四组数据的询问次数为 $2^{17}-1$。 本题也是某一道题目的加强版，原题是2问3，但是交互库是自适应的，然后我把它优化到了 $n$ 问 $2n-1$，但因为我不会打自适应的交互库（再加上减小难度），于是我就不打自适应交互库了，然后发现还可以用随机大法优化，于是就有本题了。 当然，Orz @qazswedx，直接爆标了。