AdditionalFile5622.zip

#5622. 「KTSC 2026 R2」五万种调味汁

标签: 传统 | 时间限制: 3000 ms | 内存限制: 2048 MiB |

注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 17 及以上）

请在提交源代码前添加 #include "sauce.h"。

题目描述

题目译自 2026년도 국제정보올림피아드 대표학생 선발고사 - 2차 선발고사 T1 「오만가지 소스」

金东贤大厨自诩能够制作出「五万种」调味汁。事实果真如此吗？你现在是烹饪大赛的评委，需要通过测试来评估金东贤大厨制作调味汁的能力。

赛场共有 $N$ 种食材，每种食材分别编号为 $0, 1, \ldots, N-1$。金东贤大厨可以制作的每种调味汁都由其中的 $2$ 种或 $3$ 种食材组成。对于任意两种不同的调味汁，它们所包含的食材列表不能完全相同（尽管部分食材可能会重叠）。

从数学角度来看，金东贤大厨能制作的调味汁是集合 $X$ 中的元素。$X$ 的每个元素 $S$ 都是 $\{0, 1, \ldots, N-1\}$ 的一个子集，且满足 $|S|$ 为 $2$ 或 $3$。根据集合的标准定义，每个 $S$ 中不包含重复元素。

作为评委，你需要确定金东贤大厨能制作的调味汁总数 $|X|$。虽然你无法直接获得关于 $X$ 的完整信息，但可以通过“盲测”来获取相关情报。

盲测的流程如下：

• 你可以选择食材 $\{0, 1, \ldots, N-1\}$ 的一个子集 $Y$ 放入锅中交给大厨。由于锅的容积有限，一次能放入的食材数量 $|Y|$ 不能超过 $\lceil N/2 \rceil + 1$。即必须满足 $|Y| \leq \lceil N/2 \rceil + 1$。其中 $\lceil t \rceil$ 表示大于或等于实数 $t$ 的最小整数。
• 金东贤大厨会告诉你，他仅利用锅里的食材 $Y$ 总共能制作出多少种调味汁。也就是说，大厨会向你返回 $f(Y) = |\{S \in X \mid S \subseteq Y\}|$。

你的目标是通过尽可能少的盲测次数，准确地求出 $|X|$。

实现细节

你需要实现以下函数：

int solve(int N)

• $N$：食材的总数。
• 该函数应返回 $|X|$ 的值。
• 该函数仅会被调用一次。

该函数可以调用以下函数：

int query(vector<int> Y)

• $Y$ 的每个元素代表食材的编号。
• $Y$ 中的元素必须互不相同。
• 必须满足 $0 \leq Y[i] \leq N-1$（对于 $0 \leq i \leq |Y|-1$）。
• 必须满足 $|Y| \leq \lceil N/2 \rceil + 1$。
• 该函数返回 $f(Y) = |\{S \in X \mid S \subseteq Y\}|$。
• 在单个测试用例中，该函数最多可调用 $3000$ 次。

样例

假设 $N=6$，金东贤大厨能制作的调味汁集合为 $X = \{ \{0, 1\}, \{2, 3, 4\} \}$。则 $|X|=2$。 锅的最大容量为 $\lceil 6/2 \rceil + 1 = 4$。 评测程序最初调用如下函数： solve(6) 选手的代码可能会进行如下交互：

query({0, 1, 2})
query({2, 3, 4})
query({0, 2, 3, 5})

• 由于 $\{0, 1\} \subseteq \{0, 1, 2\}$ 且 $\{2, 3, 4\} \not\subseteq \{0, 1, 2\}$，query({0, 1, 2}) 返回 $1$。
• 由于 $\{0, 1\} \not\subseteq \{2, 3, 4\}$ 且 $\{2, 3, 4\} \subseteq \{2, 3, 4\}$，query({2, 3, 4}) 返回 $1$。
• 由于 $\{0, 2, 3, 5\}$ 不包含 $X$ 中的任何元素，query({0, 2, 3, 5}) 返回 $0$。

选手的代码作为 solve(6) 的返回值返回 $2$，即提交了正确答案。

数据范围与提示

对于所有输入数据，满足：

• $6 \leq N \leq 1000$
• $1 \leq |X| \leq 50000$
• 对于所有 $S \in X$，满足 $|S| \in \{2, 3\}$。
• 在此题目中，评测程序不是自适应的（non-adaptive）。这意味着集合 $X$ 在调用 solve 之前就已经确定。

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$11$	$N \leq 500$；对于 $X$ 中任意两个不同元素 $S_i, S_j$，满足 $S_i \cap S_j = \emptyset$；且对于所有 $S \in X$，满足 $
$2$	$32$	$N \leq 500$；对于 $X$ 中任意两个不同元素 $S_i, S_j$，满足 $S_i \cap S_j = \emptyset$
$3$	$25$	对于所有 $S \in X$，满足 $
$4$	$32$	无附加限制

在每个子任务中，如果你的程序有任何一次未能准确返回 $|X|$ 的值，则该子任务得 $0$ 分。

如果你在某个子任务的所有测试用例中都能准确返回 $|X|$，则该子任务的得分计算规则如下：设该子任务所有测试用例中使用的最大查询次数（调用 query 的次数）为 $Q$。

子任务 1 和 2：

如果 $Q \leq 3000$，则获得该子任务 $100\%$ 的分数。

子任务 3 和 4：

得分根据以下公式计算：

• 如果 $41 < Q \leq 3000$，则该子任务得分乘以以下比例：

$$0.5 + \frac{41}{2Q}$$

• 如果 $Q \leq 41$，则获得该子任务 $100\%$ 的分数。

示例评测程序

示例评测程序的输入格式如下：

• 第一行：$N$
• 第二行：$K$（即 $|X|$）
• 接下来的 $K$ 行（对于 $0 \leq i < K$）：
  • 第 $3+i$ 行：$L \ a_0 \ a_1 \ \ldots \ a_{L-1}$
  • 满足 $2 \leq L \leq 3$
  • $0 \leq a_j \leq N-1$
  • $a_0, a_1, \ldots, a_{L-1}$ 互不相同
  • $\{a_0, a_1, \ldots, a_{L-1}\}$ 是集合 $X$ 的一个元素

示例评测程序会按以下格式输出你的代码在 solve 函数中返回的值以及调用 query 的次数：

• 第一行：solve 函数返回的值 $x$
• 第二行：调用 query 的次数 $Q$