目 录 1 课 程 与 作 业...1 1.1 作 业 概 述...1 1.2 作 业 提 交...1 1.3 无 效 的 提 交...1 1.4 补 交...2 2 评 分 方 式...2 2.1 诚 信 守 则...2 2.2 黑 盒 评 测...2 2.3 白 盒 评 测...2 3 课 程

数 据 结 构 编 程 作 业 说 明 清 华 大 学 计 算 机 系 数 据 结 构 教 学 团 队 2016.09

目 录 1 课 程 与 作 业...1 1.1 作 业 概 述...1 1.2 作 业 提 交...1 1.3 无 效 的 提 交...1 1.4 补 交...2 2 评 分 方 式...2 2.1 诚 信 守 则...2 2.2 黑 盒 评 测...2 2.3 白 盒 评 测...2 3 课 程 要 求...3 3.1 MOOC 课 堂 (xuetangx, edx)...3 3.2 全 校 选 修 课 ( 秋 季 )...3 3.3 全 校 选 修 课 (SPOC 春 季 )...3 3.4 计 算 机 系 专 业 课...4 3.5 其 它 课 堂...4 附 :FAQ...4 附 :OJ 分 档 评 测 的 图 片 说 明...7 附 : 新 增 Java 支 持...8 附 :OJ 使 用 技 巧...8 附 : 输 入 输 出 技 巧...9 附 : 一 些 常 见 编 程 错 误... 11 附 :Visual Studio msvc 与 GNU gcc 的 差 异... 11

1 课 程 与 作 业 1.1 作 业 概 述 编 程 作 业 在 线 提 交, 网 址 http://dsa.cs.tsinghua.edu.cn/oj/ 有 些 课 程 是 公 开 课 程 ( 如 MOOC 等 ), 在 Course->Select public courses 里 直 接 选 课 有 些 课 程 是 私 有 课 程, 需 要 使 用 教 师 发 放 的 邀 请 码 选 课, 或 直 接 由 教 师 加 进 课 堂 进 入 一 个 课 堂, 有 若 干 次 编 程 作 业 ( 简 称 PA), 并 在 左 边 显 示 PA 截 止 时 间 PA 标 题 的 背 景, 绿 色 表 示 尚 未 截 止, 红 色 表 示 即 将 在 一 周 内 截 止, 灰 色 表 示 已 经 截 止 每 次 PA 有 若 干 道 题 目, 各 题 目 在 本 次 PA 中 占 的 权 重 在 题 目 标 题 的 后 面 题 目 通 常 分 为 标 题 描 述 输 入 输 出 样 例 限 制 提 示 等 部 分 如 无 特 殊 说 明, 所 有 题 目 统 一 使 用 标 准 输 入 和 标 准 输 出 在 限 制 部 分, 通 常 都 指 定 了 输 入 的 取 值 范 围, 你 的 程 序 不 必 考 虑 范 围 之 外 的 情 况 在 限 制 部 分, 有 的 题 目 限 制 了 你 能 使 用 的 方 法 程 序 输 出 应 与 标 准 答 案 一 致, 请 留 意 多 余 的 空 格 制 表 符 回 车 和 换 行 行 末 空 格 和 文 末 换 行 一 般 不 会 影 响 评 分 每 题 得 分 由 黑 盒 测 试 和 白 盒 测 试 组 成, 成 绩 比 例 详 见 课 程 要 求 节 提 醒 : 应 对 算 法 的 时 间 和 空 间 复 杂 度 做 充 分 和 准 确 的 估 计, 正 确 但 低 效 的 程 序 无 法 获 得 高 分, 甚 至 可 能 无 法 得 分 1.2 作 业 提 交 在 截 止 时 间 前, 提 交 代 码 至 OJ 并 标 记 为 最 终 版 本 (Mark it as final version); 截 止 时 间 前 可 以 多 次 标 记, 以 最 后 标 记 的 为 准 ; 通 过 其 它 渠 道 ( 电 子 邮 件 网 络 学 堂 等 ) 提 交 的 无 效 每 道 题 需 要 在 OJ 上 签 署 Honor Code 有 的 课 程 不 需 要 Honor Code, 详 见 课 程 要 求 节 每 道 题 需 要 在 OJ 上 提 交 一 份 解 题 报 告 (Report) 有 的 课 程 不 需 要 Report, 详 见 课 程 要 求 节 代 码 如 果 含 有 多 个 文 件, 可 以 将 所 有 代 码 置 于 顶 层 目 录 直 接 打 包 (zip tar gz 等 格 式 ) 提 交 每 次 提 交 的 代 码 文 件 不 超 过 200KB 1.3 无 效 的 提 交 无 效 的 提 交 记 0 分, 包 括 ( 但 不 限 于 ) 以 下 方 面 : a) 未 在 作 业 截 止 时 间 前 标 记 最 终 版 本 b) 标 记 的 最 终 版 本 在 OJ 上 无 法 通 过 编 译 c) 需 要 签 署 Honor Code 但 未 签 署 1

