题解：P5208 [WC2019] I 君的商店

· · 题解

如实记录做题过程。

【题意】

交互题。

有一个商店，有 n 个物品，每个物品的价格为 0/1，至少存在一个价格为 1 的物品。但是你并不知道哪些是 0 哪些是 1，不过你知道 cnt_1 的奇偶性。你的目的是通过询问求出每个物品的价格。

询问：一次询问输入两个集合 S,T 作为参数（同一个集合内的物品必须两两不同，即每种物品在每个集合类最多包含一个），返回 S 内物品的价格之和与 T 内物品的价格之和的大小关系，如果价格之和相等则随机返回结果。一次询问的花费为 |S|+|T|。

花费不超过 M 求出答案。

我们令代价之和的上界为 M，记答案数组为 \text{ans[]}：

【题解】

这是个 m\approx 5n 的限制。这么神秘？先不管它。

考虑怎么才能确定一个物品的价格。感觉这还是有点太困难了，考虑能不能二分找到 1，转化为判定性问题：能不能判定一个集合里是否存在 1？

咋感觉也没啥方向。考虑在确定什么信息之后是比较简单的。

如果确定了一个 0 和一个 1 是简单的吗？对于剩下的数依次和它们俩询问：

这么诡异。考虑怎么处理 >0,<1 这个情况，考虑检验它是不是 0。好像也有点诡异，这咋判定？？

回归原点。考虑这个询问，发现其实可以看作回答为 \le 和 \ge 。要利用 \le 和 \ge 推出具体值。

有一个基础的想法：x\le 0\Rightarrow x=0,x\ge 1\Rightarrow x=1。

如果 S,T 只局限在一个数里肯定是无法确定的。考虑拿哪些数拼起来询问可以得到信息。

考虑三个数 x,y,z，认为询问只限于它们三个内部，怎么推？询问只有 1+1,1+2 两种类型，一共 9 种，都拿出来考虑一下。

发现：x\le y,x+y\le z\Rightarrow x=0，否则 x=y=1,x+y=2>z。更广泛地说，只要 x+y\le z，那么 x,y 内必有一个 0。

进一步考虑，直接把 (x+y,z),(x+z,y),(y+z,x) 三组都问了，如果有 L\le R 的组就可以直接确定一个数。而如果全部都是 L\ge R，思考一下必然是 011/000 的情况。那这种情况怎么确定数呢？哎感觉分讨一下，假设一次操作可以确定一个数好了。

所以这样就可以用 4 次操作确定一个数！所以 4n 次操作就可以问得只剩最后两个未知数，记作 x,y，应该分类讨论能解决？怎么好像做完了？

不是，我草为什么我没用到奇偶性这个条件？？？而且为啥是 4n 级别的？？？

甲烷了，询问代价是 |S|+|T|。

但是想法很对，(x\ge y+z)+(y\ge z)\Rightarrow z=0，这样刚好是 5 次操作确定 y,z 其一！

但是 x\le y+z 能推出个啥？？还是考虑比如 y\le z。那么 x\le y+z,y\le z，所以 x\le z，如果 x=1 就好了。

发现只要有一个确定的 1，把这个 1 作为 x 就可以直接问完剩下的数，花费 5n 次。

那感觉对完了。但是发现我们没有留次数给找这个 1。

如果暴力找，显然可以花 2n 次找最大值。那么一共 7n 次操作，还剩 sub36 过不了。

考虑一下这个 sub3，这个相当于说一定形如 1\cdots10\cdots0/0\cdots01\cdots1。此时能做啥呢？考虑能不能二分这个分界点出来。因为开头结尾不相等，所以花费 2 就可以找到哪头是 1。

怎么二分这个分界点。想了一下，令边界的 1 为 z，二分 x，询问 (x+(x+1),z)，如果是 \le 说明分界点在 x 右侧，如果是 \ge 说明分界点在 x+1 左侧，以此二分可以用 3\log n 的代价找到这个分界点，注意最后会发现分界点在两个位置无法确定，根据奇偶性判定。

sub3 做完了，然后考虑 sub6。

看一眼次数限制，多了 100 点能量，能不能把 sub3 的方法拓展过来？难点在于 sub3 里是有单调性的，但是 sub6 里没有。

感觉还是没想清楚这个单调结构怎么和 5n 结合。是说利用这个单调结构找到 1，然后做 5n 吗？这二分已经 3\log len 了，就是说找到一个 len 长度的单调结构，要求 5(n-len)+3\log len+cost\le 5\cdot 10^6+100，cost 是 "找" 花费的代价。

那这样看来还是可以尝试用 5 次操作给单调结构加一个元素。

这个单调结构最后必须包含最大值，因为显然 0\cdots 01 只有最大值才是 1。所以想法就是维护一个单调结构，用 5 次操作在末尾加一个新的元素，直到把全局最大值也加进来。

设我们现在单调结构的末尾是 x。因为是五次操作依然考虑 x+y\ge z,x\le y 那一套。

随便拿两个还不在单调结构里的数 y,z，然后问一下 (x,y+z),(y,z)。发现如果 x\ge y+z，直接在这里确定 y,z 之一就可以了（原本它是放在最后的部分里由 5(n-len) 确定的），而如果 x\le y+z，就考虑能不能拓展这个单调结构。

发现此时 x\le \max(y,z)，哦哦哦那就对了。

所以花费 5 次操作，要么确定一个数，要么把单调结构拓展 1 长度。直到最后可能只剩一个未知数，找不到 y,z 了。那么记这个未知数为 w，把 w 和单调结构的 top 比一下，如果 w\le top 那么 top 是全局最大值肯定是 1；否则 w 是全局最大值，加到单调结构的末尾。

那么此时这个单调结构末尾是 1，不在单调结构里的都被确定了。所以二分一下这个单调结构即可。