NOIP2016提高组复赛试题-(Day1+Day2~).doc

《NOIP2016提高组复赛试题-(Day1+Day2~).doc》由会员分享，可在线阅读，更多相关《NOIP2016提高组复赛试题-(Day1+Day2~).doc（24页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、|第 22 届 全 国 青 少 年 信 息 学 奥 林 匹 克 联 赛CCF-NOIP-2016提 高 组 （ 复 赛 ） 第一试竞赛时间 ： 2016 年 11 月 19 日 8:30 12:00题目名称 玩具谜题 天天爱跑步 换教室 题目类型 传统型 传统型 传统型 目录 toy running classroom可执行文件名 toy running classroom输入文件名 toy.in running.in classroom.in输出文件名 toy.out running.out classroom.out每个测试点时限 1.0 秒 2.0 秒 1.0 秒 内存限制 512 MB

2、 512 MB 512 MB测试点数目 20 20 25每个测试点分值 5 5 4提交源程序文件名对于 C+ 语言 toy.cpp running.cpp classroom.cpp对 于 C 语言 toy.c running.c classroom.c对 于 Pascal 语言 toy.pas running.pas classroom.pas编译选项对于 C+ 语言 -lm -lm -lm对 于 C 语言 -lm -lm -lm对 于 Pascal 语言 注意事项：1. 文件名（程序名和输入输出文件名）必须使用英文小写 。2. 除非特殊说明 ， 结果比较方式均为忽略行末空格及文末回车的全文

3、比较 。3. C/C+中 函 数 main()的 返 回 值 类 型 必 须 是 int， 程 序 正 常 结 束 时 的 返 回 值 必 须 是 0。4. 全 国 统 一 评 测 时 采 用 的 机 器 配 置 为 ： CPU AMD Athlon(tm) II x2 240 processor， 2.8GHz， 内 存 4G， 上 述 时 限 以 此 配 置 为 准 。5. 只 提 供 Linux 格 式 附 加 样 例 文 件 。6. 评测在 NOI Linux 下 进 行 。7. 编 译 时 不 打 开 任 何 优 化 选 项 。|玩具谜题（toy)【问题描述】小南有一套可爱的玩具小人

4、，它们各有不同的职业。有一天，这些玩具小人把小南的眼镜藏了起来。小南发现玩具小人们围成了一个圈，它们有的面朝圈内，有的面朝圈外。如下图：这时 singer 告诉小南一个谜题：“ 眼镜藏在我左数第 3 个玩具小人的右数第 1 个玩具小人的左数第 2 个 玩 具 小 人 那 里 。 ”小 南 发 现 ， 这 个 谜 题 中 玩 具 小 人 的 朝 向 非 常 关 键 ， 因 为 朝 内 和 朝 外 的 玩 具 小 人 的左 右 方 向 是 相 反 的 ： 面 朝 圈 内 的 玩 具 小 人 ， 它 的 左 边 是 顺 时 针 方 向 ， 右 边 是 逆 时 针 方向；而面向圈外的玩具小人 ， 它的

5、左边是逆时针方向 ， 右边是顺时针方向 。小 南 一 边 艰 难 地 辨 认 着 玩 具 小 人 ， 一 边 数 着 ：“singer 朝 内 ， 左 数 第 3 个 是 archer。“archer 朝 外 ， 右 数 第 1 个 是 thinker。“thinker 朝 外 ， 左 数 第 2 个 是 writer。“所以眼镜藏在 writer 这 里 ！ ”虽 然 成 功 找 回 了 眼 镜 ， 但 小 南 并 没 有 放 心 。 如 果 下 次 有 更 多 的 玩 具 小 人 藏 他 的 眼镜 ， 或 是 谜 题 的 长 度 更 长 ， 他 可 能 就 无 法 找 到 眼 镜 了 。

6、所 以 小 南 希 望 你 写 程 序 帮 他 解决 类 似 的 谜 题 。 这 样 的 谜 题 具 体 可 以 描 述 为 ：有 n 个 玩 具 小 人 围 成 一 圈 ， 己 知 它 们 的 职 业 和 朝 向 。现 在 第 1 个 玩 具 小 人 告 诉 小 南一 个 包 含 m 条 指 令 的 谜 题 ， 其 中 第 i 条指令形如“左数/ 右数第 si 个 玩 具 小 人 ”。 你需要输出依次数完这些指令后 ， 到达的玩具小人的职业 。|【输入格式】从 文 件 toy.in 中 读 入 数 据 。输入的第一行包含两个正整数 n,m ， 表 示 玩 具 小 人 的 个 数 和 指 令