d) 未 在 题 目 限 制 部 分 规 定 的 范 围 内 选 用 数 据 结 构 和 算 法 ( 题 目 提 示 部 分 只 是 提 供 了 一 些 方 法, 不 具 有 约 束 力 ) 注 : 如 果 需 要 提 交 Report 但 未 提 交, 那 么 只 会 导 致 本 题 白 盒 成 绩 计 0 分, 不 会 导 致 整 题 无 效 1.4 补 交 补 交 作 业 会 影 响 整 个 课 堂 的 评 测 和 代 码 查 重, 因 此 原 则 上 不 接 受 补 交 补 交 的 作 业 ( 源 代 码 Report Honor Code 文 本 ) 请 第 一 时 间 以 附 件 形 式 交 到 网 络 学 堂 课 程 答 疑 区, 并 在 正 文 里 说 明 情 况 提 交 后 不 要 修 改, 以 免 时 间 戳 变 化 即 使 接 受 补 交, 该 题 分 数 也 会 受 到 折 扣, 迟 交 时 间 过 长 会 导 致 折 扣 至 0 2 评 分 方 式 2.1 诚 信 守 则 若 标 记 的 最 终 版 本 出 现 代 码 雷 同, 则 在 Honor Code 中 未 予 声 明 者 题 分 记 -100 分, 有 声 明 者 题 分 酌 情 折 扣 若 查 阅 资 料 参 考 了 代 码, 但 在 Honor Code 中 未 予 声 明, 则 题 分 酌 情 折 扣 过 度 参 考 资 料, 在 一 定 程 度 上 降 低 了 作 业 难 度, 可 能 影 响 起 评 分 若 标 记 的 最 终 版 本 出 现 代 码 雷 同, 但 没 有 签 署 Honor Code, 那 么 按 无 效 的 提 交 计 算, 记 0 分 而 不 会 记 负 分, 代 码 雷 同 的 另 一 方 也 不 会 因 此 受 到 影 响 2.2 黑 盒 评 测 每 题 参 与 黑 盒 测 试 的 代 码 版 本, 以 作 业 截 止 前 最 后 一 次 标 记 的 为 准 评 测 分 为 五 成 测 九 成 测 和 全 集 测 五 成 测 : 测 前 50 % 的 测 试 点 九 成 测 : 测 前 90 % 的 测 试 点 全 集 测 : 测 所 有 测 试 点 作 业 截 止 时, 统 一 对 所 有 学 生 的 最 终 版 本 进 行 全 集 测, 以 这 次 测 试 成 绩 作 为 本 题 的 黑 盒 测 试 成 绩 作 业 截 止 后, 再 经 过 一 段 预 设 时 间, 可 以 自 由 全 集 测 有 三 天 申 诉 期, 如 果 发 现 全 集 测 成 绩 与 黑 盒 测 试 成 绩 有 较 大 差 异, 请 在 Piazza 讨 论 区 提 出 申 诉 参 考 附 :OJ 分 档 评 测 的 图 片 说 明 2.3 白 盒 评 测 先 考 察 解 题 报 告 (Report), 然 后 考 察 代 码 风 格 模 块 划 分 注 释 清 晰 度 等 若 没 有 提 2

