[EGOI2021] Twin Cookies 题解

FFTotoro · 2023-05-18 17:24:49 · 题解

注意到本题饼干美味度的值域很大，为 [1,10^{16}]，考虑使用随机化算法。

注意到前面的 100 次我们可以订购 100 块美味度随机的饼干，然后最后一次订购的每一块饼干的美味度都是从前面的 100 块饼干中选出 3 块美味度之和，这样如果不考虑美味度的重复，一共会有 C^3_{100}=161700 种美味度，远大于一次需要订购的 n\left(n_{\max}=5\times 10^3\right)，所以美味度重复的影响可以忽略不计。

实现的时候每次订购的饼干的美味度可以用 std::map 判重。

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
main(){
  ios::sync_with_stdio(false);
  int n; cin>>n;
  vector<int> a(100),s;
  mt19937 g(7202303); // 随机数生成器
  uniform_int_distribution<int> u(1,2e15);
  map<int,bool> m,m2;
  for(int i=0;i<100;i++){
    cout<<"? ";
    for(int j=1;j<=n;j++){
      int x=u(g);
      while(m[x])x=u(g); // 美味度重复了就一直生成
      cout<<x<<' '; m[x]=true;
    }
    cout<<endl; cin>>a[i];
  }
  for(int i=0;i<98;i++)
    for(int j=i+1;j<99;j++)
      for(int k=j+1;k<100&&s.size()<n;k++)
        if(!m2[a[i]+a[j]+a[k]])
          s.emplace_back(a[i]+a[j]+a[k]),m2[a[i]+a[j]+a[k]]=true;
  cout<<"? ";
  for(int i:s)cout<<i<<' '; // 最后一次订购
  cout<<endl; int r; cin>>r;
  cout<<"! 1 3"<<endl<<r<<endl;
  for(int i=0;i<98;i++)
    for(int j=0;j<99;j++)
      for(int k=0;k<100;k++)
        if(r==a[i]+a[j]+a[k]) // 找到求和的 3 块饼干
          cout<<a[i]<<' '<<a[j]<<' '<<a[k]<<endl,exit(0);
}