A21 Hint

题目类型说明

这是一道提交函数题 / 评分题。

你不需要编写 main 函数，而是需要实现两个函数：

std::vector<bool> genHint(const std::vector<int>& a, const std::vector<int>& b,
                          const std::vector<int>& sol);
std::vector<int> solve(const std::vector<int>& a, const std::vector<int>& b,
                       const std::vector<bool>& hint);

评测时，genHint 与 solve 会在两个独立进程中分别调用，因此你不能依赖全局变量或静态状态在两次调用之间传递信息。你唯一能够传递的信息，就是 genHint 返回的那段布尔序列 hint。

---

题目描述

布朗博士把他的 DeLorean 改造成了时光机。现在他盯上了一个更大的难题：最长公共子序列（LCS）。

给定两个整数序列 A 与 B，长度分别为 N 和 M，他想求出一个最长的序列 C，满足：C 中所有元素都以相同顺序出现在 A 和 B 中，但不要求连续。

布朗博士已经写好了一个很慢的程序，它在未来若干天后能够算出一个最优解。但他希望现在就拿到答案。最初，他打算让未来的自己把完整答案发回现在；然而时空传输非常耗能，直接传送完整解的代价太高。

于是他想出了一个新方案：

• 未来的程序先算出某个最优解 sol；
• 你编写的 genHint 根据 A、B 和这个最优解 sol，生成一段尽量短的提示信息 hint；
• 然后你编写的 solve 只根据 A、B 和 hint，恢复出一个任意最优的最长公共子序列。

注意，solve 恢复出的最优解不一定要与 genHint 收到的 sol 完全相同，只要它也是一个最长公共子序列即可。

你需要编写 hint.cpp，实现上述两个函数。

---

实现要求

std::vector<bool> genHint(...)

std::vector<bool> genHint(const std::vector<int>& a, const std::vector<int>& b,
                          const std::vector<int>& sol);

该函数只会被调用一次。

输入参数为：

• a：原序列 A；
• b：原序列 B；
• sol：某个最优的最长公共子序列。

你需要返回一段布尔序列 hint，作为发回过去的提示信息。

std::vector<int> solve(...)

std::vector<int> solve(const std::vector<int>& a, const std::vector<int>& b,
                       const std::vector<bool>& hint);

该函数只会被调用一次。

输入参数为：

• a：原序列 A；
• b：原序列 B；
• hint：genHint 返回的提示信息。

你需要返回一个最优的最长公共子序列。

---

提交要求

你提交的源文件必须：

• 包含头文件：

#include "hint.h"

• 可以包含任意辅助函数、类、变量等；
• 不能包含 main 函数。

注意：在正式评测中，genHint 和 solve 会在不同进程中运行，因此无法共享全局状态。

---

本地测试

题目提供 Lgrader.cpp 供本地测试。

将它与你的程序一起编译后，本地评测器会按如下格式读入：

• 第一行两个整数 N, M；
• 第二行给出序列 A；
• 第三行给出序列 B；
• 接着给出最优解长度 K；
• 最后一行给出一个最优解 C。

本地评测器会输出：

• 你生成的 hint 的长度；
• 以及 solve 返回的解。

注意，本地评测器与正式评测不同：它不会在两个独立进程中运行这两个函数。

---

数据范围

• 1 <= N, M <= 2 * 10^5
• 0 <= A_i, B_j < min(N, M)

---

子任务

子任务	分值	N, M
1	10	<= 10^4
2	90	<= 2 * 10^5

只有通过某个子任务中的全部测试，才能获得该子任务分数。

---

评分方式

设在某个子任务中，你的程序在该子任务所有测试中生成的提示长度最大值为 L，则该子任务的得分比例为：

$$\min\left(\left(\frac{640}{L+1}\right)^{0.3},\ 1\right)$$

也就是说，提示越短，得分越高。