交 Report, 则 该 题 白 盒 测 试 记 0 分 解 题 报 告 请 尽 量 使 用 纯 文 本, 内 容 包 括 ( 但 不 限 于 ): 1. 所 使 用 数 据 结 构 与 算 法 的 构 思 原 理 和 实 现 要 点 2. 完 成 过 程 中 遇 到 的 问 题, 排 除 问 题 的 主 要 过 程 使 用 的 方 法 和 技 巧, 以 及 参 考 资 料 3. 时 间 和 空 间 复 杂 度 的 估 算 4. ( 可 选 ) 介 绍 理 论 分 析 与 实 测 效 果 的 吻 合 程 度, 不 吻 合 时 进 一 步 解 释 原 因 5. ( 可 选 ) 所 用 方 法 的 特 别 新 颖 或 创 新 之 处 滥 用 全 局 变 量, 或 使 用 分 装 性 差 的 数 据 结 构 往 往 会 影 响 白 盒 得 分 3 课 程 要 求 3.1 MOOC 课 堂 (xuetangx, edx) 不 需 要 签 署 Honor Code, 不 需 要 提 交 Report 黑 盒 评 测 总 是 使 用 全 集 测 黑 盒 评 测 成 绩 占 100%, 不 进 行 白 盒 评 测 不 进 行 代 码 查 重, 不 接 受 补 交 和 申 诉 允 许 使 用 C/C++/JAVA 语 言 使 用 C++ 时 禁 止 使 用 STL 从 MOOC 晋 级 到 THU/CST 课 堂 的 学 生, 在 THU/CST 课 堂 上 也 不 需 要 签 署 Honor Code 和 提 交 Report, 黑 盒 评 测 成 绩 占 100%, 不 进 行 代 码 查 重 3.2 全 校 选 修 课 ( 秋 季 ) 需 要 签 署 Honor Code, 并 需 要 提 交 Report 作 业 截 止 前 使 用 五 成 测, 每 人 每 题 还 有 5 次 九 成 测 的 机 会 黑 盒 测 试 成 绩 视 情 况 占 60%~80%, 白 盒 测 试 成 绩 占 剩 余 的 分 数 进 行 代 码 查 重 有 限 地 接 受 补 交 和 申 诉 只 允 许 使 用 C/C++ 语 言 禁 止 使 用 STL 3.3 全 校 选 修 课 (SPOC 春 季 ) 需 要 签 署 Honor Code, 并 需 要 提 交 Report 作 业 截 止 前 使 用 五 成 测, 每 人 每 题 还 有 5 次 九 成 测 的 机 会 黑 盒 测 试 成 绩 视 情 况 占 60%~80%, 白 盒 测 试 成 绩 占 剩 余 的 分 数 进 行 代 码 查 重 有 限 地 接 受 补 交 和 申 诉 只 允 许 使 用 C/C++ 语 言 禁 止 使 用 STL 每 次 PA 只 取 N 题 的 得 分,N 在 学 期 初 确 定, 详 见 FAQ 3

