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

FFTotoro · 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;
}