P9918 题解（2023 激励计划评分 10）

· · 题解

有人觉得 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 的，所以似乎并不很有必要。