7、的 条 数 。接 下 来 n 行 ， 每 行 包 含 一 个 整 数 和 一 个 字 符 串 ， 以 逆 时 针 为 顺 序 给 出 每 个 玩 具 小人的朝向和职业 。 其中 0 表示朝向圈内 ， 1 表示朝向圈外 。 保证不会出现其他的数 。 字符串长度不超过 10 且 仅由小写字母构 成 ， 字符串不为 空 ， 并且字符串两两不 同 。整数和 字 符 串 之 间 用 一 个 空 格 隔 开 。接下来 m 行 ， 其 中 第 i 行包含两个整数 ai, si ， 表 示 第 i 条 指 令 。 若 ai = 0 ， 表 示 向左数 si 个 人 ； 若 ai = 1 ， 表 示 向 右 数

8、 si 个 人 。 保 证 ai 不 会 出 现 其 他 的 数 ， 1 si n。【输出格式】输 出 到 文 件 toy.out 中 。 输 出 一 个 字 符 串 ， 表 示 从 第 一 个 读 入 的 小 人 开 始 ， 依 次 数完 m 条指令后到达的小人的职业。【样例 1 输入】7 30 singer0 reader0 mengbier1 thinker1 archer0 writer1 mogician0 31 10 2【样例 1 输出】writer【样例 1 说明】这 组 数 据 就 是 【 题 目 描 述 】 中 提 到 的 例 子 。|【样例 2 输入】10 101 c0 r

9、0 p1 d1 e1 m1 t1 y1 u0 v1 71 11 40 50 30 11 61 20 80 4【样例 2 输出】y【子任务】子 任 务 会 给 出 部 分 测 试 数 据 的 特 点 。如 果 你 在 解 决 题 目 中 遇 到 了 困 难 ， 可 以 尝 试只 解 决 一 部 分 测 试 数 据 。每个测试点的数据规模及特点如下表：|测试点 n m 全朝内 全左数 si = 1 职业长度为 11 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16= 20 = 103 17 18 19 20= 105 = 105 其中一些简写的列意义如下： 全朝内：若为“

10、”， 表示该测试点保证所有的玩具小人都朝向圈内； 全左数：若为“ ”，表示该测试点保证所有的指令都向左数，即对任意的 1 i m， ai = 0 ； si = 1 ：若为 “”，表示该测试点保证所有的指令都只数 1 个，即对任意的 1 i m， si = 1 ； 职业长度为 1：若为“ ”，表示该测试点保证所有玩具小人的职业一定是一个长度为 1 的字符串。|天 天 爱 跑 步 （ running)【 问 题 描 述 】小 C 同 学 认 为 跑 步 非 常 有 趣 ， 于 是 决 定 制 作 一 款 叫 做 天 天 爱 跑 步 的 游 戏 。天 天爱跑步是一个养成类游戏 ， 需要玩家每天按时上

11、线 ， 完成打卡任务 。这个游戏的地图可以看作一棵包含 n 个结点和 n 1 条边的树，每条边连接两个结点 ， 且任意两个结点存在一条路径互相可达 。 树上结点编号为从 1 到 n 的连续正整数 。现在有 m 个 玩 家 ， 第 i 个玩家的起点为 Si ，终点为 Ti 。每 天 打 卡 任 务 开 始 时 ， 所 有 玩 家 在 第 0 秒 同 时 从 自 己 的 起 点 出 发 ， 以 每 秒 跑 一 条 边 的 速 度 ， 不 间 断 地 沿 着 最短 路径向 着自己的终点跑 去 ， 跑到终点后该玩家就算完成了打卡任 务 。 （由于地图是一 棵 树 ， 所 以 每 个 人 的 路 径 是

12、 唯 一 的 ）小 C 想知道游戏的活 跃 度 ， 所以在每个结点上都放置了一个观察 员 。在结点 j 的 观 察员会选择在第 Wj 秒 观 察 玩 家 ， 一 个 玩 家 能 被 这 个 观 察 员 观 察 到 当 且 仅 当 该 玩 家 在 第 Wj 秒也正好到达了结点 j 。小 C 想知道每个观察员会观察到多少人？注 意 ： 我 们 认 为 一 个 玩 家 到 达 自 己 的 终 点 后 该 玩 家 就 会 结 束 游 戏 ， 他 不 能 等 待 一 段时间后再被观察员观察 到 。即对于把结点 j 作为终点的玩家：若他在第 Wj 秒前到达 终点，则在结点 j 的 观 察 员 不 能 观

