输 出 同 样 分 为 T 个 部 分 两 组 数 据 的 输 出 之 间 应 当 输 出 一 空 白 行 注 意 输 出 文 件 的 末 尾 应 当 恰 有 一 空 白 行 对 于 每 组 数 据 的 每 个 询 问, 输 出 一 行, 包 含 一 个 整 数, 即 为 询 问 的 答 案 5 1

A. 单 调 时 间 限 制 :3000 毫 秒 内 存 限 制 :64MB 有 一 个 长 度 为 n 的 序 列, 记 作 a 1,, a n 你 需 要 回 答 m 个 询 问 每 个 询 问 会 给 定 一 个 区 间 [l, r], 你 需 要 输 出 序 列 a 在 区 间 [l, r] 的 部 分 中, 有 多 少 个 单 调 的 子 串 如 果 你 不 是 很 明 白 上 文 中 的 一 些 说 法, 请 参 考 下 面 的 定 义 : 序 列 a 在 区 间 [l, r] 的 部 分 是 由 原 序 列 a 的 元 素 a l, a l+1,, a r 1, a r 所 构 成 的 新 序 列 序 列 的 子 串 是 由 在 原 序 列 的 位 置 连 续 的 若 干 元 素 构 成 的 新 序 列 或 者 说, 序 列 在 任 意 合 法 区 间 的 部 分 都 是 一 个 子 串, 任 意 子 串 也 都 能 对 应 到 这 样 的 一 个 区 间 上 称 一 个 序 列 单 调, 当 且 仅 当 这 个 序 列 单 调 增 或 者 单 调 减 称 一 个 序 列 单 调 增, 当 且 仅 当 序 列 中 除 了 开 头 的 元 素 之 外, 其 他 所 有 元 素 都 严 格 大 于 其 前 一 元 素 单 调 减 序 列 的 定 义 类 似 输 入 文 件 包 含 若 干 组 测 试 数 据 第 一 行 包 含 一 个 整 数 T (T 5), 代 表 输 入 中 一 共 T 组 数 据 接 下 来 一 共 T 个 部 分 每 个 部 分 的 第 一 行 包 含 两 个 由 空 格 隔 开 的 整 数 n (1 n 00,000) 和 m (1 m 00,000), 分 别 代 表 序 列 长 度 和 操 作 数 第 二 行 包 含 n 个 由 空 格 隔 开 的 整 数 a 1,, a n (1 a i 10 9 ), 代 表 序 列 的 每 个 元 素 第 三 行 包 含 六 个 由 空 格 隔 开 的 整 数 l 1, r 1, b, c, d, e (1 l 1 r 1 n, 1 b, c, d, e 10 9 ), 其 作 用 将 在 下 一 段 中 阐 述 为 了 减 小 输 入 文 件 的 大 小, 询 问 均 由 给 定 公 式 产 生 记 第 i 个 询 问 中 的 区 间 为 [l i, r i], 则 第 1 个 询 问 中 区 间 的 左 右 端 点 为 数 据 第 三 行 中 的 头 两 个 整 数 l 1 和 r 1 对 于 剩 下 的 询 问, 通 过 下 面 的 公 式 计 算 其 区 间 的 左 右 端 点 l i 和 r i: 令 p i = ((b l i 1 + c) mod n) + 1, q i = ((d r i 1 + e) mod n) + 1; 则 l i = min(p i, q i), r i = max(p i, q i) 显 然 有 1 l i r i n 保 证 序 列 中 相 邻 的 元 素 不 相 等 第 1 页, 共 15 页

