P9529 [JOISC2022] 一流团子师傅

Alex_Wei · 2023-09-17 13:08:52 · 题解

P9529 [JOISC2022] 一流团子师傅

一个神秘的简单做法。

考虑怎么找到一组团子：设下标集合为 S。按任意顺序枚举 S 中的元素 s_1, s_2, \cdots, s_{|S|}。每次从 S 中删去 s_i，若询问 S 得到的结果为 M - 1，说明 s_i 可以加入当前团子串。否则将 s_i 重新插入 S。当团子串大小为 N 时退出，M 减小 1。

按随机顺序枚举时，感性理解一下，很快就能找到团子串，个人猜测期望次数是 N\log M。可以通过本题，极限数据询问次数在 4.3\times 10 ^ 4\sim 4.8\times 10 ^ 4 之间波动。

#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(0x1064822E);
int Query(const vector<int> &x);
void Answer(const vector<int> &a);
void Solve(int N, int M) {
  vector<int> rem;
  for(int i = 1; i <= N * M; i++) rem.push_back(i);
  for(int i = 1; i < M; i++) {
    shuffle(rem.begin(), rem.end(), rnd);
    vector<int> pack;
    pack.push_back(rem.front());
    rem.erase(rem.begin());
    while(pack.size() < N) {
      int v = rem.front();
      rem.erase(rem.begin());
      if(Query(rem) == M - i) pack.push_back(v);
      else rem.push_back(v);
    }
    Answer(pack);
  }
  Answer(rem);  
}