题目背景
「{!@@(*@@¥’;l]dw@)%)%&^_^}(可恶的人类!我一定会回来的!)」
它将飞船拉到了最高速度,试图离开这个充满人类的地狱。
……
题目描述
过了那么多年,外星人的飞船速度早已比不过地球的飞船。因此,它决定使用折跃点逃离。
平面地图上有 nn 个折跃点,坐标分别为 (xi,yi)(xi,yi)。某些折跃点之间有双向空间隧道连接,共 mm 条隧道,每条隧道分别连接折跃点 ui,viui,vi,且激活该隧道需要消耗 wiwi 单位能量。请注意,为了保证空间隧道之间互不干扰,对于任意两条空间隧道 i,ji,j,都保证连接点 ui,viui,vi 与点 uj,vjuj,vj 的线段没有交点。
外星人的科技非常神奇,因此为了成功折跃离开,外星人必须经过地图上的所有折跃点 至少一次,它可以从任意一点开始折跃并从任意一点结束折跃,最终,外星人所花费的总能量为激活路径上所有隧道所消耗能量的 按位或运算和。经过两次或两次以上同一隧道只需激活一次该隧道。
外星人的飞船上拥有 xx 单位能量,因此,它所选择的折跃方案花费的总能量不能超过 xx。为了拦截外星人,地方可以执行以下操作任意多次:
- 选择一条连接 uu 和 vv 的双向隧道(你需要保证在点 uu 和 vv 之间存在双向隧道连接);
- 将激活它所需要的能量增加 ww(w≥0w≥0 且操作后激活该通道所需要的能量不能超过 231−1231−1)。
其中,u,v,wu,v,w 都可以自行指定。每次操作所需要的代价为 ww 的二进制表示下 11 的个数。(即 c++
中的 __builtin_popcount()
函数)
为了赎罪,你需要设计一种操作方案,使得外星人无法通过折跃逃离,并最小化该方案所需要的代价。
输入格式
从标准输入读入数据。
输入的第一行包含 11 个正整数 WW,表示该测试点的评分参数。
输入的第二行包含 33 个整数 n,m,xn,m,x,分别表示折跃点个数,双向隧道条数以及外星人飞船上拥有的能量。
第 33 至 (n+2)(n+2) 行,第 (i+2)(i+2) 行有 22 个整数 xi,yixi,yi,表示第 ii 个折跃点的坐标。
接下来 mm 行,每行 33 个整数 ui,vi,wiui,vi,wi,表示每条双向隧道连接的两个折跃点和激活所需能量。
输出格式
输出到标准输出。
本题采用自定义校验器(special judge)评测。
输出的第一行应包含一个非负整数 kk,表示操作总次数。
接下来 kk 行,每行一次操作,形如 u v wu v w,表示将激活连接 uu 和 vv 的双向隧道所需能量增加 ww。
你需要保证 0≤k≤100000≤k≤10000,否则将被判定为不合法答案。
输入输出样例
1 5 6 9 0 1 0 0 0 -1 -1 0 1 0 1 2 10 1 4 1 2 3 8 3 4 5 3 5 1 1 5 1
1 2 3 2
见附件中的 intercept2.in
见附件中的 intercept2.ans
见附件中的 intercept3.in
见附件中的 intercept3.ans
说明/提示
【样例解释】
- 样例 1 解释:
经过操作后的平面地图如下图所示(省略坐标轴):
由于与 22 号折跃点相连的空间隧道所需要的激活能量全部为 1010,所以成功折跃所需要的能量至少为 1010,因此外星人无法通过折跃逃离,代价为 11,显然不存在代价更小的操作方案。
【评分方式】
对于每个测试点,如果你的操作方案不合法或使得外星人能够成功通过折跃逃离,你将在该测试点得到 00分。
否则,设该测试点的评分参数为 WW,标准答案的代价为 aa,你的操作方案的代价为 bb,则你的分数 ss 将由下列公式给出:
s=max(1−b−aa×W,0)×10s=max(1−ab−a×W,0)×10
【数据范围】
对于 100%100% 的数据,12≤n≤5328012≤n≤53280,n−1≤m≤3n−6n−1≤m≤3n−6,0≤x<231−10≤x<231−1,0≤∣xi∣,∣yi∣≤3×1040≤∣xi∣,∣yi∣≤3×104,0≤wi<2310≤wi<231,1≤W≤10001≤W≤1000。
测试点编号 | n=n= | m=m= | W=W= | 数据随机生成 |
---|---|---|---|---|
11 | 1212 | 2626 | 10001000 | 否 |
22 | 1212 | 2626 | 11 | 是 |
33 | 200200 | 579579 | 22 | 是 |
44 | 500500 | 14821482 | 55 | 是 |
55 | 50005000 | 1497114971 | 55 | 否 |
66 | 50005000 | 1496214962 | 11 | 是 |
77 | 1065610656 | 3018830188 | 10001000 | 否 |
88 | 1065610656 | 3018830188 | 55 | 否 |
99 | 5328053280 | 150960150960 | 10001000 | 否 |
1010 | 5328053280 | 150960150960 | 10001000 | 否 |
【校验器】
为了方便测试,在 interceptintercept 目录下我们下发了 checker.cppchecker.cpp 文件。你可以编译该文件,并使用它校验自己的输出文件。请注意它与最终评测时所用的校验器并不完全一致,你不需要也不应该关心其代码的具体内容。
编译命令为:
g++ checker.cpp -o checker -std=c++14
使用方式为:
./checker <inputfile> <outputfile> <answerfile>
校验器可能会返回以下状态中的其中一种:
- acceptedaccepted:表示你的输出完全正确。
- points xpoints x:表示你的输出部分正确,可以在该测试点得到比例为 xx 的分数。
- wrong answerwrong answer:表示你在该测试点得到 00 分。
对于所有非 acceptedaccepted 状态,校验器接下来会输出以下信息中的一种:
- AA:表示你的输出不合法。
- B x yB x y:表示你的输出方案的代价为 xx,标准答案为 yy。
- CC:表示你的输出方案使得外星人能够成功通过折跃逃离。
【后记】
他知道,他将永远离开家乡了。他仍记得,在倒转时空前,指挥官最后的那句叮嘱。他花了几乎半辈子,终于建立了新的基地,重整了军队。他的目的,就是为了防止这一切重蹈覆辙。现在,基地被毁了,他被困在这暗淡无光的星系里。他终于醒悟了,一切都是早已被决定好的。
「指挥官,对不起。」
「舱室将在十秒后自毁。十。九。八。七……」
举起手枪,对准自己太阳穴。
「六。五。四。三……」
随着砰的一声,他无力地倒下了,眼里黯淡无光。
「二。一。」
巨响过后,无人将被铭记。
相关文章
- 1 信息学奥赛一本通1001:Hello,World答案及题解
- 2 信息学奥赛一本通C++练习题: 求10000以内n的阶乘
- 3 信息学奥赛一本通C++练习题: 大整数的因子
- 4 信息学奥赛一本通C++练习题: 计算2的N次方
- 5 信息学奥赛一本通C++练习题: 大整数减法
- 6 信息学奥赛一本通C++练习题: 大整数加法
- 7 信息学奥赛C++一本通练习题: 回文数。
- 8 2023年5月电子学会C语言等级考试1~8级真题及答案
- 9 单词分析:小蓝正在学习一门神奇的语言,这门语言
- 10 生理周期:给定时间为10,下次出现三个高峰同天的时间是12,则输出2
- 11 Scratch青少年等级考试一级编程题:猫捉老鼠
- 12 2023年5月青少年软件编程C语言三级等级考试
- 13 2023年3月电子学会Scratch等级考试试卷一级编程真题
- 14 回文日期:2020 年春节期间,有一个特殊的日期引起了大家的注意:
- 15 蓝桥杯比赛5道Scratch编程题答案及代码
- 16 2023年3月电子学会Scratch等级考试四级真题
- 17 2023年3月份的蓝桥杯STEMA测评真题
- 18 盈亏问题:假设有一群人买一件物品,如果每个人出a元,
- 19 Python编程等级考试真题彩色螺旋文字
- 20 Python等级考试试卷(五级)及答案
-
扫码下载安卓APP
-
微信扫一扫关注我们
微信扫一扫打开小程序
手Q扫一扫打开小程序
-
返回顶部
发表评论