输 出 同 样 分 为 T 个 部 分 两 组 数 据 的 输 出 之 间 应 当 输 出 一 空 白 行 注 意 输 出 文 件 的 末 尾 应 当 恰 有 一 空 白 行 对 于 每 组 数 据 的 每 个 询 问, 输 出 一 行, 包 含 一 个 整 数, 即 为 询 问 的 答 案 5 1 3 4 5 1 5 1 0 1 3 5 1 4 3 5 1 5 4 1 1 0 15 6 10 1 样 例 解 释 第 一 组 数 据 中 的 两 个 询 问 为 :[1, 5] 和 [, 4] 第 二 组 数 据 中 的 两 个 询 问 为 :[1, 5] 和 [1, 1] 第 二 组 数 据 的 第 一 个 询 问 中 的 10 个 单 调 子 串 如 下 : [1,1]: 1; [,]: ; [3,3]: 4; [4,4]: 3; [5,5]: 5; [1,]: 1 ; [,3]: 4; [3,4]: 4 3; [4,5]: 3 5; [1,3]: 1 4. 第 页, 共 15 页

B. SPFA 时 间 限 制 :1000 毫 秒 内 存 限 制 :56MB 小 七 很 喜 欢 信 息 学, 尤 其 喜 欢 用 SPFA 算 法 求 最 短 路 假 如 有 一 个 n 个 节 点 m 条 边 的 带 权 有 向 图, 节 点 编 号 为 1 到 n, 边 权 均 为 正 数 小 七 会 这 样 求 1 号 节 点 到 其 它 所 有 节 点 的 最 短 路 : 1. 有 一 个 队 列 Q, 初 始 化 为 空 有 一 个 d 数 组, 对 于 1 v n 有 d[v] = 10^100. 执 行 d[1] = 0, 把 1 加 入 队 列 末 尾 3. 当 Q 不 为 空 时 重 复 执 行 第 4 步 4. 弹 出 Q 队 首 元 素 v, 从 小 到 大 枚 举 u = 1,..., n, 如 果 v 到 u 有 一 条 长 度 为 w 的 有 向 边 且 d[v] + w < d[u], 那 么 把 d[u] 赋 值 为 d[v] + w 然 后 如 果 u 不 在 Q 中 就 把 u 加 入 队 列 末 尾 现 在, 给 你 一 个 正 整 数 T, 你 需 要 给 出 一 个 带 权 无 向 图 使 得 SPFA 算 法 中 第 4 步 的 执 行 次 数 恰 好 为 T 若 干 行, 每 行 一 个 正 整 数 T, 表 示 一 组 数 据 数 据 组 数 不 超 过 0 1 T 15000 对 于 每 组 数 据, 输 出 一 个 带 权 有 向 图 其 中, 第 一 行 两 个 整 数 n 和 m 你 需 要 保 证 1 n 00,m 0 接 下 来 m 行, 每 行 三 个 正 整 数 v, u, w 你 需 要 保 证 1 v, u n,1 w 1000, 且 v u 你 需 要 保 证 图 中 任 意 两 点 v, u 之 间,v 到 u 至 多 只 有 一 条 边 第 3 页, 共 15 页

SPFA 1 3 1 0 3 3 1 1 3 1 1 3 3 第 4 页, 共 15 页

C. 琴 和 梨 时 间 限 制 :1000 毫 秒 内 存 限 制 :64MB 欧 葱 女 士 喜 欢 弹 钢 琴, 然 而 奇 怪 的 事, 她 喜 欢 在 弹 钢 琴 的 时 候 在 每 个 琴 键 旁 放 一 些 梨 然 而 比 这 更 奇 怪 的 事, 欧 葱 女 士 的 钢 琴 有 N 个 键 而 非 108 个 键, 并 且 第 i 个 琴 键 旁 有 a i 个 梨 然 而 比 更 奇 怪 的 事 还 要 奇 怪 的 是, 欧 葱 女 士 弹 钢 琴 的 时 候 会 选 出 一 些 琴 键 ( 且 必 须 选 出 一 些 琴 键 ), 如 果 这 些 琴 键 不 存 在 三 个 琴 键 i<j<k 满 足 a i<a j<a k, 那 么 这 样 的 一 种 选 择 方 式 便 是 欧 葱 女 士 喜 欢 的 现 在 欧 葱 女 士 希 望 知 道 有 多 少 选 择 琴 键 的 方 法 是 她 所 喜 欢 的 输 入 数 据 有 多 组 测 试 数 据, 第 一 有 一 个 整 数 T 代 表 数 据 组 数 对 于 每 组 测 试 数 据, 第 一 行 一 个 整 数 N 代 表 琴 键 的 个 数 接 下 来 一 行 N 个 整 数 a 1,a,,a N 代 表 琴 键 旁 梨 的 个 数 我 们 保 证 1 N 100,1 a i N 并 且 i j,a i a j. 对 于 每 组 测 试 数 据, 输 出 答 案 模 10 9 +7 5 1 3 3 1 4 3 1 4 5 1 3 5 4 6 5 4 3 6 1 第 5 页, 共 15 页

