集训队试题

Transcription

1 IOI 2012 中 国 信 息 学 国 家 集 训 队 命 题 答 辩 试 题 册 教 练 : 胡 伟 栋 唐 文 斌 中 国 计 算 机 学 会 2012 年 5 月

2 答 辩 顺 序 答 辩 顺 序 姓 名 所 在 学 校 试 题 名 称 1 李 超 浙 江 省 杭 州 学 军 中 学 拆 弹 计 划 2 徐 捷 浙 江 省 绍 兴 市 第 一 中 学 字 符 串 游 戏 3 梁 盾 湖 南 省 长 沙 市 长 郡 中 学 字 符 串 加 密 4 艾 雨 青 湖 南 省 长 沙 市 雅 礼 中 学 近 似 平 均 数 5 刘 洪 轩 天 津 市 南 开 中 学 电 子 对 撞 机 6 顾 昱 洲 江 苏 省 南 京 师 范 大 学 附 属 中 学 JZPLCM 7 沈 添 笑 湖 南 省 长 沙 市 雅 礼 中 学 生 日 蜡 烛 8 卓 亮 福 建 省 福 州 第 一 中 学 Flare 9 王 钦 石 黑 龙 江 省 哈 尔 滨 市 第 三 中 学 校 能 量 棒 10 陈 立 杰 浙 江 省 杭 州 外 国 语 学 校 Color 11 伍 一 鸣 湖 南 省 长 沙 市 雅 礼 中 学 Binomial 12 钟 沛 林 湖 南 省 长 沙 市 雅 礼 中 学 可 见 区 域

3 拆 弹 计 划 拆 弹 计 划 命 题 人 : 李 超 资 源 限 制 时 间 限 制 :3 秒 内 存 限 制 :512MB 关 键 字 序 的 应 用, 分 治, 线 段 树 问 题 描 述 A 国 和 B 国 是 两 个 超 级 大 国, 长 期 处 于 冷 战 状 态 A 国 在 B 国 中 设 有 N 个 情 报 站, 编 号 为 1,2,3,,N, 第 i 个 情 报 站 的 坐 标 是 (X i, Y i ) 但 是,A 国 的 工 作 人 员 发 现, 每 个 情 报 站 里 都 被 埋 上 了 炸 弹! 这 些 炸 弹 非 常 的 特 殊, 必 须 同 时 拆 除 且 仅 拆 除 其 中 的 三 个 炸 弹, 才 能 使 所 有 炸 弹 都 不 爆 炸 拆 除 炸 弹 的 总 代 价 由 两 部 分 组 成, 第 一 部 分 为 情 报 站 之 间 联 络 的 代 价, 第 二 部 分 为 拆 除 炸 弹 所 需 要 的 代 价 其 中, 联 络 的 代 价 为 要 拆 除 炸 弹 的 三 个 情 报 站 的 坐 标 的 曼 哈 顿 距 离 和, 在 第 i 个 情 报 站 拆 除 炸 弹 的 代 价 为 Z i 现 在 A 国 的 指 挥 部 门 找 到 了 你, 他 想 要 知 道, 使 所 有 炸 弹 都 不 爆 炸 的 最 小 花 费 代 价 是 多 少 输 入 格 式 输 入 的 第 一 行 包 含 一 个 整 数 N 接 下 来 N 行, 第 i+1 行 有 三 个 整 数 X i, Y i, Z i, 表 示 第 i 个 情 报 站 的 坐 标 与 拆 除 炸 弹 的 代 价 输 出 格 式 输 出 一 行, 包 含 一 个 整 数, 表 示 使 所 有 炸 弹 都 不 爆 炸 的 最 小 花 费 代 价 样 例 输 入 第 3 页 共 24 页

