自动搬运

查看原文

来自洛谷，原作者为

	irris Good Luck.

搬运于2025-08-24 22:53:02，当前版本为作者最后更新于2023-12-09 20:29:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

有人觉得 Hard Ver 比 Easy Ver 简单，哎。

设上一次询问的集合 $S$。我们使用 $\lang S \rang$ 表示 $S$ 内元素的乘积。同时，考虑维护 $S$ 的符号。

我们维护 $\lvert Q \rvert \in [0, \lvert\lang S \rang\rvert]$，这是一个看起来很自然的想法，因为我们就可以比较少的减小 $Q$ 对后续状态的影响。

根据 Easy Ver 的思路，施二分 $[l, r]$。考虑把当前区间集合分成两半 $A, B$。首先，令 $Q \gets Q + \lang S\rang\cdot\lang A\rang$。如果 $Q$ 改变了符号，那么此时一定有 $\lang S \rang \cdot \lang A \rang$ 的符号是确定的。令 $S \gets S \cup A$ 后继续找到相应的一部分二分即可。

否则，$Q$ 没有改变符号，这说明一定有 $\lang S\rang \cdot \lang A \rang$ 与原来的 $Q$ 同号，我们已经确定了负号存在于 $A$ 或 $B$ 中。因为这个时候 $\frac{\lang S\rang \cdot \lang A \rang}{\lvert Q\rvert}$ 其实也不是很大，那么我们由于仿照上例需要给 $Q$ 的符号改变方便后续维护，所以令 $S \gets S \cup A \cup B$，这样 $S$ 的符号就变化掉了，我们最多实行两次 $Q \gets Q + S$ 就可以把 $Q$ 的符号变掉，这样同样形成了易于维护的形式。

朴素实现是 $S_{\max} \leq n + \lceil \frac n2 \rceil + \lceil \frac n4 \rceil + \cdots \leq 2n + \mathcal O(\log_2 n)$ 的，但是注意到我们可以先行询问一次 $[1, \lceil\frac n2\rceil]$ 来找到负号的位置，所以就变成了 $\frac n2 + 2(\frac n2 + \mathcal O(\log_2 n)) = 1.5n + \mathcal O(\log_2 n)$，非常优秀。

实际上没有卡交互次数，反正都是期望 $2.5n$，就直接保证负号位置随机了。

Subtask 0 特判乘积为 $-1$ 后二分，Subtask 1 是古老做法被 srz 一拳爆了（想要看的可以私聊我），Subtask 2 是增加区分度用的。

std::vector<int> S;
inline char query(int l = 1, int r = 0) {
	std::cout << "? " << S.size() + (r - l + 1) << ' ';
	for (int i : S) std::cout << i << ' ';
	for (int i = l; i <= r; ++i) std::cout << i << ' ';
	std::cout << std::endl;
	char x; std::cin >> x; return x;
}
inline void pb(int l, int r) { for (int i = l; i <= r; ++i) S.push_back(i); }

inline char reverse(char ch) { return ch == '+' ? '-' : ch == '-' ? '+' : ch; }
inline char func(char ch1, char ch2) { return ch1 == '0' ? ch2 : ch1; }
void solve() {
	int N, K, Smax; std::cin >> N >> K >> Smax; S.clear();
	if (N == 1) {
		std::cout << "! 1" << std::endl;
		return;
	}
	pb(1, pos[N]); char lst = query(), Ssgn = lst;
	int l = 1, r = N; if (lst == '+') l = pos[N] + 1; else r = pos[N];
	while (l < r) {
		int mid = l + r >> 1; char now = query(l, mid);
		if (now != lst) {
			char Nsgn = func(reverse(lst), now);
			pb(l, mid);
			if (Ssgn == Nsgn) l = mid + 1; else r = mid, Ssgn = Nsgn;
		} else {
			char Asgn = lst == Ssgn ? '+' : '-', orig = now;
			pb(l, mid), pb(mid + 1, r), Ssgn = reverse(Ssgn);
			while ((now = query()) == orig);
			if (Asgn == '+') l = mid + 1; else r = mid;
		}
		lst = now;
	}
	std::cout << "! " << l << std::endl;
}

其中 $pos_i$ 是提前 $\mathcal O(n^2)$ 预处理出来的最优下标，可以保证通过 Subtask，不过反正我数据里 $n$ 是一定范围和一定概率随的，$p$ 是 shuffle 的，所以似乎并不很有必要。