「WC2019」I 君的商店 题解

问题重述

本题是交互题，我们需要确定 $N$ 个物品的价格（每个为 $0$ 或 $1$）。已知：

1. 价格 $1$ 的物品个数为奇数（$K=1$）或偶数（$K=0$）
2. 至少有一个价格为 $1$ 的物品

我们可以进行的操作是：比较两个物品集合的价格之和。但当两个集合价格之和相等时，回答是任意的（由交互库决定）。每次询问的代价是 $|S|+|T|$，总代价不能超过 $M$。

核心思路

1. 基本观察

• 物品价格为 $0$ 或 $1$，所以集合价格和就是其中价格为 $1$ 的物品数量
• 关键限制：价格和相等时的回答不确定，这排除了直接二分查找等方法

2. 子任务3的特殊性质

子任务3保证：如果 $\text{ans[i]} = \text{ans[k]}$，则对所有 $j \in (i,k)$，$\text{ans[j]} = \text{ans[i]}$。
这意味着 $0$ 和 $1$ 是分别连续出现的，因此物品价格形成了一个前缀0+后缀1或前缀1+后缀0的模式。这样，问题就转化为了寻找分界点。

3. 主算法框架

代码的核心是一个三分查找变种，用于在不确定比较结果的情况下找到价格的分界点。

步骤一：建立有序序列

首先通过一系列比较，构建一个部分有序的物品序列 a。关键技巧：

• 维护一个当前已知可能最大的物品 z（价格可能是1）
• 通过比较 {z} 和 {x,y}，判断 x 和 y 的相对大小
• 如果 {z} 比 {x,y} 大，说明 z 价格更高，将 y 加入有序序列
• 否则，说明 x 价格较低，标记为0

这部分代码有效地利用了比较操作的组合，在不确定回答的情况下逐步筛选。

步骤二：二分查找分界点

在构建的有序序列 a 上，通过比较 {z} 和 {a[mid], a[mid+1]} 来二分查找第一个价格为1的物品：

• 如果 {z} 更大，说明分界点在左侧
• 否则，分界点在右侧

步骤三：确定剩余物品价格

找到分界点后：

• 分界点左边的物品价格都是0
• 分界点右边的物品价格都是1（根据 $K$ 调整奇偶性）
• 需要特殊处理分界点处的两个物品

关键技巧

1. 处理不确定比较

通过组合比较来规避不确定回答：

• 单个比较：query({z}, {x}) 在 $z=x$ 时不确定
• 组合比较：query({z}, {x,y}) 提供了更多信息，即使在 $z=x+y$ 时也有确定结果

2. 构建部分有序结构

算法不要求完全排序所有物品，只需要构建一个单调不降的序列，其中价格从0变为1最多一次。

3. 代价控制

• 每次询问代价为集合大小之和
• 算法中主要使用大小为1或2的集合，控制单次询问代价
• 总询问次数 $O(n)$，总代价 $O(n)$

复杂度分析

• 询问次数：$O(n)$
• 总代价：$O(n)$，满足 $M$ 的限制
• 时间复杂度：$O(n)$

算法总结

本题是一个交互式搜索问题，核心挑战是比较结果的不确定性。解题的关键思想包括：

1. 利用已知结构：在子任务3中，利用0和1连续出现的性质，将问题转化为寻找分界点
2. 规避不确定回答：通过组合比较（比较单个物品与两个物品的和）来获得确定信息
3. 逐步缩小范围：构建部分有序序列，然后二分查找分界点
4. 奇偶性约束：利用 $K$ 提供的奇偶信息确定最后几个物品的价格

难点突破

1. 理解不确定比较的含义：认识到单个物品比较可能无意义，需要设计组合查询
2. 构建有效比较策略：设计 query({z}, {x,y}) 这样的查询来获取可靠信息
3. 处理边界情况：分界点附近物品的确定需要特殊处理
4. 控制查询代价：在 $O(n)$ 代价内解决问题

这道题体现了交互题的典型特点：需要设计巧妙的查询策略来提取信息，同时要考虑查询代价的限制。解题的关键是认识到即使比较结果不确定，通过精心设计的组合查询仍然可以提取出确定的信息。