4 拆 弹 计 划 样 例 输 出 10 样 例 解 释 选 择 编 号 为 1,2,3 的 情 报 站 拆 除 炸 弹, 总 花 费 为 (1+1+2)+(1+2+3)=10, 是 所 有 花 费 中 总 花 费 最 小 的 该 数 据 中 只 有 这 一 种 选 法 数 据 规 模 与 约 定 对 于 30% 的 数 据,N 500 对 于 50% 的 数 据,N 1000 对 于 70% 的 数 据,N 另 有 10% 的 数 据, 在 所 有 情 报 站 拆 除 炸 弹 的 花 费 代 价 均 相 同 ; 对 于 100% 的 数 据,N ,0 X i, Y i, Z i 10 8 说 明 对 于 两 个 点 (X 0, Y 0 ), (X 1, Y 1 ), 它 们 的 曼 哈 顿 距 离 为 X 0 X 1 + Y 0 Y 1 第 4 页 共 24 页

5 字 符 串 游 戏 字 符 串 游 戏 命 题 人 : 徐 捷 问 题 描 述 给 定 N 个 仅 有 a ~ z 组 成 的 字 符 串 a i, 每 个 字 符 串 都 有 一 个 权 值 v i, 有 M 次 操 作, 操 作 分 三 种 : Cv x v': 把 第 x 个 字 符 串 的 权 值 修 改 为 v'; Cs x a': 把 第 x 个 字 符 串 修 改 成 a'; Q: 求 出 当 前 的 最 大 权 字 符 串 集 合, 使 得 这 个 集 合 中 的 字 符 串 经 过 重 新 排 列 后 满 足 除 最 后 一 个 字 符 串 外, 前 一 个 字 符 串 是 后 一 个 的 前 缀 ( 两 个 字 符 串 相 同 也 是 前 缀 关 系, 也 可 以 一 个 字 符 串 都 不 选 ) 前 50% 的 数 据 可 以 接 受 离 线 算 法, 后 50% 的 数 据 要 求 在 线 算 法 数 据 规 模 与 约 定 数 据 分 两 种,A 类 数 据 可 以 用 离 线 的 方 法 来 完 成,B 类 数 据 必 须 使 用 在 线 算 法 令 len= 输 入 数 据 中 所 有 出 现 的 字 符 串 总 长 度 编 号 数 据 类 别 数 据 范 围 1 N, M 30, len A B N, M 1000, len N 50000, M 10 5, len N 50000, M 10 5, len 第 5 页 共 24 页

6 字 符 串 加 密 字 符 串 加 密 命 题 人 : 梁 盾 问 题 描 述 H 国 开 发 了 一 种 新 的 字 符 串 的 加 密 方 式, 具 体 方 法 为 将 一 个 长 度 为 N 的 由 小 写 字 母 组 成 的 字 符 串 分 成 不 超 过 K 段, 分 别 将 每 一 段 翻 转, 得 到 的 新 字 符 串 即 为 加 密 以 后 的 字 符 串 H 国 为 I 国 的 敌 国,I 国 为 了 打 败 H 国, 得 到 了 一 个 加 密 以 后 的 信 息, 我 们 想 知 道 这 个 字 符 串 在 加 密 以 前 的 样 子, 不 过 可 能 有 多 个 答 案, 我 们 只 要 知 道 字 典 序 最 小 的 答 案 就 可 以 了 输 入 格 式 第 一 行 一 个 数 T, 表 示 数 据 组 数 对 于 每 组 数 据, 第 一 行 两 个 数 N, K 分 别 表 示 字 符 串 的 长 度 和 被 分 成 了 K 段 第 二 行 一 个 长 度 为 N 的 字 符 串 输 出 格 式 对 于 每 组 数 据, 输 出 一 个 长 度 为 N 的 字 符 串, 即 加 密 前 的 可 能 的 字 典 序 最 小 的 字 符 串 样 例 输 入 bacbadcba 样 例 输 出 ababcabcd 第 6 页 共 24 页

7 字 符 串 加 密 数 据 规 模 与 约 定 测 试 点 编 号 数 据 组 数 T 字 符 串 长 度 N 的 规 模 分 裂 段 数 K 的 规 模 1 ~ 2 1 N ~ 6 1 N K 3 7 ~ T 10 K = N K = 2 13 ~ 16 1 K ~ 20 1 K N 第 7 页 共 24 页

