noip2017提高组试题-(day1+day2~)Word版.doc

|CCF 全国信息学奥林匹克联赛（ NOIP2017）复赛提高组 day1（请选手务必仔细阅读本页内容）一题目概况中文题目名称 小凯的疑惑 时间复杂度 逛公园英文题目与子目录名 math complexity park可执行文件名 math complexity park输入文件名 math.in complexity.in park.in输出文件名 math.out complexity.out park.out每个测试点时限 1 秒 1 秒 3 秒测试点数目 20 10 10每个测试点分值 5 10 10附加样例文件 有 有 有结果比较方式 全文比较（过滤行末空格及文末回车）题目类型 传统 传统 传统运行内存上限 256M 256M 512M二提交源程序文件名对于 C+语言 math.cpp complexity.cpp park.cpp对于 C 语言 math.c complexity.c park.c对于 pascal 语言 math.pas complexity.pas park.pas三编译命令（不包含任何优化开关）对于 C+ 语言 g+ -o mathmath.cpp -lmg+ -o complexitycomplexity.cpp -lmg+ -o parkpark.cpp -lm对于 C 语言 gcc -o math math.c-lmgcc -o complexitycomplexity.c -lmgcc -o park park.c-lm对于 pascal 语言 fpc math.pas fpc complexity.pas fpc park.pas注意事项：1、文件名（程序名和输入输出文件名）必须使用英文小写。2、C/C+中函数 main()的返回值类型必须是 int，程序正常结束时的返回值必须是 0。3、全国统一评测时采用的机器配置为：CPU AMD Athlon(tm) II x2 240 processor，2.8GHz， 内存 4G，上述时限以此配置为准。4、只提供 Linux 格式附加样例文件。5、提交的程序代码文件的放置位置请参照各省的具体要求。6、特别提醒：评测在当前最新公布的 NOI Linux 下进行，各语言的编译器版本以其为准。|【问题描述】1小凯的疑惑(math.cpp/c/pas)小 凯 手 中 有 两 种 面 值 的 金 币 ， 两 种 面 值 均 为 正 整 数 且 彼 此 互 素 。 每 种 金 币 小 凯 都 有无 数 个 。 在 不 找 零 的 情 况 下 ， 仅 凭 这 两 种 金 币 ， 有 些 物 品 他 是 无 法 准 确 支 付 的 。 现 在 小 凯想 知 道 在 无 法 准 确 支 付 的 物 品 中 ， 最 贵 的 价 值 是 多 少 金 币 ？ 注 意 ： 输 入 数 据 保 证 存 在 小 凯无 法 准 确 支 付 的 商 品 。【输入格式】输入文件名为 math.in 。输入数据仅一行，包含两个正整数 a 和 b，它们之间用一个空格隔开，表示小凯手中金币的面值。【输出格式】输出文件名为 math.out 。输出文件仅一行，一个正整数 N，表示不找零的情况下，小凯用手中的金币不能准确支付的最贵的物品的价值。【输入输出样例 1】math.in math.out3 7 11见 选 手 目 录 下 的 math/math1.in 和 math/math1.ans。【输入输出样例 1 说明】小 凯 手 中 有 面 值 为 3 和 7 的 金 币 无 数 个 ， 在 不 找 零 的 前 提 下 无 法 准 确 支 付 价 值 为 1、2、4、5、8、11 的物品，其中最贵的物品价值为 11，比 11 贵的物品都能买到，比如：12 = 3 * 4 + 7 * 013 = 3 * 2 + 7 * 114 = 3 * 0 + 7 * 215 = 3 * 5 + 7 * 0【输入输出样例 2】见 选 手 目 录 下 的 math/math2.in 和 math/math2.ans。【数据规模与约定】对于 30%的数据： 1 a，b 50。对于 60%的数据： 1 a，b 10,000。对于 100%的数据：1 a，b 1,000,000,000。|【问题描述】2时间复杂度(complexity.cpp/c/pas)小 明 正 在 学 习 一 种 新 的 编 程 语 言 A+， 刚 学 会 循 环 语 句 的 他 激 动 地 写 了 好 多 程 序 并给 出 了 他 自 己 算 出 的 时 间 复 杂 度 ， 可 他 的 编 程 老 师 实 在 不 想 一 个 一 个 检 查 小 明 的 程 序 ， 于 是 你 的 机 会 来 啦 ！ 下 面 请 你 编 写 程 序 来 判 断 小 明 对 他 的 每 个 程 序 给 出 的 时 间 复 杂 度 是 否正 确 。A+语言的循环结构如下：其 中 “F i x y”表 示 新 建 变 量 （ i 变量 i 不 可 与 未 被 销 毁 的 变 量 重 名 ） 并 初 始 化 为 x，然 后 判 断 i 和 y 的 大 小 关 系 ， 若 i 小 于 等 于 y 则 进 入 循 环 ， 否 则 不 进 入 。 每 次 循 环 结 束后 i 都 会 被 修 改 成 i +1， 一 旦 i 大于 y 终 止 循 环 。x 和 y 可 以 是 正 整 数 （x 和 y 的 大 小 关 系 不 定 ） 或变 量 n。 n 是 一 个 表 示 数 据 规 模 的变 量 ， 在 时 间 复 杂 度 计 算 中 需 保 留 该 变 量 而 不 能 将 其 视 为 常 数 ， 该 数 远 大 于 100。“E”表示循环体结束。循环体结束时，这个循环体新建的变量也被销毁。注：本题中为了书写方便，在描述复杂度时，使用大写英文字母“O”表示通常意义下“”的概念。【输入格式】输入文件名为 complexity.in。输 入 文 件 第 一 行 一 个 正 整 数 t， 表 示 有 t（t 10）个 程 序 需 要 计 算 时 间 复 杂 度 。每 个 程 序 我 们 只 需 抽 取 其 中 “F i x y”和 “E”即 可 计 算 时 间 复 杂 度 。 注 意 ： 循 环 结 构允 许 嵌 套 。接 下 来 每 个 程 序 的 第 一 行 包 含 一 个 正 整 数 L 和 一 个 字 符 串 ， L 代 表 程 序 行 数 ， 字 符 串表 示 这 个 程 序 的 复 杂 度 ， “O(1)”表 示 常 数 复 杂 度 ， “O(nw)”表 示 复 杂 度 为 ， 其 中 w 是 一 个 小 于 100 的 正 整 数 （输 入 中 不 包 含 引 号 ） ， 输 入 保 证 复 杂 度 只 有 O(1)和 O(nw) 两种 类 型 。接下来 L 行 代 表 程 序 中 循 环 结 构 中 的 “F i x y”或 者 “E”。程 序 行 若 以 “F”开 头 ， 表 示 进 入 一 个 循 环 ， 之 后 有 空 格 分 离 的 三 个 字 符 （串 ） i x y， 其中 i 是 一 个 小 写 字 母 （保 证 不 为 “n”） ， 表 示 新 建 的 变 量 名 ， x 和 y 可 能 是 正 整 数 或 n ， 已 知 若 为 正 整 数 则 一 定 小 于 100。程序行若以“E”开头，则表示循环体结束。【输出格式】输出文件名为 complexity.out 。输 出 文 件 共 t 行 ， 对 应 输 入 的 t 个 程 序 ， 每 行 输 出 “Yes”或 “No”或 者 “ERR”（输出中不包含引号） ，若程序实际复杂度与输入给出的复杂度一致则输出“Y es”， 不 一 致则 输 出 “No”， 若 程 序 有 语 法 错 误 （ 其 中 语 法 错 误 只 有 : F 和 E 不 匹 配 新 建 的 变量 与 已 经 存 在 但 未 被 销 毁 的 变 量 重 复 两 种 情 况 ） ， 则 输 出 “ERR”。注 意 ： 即 使 在 程 序 不 会 执 行 的 循 环 体 中 出 现 了 语 法 错 误 也 会 编 译 错 误 ， 要 输 出“ERR”。F i x y循环体E|【输入输出样例 1】complexity.in complexity.out82 O(1)F i 1 1 E2 O(n1)F x 1 n E1 O(1)F x 1 n 4 O(n2)F x 5 n F y 10 n EE4 O(n2)F x 9 n EF y 2 n E4 O(n1)F x 9 n F y n 4 EE4 O(1)F y n 4 F x 9 n EE4 O(n2)F x 1 n F x 1 10 EEYes Yes ERRYes No Yes Yes ERR见选手目录下的complexity/complexity1.in 和 complexity/complexity1.ans。【输入输出样例 1 说明】第 一 个 程 序 i 从 1 到 1 是 常 数 复 杂 度 。第 二 个 程 序 x 从 1 到 n 是 n 的 一 次 方 的 复 杂 度 。|第 三 个 程 序 有 一 个 F 开 启 循 环 却 没 有 E 结 束 ， 语 法 错 误 。第 四 个 程 序 二 重 循 环 ， n 的 平 方 的 复 杂 度 。第五个程序两个一重循环，n 的一次方的复杂度。第 六 个 程 序 第 一 重 循 环 正 常 ， 但 第 二 重 循 环 开 始 即 终 止 （因 为 n 远 大 于 100， 100 大 于 4） 。第 七 个 程 序 第 一 重 循 环 无 法 进 入 ， 故 为 常 数 复 杂 度 。第八个程序第二重循环中的变量 x 与第一重循环中的变量重复，出现语法错误，输出ERR。【输入输出样例 2】见选手目录下的complexity/complexity2.in 和 complexity/complexity2.ans。【数据规模与约定】对 于 30%的 数 据 ： 不 存 在 语 法 错 误 ， 数 据 保 证 小 明 给 出 的 每 个 程 序 的 前 L/2 行一定为 以 F 开 头 的 语 句 ， 第 L/2+1 行 至 第 L 行 一 定 为 以 E 开 头 的 语 句 ， L<=10， 若 x、 y 均为整数，x 一 定 小 于 y， 且 只 有 y 有 可 能 为 n。对 于 50%的 数 据 ： 不 存 在 语 法 错 误 ， L<=100， 且 若 x、 y 均 为 整 数 ， x 一定小于 y， 且 只 有 y 有 可 能 为 n。对于 70%的数据：不存在语法错误， L<=100。对于 100%的数据：L<=100。|【问题描述】3. 逛公园(park.cpp/c/pas)策策同学特别喜欢逛公园。公园可以看成一张 个点 条边构成的有向图，且没有自 环 和 重 边 。 其 中 1号 点 是 公 园 的 入 口 ， 号 点 是 公 园 的 出 口 ， 每 条 边 有 一 个 非 负 权 值 ，代 表 策 策 经 过 这 条 边 所 要 花 的 时 间 。策策每天都会去逛公园，他总是从1号点进去，从 号点出来。策 策 喜 欢 新 鲜 的 事 物 ， 他 不 希 望 有 两 天 逛 公 园 的 路 线 完 全 一 样 ， 同 时 策 策 还 是 一 个特 别 热 爱 学 习 的 好 孩 子 ， 他 不 希 望 每 天 在 逛 公 园 这 件 事 上 花 费 太 多 的 时 间 。 如 果 1号 点 到 号 点 的 最 短 路 长 为 ， 那 么 策 策 只 会 喜 欢 长 度 不 超 过 + 的 路 线 。策策同学想知道总共有多少条满足条件的路线，你能帮帮他吗？ 为避免输出过大，答案对 取模。如果有无穷多条合法的路线，请输出1。【输入格式】输入文件名为 park.in 。第一行包含一个整数 , 代表数据组数。接下来 组数据，对于每组数据：第一行包含四个整数 , , , ，每两个整数之间用一个空格隔开。接 下 来 行 ， 每 行 三 个 整 数 , , ， 代 表 编 号 为 , 的 点 之 间 有 一 条 权值 为 的有 向 边 ， 每 两 个 整 数 之 间 用 一 个 空 格 隔 开 。【输出格式】输出文件名为 park.out 。输出文件包含 行，每行一个整数代表答案。【输入输出样例 1】park.in park.out25 7 2 101 2 12 4 04 5 22 3 23 4 13 5 21 5 32 2 0 101 2 02 1 03-1见 选 手 目 录 下 的 park/park1.in 和 park/park1.ans。对 于 第 一 组 数 据 ， 最 短 路 为 3。1 5, 1 2 4 5, 1 2 3 5 为 3 条合法路径。|【输入输出样例 2】见 选 手 目 录 下 的 park/park2.in 和 park/park2.ans。【数据规模与约定】对于不同的测试点，我们约定各种参数的规模不会超过如下测试点编号 是否有 0 边 1 5 5 10 0 否 2 5 1000 2000 0 否 3 5 1000 2000 50 否 4 5 1000 2000 50 否 5 5 1000 2000 50 否 6 5 1000 2000 50 是 7 5 100000 200000 0 否 8 3 100000 200000 50 否 9 3 100000 200000 50 是 10 3 100000 200000 50 是 对于 100% 的数据 , 1 109,1 , , 0 1000。数据保证：至少存在一条合法的路线。 |CCF 全国信息学奥林匹克联赛（ NOIP2017）复赛提高组 day2（请选手务必仔细阅读本页内容）一题目概况中文题目名称 奶酪 宝藏 列队英文题目与子目录名 cheese treasure phalanx可执行文件名 cheese treasure phalanx输入文件名 cheese.in treasure.in phalanx.in输出文件名 cheese.out treasure.out phalanx.out每个测试点时限 1 秒 1 秒 2 秒测试点数目 10 20 20每个测试点分值 10 5 5附加样例文件 有 有 有结果比较方式 全文比较（过滤行末空格及文末回车）题目类型 传统 传统 传统运行内存上限 256M 256M 512M二提交源程序文件名对于 C+语言 cheese.cpp treasure.cpp phalanx.cpp对于 C 语言 cheese.c treasure.c phalanx.c对于 pascal 语言 cheese.pas treasure.pas phalanx.pas三编译命令（不包含任何优化开关）对于 C+ 语言 g+ -o cheesecheese.cpp -lmg+ -o treasuretreasure.cpp -lmg+ -o phalanxphalanx.cpp -lm对于 C 语言 gcc -o cheesecheese.c -lmgcc -o treasuretreasure.c -lmgcc -o phalanxphalanx.c -lm对于 pascal 语言 fpc cheese.pas fpc treasure.pas fpc phalanx.pas注意事项：1、文件名（程序名和输入输出文件名）必须使用英文小写。2、C/C+中函数 main()的返回值类型必须是 int，程序正常结束时的返回值必须是 0。3、全国统一评测时采用的机器配置为：CPU AMD Athlon(tm) II x2 240 processor，2.8GHz， 内存 4G，上述时限以此配置为准。4、只提供 Linux 格式附加样例文件。5、提交的程序代码文件的放置位置请参照各省的具体要求。6、特别提醒：评测在当前最新公布的 NOI Linux 下进行，各语言的编译器版本以其为准。|【问题描述】1奶酪(cheese.cpp/c/pas)现 有 一 块 大 奶 酪 ， 它 的 高 度 为 h， 它 的 长 度 和 宽 度 我 们 可 以 认 为 是 无 限 大 的 ， 奶 酪 中间 有 许 多 半径相同 的 球 形 空 洞 。 我 们 可 以 在 这 块 奶 酪 中 建 立 空 间 坐 标 系 ， 在 坐 标 系 中 ， 奶 酪 的下 表 面 为 z = 0， 奶 酪 的 上 表 面 为 z = h。现 在 ， 奶 酪 的 下 表 面 有 一 只 小 老 鼠 Jerry，它知道奶酪中所有空洞的球心所在的坐标 。 如 果 两 个 空 洞 相 切 或 是 相 交 ， 则 Jerry 可 以 从 其 中 一 个 空 洞 跑 到 另 一 个 空 洞 ， 特 别地 ， 如 果 一 个 空 洞 与 下 表 面 相 切 或 是 相 交 ， Jerry 则可以从奶酪下表面跑进空洞；如果一 个 空 洞 与 上 表 面 相 切 或 是 相 交 ， Jerry 则 可 以 从 空 洞 跑 到 奶 酪 上 表 面 。位于奶酪下表面的 Jerry 想知道，在 不破坏奶酪 的情况下，能否利用已有的空洞跑到奶酪的上表面去?空间内两点 1( 1, 1, 1)、 2( 2, 2, 2)的距离公式如下：dist(1, 2) = (1 2)2 + (1 2)2 + (1 2)2【输入格式】输入文件名为 cheese.in。每个输入文件包含多组数据。输入文件的第一行，包含一个正整数 T，代表该输入文件中所含的数据组数。接下来是 T 组数据，每组数据的格式如下：第 一 行 包 含 三 个 正 整 数 n， h 和 r， 两 个 数 之 间 以 一 个 空 格 分 开 ， 分 别 代 表 奶 酪 中 空洞 的 数 量 ， 奶 酪 的 高 度 和 空 洞 的 半 径 。接下来的 n 行，每行包含三个整数 x、y、z，两个数之间以一个空格分开，表示空洞球心坐标为 ( , , )。【输出格式】输出文件名为 cheese.out。输 出 文 件 包 含 T 行 ， 分 别 对 应 T 组 数 据 的 答 案 ， 如 果 在 第 i 组 数 据 中 ， Jerry 能从下表 面 跑 到 上 表 面 ， 则 输 出 “Yes”， 如 果 不 能 ， 则 输 出 “No”（ 均 不 包 含 引 号 ） 。【输入输出样例 1】cheese.in cheese.out3 Yes2 4 1 No0 0 1 Yes0 0 32 5 10 0 10 0 42 5 20 0 22 0 4|见 选 手 目 录 下 的 cheese/cheese1.in 和 cheese/cheese1.ans。【输入输出样例 1 说明】第 一 组 数 据 ， 由 奶 酪 的 剖 面 图 可 见 ： 第 一 个 空 洞 在 （0，0，0）与 下 表 面 相 切第 二 个 空 洞 在 （0，0，4）与 上 表 面 相 切两 个 空 洞 在 （0，0，2）相 切输出 Yes第二组数据，由奶酪的剖面图可见： 两个空洞既不相交也不相切输出 No第三组数据，由奶酪的剖面图可见： 两个空洞相交且与上下表面相切或相交输出 Yes【输入输出样例 2】见 选 手 目 录 下 的 cheese/cheese2.in 和 cheese/cheese2.ans。【数据规模与约定】对 于 20%的 数 据 ， n = 1，1 h , r 10,000， 坐 标 的 绝 对 值 不 超 过 10,000。对 于 40%的 数 据 ， 1 n 8， 1 h , r 10,000， 坐 标 的 绝 对 值 不 超 过 10,000。对于 80%的 数 据 ， 1 n 1,000， 1 h , r 10,000， 坐 标 的 绝 对 值 不 超 过 10,000。对于 100%的 数 据 ， 1 n 1,000，1 h , r 1,000,000,000，T 20，坐标的绝对值不超过 1,000,000,000。