#2136. 三色花园
三色花园
三色花园
题目描述
第二试三色花园(garden) IOI2026 中国国家队选拔 三色花园(garden) .这.是.一.道.通.信.题。 【题目描述】 Alice 经营着一个美丽的花园,其中有n 个供游客用餐与休息的休息厅,编号从1 到n。这些休息厅之间连接着一些花廊,供游客们赏花与在休息厅之间通行。花廊里种 植着三种不同颜色的花朵,每座花廊里恰好种植着其中一种颜色的花。为了保证游览的 秩序,对于.任.意.两.个不同的休息厅u, v (1 ≤u < v ≤n),休息厅u 与休息厅v 之间.恰 .好连接着一个只能.单.向.通.行的花廊,即花廊的通行方向要么为u →v,要么为v →u。 游客在花园里赏花时,会选择一系列互不相同的休息厅,并按照顺序环绕这些休息 厅一圈。具体地,游客会选择l (l ≥3) 个休息厅a1, . . . , al,然后按照a1 →a2 →· · · → al →a1 的顺序游览这些休息厅间的花廊。由于花廊的通行方向限制,可行的游览方式 很少。定义a1, . . . , al 为一种.游.览.方.式当且仅当l ≥3,a1, . . . , al 互不相同,且对于所 有1 ≤i ≤l,连接休息厅ai 与a(i mod l)+1 的花廊的通行方向为ai →a(i mod l)+1。两 种游览方式a1, . . . , al 与b1, . . . , bl .本.质.不.同当且仅当两种可行游览方式经过的花廊不 同,或.环.绕.的.路.径.不.同,即l1̸ = l2 或对于任意0 ≤x < l1,均存在0 ≤y < l1 满足 ay̸ = b(y+x−1) mod l1+1。 对于一种游览方式,游客将会观赏到不同颜色的花朵。若游览方式中经过的花廊包 括所有三种颜色的花朵,则游客会对此感到满意,否则会对此感到不满。为了确保游客 的游览体验,对于每个休息厅,经过该休息厅的游览方式中,.至.多.只.有k .种.本.质.不.同.的 .游.览.方.式.会.使.游.客.感.到.不.满。 Bob 也想经营一个和Alice 一样的花园,于是他找来了Alice 的花园设计图纸,同 样修建了一个有n 个休息厅的花园。然而,Alice 丢失了花廊的设计图纸。Bob 希望他 修建的花园的.花.廊.的.布.局.与.通.行.方.向.均.与Alice .的.花.园.相.同,且同样对于每个休息厅, 经过该休息厅的游览方式中,至多只有k 种本质不同的游览方式会使游客感到不满。.注 .意:.花.廊.种.植.的.花.朵.的.颜.色.不.需.要.完.全.相.同,.只.需.要.满.足.上.述.条.件.即.可。 为了尽快完成修建,Alice 需要向Bob 发送尽可能少的信息,让Bob 能够按照要求 建立花廊。具体地,Alice 可以向Bob 传输一个长度为l 的01 串,Bob 需要通过这个 01 串修建他的花园的花廊,即确定每两个休息厅间花廊的通行方向与种植的花朵的颜 色。你需要帮助Alice 发送尽可能少的信息,并帮助Bob 通过这些信息修建他的花园的 花廊。 【实现细节】 .选.手.不.需.要,.也.不.应.该.实.现main .函.数。 选手需要确保提交的程序包含头文件garden.h,即在程序开头加入以下代码: #include "garden.h" 1 第6 页 共14 页 第二试三色花园(garden) IOI2026 中国国家队选拔 选手需要在提交的程序源文件中实现以下三个函数: int init(int n, int k); 1 • n, k 分别表示休息厅的数量与使游客感到不满的游览方式的数量上限。 • 该函数需要返回一个非负整数l,表示Alice 向Bob 传输的01 串的长度。选手 需要保证0 ≤l ≤1.5 × 105。 • 对于每个测试点,该函数会在.程.序.第.一.次.开.始.运.行.时被交互库调用.恰.好.一.次。 std::string send_message(int n, int k, 1 std::vector<std::vector<std::pair<bool, int>>> e); • n, k 分别表示休息厅的数量与使游客感到不满的游览方式的数量上限。 • 对于0 ≤i ≤n −2,0 ≤j ≤n −i −2,ei,j 表示Alice 的花园中连接休息厅i + 1 与休息厅i + j + 2 的花廊的通行方向与种植的花朵的颜色。具体地,ei,j 是一个 二元组, – 若ei,j 的第一个元素为true,则该花廊的通行方向为i + 1 →i + j + 2,否 则为i + j + 2 →i + 1; – ei,j 的第二个元素是一个{0, 1, 2} 中的非负整数,表示连接休息厅i + 1 与 休息厅i + j + 2 的花廊种植的花朵的颜色。 • 该函数需要返回一个长度为l 的01 字符串s,表示Alice 向Bob 传输的01 串。 选手需要保证s 的长度与init 函数的返回值相同。 • 对于每个测试点,该函数会被.程.序.第.一.次.运.行.时被交互库调用.恰.好10 .次,且传 入该函数中的变量n, k 与传入init 函数中的变量n, k 相同。 std::vector<std::vector<std::pair<bool, int>>> 1 build_flower_garden(int n, int k, std::string s); • n, k, s 分别表示休息厅的数量、使游客感到不满的游览方式的数量上限与Alice 向Bob 传输的01 串。 • 该函数需要返回Bob 修建的花园中花廊的通行方向与种植的花朵的颜色,表示 方法与传入send_message 函数中的变量e 一致。选手需要保证: – e 的长度为n −1; – 对于0 ≤i ≤n −2,ei 的长度为n −i −1; – 对于0 ≤i ≤n −2,0 ≤j ≤n −i −2,ei,j 的第二个元素是一个{0, 1, 2} 中 的非负整数。 • 对于每个测试点,该函数会被.程.序.第.二.次.运.行.时被交互库调用.恰.好10 .次,且 传入该函数中的变量的n, k 与程序第一次运行时传入init 函数中的变量n, k 相同,且第c (1 ≤c ≤10) 次传入该函数中的变量s 与程序第一次运行时第 c (1 ≤c ≤10) 次send_message 函数的返回值相同。 第7 页 共14 页 第二试三色花园(garden) IOI2026 中国国家队选拔 • 选手还需要保证: – 对于1 ≤c ≤10,0 ≤i ≤n −2,0 ≤j ≤n −i −2,程序第一次运行时第 c 次传入send_message 函数的ei,j 的第一个元素与程序第二次运行时第c 次build_flower_garden 函数的返回值的ei,j 的第一个元素相同。 – 按照该函数返回值修建的花廊满足对于每个休息厅,经过该休息厅的游览方 式中至多只有k 种本质不同的游览方式会使游客感到不满。 .注.意:.在.任.何.情.况.下,.交.互.库.运.行.所.需.时.间.均.不.会.超.过0.2 .秒,.所.用.内.存.为.固.定.大 .小,.且.均.不.超.过64 MiB。 【测试程序方式】 .试.题.目.录.下.的stub.cpp .是.交.互.库.参.考.实.现,.最.终.测.试.时.所.用.的.交.互.库.实.现.与.该.参 .考.实.现.有.所.不.同,.因.此.选.手.的.解.法.不.应.该.依.赖.交.互.库.实.现。 选手可以在本题目录下使用如下命令进行测试: bash run.sh garden.cpp 1 • 上述脚本将从.标.准.输.入读入以下格式的数据: – 输入的第一行包含三个正整数t, n, k,分别表示测试数据组数,休息厅的数 量与使游客感到不满的游览方式的数量上限。 – 输入的第i + 1 (1 ≤i ≤n −1) 行包含n −i 个非负整数,其中第j (1 ≤j ≤ n −i) 个非负整数表示连接休息厅i 与休息厅i + j 的花廊的通行方向,若 为1 则该花廊的通行方向为i + 1 →i + j + 2,否则为i + j + 2 →i + 1; – 输入的第i + n (1 ≤i ≤n −1) 行包含n −i 个非负整数,其中第j (1 ≤j ≤ n −i) 个非负整数表示连接休息厅i 与休息厅i + j 的花廊种植的花朵的颜 色。 • 上述脚本将输出以下格式的数据至.标.准.输.出: – 输出的第一行包含一个非负整数l,表示Alice 向Bob 传输的01 串的长度。 – 输出的第二行包含一个[0, 1] 间的实数p,表示该测试点的得分比例。 【样例1】 见题目目录下的1.in 与1.ans。 该样例满足子任务1 的约束条件。 【样例2】 见题目目录下的2.in 与2.ans。 该样例满足子任务2 的约束条件。 第8 页 共14 页 第二试三色花园(garden) IOI2026 中国国家队选拔 【样例3】 见题目目录下的3.in 与3.ans。 该样例满足子任务3 的约束条件。 【附加文件说明】 在附加文件中:
- stub.cpp 是提供的交互库参考实现。
- garden.h 是头文件,选手不用关心具体内容。
- template_garden.cpp 是提供的示例代码,选手可参考并实现自己的代码。
- bigint.cpp 是提供的高精度模板,选手可参考并使用。
- bigint.pdf 是提供的高精度模板使用说明。 【子任务】 对于所有测试数据,均有: • t = 10,n = 300,0 ≤k ≤2; • 所有花廊的通行方向为{0, 1} 中的非负整数; • 所有花廊种植的花朵的颜色为{0, 1, 2} 中的非负整数。 子任务编号 分值 k = 1 0 30 2 1 3 40 2 【评分方式】 .注.意: • 选手不应当通过非法方式获取交互库的内部信息,如直接与标准输入、输出流进 行交互。此类行为将被视为作弊; .最.终.的.评.测.交.互.库.与.样.例.交.互.库.的.实.现.不.同。 • .本.题.首.先.会.受.到.和.传.统.题.相.同.的.限.制,例如编译错误会导致整道题目得0 分,运行 时错误、超过时间限制、超过空间限制等会导致相应测试点得0 分等。选手只能在程序 中访问自己定义的变量以及交互库给出的变量,尝试访问其他地址空间将可能导致编译 错误或运行错误。 若init 函数的返回值或send_message 函数的返回值或build_flower_garden 函数的返回值不合法,则相应测试点得0 分。 在上述条件基础上: 第9 页 共14 页 第二试三色花园(garden) IOI2026 中国国家队选拔 • 对于每个测试点,设B 为该测试点所属子任务的参数,l 为init 函数的返回值, 则该测试点的得分比例如下表所示: 子任务编号 B = 1 6, 200 2 6, 800 3 8, 000 得分比例 l ∈ (5 + 15 × (1.5 × 105 −l) ÷ (105 −B)) % [B + 5 × 104, 1.5 × 105] (20 + (B + 5 × 104 −l) ÷ 2000) % [B + 104, B + 5 × 104) (40 + (B + 104 −l) ÷ 400) % [B + 2 × 103, B + 104) (60 + (B + 2 × 103 −l) ÷ 50) % (B, B + 2 × 103) 100% [0, B] • 每个测试点的得分为得分比例与该测试点所属子任务的分值的乘积。 第10 页 共14 页
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
(本题数据包未提供小体积样例)