8 近 似 平 均 数 近 似 平 均 数 命 题 人 : 艾 雨 青 问 题 描 述 Xi i 1 定 义 N 个 数 X1, X 2,..., X n( n 1) 的 近 似 平 均 数 为 n 1 对 于 给 出 的 长 度 为 N 的 一 个 序 列 A, 要 求 回 答 Q 个 询 问 每 个 询 问 会 给 出 L, R(1 L R N), 请 找 出 a 与 b ( L a b R) 使 得 n Aa, Aa 1,..., Ab 的 近 似 平 均 数 最 大 输 入 格 式 第 一 行 两 个 正 整 数 N, Q 第 二 行 N 个 数 表 示 序 列 S 接 下 来 Q 行, 每 行 两 个 数 L, R 输 出 格 式 对 于 每 个 询 问 回 答 一 行, 用 一 个 既 约 分 数 表 示 最 大 的 几 乎 平 均 数 若 答 案 为 整 数 x, 输 出 x/1 样 例 输 入 样 例 输 出 -3/1-5/2 第 8 页 共 24 页

9 近 似 平 均 数 数 据 规 模 与 约 定 对 于 所 有 数 据 S i <=10 6 TEST N Q TEST N Q 1 =10 =10 11 =3*10^4 =10^4 2 =100 = =4*10^4 =10^4 3 =1000 = =5*10^4 =10^4 4 =2000 = =6*10^4 =2*10^4 5 =5000 = =7*10^4 =2*10^4 6 =10^4 = =8*10^4 =3*10^4 7 =10^4 =10^4 17 =9*10^4 =3*10^4 8 =2*10^4 = =10^5 =10 9 =2*10^4 =10^4 19 =10^5 =3*10^4 10 =3*10^4 = =10^5 =3*10^4 第 9 页 共 24 页

10 电 子 对 撞 机 电 子 对 撞 机 命 题 人 : 刘 洪 轩 资 源 限 制 时 间 限 制 :3 秒 内 存 限 制 :256MB 问 题 描 述 Q 国 最 近 科 学 技 术 不 断 进 步, 经 过 不 懈 努 力,Q 国 主 席 QQ 终 于 在 质 子 对 撞 机 的 基 础 上 研 发 了 新 一 代 能 量 供 给 装 置 : 电 子 对 撞 机 这 个 设 备 呈 长 条 状 且 对 外 封 闭, 设 备 内 部 有 N 个 带 有 一 定 能 量 的 电 子 长 条 状 的 外 形 使 得 这 些 电 子 只 能 沿 条 形 走 向 左 右 运 动 设 备 长 度 为 L, 左 端 位 置 为 0, 右 端 位 置 为 L 内 部 的 电 子 速 率 恒 定, 每 一 个 单 位 时 间 在 左 右 方 向 上 移 动 一 个 单 位 长 度, 而 方 向 可 能 是 向 左 或 向 右 当 两 个 电 子 相 遇 即 运 动 到 同 一 个 点 时, 它 们 之 间 会 发 生 对 撞, 对 撞 后 它 们 的 速 率 不 变 但 运 动 方 向 反 向 设 备 的 两 个 端 点 处 ( 即 坐 标 为 0 和 L 的 位 置 ) 存 在 保 护 外 壳, 当 电 子 运 动 到 端 点 时 会 和 外 壳 发 生 碰 撞, 碰 撞 后 电 子 也 会 保 持 不 变 的 速 率 但 运 动 方 向 反 向 电 子 分 为 高 能 电 子 和 低 能 电 子, 电 子 之 间 对 撞 会 产 生 能 量, 低 能 电 子 和 低 能 电 子 对 撞 会 产 生 1 个 单 位 的 能 量, 低 能 电 子 和 高 能 电 子 对 撞 会 产 生 4 个 单 位 的 能 量, 高 能 电 子 和 高 能 电 子 对 撞 会 产 生 25 个 单 位 的 能 量, 电 子 和 外 壳 碰 撞 不 会 产 生 能 量 设 备 内 部 还 有 M 个 能 量 接 收 器, 每 个 接 收 器 可 以 接 受 从 A 到 B 的 一 个 区 间 内 ( 包 括 两 个 端 点 ) 的 能 量, 且 接 收 器 可 以 接 受 的 范 围 没 有 交 集 若 电 子 对 撞 的 位 置 处 于 接 收 器 的 接 受 范 围 内, 对 撞 产 生 的 能 量 会 被 接 收 器 接 受, 若 对 撞 位 置 不 在 接 收 器 上, 这 些 能 量 则 会 丢 失 这 项 技 术 的 核 心 在 于 : 对 撞 时 电 子 的 能 量 不 会 有 损 失, 所 以 电 子 对 撞 机 可 以 一 直 不 断 地 运 行 下 去 供 给 能 量 现 在 QQ 已 经 制 造 出 了 第 一 批 电 子 对 撞 机, 并 测 得 了 时 刻 为 0 时 电 子 的 位 置 和 运 动 状 态, 现 在 QQ 想 知 道 从 时 刻 0 到 时 刻 T( 包 括 T) 总 共 接 收 到 的 能 量, 于 是 这 个 任 务 交 给 了 神 犇 你 输 入 格 式 第 一 行 四 个 整 数 N, M, L, T, 分 别 表 示 电 子 个 数, 能 量 接 收 器 个 数, 设 备 长 度 和 时 间 之 后 N 行 每 行 3 个 整 数,X i, P i, E i 分 别 表 示 第 i 个 电 子 的 位 置, 运 动 方 向 和 能 量 级 别 P i 为 1 表 示 向 右 运 动, 为 -1 表 示 向 左 运 动 E i 为 0 表 示 低 能 电 子, 为 1 表 示 高 能 电 子 之 后 M 行 每 行 2 个 整 数,A i 和 B i, 表 示 接 收 器 的 接 收 范 围 输 出 格 式 仅 一 行, 包 括 一 个 整 数, 表 示 总 共 接 收 到 的 能 量 数 第 10 页 共 24 页

