#PQJ3494x17305. QOJ 3494_17305

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

QOJ 3494_17305

2026 联合省选 第二试星图(starmap) 星图(starmap) 【题目背景】 星图铺就的,未必是归途。 但有人循着它,便不算迷路。 【题目描述】 夜空中共有n 颗星辰,编号为1 ∼n。初始时,夜空中共有m 条光轨,其中第 i (0 ≤i < m) 条光轨连接星辰ui 与vi。 古籍中记载了一种神秘的仪式,可以改变夜空中的光轨的状态。具体地,每次举行 仪式时,需要选择.恰.好k 颗互不相同的星辰,然后改变这些星辰之间的光轨的状态。具 体地,设选择星辰的编号分别为s0, . . . , sk−1,则对于所有0 ≤i < j ≤k −1,若星辰si 与星辰sj 之间此时存在光轨,则该光轨会被删除;若不存在,则会新增一条连接它们 的光轨。由于仪式的耗材有限,这种仪式只能举行.至.多p (p ≥n(n −1)/2) 次。 当存在更多的光轨时,夜空也会变得更加璀璨。你需要求出在举行至多p 次仪式后, 夜空中光轨数量的最大值,并尽可能地给出一种相应的举行仪式的方案。 【实现细节】 .选.手.不.需.要,.也.不.应.该.实.现main .函.数。 选手需要确保提交的程序包含头文件starmap.h,即在程序开头加入以下代码: 1 #include "starmap.h" 选手需要在提交的程序源文件starmap.cpp 中实现以下两个函数: 1 void init(int c, int t); • c, t 分别表示测试点编号与测试数据组数。c = 0 表示该测试点为样例。 • 对于每个测试点,该函数会在.程.序.开.始.运.行.时被交互库调用.恰.好.一.次。 1 void starmap(int n, int m, int k, int p, std::vector u, std::vector v); • n, m, k, p 分别表示星辰数量、光轨数量、举行仪式时选择的星辰数量与举行仪式 的次数限制。 • 对于0 ≤i < m,ui, vi 表示初始时的第i 条光轨连接的两颗星辰。 • 对于每个测试点,该函数会被交互库调用.恰.好t .次。 选手可以通过调用以下函数报告光轨数量的最大值: 1 void report(int c); 第6 页 共16 页

2026 联合省选 第二试星图(starmap) • c 表示光轨数量的最大值。 • 选手需要保证交互库调用starmap 时,.恰.好.调.用.了.一.次.该.函.数。 选手可以通过调用以下函数举行一次仪式: 1 void invert(std::vector s); • s0, . . . , sk−1 表示选择的k 颗星辰。选手需要保证s 的长度为k,且对于所有 0 ≤i ≤k −1,1 ≤si ≤n,且s0, . . . , sk−1 互不相同。 • 选手需要保证交互库每次调用starmap 时,调用该函数的次数不超过p,且所 有该函数的调用.均.在.调.用report .函.数.之.后。 .注.意:.在.任.何.情.况.下,.最.终.测.试.时.所.用.的.交.互.库.运.行.所.需.时.间.均.不.会.超.过4.5 .秒, .所.用.内.存.为.固.定.大.小,.且.均.不.超.过64 MiB。 【测试程序方式】 .试.题.目.录.下.的grader.cpp .是.交.互.库.参.考.实.现,.最.终.测.试.时.所.用.的.交.互.库.实.现.与 .该.参.考.实.现.有.所.不.同,.因.此.选.手.的.解.法.不.应.该.依.赖.交.互.库.实.现。 选手可以在本题目录下使用如下命令编译得到可执行程序: 1 g++ grader.cpp starmap.cpp -o starmap -std=gnu++14 -O2 -static 对于编译得到的可执行程序: • 可执行文件将从.标.准.输.入读入以下格式的数据: – 输入的第一行包含两个非负整数c, t,分别表示测试点编号和测试数据组数。 – 接下来依次为每组测试数据,对于每组测试数据: ∗第一行包含四个正整数n, m, k, p,分别表示星辰数量、光轨数量、举行 仪式时选择的星辰数量与举行仪式的次数限制。 ∗第i + 2 (0 ≤i < m) 行包含两个非负整数ui, vi,表示初始时的第i 条 光轨连接的两颗星辰。 • 可执行文件将输出以下格式的数据至.标.准.输.出: – 对于每组测试数据,输出一行两个非负整数,分别表示光轨数量的最大值与 举行所有仪式后光轨数量是否与最大值相等。 本题包含两个小问,正确回答第一个小问,即report 函数报告的光轨数量的最大 值正确,则可获得部分分数。具体评分规则请参见【评分方式】。 【样例1 输入】 第7 页 共16 页

