#PQJ3494x17304. QOJ 3494_17304

    ID: 2931 传统题 2000ms 1024MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:二十七省联合省选2026二分答案

QOJ 3494_17304

2026 联合省选 第二试排列游戏(perm) 排列游戏(perm) .这.是.一.道.交.互.题。 【题目描述】 小H 和小L 正在玩一个猜排列的游戏。 小H 有一个0 ∼n −1 的排列p = [p0, p1, . . . , pn−1]。现在小L 知道了排列的长度 n,他希望通过特定的询问方式猜出这个排列p。具体地,小L 可以向小H 提出如下形 式的询问: • 给定非负整数l, r 满足0 ≤l ≤r ≤n −1,求pl, . . . , pr 中.未.出.现.过.的.最.小.非.负.整 .数。 不过小H 和小L 发现,即便可以进行任意多次询问,有时也不足以唯一确定这个 排列p。于是两人约定:假设小H 的答案是p,而小L 猜测的排列是q,如果在p 和q 这两个排列中,对于任意0 ≤l ≤r ≤n −1,区间pl, . . . , pr 中未出现过的最小非负整 数,始终等于区间ql, . . . , qr 中未出现过的最小非负整数,那么就认为小L 的猜测是正 确的。 为了增加游戏的难度,小H 限制了小L 的询问次数。你需要帮助小L 猜出小H 的 排列。 【实现细节】 .选.手.不.需.要,.也.不.应.该.实.现main .函.数。 选手需要确保提交的程序包含头文件perm.h,即在程序开头加入以下代码: 1 #include "perm.h" 选手需要在提交的程序源文件perm.cpp 中实现以下两个函数: 1 void init(int c, int t); • c, t 分别表示测试点编号与测试数据组数。c = 0 表示该测试点为样例。 • 对于每个测试点,该函数会在.程.序.开.始.运.行.时被交互库调用.恰.好.一.次。 1 std::vector perm(int n); • n 表示排列的长度。 • 该函数需要返回一个0 ∼n −1 的排列,表示小L 的猜测。 • 对于每个测试点,该函数会被交互库调用.恰.好t .次。 选手可以通过调用以下函数进行一次询问: 1 int query(int l, int r); • l, r 表示询问的区间。选手需要保证0 ≤l ≤r ≤n −1。 第2 页 共16 页

2026 联合省选 第二试排列游戏(perm) • 该函数会返回pl, . . . , pr 中未出现过的最小非负整数。 • 选手需要保证交互库每次调用perm 时,调用该函数的次数不超过6 × 105。 .注.意:.在.任.何.情.况.下,.最.终.测.试.时.所.用.的.交.互.库.运.行.所.需.时.间.均.不.会.超.过0.1 .秒, .所.用.内.存.为.固.定.大.小,.且.均.不.超.过64 MiB。 【测试程序方式】 .试.题.目.录.下.的grader.cpp .是.交.互.库.参.考.实.现,.最.终.测.试.时.所.用.的.交.互.库.实.现.与 .该.参.考.实.现.有.所.不.同,.因.此.选.手.的.解.法.不.应.该.依.赖.交.互.库.实.现。 选手可以在本题目录下使用如下命令编译得到可执行程序: 1 g++ grader.cpp perm.cpp -o perm -std=gnu++14 -O2 -static 对于编译得到的可执行程序: • 可执行文件将从.标.准.输.入读入以下格式的数据: – 输入的第一行包含两个非负整数c, t,分别表示测试点编号和测试数据组数。 – 接下来依次为每组测试数据,对于每组测试数据: ∗第一行包含一个正整数n,表示排列的长度。 ∗第二行包含n 个非负整数p0, p1, . . . , pn−1,表示小H 的排列。 • 可执行文件将输出以下格式的数据至.标.准.输.出: – 对于每组测试数据: ∗第一行包含一个字符串,表示测试的结果。其中, · Correct. 表示选手返回的结果正确; · Wrong answer. 表示选手返回的结果错误; · Invalid operation. 表示选手对query 函数的调用不合法。 ∗若结果为Correct.,则第二行包含一个非负整数,表示选手在所有测 试数据中调用query 函数的次数的最大值。 【样例1 输入】 1 0 1 2 6 3 4 2 3 5 0 1 【样例1 输出】 1 Correct. 2 4 第3 页 共16 页