11 电 子 对 撞 机 样 例 输 入 样 例 输 出 5 样 例 说 明 T=1 时, 在 位 置 3, 第 一 个 电 子 和 第 二 个 电 子 对 撞, 产 生 1 的 能 量 在 位 置 8, 第 三 个 电 子 和 右 侧 外 壳 碰 撞 T=3.5 时, 在 位 置 5.5, 第 二 个 电 子 和 第 三 个 电 子 对 撞, 产 生 4 的 能 量 T=4 时, 在 位 置 0, 第 一 个 电 子 和 左 侧 外 壳 碰 撞 T=6 时, 在 位 置 8, 第 三 个 电 子 和 右 侧 外 壳 碰 撞 T=6.5 时, 在 位 置 2.5, 第 一 个 电 子 和 第 二 个 电 子 对 撞, 产 生 1 的 能 量, 由 于 在 接 收 器 范 围 外, 能 量 丢 失 最 后 结 果 为 1+4=5 个 单 位 能 量 数 据 规 模 与 约 定 输 入 保 证 开 始 时 任 意 两 个 电 子 不 处 于 同 一 个 位 置 输 入 保 证 接 收 器 的 接 受 范 围 没 有 交 集, 且 所 有 接 收 器 按 坐 标 从 小 到 大 的 顺 序 给 出 共 20 组 数 据, 满 足 如 下 条 件 1 ~ 2 N <= 10 M <= 3 L <= 1000, T <= ~ 4 N <= 100 Ei = 0 L <= ~ 6 N <= ~ 8 M = 1 且 9 ~ 10 N <= ~12 13~20 A1 = 0, B1 = L 2 <= N <= , 1 <= M <= 10, 2 <= L <= , 0 <= T <= , 0 < X < L 0 <= A < B <= L 第 11 页 共 24 页

12 JZPLCM JZPLCM 命 题 人 : 顾 昱 洲 资 源 限 制 时 间 限 制 :3 秒 内 存 限 制 : 以 硬 件 资 源 为 限 问 题 描 述 给 定 一 长 度 为 n 的 正 整 数 序 列 a, 有 q 次 询 问, 每 次 询 问 一 段 区 间 内 所 有 数 的 lcm( 即 最 小 公 倍 数 ) 由 于 答 案 可 能 很 大, 输 出 答 案 模 输 入 格 式 第 一 行, 两 个 整 数,n, q, 分 别 表 示 数 列 长 度 和 询 问 个 数 下 面 n 行, 每 行 一 个 整 数, 第 i 行 的 整 数 为 a i 下 面 q 行, 每 行 两 个 整 数 l, r, 表 示 询 问 下 标 i 在 [l, r] 范 围 内 的 a i 的 lcm 输 出 格 式 q 行 对 于 每 个 询 问, 输 出 一 行, 表 示 对 应 的 答 案 样 例 输 入 样 例 输 出 第 12 页 共 24 页