3 7 13 63 第 6 页, 共 15 页

D. LW 游 戏 时 间 限 制 :1000 毫 秒 内 存 限 制 :64MB 在 一 个 月 黑 风 高 的 夜 晚, 小 L 和 小 W 写 完 了 java 大 作 业, 寂 静 而 无 聊 的 夜 晚 要 怎 样 度 过 呢? 小 L: 小 W, 我 们 来 玩 一 个 游 戏 吧? 小 W: 好 啊! 斗 地 主? 小 L: 那 种 游 戏 你 还 没 打 够 吗, 我 们 来 点 更 好 玩 的, 我 们 来 自 己 设 计 一 个 新 游 戏 吧! 小 W: 支 持 啊! 你 有 什 么 好 的 idea? 小 L: 我 有 一 个 想 法, 你 看 如 何? 假 设 n 个 棋 子, 棋 子 i 被 我 选 中 得 分 为 xi, 被 你 选 中 得 分 为 yi, 有 些 棋 子 两 两 之 间 有 特 殊 关 系, 如 果 棋 子 A 和 B 有 特 殊 关 系, 那 么 他 们 如 果 同 时 被 你 选 有 额 外 得 分 a,a 被 我 选 B 被 你 选 有 额 外 得 分 b,a 被 你 选 B 被 我 选 有 额 外 得 分 c, 同 时 被 我 选 有 额 外 得 分 d,ab 之 间 可 能 有 多 对 特 殊 关 系 我 的 目 标 是 让 得 分 最 小 化, 你 的 目 标 是 让 得 分 最 大 化 为 了 游 戏 的 平 衡, 应 该 保 证 a+d=b+c 为 了 保 证 我 们 两 最 后 选 的 棋 子 数 一 样, 应 该 保 证 n 是 偶 数 小 W: 这 个 好 啊! 比 斗 地 主 不 知 道 高 到 哪 里 去 了! 就 叫 LW 游 戏 吧? 小 L: 支 持 啊 那 我 先 手, 你 后 手, 我 们 开 始 吧? 小 C 在 旁 边 默 默 的 白 了 他 们 两 一 眼 小 C 知 道, 小 L 和 小 W 都 是 绝 顶 聪 明 之 人, 他 们 每 一 步 总 是 选 择 当 前 情 况 下 的 最 优 策 略 为 了 证 明 自 己 比 他 们 更 聪 明, 小 C 想 预 测 出 LW 游 戏 最 后 的 得 分 结 果 你 能 帮 助 他 吗? 输 入 文 件 包 含 若 干 组 测 试 数 据 第 一 行 包 含 一 个 整 数 T (T 5), 代 表 输 入 中 一 共 T 组 数 据 接 下 来 一 共 T 个 部 分 每 个 部 分 的 第 一 行 一 个 数 n(n<=100), 表 示 棋 子 个 数 ; 接 下 来 n 行 每 行 个 数 xi,yi; 接 下 来 一 行 一 个 数 m, 表 示 特 殊 关 系 对 数 ; 接 下 来 m 行 每 行 6 个 数, 分 别 是 A,B,a,b,c,d; 第 7 页, 共 15 页