3.4 计 算 机 系 专 业 课 需 要 签 署 Honor Code, 并 需 要 提 交 Report 作 业 截 止 前 使 用 五 成 测, 每 人 每 题 还 有 5 次 九 成 测 的 机 会 黑 盒 测 试 成 绩 视 情 况 占 60%~80%, 白 盒 测 试 成 绩 占 剩 余 的 分 数 进 行 代 码 查 重 有 限 地 接 受 补 交 和 申 诉 只 允 许 使 用 C/C++ 语 言 禁 止 使 用 STL 每 次 PA 只 取 N 题 的 得 分,N 在 学 期 初 确 定, 详 见 FAQ 3.5 其 它 课 堂 其 它 课 堂 由 教 师 确 定 评 分 方 案 下 表 简 要 对 比 以 上 四 个 课 堂 的 要 求 MOOC THU THU(SPOC) CST Honor Code 不 需 要 需 要 需 要 需 要 Report 不 需 要 需 要 需 要 需 要 黑 盒 测 试 点 全 集 测 五 成 测 / 九 成 测 五 成 测 / 九 成 测 五 成 测 / 九 成 测 黑 盒 成 绩 比 重 100% 60%~80% 60%~80% 60%~80% 白 盒 成 绩 比 重 0% 20%~40% 20%~40% 20%~40% 代 码 查 重 无 有 有 有 补 交 / 申 诉 不 接 受 有 限 接 受 有 限 接 受 有 限 接 受 JAVA 语 言 接 受 禁 用 禁 用 禁 用 STL 禁 用 禁 用 禁 用 禁 用 PA 得 分 方 案 所 有 题 所 有 题 只 取 N 题 只 取 N 题 附 :FAQ 1. 杂 项 a) 助 教 的 联 系 方 式? 在 Piazza 讨 论 区 的 公 告 中 有 助 教 的 联 系 方 式 本 课 程 主 要 使 用 Piazza 讨 论 区 讨 论 解 答 问 题 校 内 学 生 在 Piazza(https://piazza.com) 中 搜 索 本 学 期 本 课 程,MOOC 学 生 使 用 MOOC 平 台 提 供 的 讨 论 区 b) 课 程 讲 义 在 哪 下 载? 讲 义 统 一 在 网 盘 上 发 布 c) 如 何 提 问, 并 更 加 高 效 地 得 到 有 帮 助 的 解 答? 4

描 述 问 题 时 请 不 要 过 于 概 括, 比 如 这 样 两 个 问 题 : 我 本 地 运 行 正 确 怎 么 在 OJ 上 就 错 了? 我 本 地 运 行 正 确, 为 什 么 OJ 上 编 译 错 误, 并 提 示 main should return int? 显 然, 后 者 更 能 得 到 有 帮 助 的 回 答 d) 请 问 总 评 成 绩 的 额 外 加 分 是 什 么 意 思? 请 参 见 讲 义 00.Syllabus 一 节 中 的 相 关 说 明 2. OJ 使 用 说 明 a) OJ 上 需 要 提 交 哪 些 文 件? 只 需 要 提 交 源 代 码 文 件 (*.cpp/*.c/*.h), 其 余 文 件 尽 量 不 要 一 同 打 包 Report 只 需 要 提 交 readme.txt/pdf 单 文 件 b) OJ 上 的 编 译 环 境 与 本 地 有 何 不 同, 需 要 注 意 哪 些 问 题? OJ 使 用 的 是 Linux 系 统,GCC 4.9.2 编 译 器, 不 支 持 C++11 它 与 Visual Studio 中 的 MSVC 编 译 器 有 一 些 微 小 的 区 别, 例 如 :main 函 数 的 返 回 值 必 须 为 int, 默 认 不 会 包 含 任 何 头 文 件 等 等 一 般 认 为 GCC 编 译 器 是 更 加 符 合 C / C++ 标 准 的, 所 以 如 果 遇 到 了 本 地 编 译 成 功 OJ 编 译 失 败 的 例 子, 请 根 据 提 示 进 一 步 修 改 源 程 序 主 要 区 别 在 附 :Visual Studio msvc 与 GNU gcc 的 差 异 中 列 出 c) OJ 上 是 否 禁 止 使 用 某 些 库? 是 的, 在 OJ 上 移 除 了 某 些 头 文 件, 例 如 vector algorithm 原 则 上, 只 要 你 的 作 业 能 够 通 过 编 译, 且 不 违 反 课 程 要 求 和 题 目 要 求, 就 没 有 任 何 问 题 不 过 不 包 括 手 动 把 这 些 头 文 件 与 你 的 作 业 其 他 代 码 一 同 打 包 提 交 上 来 :) 例 如 C 标 准 库 stdlib 中 的 qsort 函 数 是 允 许 使 用 的 d) 输 入 输 出 应 该 采 用 哪 些 函 数? 请 使 用 scanf 和 printf 来 代 替 cin 和 cout, 某 些 情 况 下 后 者 效 率 远 远 远 远 低 于 前 者 更 高 效 的 读 入 是 用 fread, 然 后 手 动 解 析 文 本 e) Runtime Error 是 怎 么 回 事? Runtime Error 是 指 程 序 在 运 行 过 程 中 出 现 了 问 题, 通 常 是 内 存 访 问 的 问 题, 比 如 数 组 下 标 越 界 一 般 这 些 问 题 在 小 规 模 测 试 的 时 候 不 会 发 现, 而 在 OJ 上 大 规 模 数 据 测 试 时 候 就 容 易 暴 露 出 来, 所 以 请 自 行 构 造 一 些 数 据 来 调 试 程 序 此 外, 需 要 注 意 的 是,main 函 数 必 须 以 return 0; 结 束, 如 果 返 回 值 非 0, 也 会 被 认 为 是 Runtime Error 如 果 保 证 返 回 值 为 0 并 且 希 望 知 道 OJ 返 回 错 误 代 码 的 含 义, 可 以 参 考 http://dsa.cs.tsinghua.edu.cn/oj/static/unix_signal.html 常 见 的 是 8 除 0 错 和 11 内 存 访 问 错 误 f) 我 的 运 行 结 果 是 Exceed time limit, 时 间 2200ms, 是 不 是 只 要 再 做 一 些 常 数 级 优 化 就 不 会 超 时 了? 当 超 过 题 目 规 定 的 时 限,OJ 会 杀 死 进 程 显 示 用 时 2200ms, 说 明 程 序 运 行 时 间 超 过 时 限 ( 2s), 并 不 说 明 程 序 只 花 2200ms 就 能 运 行 完 因 此, 不 是 把 程 序 运 行 速 度 优 化 200ms 就 能 解 决 的 5

3. 作 业 说 明 a) 必 须 采 用 题 目 中 提 示 所 指 出 的 方 法 吗? 不 是 的, 题 目 中 的 提 示 只 是 一 种 可 行 思 路, 不 排 除 有 更 好 的 思 路, 可 以 任 意 选 择 方 法 但 是 如 果 题 目 正 文 和 题 目 的 限 制 中 对 方 法 有 限 制, 那 么 必 须 遵 守 b) 每 个 作 业 只 能 标 记 一 次 Final Version 吗? Deadline 前 可 以 多 次 mark final version, 评 测 时 以 最 后 一 次 mark 的 为 准 c) 程 序 调 试 了 很 久 没 有 调 通, 可 以 使 用 助 教 来 进 行 调 试 吗? 由 于 调 试 工 作 量 实 在 太 大, 所 以 助 教 不 会 来 帮 助 大 家 进 行 调 试 :) 比 较 建 议 大 家 在 同 学 中 寻 找 一 些 伙 伴 来 互 相 帮 助 调 试, 这 样 双 方 都 会 有 明 显 的 进 步, 助 教 自 己 的 程 序 就 是 这 样 调 试 的 d) 题 面 上 的 输 入 样 例 就 是 第 一 个 测 试 点 吗? 不 一 定, 输 入 样 例 与 测 试 点 没 有 直 接 联 系 e) 教 材 上 的 示 例 代 码 可 以 直 接 在 作 业 中 使 用 吗? 1. 支 持 借 鉴 学 习 教 材 中 的 代 码, 完 善 自 己 作 业 程 序 的 效 率 ; 2. 如 果 直 接 使 用 教 材 中 的 代 码, 需 要 进 行 声 明 ; 3. 原 则 上, 并 不 鼓 励 使 用 教 材 和 课 件 中 的 代 码, 鼓 励 同 学 们 自 己 实 现 完 善 相 应 的 数 据 结 构 ; 4. 教 材 中 的 代 码, 更 多 的 是 一 种 原 理 的 示 范, 并 不 保 证 正 确 性, 如 果 因 此 出 现 Bug, 请 同 学 们 自 负 后 果 f) 如 果 作 业 抄 袭 后 果 如 何? 这 会 给 被 抄 袭 同 学 带 来 极 大 的 困 扰, 因 为 会 导 致 记 -100 分, 太 惨 了 :) 提 前 说 明 的 是 本 课 程 对 作 业 雷 同 的 判 定 比 较 严 格, 所 以 请 大 家 独 立 完 成 作 业 需 要 强 调 的 是, 在 签 署 的 Honor Code 中, 你 已 承 诺 我 未 曾 也 不 会 向 同 一 课 程 ( 包 括 此 后 各 届 ) 的 同 学 复 制 或 公 开 我 这 份 程 序 的 代 码, 我 有 义 务 妥 善 保 管 好 它 们 g) SPOC/CST 课 堂 的 PA 是 如 何 计 分 的? 正 常 情 况 下, 取 本 次 PA 中 得 分 最 高 的 N 题 的 ( 加 权 ) 总 分 特 殊 地, 若 有 M 题 出 现 代 码 雷 同, 那 么 优 先 取 这 M 题, 然 后 在 剩 余 的 题 里 取 N-M 道 得 分 最 高 的 例 如 某 次 PA 共 6 道 题, 得 分 分 别 是 70 分 80 分 0 分 ( 因 代 码 雷 同 ) -100 分 ( 因 代 码 雷 同 ) 90 分 100 分 ;N=5, 那 么 优 先 级 从 高 到 低 分 别 是 0 分 -100 分 100 分 90 分 80 分 h) PA 会 出 现 负 分 吗? 不 会 如 果 代 码 雷 同 导 致 PA 的 ( 加 权 ) 总 分 小 于 0, 那 么 这 次 PA 记 0 分 6

附 :OJ 分 档 评 测 的 图 片 说 明 作 业 截 止 前, 有 两 个 测 试 按 钮 50% Judge 进 行 五 成 测, 不 限 制 次 数 右 边 的 小 按 钮 上 的 数 字 是 九 成 测 剩 余 机 会 数 初 始 状 态 下, 每 人 每 题 有 5 次 九 成 测 的 机 会 使 用 九 成 测 机 会 时, 提 交 页 面 会 显 示 一 行 警 告 你 还 可 以 为 每 次 提 交 做 批 注, 这 样, 批 注 会 显 示 在 测 试 结 果 的 右 边, 以 便 你 在 众 多 提 交 中 分 辨 你 的 每 次 提 交 显 示 的 分 数 是 通 过 的 测 试 点 占 所 有 测 试 点 的 比 例, 而 不 是 通 过 测 试 点 占 参 与 测 试 的 测 试 点 的 比 例 因 此, 五 成 测 最 高 50 分, 九 成 测 最 高 90 分 作 业 截 止 后, 可 以 进 行 全 集 测, 次 数 不 限 你 有 申 诉 期, 详 见 作 业 说 明 黑 盒 测 试 部 分 7

附 : 新 增 Java 支 持 OJ 现 已 支 持 提 交 Java 源 代 码, 需 要 提 交 一 个 压 缩 包 : 1. 主 类 名 是 Main 2. 使 用 标 准 输 入 标 准 输 出 3. 需 打 包 提 交, 即 使 只 是 单 文 件 OJ 的 打 包 规 则 : 所 有 文 件 置 于 顶 层 目 录 打 包, 即 点 开 压 缩 包 就 能 看 到 Main.java, 而 不 是 点 开 压 缩 包 后 再 点 开 一 层 目 录 才 能 看 到 Main.java 对 应 于 Tutorial 第 一 题 0. 加 法 (Add), 需 要 提 交 的 打 包 文 件 可 在 这 里 下 载 : http://www.xuetangx.com/assetv1:tsinghuax+30240184+2015_t2+type@asset+block/javaexample.zip 附 :OJ 使 用 技 巧 1. OJ 使 用 手 册 http://dsa.cs.tsinghua.edu.cn/oj/guide.shtml 视 频 教 程 https://d2f1egay8yehza.cloudfront.net/tsg-ds/tsgdatast114- V052400_DTH.mp4 2. 几 种 主 要 的 读 入 数 据 方 法, 大 多 数 情 况 下 性 能 是 fread > getchar > scanf > cin 的 顺 序 3. OJ 上 的 编 译 器 采 用 的 是 gcc(g++), 对 于 Linux 和 Mac 用 户 可 以 无 缝 衔 接, 而 如 果 使 用 Windows 的 同 学 希 望 能 够 在 本 地 编 译 与 OJ 编 译 之 间 较 快 衔 接 的 话, 可 以 考 虑 使 用 MinGW 4. Runtime Error 的 exit code 同 样 反 映 了 某 种 信 息, 可 以 查 阅 相 关 资 料 了 解 RE 各 个 exit code 的 意 义 参 考 http://dsa.cs.tsinghua.edu.cn/oj/static/unix_signal.html 5. 评 测 所 依 赖 的 输 出 流 是 stdout, 而 使 用 stderr 的 输 出 不 会 被 纳 入 最 终 评 测 但 如 果 你 使 用 stderr 进 行 调 试 却 没 有 在 提 交 中 移 除, 这 将 显 著 地 拖 累 你 程 序 的 性 能 6. 常 用 的 调 试 工 具 包 括 gdb MSVC debugger 室 友 小 黄 鸭 7. 如 果 不 确 定 某 一 特 性 是 否 为 OJ 所 支 持, 不 妨 动 手 试 一 试 8

附 : 输 入 输 出 技 巧 1. 判 断 输 入 结 束 有 些 编 程 作 业 题 并 未 指 明 测 试 数 据 的 组 数, 此 时 需 要 自 己 判 断 输 入 结 束 其 实, 根 据 题 意 正 确 处 理 输 入 数 据 也 是 同 学 们 在 这 门 课 中 需 要 练 习 的 编 程 能 力 之 一 处 理 输 入 的 方 法 很 简 单, 使 用 C++ 风 格 的 cin, 可 以 这 样 写 string a, b; char c; while (cin >> a >> b >> c) { /* blablabla */ } 如 果 使 用 C 风 格 的 scanf() 函 数, 则 可 根 据 其 返 回 值 做 出 判 断, 具 体 地 可 以 这 样 写 : while (scanf("%s\n%s\n%c\n\n", &a, &b, &c)!= EOF) { /* blablabla */ } 这 样 当 格 式 输 入 流 读 到 文 件 末 尾 时 会 返 回 EOF, 于 是 while 退 出 2. 过 滤 空 白 字 符 有 些 题 目 是 这 样 的 输 入 格 式 : E 6 M E 2 M 即 字 母 数 字 混 输 如 果 用 getchar 或 scanf 的 %c 参 数, 会 受 到 行 末 空 白 符 ( 比 如 空 格 换 行 等 ) 的 困 扰 cin 到 字 符 串 scanf 的 %s 参 数 都 会 自 动 过 滤 空 白 符 使 用 标 准 库 的 功 能 来 过 滤 空 白 符, 会 使 程 序 逻 辑 更 清 晰 示 例 代 码 : char buf[8]; int x; while (scanf("%s", buf)!= EOF) { } switch (buf[0]) { case 'E': } scanf("%d", &x); /* balabala */ 3. I/O 缓 存 加 速 使 用 cstdio 中 的 setvbuf 函 数, 设 置 一 个 较 大 的 I/O 缓 冲 区, 有 时 有 很 好 的 加 速 效 果 用 法 示 例 : setvbuf(stdin, new char[1 << 20], _IOFBF, 1 << 20); setvbuf(stdout, new char[1 << 20], _IOFBF, 1 << 20); 注 意 : 一 必 须 在 所 有 I/O 操 作 前 调 用 这 个 函 数, 不 能 在 已 读 入 一 些 数 据 后 再 设 置 缓 存 ; 二 如 果 设 置 了 I/O 缓 存, 控 制 台 输 入 输 出 可 能 失 效 4. 重 定 向 为 便 于 反 复 测 试 及 再 现 运 行 过 程, 可 采 用 输 出 输 入 重 定 向 的 方 法 9

