首页 > 其他分享 >[IOI2022] 最罕见的昆虫

[IOI2022] 最罕见的昆虫

时间:2023-01-23 22:14:03浏览次数:45  
标签:机器 int inside move IOI2022 press 昆虫 罕见

[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 不知道这些昆虫的类型。他有一台单按钮的机器,可以提供昆虫类型相关的信息。刚开始时,机器是空的。在使用机器时,可以做如下三种操作:

  1. 将一只昆虫放进机器。
  2. 将一只昆虫取出机器。
  3. 按下机器的按钮。

每种操作最多可以做 \(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_insidemove_outsidepress_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\)。

子任务

  1. (10 分) \(N \le 200\);
  2. (15 分) \(N \le 1000\);
  3. (75 分) 没有额外的约束条件。

如果在某个测试用例上,函数 move_insidemove_outsidepress_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_insidemove_outside 时,参数 \(i\) 的值不在 \(0\) 至 \(N-1\) 的范围内(包括 \(0\) 和 \(N-1\))。
  • too many calls:函数 move_insidemove_outsidepress_button某个的调用次数超过 \(40\;000\) 次。

否则,评测程序示例按以下格式输出:

  • 第 \(1\) 行:min_cardinality 的返回值;
  • 第 \(2\) 行:\(q\)。

约定

题面在给出函数接口时,会使用一般性的类型名称 voidboolintint[](数组)和 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;
}

标签:机器,int,inside,move,IOI2022,press,昆虫,罕见
From: https://www.cnblogs.com/mekoszc/p/17065597.html

相关文章

  • UOJ #761. 【IOI2022】最罕见的昆虫
    题面传送门首先有一个显然的想法:从小到大枚举答案,每次尝试将每个数加进去,如果加进去大小能在枚举的这个答案以内那就加进去,否则就不加。容易发现这是\(O(n^2)\)的询问次数......
  • 信息学一本通 1312:【例3.4】昆虫繁殖
    时间限制:1000ms      内存限制:65536KB提交数:30159   通过数:15099【题目描述】科学家在热带森林中发现了一种特殊的昆虫,这种昆虫的繁殖能力很......
  • IOI2022乱做
    最罕见的昆虫考虑二分答案。首先花\(n\)次算出种类。记有\(n\)只昆虫,\(c\)个种类的最小步数为\(F(n,c)\)。枚举一个答案\(ans\),接下来\(O(n)\)check它:往机器......
  • IOI2022
    鲶鱼塘\((\texttt{Easy}\0/3)\)设第\(i\)列的高度为\(h_i\),若\(h_{i-1}>h_i<h_{i+1}\),则可以直接令\(h_i=0\)。于是可以设\(f_{i,j}\)表示\(h_{......
  • IOI2022 数字电路
    第一次体验当年IOI的题(虽然是Day2的签到)这题有一个经典的套路——在一些计数DP题,我们不直接统计方案数,而是统计出现合法方案的概率。这样我们设\(dp(i)\)表示子树\(i\)内......
  • 【笔记】IOI2022
    「IOI2022」鲶⻥塘签到题。如果我们记\(a_i\)表示第\(i\)列的高度,那么一定不存在\(a_i\gea_{i+1}\lea_{i+2}(a_{i+1}\neq0)\)的情况,假设存在,我们将\(a_{i+......