输 入 数 据 保 证 n 是 偶 数,a+d=b+c; 输 入 数 据 保 证 0<=x,y,a,b,c,d,m<=10000. 输 出 T 行, 每 行 是 输 入 游 戏 的 最 后 得 分 ( 见 ) 6 9 4 1 0 7 6 0 7 6 1 5 6 4 5 7 5 1 8 9 6 5 8 0 8 8 7 3 9 6 0 4 6 6 3 1 0 0 9 9 1 0 9 7 1 4 0 1 1 3 9 1 8 1 5 6 6 1 6 5 0 14 9 Case 1: 6 Case : 53 第 8 页, 共 15 页

E. 随 机 时 间 限 制 :1000 毫 秒 内 存 限 制 :64MB 有 n 个 点, 编 号 为 1 到 n, 每 次 独 立 随 机 地 选 取 1 到 n 之 间 两 个 数 字 u 和 v, 将 节 点 u 和 节 点 v 连 起 来 问 期 望 多 少 步 后 整 个 图 成 为 一 个 连 通 图 答 案 对 p 取 模 输 入 文 件 包 含 若 干 组 测 试 数 据 第 一 行 包 含 一 个 整 数 T(T 5), 表 示 输 入 中 一 共 T 组 数 据 接 下 来 T 行, 每 行 两 个 正 整 数 n(1 n 100) 和 p(10 6 p 10 9 +7) 保 证 p 为 素 数 输 出 同 样 分 为 T 个 部 分 对 于 每 组 数 据 输 出 一 行, 一 个 整 数, 如 果 答 案 能 被 表 示 为 最 简 分 数 a/b, 请 输 出 c(0 c<p), 满 足 b*c=a (mod p) 保 证 答 案 存 在 1000000007 3 1000000007 750000009 样 例 解 释 n= 时 有 1/ 的 概 率 选 到 1 与 之 间 的 边, 期 望 为 n=3 时 答 案 为 3.75 第 9 页, 共 15 页

F. Theta s 时 间 限 制 :5000 毫 秒 内 存 限 制 :56MB 为 了 拯 救 处 于 废 校 危 机 中 的 学 校, 小 C 小 F 小 H 小 K 小 P 小 T 小 V 小 Y 小 Z 九 名 学 生 决 定 站 出 来, 参 加 ACM 的 比 赛 在 ACM 的 天 地 之 中, 他 们 的 世 界 宽 广 无 边, 所 有 的 土 地 都 在 他 们 的 脚 下 被 丈 量 ; 心 灵 的 草 原 宽 广 无 垠, 是 他 们 的 向 往, 每 一 刻 皆 在 奔 波 的 旅 途 上 生 活 原 本 就 是 奔 波 踏 遍 千 山 万 水, 心 灵 的 骨 骼 强 壮, 收 集 所 能 感 知 捕 获 的 一 切 信 息, 纳 入 记 忆 的 皮 囊, 待 到 休 憩 时 刻, 拿 出 品 尝 直 到 世 界 终 了 之 时, 他 们 遇 到 了 他 们 必 须 解 决 的 一 道 问 题 现 在 有 一 棵 N 个 点 的 树, 每 条 边 都 有 边 权 小 F 和 小 K 现 在 要 玩 一 个 游 戏, 每 次 游 戏 开 始 的 时 候, 小 F 和 小 K 的 得 分 都 是 0, 并 且 他 们 会 站 到 树 上 两 个 不 同 的 节 点 上 去 小 F 和 小 K 两 人 轮 流 行 动, 小 F 先 行 动 每 次 行 动 他 们 会 走 到 与 当 前 节 点 相 邻 的 节 点 中 的 一 个, 并 且 自 己 的 得 分 会 异 或 上 这 条 边 的 边 权 每 个 人 不 能 走 对 方 到 达 过 的 节 点, 但 是 自 己 走 过 的 节 点 可 以 反 复 经 过, 并 且 他 们 随 时 可 以 选 择 结 束 自 己 的 游 戏 小 F 和 小 K 都 想 取 得 胜 利, 所 以 他 们 在 最 大 化 自 己 分 数 的 前 提 下 要 最 小 化 对 方 的 分 数, 而 你 需 要 做 的 是, 对 他 们 的 每 次 游 戏, 回 答 双 方 都 采 取 最 优 策 略 下 小 F 所 能 得 到 的 分 数 数 据 多 组 测 试 数 据, 第 一 有 一 个 整 数 T 代 表 数 据 组 数 对 于 每 组 测 试 数 据, 第 一 行 一 个 整 数 N(1 N 10 5, N 5*10 5 ), 代 表 树 中 的 节 点 个 数 接 下 来 N-1 行, 每 行 三 个 整 数 s,e,d(0 d 10 9 ), 代 表 s 与 e 之 间 有 一 条 边 权 为 d 的 边 接 下 来 一 行 一 个 整 数 M, 代 表 他 们 进 行 了 M(1 M 10 5, M 5*10 5 ) 次 游 戏 接 下 来 M 行, 每 行 两 个 整 数 x,y 代 表 这 轮 游 戏 中, 小 F 和 小 K 分 别 站 在 x,y 上 对 于 每 组 询 问, 输 出 小 F 的 得 分 1 6 1 5 4 4 5 3 6 1 1 3 1 第 10 页, 共 15 页