13 JZPLCM 数 据 规 模 与 约 定 测 试 数 据 编 号 规 模 和 约 定 1, 2 n, q<=1000 3, 4 n, q<=5000 5, 6 n, q<= , 8 n, q<= , 10 n, q<= , 12 n, q<= , 14 n, q<= , 16 n, q<= , 18, 19, 20 n, q<= 数 列 a 中 每 个 数 能 表 示 为 不 超 过 100 的 素 数 的 积 对 于 所 有 测 试 点, 数 列 a 中 每 个 数 满 足 1<=ai<= 第 13 页 共 24 页

14 生 日 蜡 烛 生 日 蜡 烛 命 题 人 : 沈 添 笑 资 源 限 制 时 间 限 制 :2 秒 空 间 限 制 :256M 问 题 描 述 小 A 的 生 日 到 了! 生 日 派 对 上, 大 家 送 上 了 一 份 精 心 准 备 的 大 礼 : 生 日 蛋 糕! 蛋 糕 上 五 颜 六 色 的 蜡 烛 闪 闪 发 光 随 风 摇 曳 小 A 很 喜 欢 这 个 漂 亮 的 蛋 糕, 然 而, 在 吹 蜡 烛 许 愿 的 时 候, 他 却 犯 难 了 : 烛 火 怎 么 也 吹 不 灭! 原 来, 这 是 大 家 要 考 考 小 A 这 份 特 制 的 蛋 糕 上 共 有 n 根 蜡 烛, 编 号 为 1~n, 相 应 的, 有 n 个 开 关, 第 i 根 蜡 烛 由 第 i 个 开 关 控 制 此 外, 第 i 根 蜡 烛 还 可 能 由 至 多 一 个 其 他 的 开 关 j 控 制, 当 i=1 时,j 可 以 是 2 ~ n 中 的 任 意 一 个 数, 当 i > 1 时,j < i 按 下 一 个 开 关, 它 所 控 制 的 蜡 烛 的 状 态 就 会 发 生 改 变 : 由 亮 变 暗 或 由 暗 变 亮 小 A 知 道 每 根 蜡 烛 此 时 是 亮 是 暗, 以 及 它 由 哪 些 开 关 控 制, 他 希 望 尽 量 少 地 按 开 关, 使 所 有 的 蜡 烛 熄 灭 不 过, 参 加 聚 会 的 m 个 同 学 并 不 打 算 就 这 样 放 过 可 怜 的 小 A, 他 们 会 依 次 改 变 某 个 蜡 烛 的 状 态 以 及 控 制 它 的 开 关, 并 询 问 小 A 此 时 最 少 要 按 多 少 次 开 关 快 来 帮 帮 小 A 吧, 他 会 亲 手 切 下 第 一 块 生 日 蛋 糕 送 给 你 的! 输 入 格 式 第 一 行 为 一 个 正 整 数 n, 表 示 蜡 烛 和 开 关 的 个 数 接 下 来 n 行, 第 i 行 描 述 第 i 根 蜡 烛 每 行 包 含 两 个 整 数, 第 一 个 数 a i 为 0( 暗 ) 或 1( 亮 ), 代 表 蜡 烛 的 状 态, 第 二 个 数 b i 为 控 制 第 i 根 蜡 烛 的 另 一 个 开 关,b i =0 时 表 示 第 i 根 蜡 烛 只 由 第 i 个 开 关 控 制 接 下 来 一 行 为 一 个 正 整 数 m, 表 示 参 加 派 对 的 人 数 接 下 来 m 行, 每 行 包 含 三 个 整 数 u v w, 代 表 第 u 根 蜡 烛 的 状 态 变 为 v, 控 制 它 的 另 一 个 开 关 变 为 w 输 出 格 式 输 出 应 有 m 行, 第 i 行 一 个 整 数 time i, 表 示 经 过 前 i 次 修 改 后, 此 时 最 少 需 按 多 少 次 开 关, 才 能 使 所 有 蜡 烛 熄 灭 若 是 无 论 如 何 都 不 能 使 所 有 蜡 烛 熄 灭, 输 出 -1 第 14 页 共 24 页