你 只 需 事 先 将 输 入 数 据 存 成 文 件, 运 行 时 系 统 会 自 动 从 中 获 取 输 入 其 效 果 完 全 等 同 于 你 从 ( 作 为 默 认 输 入 流 的 ) 键 盘 逐 项 输 入 类 似 地, 你 也 可 以 指 定 另 一 文 件, 并 使 运 行 的 结 果 自 动 存 入 其 中 其 效 果 完 全 等 同 于 从 ( 作 为 默 认 输 出 流 的 ) 屏 幕 截 取 输 出 结 果 重 定 向 的 好 处 很 多 : 可 以 避 免 手 工 输 入 的 出 错, 忠 实 可 靠 地 重 复 测 试 ; 可 以 实 现 大 规 模 数 据 的 输 入 ; 可 以 完 整 精 确 地 记 录 程 序 的 输 出, 以 便 事 后 的 对 比 分 析 ; 可 以 省 去 默 认 输 入 输 出 流 占 用 的 大 量 时 间, 更 加 准 确 地 测 量 程 序 的 执 行 效 率 a) 方 法 一 : 修 改 源 文 件, 指 定 重 定 向 的 输 入 输 出 文 件 例 如, 若 希 望 从 文 件 input.txt 中 获 取 输 入, 将 输 出 保 存 到 文 件 output.txt 中, 则 可 在 主 程 序 开 头 增 加 如 下 语 句 : #ifndef _OJ_ #endif freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); 注 意 : 如 果 用 c++ 风 格 的 cin/cout 的 话, 还 要 在 前 面 引 用 头 文 件 的 部 分 加 入 #include <cstdio> OJ 在 编 译 程 序 的 时 候 会 提 供 一 个 _OJ_ 的 符 号, 所 以 上 面 这 段 语 句 会 在 OJ 运 行 的 时 候 被 跳 过 b) 方 法 二 : 在 IDE 中 通 过 设 置 命 令 行, 重 定 向 输 入 输 出 文 件 以 Visual Studio 为 例, 可 打 开 对 应 工 程 的 属 性 页, 在 配 置 属 性 下 的 调 试 页, 设 置 命 令 行 参 数 输 入 参 数 不 多 时, 可 直 接 键 入 例 如 ADD 一 题, 键 入 100 200 即 可 若 其 中 包 含 特 殊 字 符, 则 需 以 '^' 引 导, 或 者 使 用 一 对 半 角 括 号 消 除 歧 义 若 输 入 参 数 多, 且 不 止 一 行, 则 可 将 其 存 成 一 个 文 件 比 如, 可 在 命 令 行 参 数 中 键 入 : < D:\test\input.txt ( 注 意 起 始 字 符 "<" 不 能 省 略 ) 为 将 程 序 的 输 出 保 存 至 指 定 文 件, 可 在 命 令 行 参 数 中 继 续 键 入 : > D:\result\output.txt ( 同 样 地, 起 始 字 符 "<" 也 不 能 省 略 ) 若 不 希 望 覆 盖 文 件 原 有 的 内 容, 只 需 用 ">>" 替 换 以 上 的 ">", 即 可 将 每 次 运 行 的 输 出 追 加 至 D:\result\output.txt 输 入 输 出 的 重 定 向 可 同 时 采 用 并 生 效 比 如 可 在 命 令 行 参 数 中 键 入 : < D:\test\input.txt >> D:\result\output.txt 重 定 向 文 件 的 具 体 路 径 与 文 件 名 可 自 行 选 择, 但 若 包 含 空 格, 则 需 使 用 一 对 半 角 引 号 消 除 歧 义, 比 如 : < "D:\my test\input.txt" >> "D:\my result\output.txt" 5. 帮 助 资 料 关 于 输 入 输 出 的 进 一 步 问 题, 可 以 自 己 查 阅 相 关 手 册 或 资 料 也 可 参 考 标 准 手 册, 以 上 输 入 输 出 方 法 都 是 C/C++ 标 准 输 入 输 出, 在 manual 中 都 有 详 细 介 绍 10