3 1 3 4 1 5 4 3 5 第 11 页, 共 15 页

G. 三 角 形 时 间 限 制 :1000 毫 秒 内 存 限 制 :64MB 小 W 有 三 条 木 棍, 长 度 为 a,b,c 他 能 将 这 三 条 木 棍 分 别 增 加 x,y,z 的 长 度, 代 价 为 (x+1)(y+1)(z+1) 他 想 把 这 三 条 木 棍 拼 成 面 积 为 正 的 三 角 形, 求 最 小 的 代 价 输 入 文 件 包 含 若 干 组 测 试 数 据 第 一 行 包 含 一 个 整 数 T, 表 示 输 入 中 一 共 T 组 数 据 接 下 来 T 行, 每 行 三 个 正 整 数 a,b,c(1 a,b,c 10 9 ) 输 出 同 样 分 为 T 个 部 分 对 于 每 组 数 据 输 出 一 行, 一 个 整 数, 表 示 最 小 的 代 价 3 3 1 1 1 样 例 解 释 第 二 个 样 例 中 需 要 把 其 中 一 根 长 度 为 1 的 木 棍 增 加 1 第 1 页, 共 15 页

H. 酒 井 杯 足 球 赛 时 间 限 制 :1000 毫 秒 内 存 限 制 :51MB 一 年 一 度 的 酒 井 杯 又 开 赛 了! 今 年 一 共 有 n 支 队 伍 参 赛, 每 支 队 伍 都 有 一 个 对 应 的 能 力 值 ai 比 赛 的 规 则 是 这 样 的 : 每 一 轮 从 当 前 所 有 的 参 赛 队 伍 中 以 等 概 率 随 机 抽 取 两 支 队 伍, 让 这 两 支 队 伍 进 行 比 赛, 胜 利 的 队 伍 保 留, 失 败 的 队 伍 淘 汰 直 到 最 后 只 剩 下 一 支 参 赛 队 伍 为 止 两 支 队 伍 比 赛 的 结 果 取 决 于 他 们 的 能 力 值, 能 力 值 高 的 队 伍 将 会 取 得 比 赛 的 胜 利 若 两 支 队 伍 能 力 值 相 同, 则 两 支 队 伍 将 分 别 以 0.5 的 概 率 胜 利 你 能 告 诉 体 育 部 的 同 学 们, 最 后 酒 井 杯 的 冠 军 能 力 值 的 期 望 么? 输 入 有 多 组 测 试 数 据 对 于 每 组 测 试 数 据 : 第 一 行 一 个 整 数 n, 表 示 n 支 参 赛 队 伍 (n <= 100000) 第 二 行 n 个 整 数 :a 1, a,... a n 表 示 每 支 队 伍 的 能 力 值 (0<= a i <=100000) 对 于 每 组 输 入 数 据 : 输 出 一 个 数 X, 表 示 酒 井 杯 冠 军 的 能 力 值 期 望, 四 舍 五 入 保 留 小 数 点 后 两 位 10 1 3 9 7 8 4 9 9 9.00 第 13 页, 共 15 页

