自动搬运

查看原文

来自洛谷，原作者为

	FFTotoro 龙猫

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

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

以下是正文

前言

Div.2 Rank $13$ 获奖了，题目也好评。

解法

从 Subtask $3$ 出发，考虑构造 $\prod(a_i+1)$ 这种形式，因为它可以便利地在加入一个新数维护当前乘积的正负性，进而推出该数的正负性；加入一个新数时只需枚举遍历过的每一个子集，对该子集加入该数后形成的集合作询问并存储，可以过 Subtask $3$。如果把 $a_1+1$ 换成 $a_1$（即一开始不询问那个空集）那么就能把询问次数除以 $2$，可以过 Subtask $4$。

正解需要一个 trick：先前一个一个数的做法询问次数很多，考虑把一些数一起询问。具体地，使用二分，令 $m$ 为二分中点，每次将 $q_{[l,m)}$（这里 $m=\left\lceil\frac{l+r}{2}\right\rceil$）绑在一起进行询问。如果 $Q=0$，那么仿照上面 Subtask $4$ 对 $a_1$ 的处理方法把当前集合清空并仅加入 $[l,m)$，正负性直接询问；否则考虑这一段的乘积正负性只需将其询问的最终结果的符号 $\mathrm{sgn}(Q')$ 与上一次的结果的符号 $\mathrm{sgn}(Q)$ 比较，如果相同则这一段乘积为正，否则为负。

原来的集合可以用 std::vector 存储 std::pair 实现。

放代码：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
char ask(vector<pii> a){
  vector<int> v; char c;
  for(auto [l,r]:a)
    for(int j=l;j<=r;j++)
      v.emplace_back(j);
  cout<<"? "<<v.size()<<' ';
  for(int i:v)cout<<i<<' ';
  cout<<endl,cin>>c;
  return c;
} // 单次询问
int main(){
  ios::sync_with_stdio(false);
  int t; cin>>t;
  while(t--){
    int n,k; cin>>n>>k>>n;
    int l=1,r=n; bool f=true; char s='+';
    vector<vector<pii> > a;
    while(l<r){
      int m=l+r+1>>1; char c;
      if(f){
        s='+',a={{make_pair(l,m-1)}};
        c=ask(a[0]),f=false;
      } // Q=0 时
      else{
        vector<vector<pii> > b;
        for(auto i:a){
          vector<pii> v=i;
          v.emplace_back(l,m-1);
          b.emplace_back(v);
          c=ask(v);
        } // 遍历并询问
        a.insert(a.end(),b.begin(),b.end());
        // 将产生的新集合加入 a 中
      }
      if(c==s)l=m; // 贡献为正，负数在右
      else if(c==48)r=m-1,f=true;
      else s=c,r=m-1; // 贡献为非正数，负数在左
    }
    cout<<"! "<<l<<endl;
  }
  return 0;
}