洛谷P9529 [JOISC2022] 一流团子师傅题解

题目链接：P9529 [JOISC2022] 一流团子师傅

题意：

JOI 君是一位专业的团子师傅。在 JOI 君的店里，团子的颜色很有讲究。一共有 \(N\) 种颜色，编号为 \(1,2,\dots,N\)。

一流团子串是 JOI 君的店里的招牌食品。制作一个一流团子串，需要将 \(N\) 个颜色不同的团子串在一根竹签上。

对于每一种颜色，JOI 君都制作了 \(M\) 个这种颜色的团子。因此，JOI 君总共有了 \(NM\) 个团子。这些团子被编号为 \(1,2,\dots,NM\)。使用这些团子和 \(M\) 根竹签，JOI 君希望串出 \(M\) 个一流团子串。

为了避免在颜色上犯错误，JOI 君将会启用他的团子检测器。如果 JOI 君输入一些团子的编号，团子检测器会返回使用这些团子能制作的一流团子串的个数的最大值。当然，前提是充分使用竹签。

JOI 君希望能通过使用若干次团子检测器将 \(NM\) 个团子分为 \(M\) 组。其中，每一组包含 \(N\) 个团子，且每种颜色的团子恰有一个。

JOI 君想在使用不超过 \(50\,000\) 次团子检测器的前提下完成这件事。

请写一个程序，对于给定的团子的信息，实现 JOI 君使用不超过 \(50\,000\) 次团子检测器来完成任务的策略。

省流：

有 \(nm\) 个团子，共 \(n\) 种颜色，每种有 \(m\) 个。现在要将这些团子串成 \(m\) 串，每串上的颜色两两不同。

不过你是一个色盲，需要用团子检测器检测颜色。每次给定若干个编号，检测器会告诉你最多能串几串。

交互格式：

你的程序需要实现以下函数。

void Solve(int N, int M)。
对于每组测试数据，该函数会被调用恰好一次。

参数 \(\texttt N\) 是团子的颜色数 \(N\)。

参数 \(\texttt M\) 是 JOI 君想制作的一流团子串的个数 \(M\)。

你的程序可以调用以下函数。

int Query(const std::vector<int> &x)。
你的程序可以通过调用这个函数来使用团子检测器。

参数 x 是输入给团子检测器的团子的编号列表。

该函数返回使用 x 中的团子能制作的一流团子串的最大值。

x 中的每个元素都应当是 \([1,NM]\) 中的整数。否则你的程序会被判定为 Wrong Answer [1]。

x 中的元素应当互不相同。否则你的程序会被判定为 Wrong Answer [2]。

你的程序不得调用该函数超过 \(50\,000\) 次。否则你的程序会被判定为 Wrong Answer [3]。

void Answer(const std::vector<int> &a)。
你的程序可以通过调用这个程序来报告分组方案。

参数 a 是你分出的一组团子的编号列表。

a 的长度应当为 \(N\)。否则你的程序会被判定为 Wrong Answer [4]。

a 中的每个元素都应当是 \([1,NM]\) 中的整数。否则你的程序会被判定为 Wrong Answer [5]。

在整个过程中，同一个团子不能出现在参数中多于一次。否则你的程序会被判定为 Wrong Answer [6]。

如果用 a 中的团子并不能制作一个一流团子串，你的程序会被判定为 Wrong Answer [7]。

该函数应当被调用恰好 \(M\) 次。否则你的程序会被判定为 Wrong Answer [8]。

数据范围：

对于所有测试数据，满足：

\(1 \le C_i \le N\) \((1 \le i \le NM)\)。

对于每个 \(j\) \((1 \le j \le N)\)，恰有 \(M\) 个 \(i\) \((1 \le i \le NM)\) 满足 \(C_i = j\)。

\(N,M\) 是正整数。

\(C_i\) \((1 \le i \le NM)\) 是一个 \([1,N]\) 内的整数。

\(1 \le N \le 400, ~1 \le M \le 25\) 。

首先考虑如何找到一组团子。设下标集合为 \(S\) ，按任意顺序枚举 \(S\) 中的元素 \(s_{i}\)

每次从 \(S\) 中删去 \(s_i\) ，若询问得到的结果为 \(m-1\) ，那 \(s_i\) 这个团子就可以加入当前团子串。

否则将 \(s_i\) 重新扔到 \(S\) 里。当前团子串串好后，令 \(m \gets m - 1\) ，继续做即可。

这样的话复杂度是 \(\mathcal{O}(nm^2)\) 的，显然过不了，因此考虑随机化（尽管本题可以二分，~~但是呢，对吧~~）。

那么每次组团子串之前我们把 \(S\) 随机打乱，然后按照之前的做法取即可。

这个思路来源于参考文献1，不过没有证明，因此我来尝试分析一下复杂度和操作数。

如果把取出的团子再复制一个扔到 \(S\) 里，那么这个问题就变成了经典的「赠券收集问题」。

设有 \(n\) 种赠券，每种获取概率相同，赠券无限供应，求集齐 \(n\) 张赠券的期望获取次数。

这个问题的答案是 \(\mathrm{E} = nH_n\) ，其中 \(H_n=\sum_{i=1}^n\frac{1}{i}\) 表示调和数。

根据调和数的近似公式可得 \(\mathrm{E} = nH_n \approx n (\ln n + \gamma)\) ，其中 \(\gamma\approx 0.5772156649\) 是欧拉-马歇罗尼常数。

况且以上还是在取出的团子复制一个扔回去的前提下，实际期望显然会更小一些。

故时间复杂度 \(\mathcal{O}(mn\log n)\) ，期望操作数 \(mn(\ln n + \gamma) \le 37961\) 。实测极限数据至多需要 \(4.8\times 10^4\) 次。

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)

mt19937 rd(time(0));
int Query(const vector<int> &x);
void Answer(const vector<int> &a);
void Solve(int n, int m)
{
    vector<int> vec;
    rep(i, 1, n * m) vec.push_back(i);
    rep(i, 1, m - 1)
    {
        shuffle(vec.begin(), vec.end(), rd);
        vector<int> ans;
        ans.push_back(vec.front()); vec.erase(vec.begin());
        while(ans.size() < n)
        {
            int v = vec.front(); vec.erase(vec.begin());
            if(Query(vec) == m - i) ans.push_back(v); else vec.push_back(v);
        }
        Answer(ans);
    }
    Answer(vec);
}