P15942 [JOI Final 2026] 赌场 / Casino
题目描述
**这是一道通信题。本题中，交互库是非自适应的。**
Azzurro 和 Bordeaux 是一对在意大利游览赌场的伴侣，他们决定玩一个由荷官 Chiaro 提议的游戏。
在这个游戏中，信息通过一个 $N \times N$ 的网格 ($N = 8$) 进行传递。网格的行从上到下编号为 $0$ 到 $N-1$，列从左到右编号为 $0$ 到 $N-1$。
行号为 $r$、列号为 $c$ 的单元格记作 $(r, c)$。
在这个游戏中，Azzurro 和 Bordeaux 被隔离在不同的房间里。他们将进行 $Q$ 轮游戏。第 $i$ 轮 ($1 \leq i \leq Q$) 的过程如下。
1. Azzurro 从 Chiaro 那里收到一个整数 $N$、一个整数 $L_i$ ($1 \leq L_i \leq 51$)、一张写有长度为 $L_i$ 且由 'A' 和 'B' 组成的字符串 $S_i$ 的卡片，以及一个单元格全是白色的 $N \times N$ 网格。
2. Azzurro 将 $N^2$ 个单元格中的每一个涂成蓝色或红色。然后他将网格交给 Chiaro。
3. Chiaro 在 Azzurro 和 Bordeaux 都看不见的情况下执行以下操作。
(a) 他选择一条从 $(0,0)$ 到 $(N-1, N-1)$ 的路径，移动方式仅限重复向相邻的下方或右方单元格移动。
(b) 对于路径上的每个单元格，如果该单元格颜色为蓝色，他将其重涂为红色；如果颜色为红色，他将其重涂为蓝色。
4. Bordeaux 从 Chiaro 那里收到一张写有整数 $N$ 和 $L_i$ 的卡片以及该网格。
5. Bordeaux 在一张纸上写下一个长度为 $L_i$ 且由 A 和 B 组成的字符串。如果写下的字符串与 $S_i$ 匹配，则 Azzurro 和 Bordeaux 获胜。
编写程序实现 Azzurro 和 Bordeaux 在此游戏中获胜的策略。关于此任务的评分，请参阅“评分”。
### 实现细节
~~你需要提交两个文件。~~
第一个文件是 $\texttt{Azzurro.cpp}$。它应该实现 Azzurro 的策略。它应该实现以下函数。程序应使用预处理指令 `#include` 包含 $\texttt{Azzurro.h}$。
```cpp
std::vector Azzurro(int N, int L, std::string S)
```
该函数被调用 $Q$ 次。第 $i$ 次调用 ($1 \leq i \leq Q$) 对应于游戏第 $i$ 轮的过程 1 和 2。
- 参数 $\texttt{N}$ 是第 $i$ 轮过程 1 中交给 Azzurro 的卡片上写的整数 $N$。
- 参数 $\texttt{L}$ 是第 $i$ 轮过程 1 中交给 Azzurro 的卡片上写的整数 $L_i$。
- 参数 $\texttt{S}$ 是第 $i$ 轮过程 1 中交给 Azzurro 的卡片上写的字符串 $S_i$。
对于每次 `Azzurro` 函数调用，你的程序必须返回一个 $N \times N$ 的二维数组 $\texttt{x}$，其每个元素均为 $0$ 或 $1$。如果不满足此条件，你的程序将被判定为 **Wrong Answer [1]**。
- 如果 $\texttt{x[r][c]}=0$ ($0 \leq r \leq N-1, 0 \leq c \leq N-1$)，表示单元格 $(r, c)$ 涂成蓝色。
- 如果 $\texttt{x[r][c]} = 1$ ($0 \leq r \leq N-1, 0 \leq c \leq N-1$)，表示单元格 $(r, c)$ 涂成红色。
第二个文件是 $\texttt{Bordeaux.cpp}$。它应该实现 Bordeaux 的策略。它应该实现以下函数。程序应使用预处理指令 `#include` 包含 $\texttt{Bordeaux.h}$。
```cpp
std::string Bordeaux(int N, int L, std::vector T)
```
该函数在 Azzurro 每次完成网格涂色后被调用。该函数总共被调用 $Q$ 次。第 $i$ 次调用 ($1 \leq i \leq Q$) 对应于游戏第 $i$ 轮的过程 4 和 5。
- 参数 $\texttt{N}$ 是第 $i$ 轮过程 4 中交给 Bordeaux 的卡片上写的整数 $N$。
- 参数 $\texttt{L}$ 是第 $i$ 轮过程 4 中交给 Bordeaux 的卡片上写的整数 $L_i$。
- 参数 $\texttt{T}$ 是对应于第 $i$ 轮过程 4 中交给 Bordeaux 的网格的 $N \times N$ 二维数组。如果 $\texttt{T[a][b]} = 0$，则单元格 $(r, c)$ ($0 \leq r \leq N-1, 0 \leq c \leq N-1$) 的颜色为蓝色；如果 $\texttt{T[a][b]} = 1$，则为红色。
对于每次 `Bordeaux` 函数调用，你的程序必须返回一个长度为 $L_i$ 且由 '$\texttt{A}$' 和 '$\texttt{B}$' 组成的字符串 s。如果不满足此条件，你的程序将被判定为 **Wrong Answer [2]**。
### 重要注意事项
- 你的程序可以实现其他用于内部使用的函数，或使用全局变量。提交的文件将与评测程序（grader）一同编译，并生成一个单一的可执行文件。所有全局变量和内部函数应声明在匿名命名空间中，以避免与其他文件冲突。在评测时，它将作为 Azzurro 和 Bordeaux 两个进程执行。Azzurro 进程和 Bordeaux 进程不能共享全局变量。
- 你的程序不得使用标准输入和标准输出。你的程序不得通过任何方法与其他文件通信。但是，你的程序可以向标准错误输出调试信息。
### 编译与测试运行
你可以从竞赛网页下载一个压缩文件，其中包含用于测试程序的示例评测程序。该压缩文件还包含你程序的示例源文件。
示例评测程序是文件 $\texttt{grader.cpp}$。为了测试你的程序，请将 $\texttt{grader.cpp}$、$\texttt{Azzurro.cpp}$、$\texttt{Bordeaux.cpp}$、$\texttt{Azzurro.h}$、$\texttt{Bordeaux.h}$ 放在同一个目录下，并运行以下命令来编译你的程序。
```bash
g++ -std=gnu++20 -O2 -o grader grader.cpp Azzurro.cpp Bordeaux.cpp
```
或者，你可以运行压缩文件中包含的 $\texttt{compile.sh}$。在这种情况下，运行以下命令来编译你的程序。
```bash
./compile.sh
```
编译成功后，将生成可执行文件 `grader`。
注意，实际的评测程序与示例评测程序不同。示例评测程序将作为单个进程执行，它将从标准输入读取输入数据并将结果写入标准输出。
在实际的评测程序中，Chiaro 选择的路径是提前固定的。也就是说，在调用你提交的程序中的 $\texttt{Azzurro}$ 和 $\texttt{Bordeaux}$ 函数之前，Chiaro 选择的路径就已经确定了。
输入格式
示例评测程序从标准输入读取以下数据。
> $Q$ $N$\
> $L_1$\
> $S_1$\
> $R_1$\
> $L_2$\
> $S_2$\
> $R_2$\
> $\vdots$\
> $L_Q$\
> $S_Q$\
> $R_Q$
这里，$R_i$ ($1 \leq i \leq Q$) 是一个长度为 $2(N-1)$ 的字符串，恰好包含 $N-1$ 个 '$\texttt{D}$' 和 $N-1$ 个 '$\texttt{R}$'。该字符串表示 Chiaro 在第 $i$ 轮中选择的路径，该路径从 $(0,0)$ 开始，通过重复向相邻的下方或右方单元格移动到达 $(N-1,N-1)$。具体来说，从 $(0,0)$ 开始，对于每个 $j=1,2,\cdots,2(N-1)$，如果 $R_i$ 的第 $j$ 个字符是 '$\texttt{D}$'，则向下方相邻单元格移动；如果是 '$\texttt{R}$'，则向右方相邻单元格移动。重复此过程最终到达 $(N-1,N-1)$。
输出格式
示例评测程序将以下信息输出到标准输出（引号为了清晰起见）。
- 如果你的程序被判定为正确，它会写出 $L^*$ 的值，例如 “$\texttt{Accepted: 26}$”。关于 $L^*$ 的值，请参阅“评分”。
- 如果你的程序被判定为任何类型的 Wrong Answer，示例评测程序会将其类型写为 “**Wrong Answer [1]**”。
如果你的程序满足多种类型的 Wrong Answer 条件，示例评测程序仅报告其中一种。当满足其中一个错误答案条件时，示例评测程序可能会终止执行。
说明/提示
### 样例交互
以下是示例评测程序的样例输入及对应的函数调用。
**输入**
```text
2 2
1
B
RD
3
ABB
DR
```
**样例函数调用**
| 函数调用 | 返回值 |
|:-:|:-:|
| $\texttt{Azzurro(2,\,1,\,"B") }$ | $\texttt{[[1,\,0],\,[0,\,1]]}$ |
| $\texttt{Bordeaux(2,\,1,\,[[0,\,1],\,[0,\,0]])}$ | $\texttt{"B"}$ |
| $\texttt{Azzurro(2,\,3,\,"ABB")}$ | $\texttt{[[0,\,0],\,[0,\,0]]}$ |
| $\texttt{Bordeaux(2,\,3,\,[[1,\,0],\,[1,\,1]])}$ | $\texttt{"ABB"}$ |
该样例输入包含 $Q(=2)$ 轮，每轮使用一个 $N \times N$ 的网格 ($N = 2$)。在这个例子中，第一轮过程如下。
1. Azzurro 将 ($0$,$1$) 和 ($1$,$0$) 涂成蓝色，将 ($0$,$0$) 和 ($1$,$1$) 涂成红色。然后他将网格交给 Chiaro。
2. Chiaro 在 Azzurro 和 Bordeaux 看不见的情况下执行以下操作。
**(a)** 他选择路径 ($0$,$0$) $\to$ ($0$,$1$) $\to$ ($1$,$1$) 作为从 ($0$,$0$) 到 ($N - 1$,$N - 1$) 的路径，移动方式仅限重复向相邻的下方或右方单元格移动。
**(b)** 对于这条路径上的三个单元格 ($0$,$0$), ($0$,$1$), ($1$,$1$)，他改变它们的颜色。结果，($0$,$0$), ($0$,$1$), ($1$,$1$) 的颜色分别变为蓝色、红色和蓝色。
3. Bordeaux 可以通过在纸上写下 "B" 来赢得本轮。
第二轮过程如下。
1. Azzurro 将所有单元格涂成蓝色。然后他将网格交给 Chiaro。
2. Chiaro 在 Azzurro 和 Bordeaux 看不见的情况下执行以下操作。
**(a)** 他选择路径 ($0$,$0$) $\to$ ($1$,$0$) $\to$ ($1$,$1$) 作为从 ($0$,$0$) 到 ($N - 1$,$N - 1$) 的路径，移动方式仅限重复向相邻的下方或右方单元格移动。
**(b)** 对于这条路径上的三个单元格 ($0$,$0$), ($1$,$0$), ($1$,$1$)，他改变它们的颜色。结果，($0$,$0$), ($1$,$0$), ($1$,$1$) 的颜色都变为红色。
3. Bordeaux 可以通过在纸上写下 "ABB" 来赢得本轮。
注意，此样例输入不满足问题的限制条件。可以从竞赛网站下载的文件 $\texttt{sample-01-in.txt}$ 对应于样例输入 1。从竞赛网站下载的文件 $\texttt{sample-02-in.txt}$ 是一个满足限制条件的样例输入。
### 数据范围
所有输入数据满足以下条件。
- $1 \leq Q \leq 30000$。
- $N=8$。
- $1 \leq L_i \leq 51$ ($1 \leq i \leq Q$)。
- $Q, L_i$ ($1 \leq i \leq Q$) 均为整数。
- $S_i$ ($1 \leq i \leq Q$) 是长度为 $L_i$ 且由 '$\texttt{A}$' 和 '$\texttt{B}$' 组成的字符串。
- $R_i$ ($1 \leq i \leq Q$) 是长度为 $2(N-1)$ 的字符串，恰好包含 $N-1$ 个 '$\texttt{D}$' 和 $N-1$ 个 '$\texttt{R}$'。
### 评分
如果你的程序在任何测试用例中被判定为任何类型的 **Wrong Answer [1]** 或 **Wrong Answer [2]**（见实现细节）、超过时间限制、超过内存限制或运行错误，你的分数为 $0$ 分。
否则，设 $L^*$ 为该任务所有测试用例中以下值的最小值。你的分数按以下表格计算。
- 使得 Azzurro 和 Bordeaux 在所有满足 $L_i \leq L$ 的轮次中均获胜的最大 $L$ 值。但是，如果他们在测试用例中的所有轮次均获胜，我们令 $L = 51$。
| $L^*$ 的值 | 你的分数 |
|:-:|:-:|
| $1 \leq L^* \leq 28$ | $2L^*$ 分 |
| $29 \leq L^* \leq 39$ | $L^* + 28$ 分 |
| $40 \leq L^* \leq 50$ | $67 + 3(L^* - 40)$ 分 |
| $L^* = 51$ | $100$ 分 |