15 生 日 蜡 烛 样 例 输 入 样 例 输 出 数 据 规 模 与 约 定 10% 的 数 据 满 足 :n m 10 20% 的 数 据 满 足 :n m 1000 另 有 20% 的 数 据 满 足 : 控 制 蜡 烛 的 开 关 不 会 更 改, 即 w=b u, 且 b i =(i+n-2)%n+1 另 有 30% 的 数 据 满 足 : 控 制 蜡 烛 的 开 关 不 会 更 改 100% 的 数 据 满 足 :n m 第 15 页 共 24 页

16 Flare Flare 命 题 人 : 卓 亮 问 题 描 述 这 是 一 个 很 有 趣 的 想 法, 如 果 熊 是 蜜 蜂, 他 们 会 将 他 们 的 巢 建 在 树 下 而 且 如 此 的 话 ( 如 果 蜜 蜂 是 熊 ), 我 们 就 不 用 爬 上 楼 梯 了 这 是 小 熊 维 尼 的 一 首 充 满 抱 怨 的 歌 你 是 否 曾 经 想 过, 有 些 关 于 无 向 图 的 问 题, 如 果 把 边 看 成 点, 点 看 成 边, 会 更 容 易 解 决? 这 道 题 目 正 与 此 有 关 假 设 有 一 张 无 向 图 G 0, 让 我 们 对 G 0 执 行 一 次 简 单 变 换, 来 得 到 无 向 图 G 1 G 1 满 足, 每 个 G 1 的 顶 点 和 G 0 的 一 条 边 一 一 对 应,G 1 的 一 对 顶 点 间 有 一 条 边, 当 且 仅 当 在 G 0 中 的 对 应 边 有 一 个 公 共 顶 点 可 能 与 你 猜 测 的 不 一 样, 本 题 给 出 了 G 1, 求 一 个 满 足 条 件 的 G 0 输 入 格 式 输 入 的 第 一 行 含 两 个 数 n, m, 代 表 点 数 和 边 数 接 下 来 m 行, 每 行 有 两 个 数 a, b (1 <= a, b <= n), 表 示 a, b 间 有 一 条 边 保 证 每 条 边 连 接 了 两 个 不 同 的 顶 点, 每 对 顶 点 最 多 有 一 条 边 相 连 输 出 格 式 如 果 这 样 的 G 0 不 存 在, 输 出 -1 否 则, 输 出 n 行, 每 行 两 个 数, 代 表 G 0 的 一 条 边 的 两 个 顶 点 G 0 的 第 i 条 边 对 应 于 G 1 的 顶 点 i 输 出 需 要 满 足, 每 条 边 连 接 了 不 同 的 顶 点, 每 对 顶 点 间 至 多 只 有 一 条 边 你 可 以 自 行 给 顶 点 标 号, 但 顶 点 的 标 号 需 要 是 正 整 数, 而 且 不 应 超 过 10^9 样 例 输 入 样 例 输 出 第 16 页 共 24 页

17 Flare 提 示 样 例 的 图 是 三 角 形 ( 三 个 点, 两 两 间 均 有 边 ) 容 易 看 到 三 角 形 简 单 变 换 后 仍 是 三 角 形 当 然, 样 例 的 解 并 不 唯 一 数 据 规 模 与 约 定 对 10% 的 数 据,1<= n <= 10 对 20% 的 数 据,1<= n <= 15 对 30% 的 数 据,1<= n <= 20 另 有 5% 数 据, 图 为 一 条 链 ;5% 的 数 据, 图 为 一 个 环 ;5% 的 数 据, 图 为 完 全 图 ;5% 的 数 据, 图 的 每 个 连 通 块 为 上 述 三 种 情 形 之 一 对 70% 的 数 据,1<= n <= 10^3 对 100% 的 数 据,1<= n;m <= 10^6 第 17 页 共 24 页