13、察 到 该 玩 家 ； 若 他 正 好 在 第 Wj 秒到达终点，则在结 点 j 的 观 察 员 可 以 观 察 到 这 个 玩 家 。【 输 入 格 式 】从文件 running.in 中 读 入 数 据 。第 一 行 有 两 个 整 数 n 和 m 。其 中 n 代 表 树 的 结 点 数 量 ， 同 时 也 是 观 察 员 的 数 量 ， m 代 表 玩 家 的 数 量 。接下来 n 1 行每行两个整数 u 和 v ，表示结点 u 到结点 v 有 一 条 边 。接下来一行 n 个 整 数 ， 其 中 第 j 个整数为 Wj ，表示结点 j 出 现 观 察 员 的 时 间 。接下来 m 行

14、 ， 每 行 两 个 整 数 Si 和 Ti ， 表 示 一 个 玩 家 的 起 点 和 终 点 。对 于 所 有 的 数 据 ， 保 证 1 Si , Ti n ， 0 Wj n 。【 输 出 格 式 】输出到文件 running.out 中 。输出 1 行 n 个 整 数 ， 第 j 个整数表示结点 j 的 观 察 员 可 以 观 察 到 多 少 人 。【 样 例 1 输 入 】6 32 3|1 21 44 54 60 2 5 1 2 31 51 32 6【 样 例 1 输 出 】2 0 0 1 1 1【 样 例 1 说 明 】对 于 1 号 点 ， W1 = 0 ， 故 只 有 起 点

15、为 1 号 点 的 玩 家 才 会 被 观 察 到 ， 所 以 玩 家 1 和玩家 2 被观 察 到 ， 共 2 人 被 观 察 到 。对 于 2 号 点 ， 没 有 玩 家 在 第 2 秒 时 在 此 结 点 ， 共 0 人 被 观 察 到 。对 于 3 号 点 ， 没 有 玩 家 在 第 5 秒 时 在 此 结 点 ， 共 0 人 被 观 察 到 。对 于 4 号 点 ， 玩 家 1 被 观 察 到 ， 共 1 人 被 观 察 到 。对 于 5 号 点 ， 玩 家 1 被 观 察 到 ， 共 1 人 被 观 察 到 。对 于 6 号 点 ， 玩 家 3 被 观 察 到 ， 共 1 人 被

16、观 察 到 。【 样 例 2 输 入 】5 31 22 32 41 50 1 0 3 03 11 45 5【 样 例 2 输 出 】1 2 1 0 1|【 子 任 务 】每 个 测 试 点 的 数 据 规 模 及 特 点 如 下 表 所 示 。提 示 ： 数 据 范 围 的 个 位 上 的 数 字 可 以 帮助 判 断是 哪 一 种 数 据 类 型 。测试点编号 n m 约定 12 = 991 = 991所 有 人 的 起 点 等 于 自 己 的 终 点 ，即 Si = Ti34 = 992 = 992Wj = 05 = 993 = 993 无 678= 99994 = 99994 树 退 化

17、 成 一 条 链 ， 其 中 1 与 2 有 边 ，2 与 3 有 边 ， . . . ，n 1 与 n 有边 9101112= 99995 = 99995 所有的 Si = 113141516= 99996 = 99996 所有的 Ti = 1171819= 99997 = 9999720 = 299998 = 299998无 【提示】如果你的程序需要用到较大的 栈 空间（这通常意味着需要较深层数的递归 ） ， 请务 必仔细阅读选手目录下的文档 running/stack.pdf ， 以 了 解 在 最 终 评 测 时 栈 空 间 的 限 制 与 在 当 前 工 作 环 境 下 调 整 栈

18、空 间 限 制 的 方 法 。|换教室（classroom)【 问 题 描 述 】对 于 刚 上 大 学 的 牛 牛 来 说 ， 他 面 临 的 第 一 个 问 题 是 如 何 根 据 实 际 情 况 申 请 合 适 的 课 程 。在 可 以 选 择 的 课 程 中 ， 有 2n 节 课 程 安 排 在 n 个 时 间 段 上 。 在 第 i ( 1 i n )个时 间 段 上 ， 两 节 内 容 相 同 的 课 程 同 时 在 不 同 的 地 点 进 行 ， 其 中 ， 牛 牛 预 先 被 安 排 在 教 室ci 上 课 ， 而 另 一 节 课 程 在 教 室 di 进 行 。在 不 提 交

