P16454 [APIO 2026] Scallion Pancake Party（暂无数据）
题目描述
Bohan 正在举办一场派对。由于他热爱葱油饼，他决定从附近的商店购买一些为派对做准备。这家商店出售 $N$ 种不同口味的葱油饼，编号从 $0$ 到 $N - 1$。Bohan 决定每种口味购买 $N$ 张葱油饼，总计 $N^2$ 张。每张葱油饼在装入独立的袋子之前，会被切成 $K$ 个完全相同的小片。袋子编号从 $0$ 到 $N^2 - 1$。记 $F[i]$ 表示袋子 $i$ 中葱油饼的口味。
派对期间，Bohan 邀请所有客人参与一个游戏。游戏过程如下。
首先，Bohan 挑选 $N$ 位客人，并将他们分别带入编号为 $0$、$1$、……、$N - 1$ 的房间，每个房间恰好有一位客人。其余客人留在外面，直到游戏结束。所有 $N$ 个房间看起来完全一样，因此客人无法分辨自己身处哪个房间。
接着，对于每个房间 $i$ ($0 \le i < N$)，Bohan 进入房间 $i$ 并悄悄告诉里面的客人一个整数 $P[i]$，代表一种**禁忌口味**。他可能会、也可能不会同时告诉客人他们所在的房间编号。Bohan 保证 $[P[0], P[1], \cdots, P[N - 1]]$ 是 $[0, 1, \cdots, N - 1]$ 的一个排列。
然后，游戏进行 $N$ 轮。在第 $i$ 轮中，Bohan 将袋子 $0, 1, \cdots, N^2 - 1$ 按照顺序一个接一个地送入房间 $i - 1$。当房间 $i - 1$ 中的客人收到袋子 $j$ 时，他们会得知：
* $F[j]$，即袋子 $j$ 中所装的葱油饼口味，以及
* 袋子中剩余的小片数量。
在接收下一个袋子之前，房间 $i - 1$ 中的客人必须决定从当前袋子中吃掉多少片。他们能吃掉的小片数量取决于以下情况：
* 如果 $P[i - 1] \ne F[j]$，该客人可以从袋子中取出任意数量的小片并吃掉。
* 如果 $P[i - 1] = F[j]$，该客人不允许吃掉任何小片。
注意，客人们事先并不知道序列 $F[0], F[1], \cdots, F[N^2 - 1]$。
所有 $N$ 轮结束后，留在外面的客人会得到袋子的序列。看到这些袋子后，他们会得知每张葱油饼的口味以及每个袋子中剩余的小片数量。凭借这些信息，他们必须确定出 $P[0], P[1], \cdots, P[N - 1]$ 的值。
客人可以在游戏开始前进行沟通。他们事先也知道 $N$ 和 $K$ 的值。你的目标是实现一个策略，使得外面的客人总能正确推断出 $P[0], P[1], \cdots, P[N - 1]$ 的值。
### 实现细节
你需要实现三个函数。
对于房间 $0, 1, \cdots, N - 1$ 中的客人，你需要实现以下两个函数。
```cpp
void init(int N, int K, int p, int r)
```
假设该客人位于房间 $i$。
* $N$：葱油饼的口味数量。
* $K$：游戏开始前每张葱油饼被切成的小片数。
* $p = P[i]$：房间 $i$ 中禁止食用的口味。
* 如果 Bohan 决定告诉客人他们所在的房间，则 $r = i$。否则 $r = -1$。
```cpp
int strategy(int b, int f, int s)
```
假设该客人位于房间 $i$。
* $b$：当前袋子的编号。
* $f = F[b]$：袋子 $b$ 中葱油饼的口味。
* $s$：袋子 $b$ 中剩余的小片数量。
* 该函数应返回一个非负整数 $x$，代表该客人决定吃掉的小片数量。
* 如果 $f \ne P[i]$，则必须满足 $0 \le x \le s$。
* 如果 $f = P[i]$，则必须满足 $x = 0$。
你需要为外面的客人实现以下函数。
```cpp
std::vector guess(int N, int K, std::vector F, std::vector S)
```
* $N$：葱油饼的口味数量。
* $K$：游戏开始前每张葱油饼被切成的小片数。
* $F$：长度为 $N^2$ 的数组，其中 $F[i]$ 是袋子 $i$ 中葱油饼的口味。
* $S$：长度为 $N^2$ 的数组，其中 $S[i]$ 是经过所有 $N$ 轮后袋子 $i$ 中剩余的小片数量。
* 该函数应返回一个长度为 $N$ 的数组 $P$，其中 $P[i]$ 是给房间 $i$ 中客人的数字。
每个测试用例包含 $T$ 场独立的游戏。
在评测过程中，对于 $T$ 场游戏中的每一场，将会启动 $N + 1$ 个进程。对于每个满足 $0 \le i < N$ 的 $i$，进程 $i$ 代表房间 $i$ 中的客人。进程 $N$ 代表外面的客人。对于每个满足 $0 \le i < N$ 的 $i$，进程 $(i + 1)$ 在进程 $i$ 结束后启动。
对于进程 $0$ 到 $N - 1$：
* `init` 恰好被调用一次。
* `strategy` 在 `init` 之后被调用 $N^2$ 次。
* 保证在第 $j$ 次调用时，$b = j - 1$。
对于进程 $N$：
* `guess` 恰好被调用一次。
评测器可能会交错执行来自不同游戏的进程，但保证每一单独游戏内的进程相对顺序得以保持。
输入格式
样例评测器仅支持**每个测试用例一场游戏**。
输入格式：
```
N K
P[0] P[1] ... P[N-1]
F[0] F[1] ... F[N*N-1]
reveal
```
* `reveal` 为 $0$ 或 $1$。
* 如果 `reveal` 为 $0$，评测器将表现得好像 Bohan 没有告诉任何人他们的房间编号。
* 如果 `reveal` 为 $1$，评测器将表现得好像 Bohan 告诉了所有人他们的房间编号。
输出格式
如果 `guess` 返回的数组与 $[P[0], P[1], ..., P[N - 1]]$ 相符，样例评测器将打印
```
Accepted
```
此外，评测器会按顺序打印所进行的函数调用，以供调试。
说明/提示
### 样例
考虑这样一个场景：在测试用例的唯一一场游戏中，$T = 1$，$N = 2$，$K = 2$，$P = [1, 0]$，$F = [1, 0, 0, 1]$。
令 $S[i]$ 表示袋子 $i$ 中当前剩余的小片数。初始时，$S = [2, 2, 2, 2]$。
假设客人在游戏开始前约定以下策略。
* 对于房间中的客人，当他们被允许食用当前葱油饼时：
* 如果当前葱油饼是他们能够食用的第一张，则他们将吃掉所有剩余的小片。
* 否则，他们只吃掉一片。
* 对于外面的客人：
* 如果 $S = [0, 0, 1, 1]$，他们将猜测 $P = [1, 0]$。
* 否则，他们将猜测 $P = [0, 1]$。
游戏过程如下。
首先，评测器启动进程 $0$，代表房间 $0$ 中的客人，并调用 `init(2, 2, 1, -1)`。初始化之后，评测器进行以下调用：
| **函数调用** | **返回值** |
|:-:|:-:|
| `strategy(0, 1, 2)` | $0$ |
| `strategy(1, 0, 2)` | $2$ |
| `strategy(2, 0, 2)` | $1$ |
| `strategy(3, 1, 2)` | $0$ |
第一次和第四次调用必须返回 $0$，因为 $P[0] = F[0] = F[3] = 1$。
此进程结束后（第 $1$ 轮完成），$S = [2, 0, 1, 2]$。
接着，评测器启动进程 $1$，代表房间 $1$ 中的客人，并调用 `init(2, 2, 0, -1)`。初始化之后，评测器进行以下调用：
| **函数调用** | **返回值** |
|:-:|:-:|
| `strategy(0, 1, 2)` | $2$ |
| `strategy(1, 0, 0)` | $0$ |
| `strategy(2, 0, 1)` | $0$ |
| `strategy(3, 1, 2)` | $1$ |
注意，第二次和第三次调用必须返回 $0$，因为 $P[1] = F[1] = F[2] = 0$。
此进程结束后（第 $2$ 轮完成），$S = [0, 0, 1, 1]$。
最后，评测器启动进程 $2$，代表外面的客人。评测器进行以下调用：
| **函数调用** | **返回值** |
|:-:|:-:|
| `guess(2, 2, [1, 0, 0, 1], [0, 0, 1, 1])` | `[1,0]` |
外面的客人猜出了正确的排列。因此，该测试用例被视为正确。
请注意，这种方法并非总能让外面的客人正确猜出排列。
本题的附件包中除了本例外还包含另一组不同的样例输入。
### 数据范围
* $1 \le T \le 400$。
* $2 \le N \le 30$。
* 每个测试用例中所有游戏的 $N^3$ 之和不超过 $27\,000$。
* $1 \le K \le N$
* $K \in \{1, 3, N\}$。
* $[P[0], P[1], \cdots, P[N - 1]]$ 是 $[0, 1, \cdots, N - 1]$ 的一个排列。
* 对于每个满足 $0 \le j < N^2$ 的 $j$，有 $0 \le F[j] < N$。
* 对于每个满足 $0 \le i < N$ 的 $i$，在 $[F[0], F[1], \cdots, F[N^2 - 1]]$ 中 $i$ 恰好出现 $N$ 次。
* 评测器**不是自适应**的，也就是说，$[P[0], P[1], \cdots, P[N - 1]]$ 和 $[F[0], F[1], \cdots, F[N^2 - 1]]$ 在第一次调用 `init` 之前就已经固定。
### 子任务
| **子任务** | **分值** | **附加约束** |
|:-:|:-:|:-:|
| $1$ | $8$ | $K = 1, N = 2$。 |
| $2$ | $7$ | $K = 1$ 且 Bohan 决定告诉每个人他们所在的房间编号。 |
| $3$ | $14$ | $K = 1$ 且对于每个满足 $0 \le i < N$ 的 $i$，$[F[i \cdot N], F[i \cdot N + 1], \cdots, F[i \cdot N + N - 1]]$ 是 $[0, 1, \cdots, N - 1]$ 的一个排列。 |
| $4$ | $18$ | $K = N$。 |
| $5$ | $21$ | $K = 3, N \ge 3$。 |
| $6$ | $32$ | $K = 1$。 |
翻译由 DeepSeek V4 Pro 完成