18 能 量 棒 能 量 棒 命 题 人 : 王 钦 石 关 键 字 动 态 规 划 二 分 单 调 性 问 题 描 述 小 W 是 一 个 杰 出 的 登 山 家 一 天, 他 独 自 挑 战 一 座 神 秘 的 山 峰, 也 许 是 受 到 了 诅 咒, 他 不 小 心 将 背 包 掉 落 山 崖 他 摸 了 摸 口 袋, 发 现 只 剩 下 一 根 能 量 棒 能 量 棒 被 分 为 N 个 格 子, 每 个 格 子 上 有 一 个 正 整 数 A i, 作 为 一 个 登 山 家, 小 W 清 楚 他 应 该 把 能 量 棒 分 割 成 恰 好 K 段 使 用, 且 必 须 全 部 用 完 他 也 清 楚 使 用 一 段 A 值 和 为 x 的 能 量 棒 可 以 获 得 x 2 +B x + C 个 单 位 的 能 量 不 过 小 W 数 学 不 好, 他 不 知 道 应 该 如 何 分 割 能 量 棒 以 获 得 最 多 的 能 量, 请 你 帮 助 小 W 解 决 这 个 问 题 输 入 格 式 第 一 行 一 个 整 数 T, 表 示 此 测 试 点 包 含 测 试 数 据 的 组 数 ; 每 个 测 试 数 据 包 含 两 行 : 第 一 行 四 个 整 数 N, K, B, C, 用 空 格 隔 开, 如 题 目 描 述 中 所 述 ; 第 二 行 用 空 格 隔 开 的 N 个 整 数, 分 别 表 示 每 个 格 子 的 A i 输 出 格 式 对 于 每 个 测 试 数 据 一 行, 表 示 这 个 测 试 数 据 中 最 多 所 能 获 得 的 能 量 样 例 输 入 样 例 输 出 4 2 第 18 页 共 24 页

19 能 量 棒 数 据 规 模 与 约 定 测 试 点 编 号 T N K 其 他 约 定 1 <=10 <=2 2-4 <=100 <= <=5000 <= <= <=100 A 数 列 是 某 一 [1,v] 范 围 内 等 概 率 随 机 生 成 的 <= <= 无 对 于 全 部 的 测 试 数 据,1<=K<=N,ΣA i <= , B, C <=10 9 第 19 页 共 24 页

20 Color Color 命 题 人 : 陈 立 杰 资 源 限 制 时 间 限 制 :1 秒 内 存 限 制 :256MB 问 题 描 述 有 n 个 球 排 成 一 行, 每 个 球 有 它 的 颜 色, 我 们 每 次 随 机 取 出 两 个 球 a, b, 给 b 染 上 a 的 颜 色, 求 期 望 操 作 多 少 次 可 能 使 得 所 有 的 球 颜 色 相 同? 显 然 答 案 只 跟 每 种 颜 色 有 几 个 球 有 关 系, 我 们 只 要 给 出 每 个 颜 色 的 球 数 量 即 可 输 出 跟 答 案 相 对 误 差 在 10-9 以 内 就 算 做 正 确 输 入 格 式 第 一 行 一 个 数 c 表 示 有 c 种 颜 色 接 下 来 c 行 给 出 一 个 颜 色 球 数 输 出 格 式 一 行 一 个 数 表 示 答 案 数 据 规 模 与 约 定 10% n 5; 30% n 20; 40% n 25; 50% n 40; 80% n 10000; 100% n 10 10, c 第 20 页 共 24 页

21 Binomial Binomial 命 题 人 : 伍 一 鸣 问 题 描 述 给 定 n 和 p, 对 于 所 有 的 0 x < p x N, 求 满 足 个 数, 输 出 答 案 在 29 进 制 下 的 最 后 一 位 的 m 的 输 入 格 式 仅 一 行 包 含 两 个 正 整 数 n 和 p 输 出 格 式 仅 一 行, 为 一 个 长 度 为 p 的 字 符 串 s,s i 表 示 的 m 的 个 数 除 以 29 后 的 余 数,s i 视 为 一 个 29 进 制 的 数 字 样 例 输 入 20 4 样 例 输 出 D440 数 据 规 模 与 约 定 5% 的 数 据 :n < 2000; 30% 的 数 据 :n < 10 8 ; 50% 的 数 据 :n < p 5, p 5000; 85% 的 数 据 :n < p 5, p 2 16 ; 100% 的 数 据 :n < p 10, p 2 16 (p 为 质 数 ) 第 21 页 共 24 页