19、 任 何 申 请 的 情 况 下 ， 学 生 们 需 要 按 时 间 段 的 顺 序 依 次 完 成 所 有 的 n 节安 排好 的 课 程 。 如 果 学 生 想 更 换 第 i 节 课 程 的 教 室 ， 则 需 要 提 出 申 请 。 若 申 请 通 过 ， 学 生 就可 以 在 第 i 个 时 间 段 去 教 室 di 上 课 ， 否 则 仍 然 在 教 室 di 上 课 。由 于 更 换 教 室 的 需 求 太 多 ， 申 请 不 一 定 能 获 得 通 过 。 通 过 计 算 ， 牛 牛 发 现 申 请 更换 第 i 节 课 程 的 教 室 时 ， 申 请 被 通 过 的 概 率

20、是 一 个 己 知 的 实 数 ki ， 并 且 对 于 不 同 课 程的 申 请 ， 被 通 过 的 概 率 是 互 相 独 立 的 。学 校 规 定 ， 所 有 的 申 请 只 能 在 学 期 开 始 前 一 次 性 提 交 ， 并 且 每 个 人 只 能 选 择 至 多 m 节 课 程 进 行 申 请 。 这 意 味 着 牛 牛 必 须 一 次 性 决 定 是 否 申 请 更 换 每 节 课 的 教 室 ， 而 不能 根 据 某 些 课 程 的 申 请 结 果 来 决 定 其 他 课 程 是 否 申 请 ； 牛 牛 可 以 申 请 自 己 最 希 望 更 换教室的 m 门 课 程 ， 也

21、 可 以 不 用 完 这 m 个 申 请 的 机 会 ， 甚 至 可 以 一 门 课 程 都 不 申 请 。因 为 不 同 的 课 程 可 能 会 被 安 排 在 不 同 的 教 室 进 行 ， 所 以 牛 牛 需 要 利 用 课 间 时 间 从 一 间 教 室 赶 到 另 一 间 教 室 。牛 牛 所 在 的 大 学 有 v 个 教 室 ， 有 e 条 道 路 。每 条 道 路 连 接 两 间 教 室 ， 并 且 是 可以 双 向 通 行 的 。由 于 道 路 的 长 度 和 拥 堵 程 度 不 同 ， 通 过 不 同 的 道 路 耗 费 的 体 力 可 能 会 有 所 不 同 。当 第 i

22、 （ 1 i n 1 ） 节 课 结 束 后 ， 牛 牛 就 会 从 这 节 课 的 教 室 出 发 ， 选 择 一 条 耗 费 体力 最 少 的 路 径 前 往 下 一 节 课 的 教 室 。 现 在 牛 牛 想 知 道 ， 申 请 哪 几 门 课 程 可 以 使 他 因 在教 室 间 移 动 耗 费 的 体 力 值 的 总 和 的 期 望 值 最 小 ， 请 你 帮 他 求 出 这 个 最 小 值 。现 在 牛 牛 想 知 道 ， 申 请 哪 几 门 课 程 可 以 使 他 因 在 教 室 间 移 动 耗 费 的 体 力 值 的 总 和的 期 望 值 最 小 ， 请 你 帮 他 求 出 这

23、 个 最 小 值 。【 输 入 格 式 】从文件 classroom.in 中 读 入 数 据 。第 一 行 四 个 整 数 n, m, v, e 。 n 表 示 这 个 学 期 内 的 时 间 段 的 数 量 ； m 表 示 牛 牛 最 多 可 以 申 请 更 换 多 少 节 课 程 的 教 室 ； v 表 示 牛 牛 学 校 里 教 室 的 数 量 ； e 表 示 牛 牛 的 学 校 里 道 路 的 数 量 。第二行 n 个 正 整 数 ， 第 i （ 1 i n ） 个 正 整 数 表 示 ci ， 即 第 i 个 时间段牛牛被安 排上课的教室；保证 1 ci v 。第三行 n 个 正 整 数 ， 第 i （ 1 i n ） 个 正 整 数 表 示 di ， 即 第 i 个时间段另一间上|同样课程的教室；保证 1 di v 。