2026 联合省选 第二试排列游戏(perm) 【样例1 解释】 该样例共包含一组测试数据。 对于第一组测试数据,小H 的排列为p = [4, 2, 3, 5, 0, 1]。 以下是一种可能的交互过程: • 调用query(0, 3),交互库返回4, 2, 3, 5 中未出现过的最小非负整数0。 • 调用query(3, 4),交互库返回5, 0 中未出现过的最小非负整数1。 • 调用query(1, 5),交互库返回2, 3, 5, 0, 1 中未出现过的最小非负整数4。 • 调用query(3, 5),交互库返回5, 0, 1 中未出现过的最小非负整数2。 • 返回q = [4, 2, 5, 3, 0, 1]。 可以证明,排列q 被认为是正确的。 【样例2】 见选手目录下的perm/perm2.in 与perm/perm2.ans。 该样例满足测试点4 ∼8 的约束条件。 【下发文件说明】 在本试题目录下:

  1. grader.cpp 是提供的交互库参考实现。
  2. perm.h 是头文件,选手不用关心具体内容。
  3. template_perm.cpp 是提供的示例代码,选手可参考并实现自己的代码。 .选.手.注.意.对.所.有.下.发.文.件.做.好.备.份。.最.终.评.测.时.只.测.试.本.试.题.目.录.下.的perm.cpp, .对.该.程.序.以.外.文.件.的.修.改.不.会.影.响.评.测.结.果。 【数据范围】 对于所有测试数据,均有: • t = 10; • 2 ≤n ≤3 × 104; • 对于所有0 ≤i ≤n −1,均有0 ≤pi ≤n −1,且p 是0 ∼n −1 的排列。 测试点编号 n = 特殊性质 1 ∼3 10 无 4 ∼8 102 9, 10 3 × 104 A 11, 12 B 13, 14 C 15 ∼20 无 第4 页 共16 页

2026 联合省选 第二试排列游戏(perm) 特殊性质A:p0 = 0。 特殊性质B:存在非负整数k ∈[0, n −1] 满足p0, . . . , pk 单调递减,且pk, . . . , pn−1 单调递增。 特殊性质C:p 在所有0 ∼n −1 的排列中.独.立.均.匀.随.机生成。 【评分方式】 .注.意: • 选手不应当通过非法方式获取交互库的内部信息,如直接与标准输入、输出流进 行交互。此类行为将被视为作弊; • .最.终.的.评.测.交.互.库.与.样.例.交.互.库.的.实.现.不.同。 .本.题.首.先.会.受.到.和.传.统.题.相.同.的.限.制,例如编译错误会导致整道题目得0 分,运行 时错误、超过时间限制、超过空间限制等会导致相应测试点得0 分等。选手只能在程序 中访问自己定义的变量以及交互库给出的变量,尝试访问其他地址空间将可能导致编译 错误或运行错误。 每次调用perm 函数时,若返回的排列不被认为是正确的,或query 函数调用不 合法,或query 函数调用次数超过6 × 105,则相应测试点得0 分。 在上述条件基础上: • 在测试点1 ∼3 中,程序得到满分当且仅当每次调用perm 函数时,query 函数 调用次数不超过102。 • 在测试点4 ∼8 中,设m 表示每次调用perm 函数时的询问次数的最大值,则 程序将获得5 · f(m) 分,其中f 的计算方式如下表所示: m f(m) = m ≤100 1 100 < m ≤200 1 − √m−100 50 200 < m ≤4950 0.8 − √m−200 170 m > 4950 0 • 在测试点9 ∼20 中,设m 表示每次调用perm 函数时的询问次数的最大值,则 程序将获得5 · g(m) 分,其中g 的计算方式如下表所示: m g(m) = m ≤30000 1 30000 < m ≤30015 1 − 7(m−30000) 5(5m−149991) 30015 < m ≤60000 0.75 − √m−30015 700 m > 60000 0.5 − √m−60000 2500 第5 页 共16 页