cin:http://www.cplusplus.com/reference/iostream/cin/ scanf:http://linux.die.net/man/3/printf 对 比 :https://www.byvoid.com/blog/fast-readfile/ 附 : 一 些 常 见 编 程 错 误 1. swtich 里 忘 记 加 break, 导 致 多 个 case 后 的 语 句 都 被 执 行 2. int *v = new int[n] 误 写 成 int *v = new int(n) 前 者 申 请 了 n 个 int 的 空 间 ; 而 后 者 只 申 请 了 一 个 int 的 空 间, 并 初 始 化 为 n 3. 在 函 数 里 开 了 很 大 的 数 组, 导 致 运 行 时 栈 溢 出 错 误 示 例 : int main() { } int v[1000000]; return 0; 可 以 改 成 : int main() { } int *v = new int[1000000]; return 0; 4. 计 算 溢 出 示 例 : int a = 1000000, b = 1000000; long long int c = a * b; 程 序 会 先 在 int 范 围 内 计 算 a * b, 最 后 把 溢 出 后 的 结 果 赋 值 给 c 正 确 写 法 是 c = (long long)a * (long long)b 附 :Visual Studio msvc 与 GNU gcc 的 差 异 1. msvc 可 能 会 自 动 include 一 些 头 文 件,gcc 编 译 提 示 函 数 找 不 到 2. 使 用 scanf 等 函 数 会 警 告 not safe(warning 4996), 推 荐 使 用 scanf_s, 但 是 这 个 不 属 于 C/C++ 标 准,gcc 没 有 3. gcc 也 没 有 itoa( 数 字 转 换 为 字 符 串 的 函 数 ) 4. gcc 上, 模 板 类 继 承 模 板 类,two phase name lookup, 调 用 父 类 函 数 会 提 示 找 不 到, 需 要 用 this-> 调 用 5. gcc 禁 止 void main main 函 数 要 return 0,return 非 零 值 OJ 会 认 为 是 runtime error 的 exitcode 6. Windows 和 Linux 上 换 行 符 有 "\r\n" 跟 "\n" 的 差 别, 你 的 程 序 最 好 有 一 定 鲁 棒 性, 能 处 理 两 种 情 况 11