2026 联合省选 第二试星图(starmap) 1 0 1 2 4 2 2 20 3 1 2 4 2 3 【样例1 输出】 1 6 1 【样例2 输入】 1 0 1 2 6 1 3 20 3 1 2 【样例2 输出】 1 13 1 【样例3】 见选手目录下的starmap/starmap3.in 与starmap/starmap3.ans。 该样例满足测试点3, 4 的约束条件。 【样例4】 见选手目录下的starmap/starmap4.in 与starmap/starmap4.ans。 该样例满足测试点5 ∼7 的约束条件。 【样例5】 见选手目录下的starmap/starmap5.in 与starmap/starmap5.ans。 该样例满足测试点8 ∼10 的约束条件。 【样例6】 见选手目录下的starmap/starmap6.in 与starmap/starmap6.ans。 该样例满足测试点11 ∼13 的约束条件。 第8 页 共16 页

2026 联合省选 第二试星图(starmap) 【样例7】 见选手目录下的starmap/starmap7.in 与starmap/starmap7.ans。 该样例满足测试点17 ∼20 的约束条件。 【样例8】 见选手目录下的starmap/starmap8.in 与starmap/starmap8.ans。 该样例满足测试点21 ∼25 的约束条件。 【下发文件说明】 在本试题目录下:

  1. grader.cpp 是提供的交互库参考实现。
  2. starmap.h 是头文件,选手不用关心具体内容。
  3. template_starmap.cpp 是提供的示例代码,选手可参考并实现自己的代码。 .选.手.注.意.对.所.有.下.发.文.件.做.好.备.份。.最.终.评.测.时.只.测.试.本.试.题.目.录.下.的starmap.cpp, .对.该.程.序.以.外.文.件.的.修.改.不.会.影.响.评.测.结.果。 【数据范围】 设N 为单个测试点内所有测试数据的n 的和。对于所有测试数据,均有: • 1 ≤t ≤10; • 4 ≤n ≤500,N ≤3, 000; • 0 ≤m ≤n(n −1)/2,2 ≤k ≤n −2,n(n −1)/2 ≤p ≤2 × 105; • 对于所有0 ≤i ≤m −1,均有1 ≤ui < vi ≤n,且(u0, v0), . . . , (um−1, vm−1) 互 不相同。 测试点编号 n ≤ k p = 1, 2 8 ≤n −2 500 3, 4 18 5 ∼7 500 = 3 n(n −1)/2 8 ∼10 70 ≤n −2 11 ∼13 500 ≤70 14 ∼16 300 ≤n −2 2n2 + 5n 17 ∼20 400 n2 + 10n 21 ∼25 500 n(n −1)/2 第9 页 共16 页

2026 联合省选 第二试星图(starmap) 【评分方式】 .注.意: • 选手不应当通过非法方式获取交互库的内部信息,如直接与标准输入、输出流进 行交互。此类行为将被视为作弊; • .最.终.的.评.测.交.互.库.与.样.例.交.互.库.的.实.现.不.同。 .本.题.首.先.会.受.到.和.传.统.题.相.同.的.限.制,例如编译错误会导致整道题目得0 分,运行 时错误、超过时间限制、超过空间限制等会导致相应测试点得0 分等。选手只能在程序 中访问自己定义的变量以及交互库给出的变量,尝试访问其他地址空间将可能导致编译 错误或运行错误。 每次调用starmap 函数时,若report 函数或invert 函数调用不合法,或 invert 函数调用次数超过p 次,则相应测试点得0 分。 在上述条件基础上: • 对于每个测试点,若report 函数报告的光轨数量的最大值正确,则可以获得 25% 的分数; • 在此基础上,若举行所有仪式后光轨数量与最大值相等,则可以获得满分。 • .注.意:.若.报.告.的.光.轨.数.量.的.最.大.值.正.确,.然.而invert .函.数.调.用.次.数.超.过p .次, .则.仍.获.得0 .分。 第10 页 共16 页