NOIP 模拟赛 星际跃迁(wander) 星际跃迁(wander) 在遥远的未来,人类已经掌握了星际跃迁技术。小 A 是一名星际探险家,他需要在 星际跃迁网络上进行跃迁。整个网络由 n 个星球组成,这些星球之间有 m 条单向跃迁 通道,每条通道只能从编号较小的星球跃迁到编号较大的星球。小 A 从 1 号星球出发, 目标是到达 n 号星球。一旦到达 n 号星球,小 A 就会停止跃迁。为了保证小 A 的跃迁 路径不重复,不存在两条跃迁通道连接的两个星球均相同。因此,小 A 从 1 号星球到 n 号星球的不同跃迁路径数量恰好为 X 条。 然而,一场突如其来的宇宙风暴摧毁了星际跃迁网络,只留下了一个数字:X。你 能通过这个 X 还原出小 A 曾经使用的星际跃迁网络吗?由于可能的网络结构多种多样, 你只需要还原出任意一个符合条件的网络即可。 Ps:虽然星际跃迁网络已被摧毁,但小 A 依稀记得这个网络的规模很小,因此他希 望还原的网络规模越小越好(具体要求见数据范围与评分细则)。 【输入格式】 共一行一个整数 X。 【输出格式】 第一行两个整数 n, m,分别代表你给出的星际跃迁网络的星球数量和跃迁通道数 量。你需要保证 2 ≤ n ≤ 2 × 105 , 1 ≤ m ≤ 2 × 105。 接下来 m 行,第 i 行两个整数 ui , vi,代表你还原的星际跃迁网络的第 i 条跃迁通 道,你需要保证 1 ≤ ui < vi ≤ n,且这 m 条跃迁通道必须两两不同。 同一行相邻两个整数之间需要以单个空格隔开。 【样例 1 输入】 1 3 【样例 1 输出】 1 5 6 2 1 2 3 1 4 4 1 5 5 2 3 6 3 5 7 4 5 第 2 页 共 11 页 NOIP 模拟赛 星际跃迁(wander) 【说明/提示】 【样例 #1 解释】 上图为样例 #1 的输出的结果,显然从 1 号星球到 n 号星球共有 3 条跃迁路径符 合题目要求,且 n = 5 ≤ 62,故该答案可以获得满分。 除此之外,还有各式各样的建图方法可以获得满分,这里不再举例。 【Special Judge】 本题采用 Special Judge,下发的 checker.exe 包含在文件夹 wander 中,选手可以 用其来得知某数据点的得分,使用方式为在该文件所在目录下使用如下指令: 1 checker.exe 其中 为输入文件名, 为输出文件名, 为答案文件名(在本题中无需用到,所以你可以任意填写一个文件名,但不能为空)。 例如,输入文件为 wander.in,输出文件为 wander.out 时,调用 checker.exe 的 命令可以为: 1 checker.exe wander.in wander.out wander.out 如果你不会使用命令行,你可以打开 C++ 并调用下列语句: 1 system("checker.exe "); 关于 checker.exe 的输出结果: • 若得到 ok the number of from 1 to n on your graph is X and the number of points on your graph is in [2,62].,则说明该输出可得到 5 分。 • 若得到 points 0.40 the number from 1 to n of your graph is X and the number of points on your graph is in (62,2000].,则说明该输出可得到 2 分。 • 若得到 points 0.20 the number from 1 to n of your graph is X and the number of points on your graph is in (2000,200000].,则说明该输出可得 到 1 分。 • 若得到其它结果,则说明该输出不得分。 第 3 页 共 11 页 NOIP 模拟赛 星际跃迁(wander) 保证最终评测时使用的 checker.exe 与下发文件中的 checker.exe 相同。 【数据范围与评分细则】 对于全部测试点,1 ≤ X ≤ 1018,每个测试点满分 5 分。 对于每个测试点,如果你给出的星际跃迁网络不符合题目要求,那么你将得到 0 分。 否则,若给出的星际跃迁网络的星球数量 n ≤ 62,那么你将得到 5 分。 否则,若给出的星际跃迁网络的星球数量 n ≤ 2000,那么你将得到 2 分。 否则,你将得到 1 分。 测试点编号 X 1 ∼ 3 ≤ 61 4 ∼ 5 ≤ 1000 6 ≤ 109 且为 2 的整数次幂 7 ≤ 1018 且为 2 的整数次幂 8 ∼ 15 ≤ 109 16 ∼ 20 ≤ 1018 第 4 页 共 11 页 NOIP 模拟赛 星环宝藏(treasure) 星环宝藏(treasure) 【题目背景】 本题读入量较大,请选择较为快速的读入方式。 【题目描述】 在遥远的银河系中,有一个神秘的星环,星环由来自 n 个星球的所有能量晶体组 成,每个星球的所有晶体的能量值从 1 开始递增排列并形成连续的一段。第 i 个星球上 的能量晶体数量为 ai,能量值分别为 1, 2, . . . , ai。这些晶体按照顺序首尾相连,形成一 个闭合的星环。 作为一名星际探险家,你的任务是从这个星环中选取连续的一段,且这一段刚好有 m 个能量晶体,使得这些晶体的能量值之和最大。请问你能获得的最大能量值是多少? 【输入格式】 第一行两个整数 n, m,表示星环中星球的数量和选取的一段的能量晶体数量。 第二行 n 个整数 a1, a2, . . . , an,表示每个星球上的能量晶体数量。 【输出格式】 一个整数,表示选取连续的一段中所有能量晶体的最大能量值之和。 【样例 1 输入】 1 3 10 2 5 1 4 【样例 1 输出】 1 26 【样例 2 输入】 1 10 22 2 1 10 2 5 3 7 4 1 10 8 【样例 2 输出】 1 119 第 5 页 共 11 页 NOIP 模拟赛 星环宝藏(treasure) 【说明/提示】 【样例 #1 解释】 因为 m = ∑n i=1 ai,所以你需要收集所有能量晶体。答案为 1 + 2 + 3 + 4 + 5 + 1 + 1 + 2 + 3 + 4 = 26。 【其它样例】 所有样例包含在文件夹 treasure 中,其中: 1. ex_treasure1.in/out 为样例组 #1。 2. ex_treasure2.in/out 为样例组 #2。 3. ex_treasure3.in/out 满足测试点编号 1 ∼ 3 的限制。 4. ex_treasure4.in/out 满足测试点编号 8 ∼ 13 的限制。 【数据范围】 对于全部测试点,1 ≤ n ≤ 106,1 ≤ ai ≤ 109,1 ≤ m ≤ ∑n i=1 ai,每个测试点 5 分。 测试点编号 n ≤ ai ≤ ∑n i=1 ai 1 ∼ 3 5000 5000 ≤ 5000 4 ∼ 7 106 106 ≤ 107 8 ∼ 13 5000 106 无特殊限制 14 ∼ 19 106 106 无特殊限制 20 106 109 无特殊限制 第 6 页 共 11 页 NOIP 模拟赛 星际跃迁(starmap) 星际跃迁(starmap) 本题读入量较大,请选择较为快速的输入输出的方式。 在遥远的银河系中,有一个由 n 个星球和 m 条星际航道组成的星际网络。每个星 球都有独特的编号,而每条星际航道连接两个星球,并且被标记为“跃迁通道”或“虫 洞通道”中的一种。由于星际航道的特殊性,每个星球最多只能有一条“跃迁通道”和 一条“虫洞通道”与之相连。 i 号星球上的居民被称为 i 号星际居民,由于星际环境的变化,他们决定集体迁移 到另一个星球。每个星球只能容纳一个编号的所有星际居民,因此迁移后的星球编号必 须互不相同。 换句话说,设 i 号星际居民迁移到的星球编号为 pi,那么 pi 必须互不相同。 此外,星际居民们希望保持原有的星际关系。如果两个星球 i 和 j 之间原本有星际 航道直接连接,那么他们迁移后的星球 pi 和 pj 之间也必须有星际航道直接连接,并且 这条航道的类型必须与原来的航道类型相同。 由于迁移方案的数量可能非常庞大,所以你只需要输出其对 998244353 取模的结果 即可。 【输入格式】 第一行两个整数 n, m。 接下来 m 行,第 i 行三个整数 ui , vi , ti,代表该条星际航道连接 ui , vi,若 ti = 0, 则该条航道为“跃迁通道”,若 ti = 1,则该条航道为“虫洞通道”。 【输出格式】 共一行,代表方案数对 998244353 取模的结果。 【样例 1 输入】 1 4 2 2 3 1 0 3 4 2 0 【样例 1 输出】 1 8 【样例 2 输入】 1 500000 8 2 1 2 1 3 2 3 0 第 7 页 共 11 页 NOIP 模拟赛 星际跃迁(starmap) 4 3 4 1 5 4 1 0 6 5 6 0 7 6 7 1 8 7 8 0 9 8 5 1 【样例 2 输出】 1 660322059 【说明/提示】 【样例 #1 解释】 如图,迁移方案 p 一共有 8 种,具体如下: 1. p = [1, 2, 3, 4] 1. p = [3, 2, 1, 4] 1. p = [1, 4, 3, 2] 1. p = [3, 4, 1, 2] 1. p = [2, 1, 4, 3] 1. p = [2, 3, 4, 1] 1. p = [4, 1, 2, 3] 1. p = [4, 3, 2, 1] 【其它样例】 所有样例包含在文件夹 starmap 中,其中: ex_starmap1.in/out 为样例组 #1。 ex_starmap2.in/out 为样例组 #2。 ex_starmap3.in/out 满足测试点编号 10 ∼ 11 的限制。 ex_starmap4.in/out 满足测试点编号 13 ∼ 16 的限制。 ex_starmap5.in/out 满足测试点编号 20 ∼ 22 的限制。 ex_starmap6.in/out 满足测试点编号 23 ∼ 25 的限制。 【数据范围】 对于全部测试点,满足 1 ≤ n ≤ 5×105 , 0 ≤ m ≤ n, 1 ≤ ui , vi ≤ n, ui ̸= vi , 0 ≤ ti ≤ 1, 保证对于相同的 ti,所有的 ui 以及 vi 两两不同,每个测试点 4 分。 第 8 页 共 11 页 NOIP 模拟赛 星际跃迁(starmap) 测试点编号 n ≤ m ≤ 其它性质 1 ∼ 4 10 n 无 5 ∼ 9 5 × 105 10 无 10 ∼ 11 5 × 105 ⌊n 2 ⌋ ti = 0 12 5 × 105 n 该图连通且每个点 度数均为 2 13 ∼ 16 5 × 105 n 每个点度数为 0 或 2 17 ∼ 19 5 × 105 n 每个连通块大小均 为奇数 20 ∼ 22 5 × 105 n 不存在连通块使得 所有点度数均为 2 23 ∼ 25 5 × 105 n 无 第 9 页 共 11 页 NOIP 模拟赛 魔法符文(runes) 魔法符文(runes) 【题目描述】 本题输入输出量均比较大,请选择较为快速的输入输出的方式。 在古老的魔法世界中,魔法师小 Z 发现了一串神秘的符文序列 s,长度为 n。定义一 段符文区间 [l, r] (l ≤ r) 的魔力值 f(l, r) 为 (r −l + 1) × r min i=l si。小 Z 需要将这 n(n + 1) 2 个区间的魔力值从大到小排序,得到序列 b1, b2, . . . b n(n+1) 2 。 由于符文序列过于庞大,小 Z 只需要你输出序列 b 中第 L 到第 R 个元素,即 bL, bL+1, . . . , bR。 【输入格式】 共两行,第一行三个整数 n, L, R。 第二行 n 个整数,其中第 i 个整数为 si,表示符文序列的第 i 个符文值。 【输出格式】 共一行 R − L + 1 个整数,每两个整数之间需要用一个空格隔开,其中第 i 个整数 代表 bi+L−1。 【样例 1 输入】 1 5 1 5 2 4 5 3 5 4 【样例 1 输出】 1 15 12 12 9 9 【样例 2 输入】 1 9 16 24 2 9 9 1 8 8 1 5 9 7 【样例 2 输出】 1 7 7 6 6 6 6 5 5 5 【提示】 【样例 #1 解释】 第 10 页 共 11 页 NOIP 模拟赛 魔法符文(runes) f(1, 1) = 4, f(1, 2) = 8, f(1, 3) = 9, f(1, 4) = 12, f(1, 5) = 15, f(2, 2) = 5, f(2, 3) = 6, f(2, 4) = 9, f(2, 5) = 12, f(3, 3) = 3, f(3, 4) = 6, f(3, 5) = 9, f(4, 4) = 5, f(4, 5) = 8, f(5, 5) = 4 故将所有 f 排序后得到 b 的结果为 [15, 12, 12, 9, 9, 9, 8, 8, 6, 6, 5, 5, 4, 4, 3],所以 [bL, bL+1, . . . , bR] = [15, 12, 12, 9, 9]。 【其它样例】 所有样例包含在文件夹 runes 中,其中: ex_runes1.in/out 为样例组 #1。 ex_runes2.in/out 为样例组 #2。 ex_runes3.in/out 满足测试点 1 ∼ 2 的限制。 ex_runes4.in/out 满足测试点 6 ∼ 7 的限制。 ex_runes5.in/out 满足测试点 8 ∼ 9 的限制。 ex_runes6.in/out 满足测试点 11 ∼ 12 的限制。 ex_runes7.in/out 满足测试点 15 ∼ 16 的限制。 ex_runes8.in/out 满足测试点 19 ∼ 22 的限制。 【数据范围】 对于全部测试数据,保证 1 ≤ n ≤ 5 × 105 , 1 ≤ L, R ≤ n(n + 1) 2 , 1 ≤ R − L + 1 ≤ min(5 × 105 , n(n+1) 2 ), 1 ≤ si ≤ 109,每个测试点 4 分。 测试点编号 n ≤ L, R si 1 ∼ 2 500 无特殊限制 无特殊限制 3 ∼ 5 2500 无特殊限制 无特殊限制 6 ∼ 7 5 × 105 无特殊限制 = 1 8 ∼ 9 5 × 105 无特殊限制 = i 10 5 × 105 L = R = n(n + 1) 2 无特殊限制 11 ∼ 12 5 × 105 R = n(n + 1) 2 无特殊限制 13 ∼ 14 5 × 105 L = R = 1 无特殊限制 15 ∼ 16 5 × 105 L = 1 无特殊限制 17 ∼ 18 5 × 105 L = R 无特殊限制 19 ∼ 22 105 无特殊限制 无特殊限制 23 ∼ 25 5 × 105 无特殊限制 无特殊限制 第 11 页 共 11 页
评论
暂无评论
发表评论
可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。
活跃度
近 53 周 · 共 314 次
12月
1月
2月
3月
4月
5月
6月
7月
8月
9月
10月
11月
一
三
五
活跃程度