I. 会 议 时 间 限 制 :1000 毫 秒 内 存 限 制 :51MB 小 A 所 在 的 班 级 喜 欢 开 会 但 是 他 们 班 的 会 议 以 一 种 奇 怪 的 方 式 召 开 初 始 的 时 候, 每 个 人 都 知 道 一 定 的 消 息 ( 消 息 量 可 以 是 实 数 ) 第 一 轮, 他 们 会 把 手 中 的 消 息 平 分 之 后 传 递 给 他 们 所 有 的 好 朋 友, 并 且 给 自 己 留 一 份 ( 平 分 的 时 候 他 们 会 把 手 头 的 消 息 量 除 以 好 朋 友 的 数 量 +1) 第 二 轮, 他 们 会 将 第 一 轮 中 收 到 的 消 息 平 分 之 后 传 递 给 他 们 的 所 有 朋 友, 并 且 给 自 己 留 一 份 ( 平 分 的 时 候 他 们 会 把 手 头 的 消 息 量 除 以 好 朋 友 的 数 量 +1) 这 个 过 程 将 会 一 直 持 续 下 去, 直 到 每 一 个 人 在 某 一 轮 收 的 消 息 数 量 与 上 一 轮 的 收 到 的 消 息 数 量 相 同, 会 议 结 束 小 A 相 信 这 样 的 会 议 方 式 能 够 最 有 效 的 共 享 信 息 现 在 给 定 小 A 班 级 同 学 之 间 的 朋 友 关 系, 请 你 给 出 一 个 会 议 终 止 的 局 面 : 即 给 出 每 一 个 同 学 手 中 当 前 的 消 息 数, 满 足 下 一 轮 他 们 收 到 的 消 息 数 与 当 前 消 息 数 相 同 输 入 有 多 组 测 试 数 据 ( 不 多 于 5 组 ) 对 于 每 组 测 试 数 据 : 第 一 行 一 个 整 数 n(3 <= n <= 100), 表 示 小 A 班 上 同 学 的 个 数 接 下 来 一 个 n*n 的 01 矩 阵, 若 第 i 行 第 j 列 为 1, 表 示 i 号 同 学 和 j 号 同 学 是 好 朋 友 保 证 这 个 矩 阵 是 对 称 的, 并 且 第 i 行 第 i 列 为 0 对 于 每 组 输 入 数 据 : 输 出 n 行, 每 行 一 个 实 数, 表 示 结 束 局 面 中 第 i 个 同 学 手 中 的 消 息 量 请 保 证 所 有 同 学 的 消 息 量 之 和 近 似 地 等 于 1 3 0 1 0 1 0 1 0 1 0 0.857143141 第 14 页, 共 15 页

说 明 0.485713719 0.857143141 对 于 每 一 组 测 试 数 据 : 你 的 输 出 需 要 满 足 : 设 第 i 个 同 学 手 中 的 消 息 量 为 ai, 下 一 轮 第 i 个 同 学 收 到 的 消 息 量 为 bi, 有 : ai - bi <= 1e-5 每 一 个 同 学 手 中 的 消 息 量 ai>=0 设 所 有 同 学 手 中 消 息 量 之 和 为 sum, 则 sum-1 <= 1e-5 你 的 输 出 应 该 是 使 用 双 精 度 浮 点 数 能 够 保 存 的 实 数, 为 了 保 证 输 出 的 精 度, 你 应 该 尽 可 能 地 输 出 实 数 的 位 数 第 15 页, 共 15 页