[IOI2022] 最罕见的昆虫
题目描述
Pak Blangkon 的房子四周有 \(N\) 只昆虫，编号为 \(0\) 至 \(N-1\)。每只昆虫有一个类型，以从 \(0\) 至 \(10^9\)（包含 \(0\) 和 \(10^9\)）的整数编号。可能有多只昆虫类型相同。
假设将昆虫按照类型分组。我们定义最常见昆虫类型的基数是昆虫最多的分组中的昆虫数。类似地，最罕见昆虫类型的基数是昆虫最少的分组中的昆虫数。
例如，假设有 \(11\) 只昆虫，类型分别为 \([5, 7, 9, 11, 11, 5, 0, 11, 9, 100, 9]\)。在此情形中，最常见昆虫类型的基数是 \(3\)，是因为类型 \(9\) 和类型 \(11\) 的分组均有最多数目的昆虫，每个分组都有 \(3\) 只。最罕见昆虫类型的基数是 \(1\)，是因为类型 \(7\)、类型 \(0\) 和类型 \(100\) 的分组均有最少数目的昆虫，每个分组都有 \(1\) 只。
Pak Blangkon 不知道这些昆虫的类型。他有一台单按钮的机器，可以提供昆虫类型相关的信息。刚开始时，机器是空的。在使用机器时，可以做如下三种操作：
- 将一只昆虫放进机器。
- 将一只昆虫取出机器。
- 按下机器的按钮。
每种操作最多可以做 \(40\;000\) 次。
每当按下按钮时，机器会报告在机器内的最常见昆虫类型的基数。
你的任务是使用上述机器，确定 Pak Blangkon 的房子四周所有 \(N\) 只昆虫中最罕见昆虫类型的基数。此外，在某些子任务里，你的得分取决于机器执行某种操作的最大次数（详见子任务一节）。
输入格式
你要实现以下函数：
int min_cardinality(int N)
- \(N\)：昆虫数量。
- 此函数应返回 Pak Blangkon 的房子四周所有 \(N\) 只昆虫中最罕见昆虫类型的基数。
- 此函数恰好被调用一次。
该函数可调用以下几个函数：
void move_inside(int i)
- \(i\)：将被放进机器的昆虫编号。编号 \(i\) 的取值范围是 \(0\) 至 \(N-1\)（包含 \(0\) 和 \(N-1\)）。
- 如果昆虫已在机器内，函数调用不会影响机器内昆虫的集合。但是，调用仍会被计入此类操作的次数。
- 此函数最多可以被调用 \(40\;000\) 次。
void move_outside(int i)
- \(i\)：将被从机器中取出的昆虫编号。编号 \(i\) 的取值范围是 \(0\) 至 \(N-1\)（包含 \(0\) 和 \(N-1\)）。
- 如果昆虫已在机器外，函数调用不会影响机器内昆虫的集合。但是，调用仍会被计入此类操作的次数。
- 此函数最多可以被调用 \(40\;000\) 次。
int press_button()
- 此函数返回机器内最常见昆虫类型的基数。
- 此函数最多可以被调用 \(40\;000\) 次。
- 评测程序不是适应性的。也就是说，所有 \(N\) 只昆虫的类型在
min_cardinality调用前已经确定。
输出格式
考虑在某个场景下，有 \(6\) 只类型分别为 \([5, 8, 9, 5, 9, 9]\) 的昆虫。
函数 min_cardinality 的调用方式如下：
min_cardinality(6)
此函数按以下次序调用了 move_inside、move_outside 和 press_button。
| 函数调用 | 返回值 | 机器内的昆虫 | 机器内的昆虫类型 |
|---|---|---|---|
| \(\\{\\}\) | \([\ ]\) | ||
move_inside(0) |
\(\\{0\\}\) | \([5]\) | |
press_button() |
\(1\) | \(\\{0\\}\) | \([5]\) |
move_inside(1) |
\(\\{0, 1\\}\) | \([5, 8]\) | |
press_button() |
\(1\) | \(\\{0, 1\\}\) | \([5, 8]\) |
move_inside(3) |
\(\\{0, 1, 3\\}\) | \([5, 8, 5]\) | |
press_button() |
\(2\) | \(\\{0, 1, 3\\}\) | \([5, 8, 5]\) |
move_inside(2) |
\(\\{0, 1, 2, 3\\}\) | \([5, 8, 9, 5]\) | |
move_inside(4) |
\(\\{0, 1, 2, 3, 4\\}\) | \([5, 8, 9, 5, 9]\) | |
move_inside(5) |
\(\\{0, 1, 2, 3, 4, 5\\}\) | \([5, 8, 9, 5, 9, 9]\) | |
press_button() |
\(3\) | \(\\{0, 1, 2, 3, 4, 5\\}\) | \([5, 8, 9, 5, 9, 9]\) |
move_inside(5) |
\(\\{0, 1, 2, 3, 4, 5\\}\) | \([5, 8, 9, 5, 9, 9]\) | |
press_button() |
\(3\) | \(\\{0, 1, 2, 3, 4, 5\\}\) | \([5, 8, 9, 5, 9, 9]\) |
move_outside(5) |
\(\\{0, 1, 2, 3, 4\\}\) | \([5, 8, 9, 5, 9]\) | |
press_button() |
\(2\) | \(\\{0, 1, 2, 3, 4\\}\) | \([5, 8, 9, 5, 9]\) |
至此，已有充分信息表明，最罕见昆虫类型的基数是 \(1\)。
因此，函数 min_cardinality 应返回 \(1\)。
在这个例子里，move_inside 被调用 \(7\) 次，move_outside 被调用 \(1\) 次，press_button 被调用 \(6\) 次。
提示
约束条件
- \(2 \le N \le 2000\)。
子任务
- （10 分） \(N \le 200\)；
- （15 分） \(N \le 1000\)；
- （75 分） 没有额外的约束条件。
如果在某个测试用例上，函数 move_inside、move_outside 或 press_button 的调用次数不符合“实现细节”中给出的约束条件，或者 min_cardinality 的返回值不正确，你的解答在此子任务上得分为 \(0\)。
令 \(q\) 为以下三个值的 最大值：move_inside 的调用次数、move_outside 的调用次数、press_button 的调用次数。
在子任务 3 中，你可能会得部分分。令 \(m\) 为此子任务所有测试用例的 \(\frac{q}{N}\) 的最大值。你在此子任务的得分将根据以下表格计算：
| 条件 | 得分 |
|---|---|
| \(20 \lt m\) | \(0\) （CMS 报告“Output isn’t correct”） |
| \(6 \lt m \le 20\) | \(\frac{225}{m - 2}\) |
| \(3 \lt m \le 6\) | \(81 - \frac{2}{3} m^2\) |
| \(m \le 3\) | \(75\) |
评测程序示例
令 \(T\) 是长度为 \(N\) 的整数数组，其中 \(T[i]\) 是编号为 \(i\) 的昆虫的类型。
评测程序示例按以下格式读取输入：
- 第 \(1\) 行：\(N\)；
- 第 \(2\) 行：\(T[0] \; T[1] \; \ldots \; T[N - 1]\)。
如果评测程序示例检测到非法行为，评测程序示例将输出 Protocol Violation: <MSG>，其中 <MSG> 为如下某种类型：
invalid parameter：在函数调用move_inside或move_outside时，参数 \(i\) 的值不在 \(0\) 至 \(N-1\) 的范围内（包括 \(0\) 和 \(N-1\)）。too many calls：函数move_inside、move_outside或press_button中某个的调用次数超过 \(40\;000\) 次。
否则，评测程序示例按以下格式输出：
- 第 \(1\) 行：
min_cardinality的返回值； - 第 \(2\) 行：\(q\)。
约定
题面在给出函数接口时，会使用一般性的类型名称 void、bool、int、int[]（数组）和 union(bool, int[])。
在 C++ 中，评测程序会采用适当的数据类型或实现，如下表所示：
void |
bool |
int |
int[] |
|---|---|---|---|
void |
bool |
int |
std::vector<int> |
union(bool, int[]) |
数组 a 的长度 |
|---|---|
std::variant<bool, std::vector<int>> |
a.size() |
C++ 语言里，std::variant 定义在 <variant> 头文件中。
一个返回类型为 std::variant<bool, std::vector<int>> 的函数可以返回一个 bool 或一个 std::vector<int>。
以下示例代码给出了三个返回 std::variant 的函数，它们都能正常工作：
std::variant<bool, std::vector<int>> foo(int N) {
return N % 2 == 0;
}
std::variant<bool, std::vector<int>> goo(int N) {
return std::vector<int>(N, 0);
}
std::variant<bool, std::vector<int>> hoo(int N) {
if (N % 2 == 0) {
return false;
}
return std::vector<int>(N, 0);
}
只考了二分的IOI非送分题。
告诉你的是最大值，要求的是最小值，不难想到二分。
现在二分出来最小值是 \(md\),那么想象不断往机器里放数，如果众数数量大于 \(md\),那就把刚刚放的数拿出来。
把所有数这样子跑一次以后，如果最终机器里有 \(c\) 个数，那么想象当 \(md\) 小于等于最终答案时，\(c\) 为多少?
如果有 \(cnt\) 个种类，那么每一个种类都有多于 \(md\) 个数。所以\(c=md\times cnt\)。判定一下就可以了。操作次数大概 \(2nlogn\)，有点分了。至于怎么求 \(cnt\)，可以控制机器中众数数量为1，放入昆虫后如果大于1就拿出来，然后最后看昆虫数量就行了
那么考虑优化。发现如果此时判定出来 \(md\) 小于等于最终答案，此时已经在机器中的数就不用再拿出来了。同理，如果最终 \(md\) 大于最终答案，不在机器中的数就永远不用放进去了。可以打个标记。这样子大约是 \(n+\frac n2+\frac n4+\cdots\)，加上求 \(cnt\) 的复杂度，共 \(3n\)。
但是他不是严格的把总数除以2？而且交上去竟然只有99分。由于交互库不自适应，不需要真的把总数除以2，只要期望除2就行了。所以这99分可以卡一下。发现如果此时在机器中的数已经达到 \(cnt\times md\) 个，就可以直接 break 了。然后把放入昆虫的顺序随机打乱一下，就可以过了。
注意二分区间右端点初始化要设成 \(\frac{n}{cnt}\)，不然会被轻松卡飞的。
#include<bits/stdc++.h>
using namespace std;
int n,cnt,ret,vs[2005],vs1[2005],id[2005],now,l,r;
void move_inside(int i);
void move_outside(int i);
int press_button();
void add(int x)
{
vs[x]=1,++ret;
move_inside(x-1);
}
void del(int x)
{
vs[x]=0,--ret;
move_outside(x-1);
}
int min_cardinality(int n) {
srand(time(0));
for(int i=1;i<=n;i++)
{
add(id[i]=i);
if(press_button()>1)
del(i);
else
++cnt;
}
for(int i=1;i<=n;i++)
if(vs[i])
del(i);
r=n/cnt;
// printf("xzdakioi:%d\n",ret);
while(l<=r)
{
int md=l+r>>1;
// printf("crxzdq:%d %d\n",l,r);
random_shuffle(id+1,id+n+1);
for(int i=1;i<=n;i++)
{
if(!vs[id[i]]&&!vs1[id[i]])
{
add(id[i]);
if(press_button()>md)
del(id[i]);
}
if(ret==cnt*md)
break;
}
// printf("cjhyyds:%d\n",ret);
// for(int i=1;i<=n;i++)
// printf("%d %d\n",vs1[i],vs[i]);
// puts("");
if(ret==cnt*md)
{
for(int i=1;i<=n;i++)
if(vs[id[i]])
vs1[id[i]]=1;
l=md+1;
}
else
{
for(int i=1;i<=n;i++)
{
if(!vs[id[i]])
vs1[id[i]]=1;
else if(!vs1[id[i]])
del(id[i]);
}
r=md-1;
}
}
return r;
}