[GCJ 2020 #3] Pen Testing 题解

FFTotoro · 2025-07-06 17:08:11 · 题解

很牛的题目。学了官方题解的做法。

观察到如下的一种策略：先从左到右尝试将所有的笔都测试一遍，这样就能筛掉墨水量为 0 的笔，一旦筛出墨水量为 0 的笔就忽略剩下的笔进入下一个阶段；再从左到右尝试将所有的笔都不断测试，直到该笔被测试的总次数（即包含之前阶段的测试数）\ge 2，这样就能筛掉墨水量为 1 的笔，同理一旦筛出墨水量为 1 的笔就忽略剩下的笔进入下一个阶段……直到筛掉墨水量为 K 的笔（K 是你自己设定的一个常数），接着在没有被筛掉的笔中选择两支被测试次数最少的笔带走。

注意到 K 的数值可以根据交互库返回的信息更改以获得更高的正确率，于是考虑 DP 搜索出决策树。

设状态 f_{i,s}，其中 i(0\le i\le n-1) 表示当前已经筛掉了墨水量为 [0,i) 的笔，s 为一个长为 n-i 的非负整数序列，表示没有被筛掉的笔从左到右被测试次数分别为 s_1,s_2,\ldots,s_{n-i}。状态转移：

• 边界情况为 f_{n-1,*}=0，否则考虑如下转移；
• 设变量 \mathrm{pc} 表示考虑继续筛掉墨水量为 i 的笔的最大正确率，枚举该笔所在的位置 p，在它之前的笔被测试次数全部变为 i+1，在它后面的笔被测试次数不变，它本身对应的元素被删除，从而得出序列 s'=\{i+1,i+1,\ldots,i+1,s_{p+1},s_{p+2},\ldots,s_{n-i}\}，\mathrm{pc}\gets\mathrm{pc}+\dfrac{f_{i+1,s'}}{n-i}；
• 设变量 \mathrm{ps} 表示从当前的笔中直接挑选两个被测试次数最少的笔的正确率，令 w_0,w_1 为被测试次数最少的两支笔的被测试次数，显然有 \mathrm{ps}=\dfrac{\sum\limits_{x=i}^{n-2}\sum\limits_{y=x+1}^{n-1}[x+y-w_0-w_1\ge n]}{\dfrac{(n-i)(n-i-1)}{2}}；

我们发现这样的 DP 状态数并不多，于是直接按照上面的方法搜决策树。令 e=\{0,0,\ldots,0\}(|e|=n)，计算得到 f_{0,e}\approx 0.642，即总体正确率约为 64.2\%，可以轻松通过本题。

放代码：

#include<bits/stdc++.h>
using namespace std;
typedef double db;
int main(){
  ios::sync_with_stdio(false);
  int t,n,a; cin>>t>>n>>a;
  vector<map<vector<int>,db> > mp(n-1);
  vector<set<vector<int> > > st(n-1);
  // st 存储了决策“不继续下去，直接选出两支笔”的所有状态
  auto dfs=[&](auto &&self,int l,vector<int> v)->db{
    if(l>=n-1)return 0;
    if(mp[l].find(v)!=mp[l].end())return mp[l][v];
    db pc=0,ps=0;
    for(int t=0;t<v.size();t++){
      vector<int> w;
      for(int i=0;i<t;i++)
        w.emplace_back(l+1);
      for(int i=t+1;i<v.size();i++)
        w.emplace_back(v[i]);
      pc+=self(self,l+1,w);
    }
    pc/=v.size(); // 继续筛出 i 的最大正确率
    auto w=v;
    sort(w.begin(),w.end());
    int t=0;
    for(int x=l;x<n;x++)
      for(int y=x+1;y<n;y++)
        ps+=x+y-w[0]-w[1]>=n,t++;
    ps/=t; // 直接原地选的正确率
    if(pc>ps)mp[l][v]=pc;
    else mp[l][v]=ps,st[l].emplace(v);
    // 比较两者，得出较优的方案
    return mp[l][v];
  }; // 搜决策树
  dfs(dfs,0,vector<int>(n));
  vector<int> s(t),c(t);
  // s[i] 表示第 i 组测试数据正在进行“筛出 s[i]”的阶段
  // c[i] 表示第 i 组测试数据正在考虑剩下的第 c[i] 只笔
  vector p(t,vector<int>(n)),v=p;
  // p[i] 表示第 i 组测试数据剩下的笔在原序列中的编号（从左到右）
  // v[i] 表示第 i 组测试数据剩下的笔被测试次数（从左到右）
  for(auto &i:p)iota(i.begin(),i.end(),0);
  vector<bool> f(t);
  // f[i] 表示第 i 组测试数据的求解是否结束
  while(find(f.begin(),f.end(),false)!=f.end()){
    vector<int> a(t,-1),r(t);
    for(int q=0;q<t;q++)
      if(!f[q])a[q]=p[q][c[q]];
    for(int i:a)cout<<i+1<<' ';
    cout<<endl;
    for(auto &i:r)cin>>i;
    for(int q=0;q<t;q++){
      if(f[q])continue;
      if(r[q]){
        if(++v[q][c[q]]>s[q])c[q]++;
      } // 还在本阶段，考虑下一支笔
      else{
        p[q].erase(p[q].begin()+c[q]);
        v[q].erase(v[q].begin()+c[q]);
        s[q]++;
        if(st[s[q]].find(v[q])!=st[s[q]].end())f[q]=true;
        else c[q]=0;
      } // 进入下一个阶段或直接得出答案
    }
  }
  for(int q=0;q<t;q++)
    cout<<0<<' ';
  cout<<endl;
  for(int q=0;q<t;q++){
    int x=min_element(v[q].begin(),v[q].end())-v[q].begin();
    cout<<p[q][x]+1<<' ';
    p[q].erase(p[q].begin()+x),v[q].erase(v[q].begin()+x);
    x=min_element(v[q].begin(),v[q].end())-v[q].begin();
    cout<<p[q][x]+1<<' ';
    p[q].erase(p[q].begin()+x),v[q].erase(v[q].begin()+x);
  } // 选出被测试次数最少的两支笔回答
  cout<<endl;
  return 0;
}