#P15482. [2026四川省队集训]图星

    ID: 14697 交互题 2000ms 512MiB 尝试: 5 已通过: 1 难度: 9 上传者: 标签>图论贪心CF2700构造数学算法基础模拟

[2026四川省队集训]图星

图星

题目背景

可怜的 lzh\text{lzh} 宝宝被联合省选2026中星图这道题创飞了,事后想加害一下后人。

于是他出了一道有异或、有判断、有操作的交互题。

题目描述

这是一道交互库题。请使用 C++14 或更新版本,只提交实现 mapstar 函数的源文件。评测时 Hydro 会提供 mapstar.h 并调用你的函数。

给定一个长度为 nn 的数组 a0,a1,…,an−1a_0, a_1, \dots, a_{n-1},其中每个 aia_i 均为一个长度为 nn 的 01 序列(以布尔数组形式呈现)。另有一个长度同样为 nn 的全局 01 序列 zz,初始值为 initial_z\text{initial}\_\text{z}。

接下来你需要进行若干次操作。每次操作中,你可以选择一个整数 i (0≤i<n)i \ (0 \le i < n),随后交互库会依次执行以下两步:

  • ai←ai⊕za_{i} \leftarrow a_{i} \oplus z(即对 aia_{i} 和 zz 进行逐位异或)
  • 将 zz 的第 ii 位翻转(若将 zz 视为二进制数,即 z←z⊕2iz \leftarrow z \oplus 2^i)

你的目标是通过合理的操作序列,使得最终全局变量满足 z=final_zz = \text{final}\_\text{z},并且对于所有的 ii,都满足 ai=final_aa_{i} = \text{final}\_\text{a}。

需要注意的是,参数 $\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);
  • 参数 aa 是一个大小为 nn 的数组,每一个 aia_{i} 都是一个长度为 nn 的布尔数组。
  • 参数 $\text{initial}\_\text{z}, \text{final}\_\text{z}, \text{final}\_\text{a}$ 均有独立的两种可能
    • 一个长度为 nn 的布尔数组,表示固定好的状态
    • 一个空数组,表示你可以自行决定值
  • 每个测试点,mapstar 函数会被调用恰好 TT 次,你需要判断是否有解
    • 如果无解,则应该直接返回 false
    • 如果有解,则需要在函数结束之前先调用恰好一次 start,接下来若干次 choose,最后返回 true

在实现过程中,你可以调用以下两个交互库函数:

void start(std::vector<bool> initial_z, std::vector<bool> final_z, std::vector<bool> final_a);
  • 此函数用于确认以上三个参数的值,传入的三个参数必须均为长度为 nn 的布尔数组。
  • 你需要保证:如果题目传入的 $\text{initial}\_\text{z}, \text{final}\_\text{z}, \text{final}\_\text{a}$ 初始不为空,你必须将原数组原样传回;如果为空,则传回你自行选定的状态。
void choose(int i);
  • 表示选择一个下标 ii 进行一次题面所述的操作,必须满足 0≤i<n0 \le i < n。保证最终交互库中此函数的单次实现复杂度为 O(1)\mathcal{O}(1)。
  • 限制:该函数在单次 mapstar 调用中,最多只能被调用 8.1×1068.1 \times 10^{6} 次。

本地测试

下载 [本地评测包](file://mapstar-kit.zip) 和 [原比赛下发样例](file://mapstar-samples.zip)。将你的实现保存为 mapstar.cpp,与评测包中的文件放在同一目录。

g++ grader.cpp mapstar.cpp -O2 -std=c++14 -o mapstar
./mapstar < example.in

本地评测器对每组输出一行。合法到达目标时输出操作次数 KK,返回无解时输出 -2,返回有解但未达到目标时输出 -3,调用接口违反规则时输出 -1 并停止。若有多种构造,合法的 KK 可以不同。

例如 example.in 中 n=1n=1,初始唯一一行是 1,初始和目标的 zz 均为 0,目标行是 0。调用两次 choose(0) 就会得到目标,评测器输出 2。

本地测试输入格式

下发文件中 grader.cpp 的输入格式如下:

第一行输入一个正整数,表示数据组数 TT。接下来会依次读入 TT 组数据。

对于每一组数据:

第一行输入一个正整数表示 nn。

接下来的 nn 行,每行输入 nn 个用空格隔开的 00 或 11,第 ii 行(相对于这 nn 行而言)表示数组元素 ai−1a_{i-1}。

接下来的一行(即第 n+2n+2 行),先读入一个整数表示 initial_z\text{initial}\_\text{z} 是否为空(00 表示空,11 表示非空)。如果非空,则接下来继续输入 nn 个 0/10/1 整数表示 initial_z\text{initial}\_\text{z}。

接下来的一行(即第 n+3n+3 行),先读入一个整数表示 final_z\text{final}\_\text{z} 是否为空。如果非空,接着输入 nn 个整数表示 final_z\text{final}\_\text{z}。

接下来的一行(即第 n+4n+4 行),先读入一个整数表示 final_a\text{final}\_\text{a} 是否为空。如果非空,接着输入 nn 个整数表示 final_a\text{final}\_\text{a}。

在线提交

只需实现 mapstar,并通过 start 和 choose 与评测库交互。请勿自带 main 或操作标准输入输出。

计分

每个测试点满分 4 分,由该点所有数据组中最低的得分比例决定。接口调用违规或任一组有解性判断错误,该测试点为 0 分。正确判断无解的组按 100% 计。正确判断有解、但最终状态不符合要求的组按 25% 计。

正确达到目标时,设该组操作次数为 KK,得分比例为

$$\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$。

此题有 88 个子任务,子任务不捆绑,且每个测试点均分。

Subtask\text{Subtask} 测试点数目 initial_z=∅\text{initial}\_\text{z} = \varnothing final_z=∅\text{final}\_\text{z} = \varnothing final_a=∅\text{final}\_\text{a} = \varnothing pts\text{pts}
Subtask 1\text{Subtask 1} 11 False\text{False} False\text{False} False\text{False} 4 pts4 \ \text{pts}
Subtask 2\text{Subtask 2} 22 True\text{True} 8 pts8 \ \text{pts}
Subtask 3\text{Subtask 3} True\text{True} False\text{False}
Subtask 4\text{Subtask 4} 33 True\text{True} 12 pts12 \ \text{pts}
Subtask 5\text{Subtask 5} 22 True\text{True} False\text{False} False\text{False} 8 pts8 \ \text{pts}
Subtask 6\text{Subtask 6} 33 True\text{True} 12 pts12 \ \text{pts}
Subtask 7\text{Subtask 7} True\text{True} False\text{False}
Subtask 8\text{Subtask 8} 99 True\text{True} 36 pts36 \ \text{pts}