#PQJ3343x17206. QOJ 3343_17206

    ID: 2921 传统题 3000ms 1024MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:CTS 2026最小生成树

QOJ 3343_17206

第二试信号连接(signal) IOI2026 中国国家队选拔 信号连接(signal) 【题目描述】 太空中有n 个通信站,编号为1 ∼n。每个通信站均有两个参数,其中通信站 i (1 ≤i ≤n) 的发射系数为ai,接收系数为bi。 若通信站i (1 ≤i ≤n) 向通信站j (1 ≤j ≤n) 发射信号,则这两个通信站间会建 立起.双.向信号连接,所需代价为aibj。由于通信站可能吸收宇宙射线中的能量,因此所 需代价可能为负数。若要在通信站i, j (1 ≤i, j ≤n) 间建立双向信号连接,可以任选其 中一个通信站作为发射方发起连接,故最小代价为min(aibj, ajbi)。当两个通信站间直接 建立了信号连接,或通过其他通信站间接建立了信号连接,这两个通信站便可以加入同 一个通信系统中。 为了减少成本,往往只有一部分的通信站处于运作状态。你需要求出,对于编号处 于区间l ∼r 中的通信站,当.只.有.这.些.通.信.站.间.可.以.建.立.信.号.连.接时,.建.立.尽.可.能.少.的 .信.号.双.向.连.接将这些通信站全部加入同一个通信系统的最小代价。 【实现细节】 .选.手.不.需.要,.也.不.应.该.实.现main .函.数。 选手需要确保提交的程序包含头文件signal.h,即在程序开头加入以下代码: #include "signal.h" 1 选手需要在提交的程序源文件中实现以下两个函数: void signal(int n, std::vector a, std::vector b); 1 • n 表示通信站的个数。 • 对于1 ≤i ≤n,ai 表示通信站i 的发射系数,bi 表示通信站i 的接收系数。.注 .意:a, b .是.两.个.长.度.为n + 1 .的.序.列,.其.中a0, b0 .无.实.际.含.义。 .注.意:.对.于.每.个.测.试.点,.该.函.数.可.能.会.被.交.互.库.调.用.多.次。 • long long mincost(int l, int r); 1 • l, r 表示处于运作状态的通信站的编号区间。 • 该函数需要返回建立尽可能少的信号双向连接将这些通信站全部加入同一个通 信系统的最小代价。 • 注意:通信站的发射系数与接收系数为.最.近.一.次调用signal 函数时传入的参数。 • 所有该函数的调用.均.在.调.用.至.少.一.次signal .函.数.之.后。 .注.意:.在.任.何.情.况.下,.交.互.库.运.行.所.需.时.间.均.不.会.超.过0.1 .秒,.所.用.内.存.为.固.定.大 .小,.且.均.不.超.过64 MiB。 第11 页 共14 页 第二试信号连接(signal) IOI2026 中国国家队选拔 【测试程序方式】 .试.题.目.录.下.的grader.cpp .是.交.互.库.参.考.实.现,.最.终.测.试.时.所.用.的.交.互.库.实.现.与.该 .参.考.实.现.有.所.不.同,.因.此.选.手.的.解.法.不.应.该.依.赖.交.互.库.实.现。 选手可以在本题目录下使用如下命令编译得到可执行程序: g++ grader.cpp signal.cpp ‐o signal ‐std=gnu++14 ‐O2 ‐pipe ‐static 1 ‐s 对于编译得到的可执行程序: • 可执行文件将从.标.准.输.入读入以下格式的数据: – 输入的第一行包含一个正整数t,表示测试数据组数。 – 接下来依次为每组测试数据,对于每组测试数据: ∗第一行包含两个正整数n, q,分别表示通信站的个数与询问的次数。 ∗第二行包含n 个整数a1, . . . , an,分别表示每个通信站的发射系数。 ∗第三行包含n 个整数b1, . . . , bn,分别表示每个通信站的接收系数。 ∗第i + 3 (1 ≤i ≤q) 行包含两个正整数l, r,表示第i 次询问时处于运作 状态的通信站的编号区间。 • 可执行文件将输出以下格式的数据至.标.准.输.出: – 对于每组测试数据,输出一行q 个整数,分别表示每次询问时建立尽可能少 的信号双向连接将处于运作状态的通信站全部加入同一个通信系统的最小 代价。 【样例1 输入】 2 1 3 1 2 1 1 4 3 5 1 4 4 1 3 5 5 2 6 3 1 4 ‐1 ‐5 7 9 2 ‐6 5 ‐3 8 1 4 9 2 5 10 【样例1 输出】 第12 页 共14 页 第二试信号连接(signal) IOI2026 中国国家队选拔 5 1 ‐33 ‐47 2 【样例1 解释】 该样例共包含两组测试数据。 对于第一组测试数据,询问时所有的通信站均处于运作状态,可以从通信站1 向通 信站2, 3 发射信号,所需代价为1 × 1 + 1 × 4 = 5。此时所有通信站可以全部加入同一 个通信系统。 【附加文件说明】 在附加文件中:

  1. grader.cpp 是提供的交互库参考实现。
  2. signal.h 是头文件,选手不用关心具体内容。
  3. template_signal.cpp 是提供的示例代码,选手可参考并实现自己的代码。 【子任务】 设N, Q 分别表示单个测试点中所有测试数据的n, q 的和。对于所有测试数据,均 有: • 1 ≤t ≤105; • 1 ≤n, q ≤105,N, Q ≤105; • 对于所有1 ≤i ≤n,均有|ai|, |bi| ≤106; • 1 ≤l ≤r ≤n。 子任务编号 分值 特殊性质 N, Q ≤ 无 102 1 3 A 2 7 B 3 11 5, 000 无 4 13 A 5 14 105 B 6 16 无 7 36 特殊性质A:对于所有1 ≤i ≤n,均有ai, bi > 0。 特殊性质B:对于所有1 ≤i ≤n,均有aibi < 0。 第13 页 共14 页 第二试信号连接(signal) IOI2026 中国国家队选拔 【评分方式】 .注.意: • 选手不应当通过非法方式获取交互库的内部信息,如直接与标准输入、输出流进 行交互。此类行为将被视为作弊; .最.终.的.评.测.交.互.库.与.样.例.交.互.库.的.实.现.不.同。 • .本.题.首.先.会.受.到.和.传.统.题.相.同.的.限.制,例如编译错误会导致整道题目得0 分,运行 时错误、超过时间限制、超过空间限制等会导致相应测试点得0 分等。选手只能在程序 中访问自己定义的变量以及交互库给出的变量,尝试访问其他地址空间将可能导致编译 错误或运行错误。 在上述条件基础上: • 对于每个测试点,程序得到满分当且仅当每次调用mincost 函数时返回的答案 均正确。 第14 页 共14 页