22 可 见 区 域 可 见 区 域 命 题 人 : 钟 沛 林 问 题 描 述 在 平 面 直 角 坐 标 系 中 有 n 条 互 不 相 交 ( 没 有 公 共 点 ) 且 所 在 直 线 不 会 经 过 (0,0) 的 线 段 有 一 个 人 站 在 (0,0), 他 的 视 野 是 360 度 的 但 是 他 在 某 一 个 方 向 上 的 视 野 会 被 该 方 向 上 碰 到 的 第 一 条 线 段 所 阻 挡, 问 他 能 看 到 的 区 域 面 积 有 多 大 ( 数 据 保 证 是 有 限 面 积 ) 如 下 图 ( 样 例 ), 可 以 看 到 的 面 积 就 是 11 为 了 加 大 难 度, 他 想 知 道, 在 删 除 一 条 线 段 的 情 况 下 能 看 到 最 大 多 大 的 面 积 ( 不 保 证 是 有 限 面 积 ) 进 一 步, 他 还 想 知 道, 在 删 除 两 条 线 段 的 情 况 下 能 看 到 最 大 多 大 的 面 积 ( 不 保 证 是 有 限 面 积 ) 输 入 格 式 第 一 行 一 个 整 数 n 表 示 线 段 条 数 接 下 来 n 行, 每 行 四 个 整 数 x 1, y 1, x 2, y 2 表 示 一 条 线 段 两 个 端 点 的 坐 标 输 出 格 式 第 一 行 一 个 保 留 两 位 小 数 的 实 数, 表 示 可 见 区 域 的 面 积 第 二 行 两 种 可 能, 如 果 删 除 一 条 线 段 以 后 能 使 得 看 到 的 区 域 有 无 限 大 输 出 infinite, 否 则 输 出 一 个 保 留 两 位 小 数 的 实 数, 表 示 这 种 情 况 下 能 看 到 的 最 大 面 积 第 三 行 两 种 可 能, 如 果 删 除 两 条 线 段 以 后 能 使 得 看 到 的 区 域 有 无 限 大 输 出 infinite, 否 则 输 出 一 个 保 留 两 位 小 数 的 实 数, 表 示 这 种 情 况 下 能 看 到 的 最 大 面 积 第 22 页 共 24 页

23 可 见 区 域 样 例 输 入 样 例 输 出 infinite infinite 数 据 规 模 与 约 定 对 于 所 有 数 据 1 <= n <= 坐 标 的 绝 对 值 <=10 3 area1.in area2.in area3.in 第 23 页 共 24 页

24 可 见 区 域 area4.in n<=10, 坐 标 的 绝 对 值 <=10 删 除 某 条 线 段 后 可 看 到 无 限 区 域 area5.in n<=1000 删 除 某 条 线 段 后 可 看 到 无 限 区 域 area6.in n<=1000 删 除 某 条 线 段 后 可 看 到 无 限 区 域 area7.in n<=50000 删 除 某 条 线 段 后 可 看 到 无 限 区 域 area8.in n<=50000 删 除 某 条 线 段 后 可 看 到 无 限 区 域 area9.in n<=50000 删 除 某 条 线 段 后 可 看 到 无 限 区 域 area10.in n<=50000 删 除 某 条 线 段 后 可 看 到 无 限 区 域 area11.in n<=200 删 除 两 条 线 段 后 能 看 到 无 限 区 域 area12.in n<=1000 删 除 两 条 线 段 后 能 看 到 无 限 区 域 area13.in n<=1000 删 除 两 条 线 段 后 能 看 到 无 限 区 域 area14.in n<=50000 删 除 两 条 线 段 后 能 看 到 无 限 区 域 area15.in n<=50000 删 除 两 条 线 段 后 能 看 到 无 限 区 域 area16.in n<=50 area17.in n<=300 area18.in n<=50000 area19.in n<=50000 area20.in n<=50000 第 24 页 共 24 页