#P15482. [2026四川省队集训]图星
[2026四川省队集训]图星
图星
题目背景
可怜的 宝宝被联合省选2026中星图这道题创飞了,事后想加害一下后人。
于是他出了一道有异或、有判断、有操作的交互题。
题目描述
这是一道交互库题。请使用 C++14 或更新版本,只提交实现 mapstar 函数的源文件。评测时 Hydro 会提供 mapstar.h 并调用你的函数。
给定一个长度为 的数组 ,其中每个 均为一个长度为 的 01 序列(以布尔数组形式呈现)。另有一个长度同样为 的全局 01 序列 ,初始值为 。
接下来你需要进行若干次操作。每次操作中,你可以选择一个整数 ,随后交互库会依次执行以下两步:
- (即对 和 进行逐位异或)
- 将 的第 位翻转(若将 视为二进制数,即 )
你的目标是通过合理的操作序列,使得最终全局变量满足 ,并且对于所有的 ,都满足 。
需要注意的是,参数 $\text{initial}\_\text{z}, \text{final}\_\text{z}, \text{final}\_\text{a}$ 在某些测试点中可能为空。若某个参数为空,表示该参数的最终/初始值可由你自行选择与决定。
你需要判断给定的初始状态是否能达到目标状态;若有解,请构造并给出一组合法的操作序列。
实现细节
你需要在代码开头加入:
#include "mapstar.h"
你需要实现一个函数:
bool mapstar(int n, std::vector<std::vector<bool>> a, std::vector<bool> initial_z, std::vector<bool> final_z, std::vector<bool> final_a);
- 参数 是一个大小为 的数组,每一个 都是一个长度为 的布尔数组。
- 参数 $\text{initial}\_\text{z}, \text{final}\_\text{z}, \text{final}\_\text{a}$ 均有独立的两种可能
- 一个长度为 的布尔数组,表示固定好的状态
- 一个空数组,表示你可以自行决定值
- 每个测试点,
mapstar函数会被调用恰好 次,你需要判断是否有解- 如果无解,则应该直接返回
false - 如果有解,则需要在函数结束之前先调用恰好一次
start,接下来若干次choose,最后返回true
- 如果无解,则应该直接返回
在实现过程中,你可以调用以下两个交互库函数:
void start(std::vector<bool> initial_z, std::vector<bool> final_z, std::vector<bool> final_a);
- 此函数用于确认以上三个参数的值,传入的三个参数必须均为长度为 的布尔数组。
- 你需要保证:如果题目传入的 $\text{initial}\_\text{z}, \text{final}\_\text{z}, \text{final}\_\text{a}$ 初始不为空,你必须将原数组原样传回;如果为空,则传回你自行选定的状态。
void choose(int i);
- 表示选择一个下标 进行一次题面所述的操作,必须满足 。保证最终交互库中此函数的单次实现复杂度为 。
- 限制:该函数在单次
mapstar调用中,最多只能被调用 次。
本地测试
下载 [本地评测包](file://mapstar-kit.zip) 和 [原比赛下发样例](file://mapstar-samples.zip)。将你的实现保存为 mapstar.cpp,与评测包中的文件放在同一目录。
g++ grader.cpp mapstar.cpp -O2 -std=c++14 -o mapstar
./mapstar < example.in
本地评测器对每组输出一行。合法到达目标时输出操作次数 ,返回无解时输出 -2,返回有解但未达到目标时输出 -3,调用接口违反规则时输出 -1 并停止。若有多种构造,合法的 可以不同。
例如 example.in 中 ,初始唯一一行是 1,初始和目标的 均为 0,目标行是 0。调用两次 choose(0) 就会得到目标,评测器输出 2。
本地测试输入格式
下发文件中 grader.cpp 的输入格式如下:
第一行输入一个正整数,表示数据组数 。接下来会依次读入 组数据。
对于每一组数据:
第一行输入一个正整数表示 。
接下来的 行,每行输入 个用空格隔开的 或 ,第 行(相对于这 行而言)表示数组元素 。
接下来的一行(即第 行),先读入一个整数表示 是否为空( 表示空, 表示非空)。如果非空,则接下来继续输入 个 整数表示 。
接下来的一行(即第 行),先读入一个整数表示 是否为空。如果非空,接着输入 个整数表示 。
接下来的一行(即第 行),先读入一个整数表示 是否为空。如果非空,接着输入 个整数表示 。
在线提交
只需实现 mapstar,并通过 start 和 choose 与评测库交互。请勿自带 main 或操作标准输入输出。
计分
每个测试点满分 4 分,由该点所有数据组中最低的得分比例决定。接口调用违规或任一组有解性判断错误,该测试点为 0 分。正确判断无解的组按 100% 计。正确判断有解、但最终状态不符合要求的组按 25% 计。
正确达到目标时,设该组操作次数为 ,得分比例为
$$\frac{8.1 \times 10^6 - \max(K,4.1 \times 10^6)}{8 \times 10^6} + 0.5.$$Hydro 将每个测试点的分数向下取整,测试点之间独立计分。
数据范围与子任务
保证 $T\le 10,\sum\limits_{i=1}^Tn_i^2\le 3\times 10^7,\max\limits_{i=1}^Tn_i\le 2000$。
此题有 个子任务,子任务不捆绑,且每个测试点均分。
| 测试点数目 | |||||
|---|---|---|---|---|---|