信息学奥赛试题精选33题(附带题解)

第第1 10题为基础题 第题为基础题 第11 20题为提高题 第题为提高题 第21 33为综合题为综合题 注 因为在本文档中需要用到一些特殊的数学符号 如 求和号 分数等 所以当您在注 因为在本文档中需要用到一些特殊的数学符号 如 求和号 分数等 所以当您在 百度文库中浏览时 一些数学符号可能会显示不出来 不过当您把本文档下载下来在本地百度文库中浏览时 一些数学符号可能会显示不出来 不过当您把本文档下载下来在本地 浏览时 所有的符号即可全部都显示出来 浏览时 所有的符号即可全部都显示出来 基础题 基础题 1 Prime Frequency 问题描述问题描述 给出一个仅包含字母和数字 0 9 A Z 以及 a z 的字符串 请您计算频率 字符出现 的次数 并仅报告哪些字符的频率是素数 输入 输入 输入的第一行给出一个整数 T 0 T 201 表示测试用例个数 后面的 T 行每行给出 一个测试用例 一个字母 数字组成的字符串 字符串的长度是小于 2001 的一个正整数 输出 输出 对输入的每个测试用例输出一行 给出一个输出序列号 然后给出在输入的字符串中频 率是素数的字符 这些字符按字母升序排列 所谓 字母升序 意谓按 ASCII 值升序排列 如果没有字符的频率是素数 输出 empty 没有引号 样例输入样例输入样例输出样例输出 3 ABCC AABBBBDDDDD ABCDFFFF Case 1 C Case 2 AD Case 3 empty 注 注 试题来源 试题来源 Bangladesh National Computer Programming Contest 在线测试 在线测试 UVA 10789 提示提示 先离线计算出 2 2200 的素数筛 u 然后每输入一个测试串 以 ASCLL 码为下标统 计各字符的频率 p 并按照 ASCLL 码递增的顺序 0 i 299 输出频率为素数的字符 即 u p i 1 且 ASCLL 码值为 i 的字符 若没有频率为素数的字符 则输出失败信息 2 Twin Primes 问题描述问题描述 双素数 Twin Primes 是形式为 p p 2 术语 双素数 由 Paul St ckel 1892 1919 给 出 前几个双素数是 3 5 5 7 11 13 17 19 29 31 41 43 在本题中请你给 出第 S 对双素数 其中 S 是输入中给出的整数 输入 输入 输入小于 10001 行 每行给出一个整数 S 1 S 表示双素数对的序列编号 输入 以 EOF 结束 输出 输出 对于输入的每一行 输出一行 给出第 S 对双素数 输出对的形式为 p1 空格 p2 其 中 空格 是空格字符 ASCII 32 本题设定第对的素数小于 样例输入样例输入样例输出样例输出 1 2 3 4 3 5 5 7 11 13 17 19 注 注 试题来源 试题来源 Regionals Warmup Contest 2002 Venue Southeast University Dhaka B angladesh 在线测试 在线测试 UVA 10394 提示提示 设双素数对序列为 ans 其中 ans i 存储第 i 对双素数的较小素数 1 i num ans 的 计算方法如下 使用筛选法计算出 2 的素数筛 u 按递增顺序枚举该区间的每个整数 i 若 i 和 i 2 为双素数对 u i 最后得出的 f k n 即为问题解 6 Common Permutation 问题描述问题描述 给出两个小写字母的字符串 a 和 b 输出最长的小写字母字符串 x 使得存在 x 的一个 排列 是 a 的子序列 同时也存在 x 的一个排列是 b 的子序列 输入 输入 输入有若干行 连续的两行组成一个测试用例 也就是说 第 1 和第 2 行构成一个测 试用例 第 3 和第 4 行构成一个测试用例 等等 每个测试用例的第一行是字符串 a 第 二行是字符串 b 每个字符串一行 至多由 1000 个小写字母组成 输出 输出 对每个测试用例 输出一行 给出 x 如果有若干个 x 满足上述要求 选择按字母序 列第一个 样例输入样例输入样例输出样例输出 pretty women walking down the street e nw et 注 注 试题来源 试题来源 World Finals Warm up Contest University of Alberta Local Contest 在线测试 在线测试 UVA 10252 提示提示 试题要求按递增顺序输出两串公共字符的排列 计算方法如下 设 S1 a1a2 S2 b1b2 a l a b l b 先分别统计 S1中各字母的频率 c1 i 和 S2中各字母的频率 c2 i 1 i 26 其中字母 a 对应数字 1 字母 b 对应数字 2 字母 z 对应数字 26 然后计算 S1和 S2的公共字符的排列 递增枚举 i 1 i 26 若 i 对应的字母在 S1和 S2中同时存在 c1 i 0 字母 z 对应 50 字母 Z 对应 51 为了按照字母升序的要求生成单词的所有排列 首先将单词的所有字母转化为数字 然后递增排序数串 排列中每个位置的数字按由左而右顺序从数串中选择 设单词长度为 l 数串的第 i 个位置已访问标志为 v1 i 初始时 v1 清零 数字 k 对应 的字母已使用标志为 v2 k v2 为递归程序内的局部变量 0 i l 1 0 k 51 生成所有排列的计算过程为一个递归子程序 void dfs int d 从当前位置 d 出发 递归计算单词的所有排列 if d l 输出当前数字排列对应的单词 生成单词的一个排列 else v2 清零 所有字母未确定 for int i 0 i l i 按由左而右顺序从数串中选择 d 位置的 字母 若数串的第 i 个位置未访问且对应字母未在排列中出现 则设访问标志 该字符进 入排列中的第 d 个位置 if v1 i v2 i 位置字母对应的数字 1 i 位置字母对应的数字放入当前排列的 d 位置 dfs d 1 递归排列的第 d 1 个位置 v1 i 0 恢复数串的第 i 个位置未访问标志 显然 主程序设数串的所有位置未访问 v1 清零 递归调用 dfs 0 便可按字母升 序要求输出单词的所有排列 8 How Many Points of Intersection 问题描述问题描述 给出两行 在第一行有 a 个点 在第二行有 b 个点 我们用直线将第一行的每个点与 第二行的每个点相连接 这些点以这样的方式排列 使得这些线段之间相交的数量最大 为此 不允许两条以上的线段在一个点上相交 在第一行和第二行中的相交点不被计入 在两行之间允许两条以上的线段相交 给出 a 和 b 的值 请计算 P a b 在两行之间相交 的数量 例如 在下图中 a 2 b 3 该图表示 P 2 3 3 输入 输入 输入的每行给出两个整数 a 0 a 20000 和 b 0avg 则栈中有 hi avg 块砖头被移动 贪心使用这个度量标准是正确的 因为砖头被移动至高度低于 avg 的栈中 由于砖块总 数除以栈的数目是可除尽的 因此这些栈中的砖头是不须再移动的 由此得出最少移动的 砖数 ans 1 avghavgh i n i i 13 Minimal coverage 问题描述问题描述 给出直线的若干条线段 直线是 X 轴 线段的坐标为 Li Ri 求最少要用多少条线段 可以覆盖区间 0 m 输入 输入 输入的第一行给出测试用例的数目 后面给出一个空行 每个测试用例首先给出一个整数 M 1 M 5000 接下来若干行 每行以 Li Ri Li Ri 50000 i 表示线段 每个测试用例以 0 0 为结束 两个测试用例之间用一个空行分开 输出 输出 对每个测试用例 输出的第一行是一个数字 表示覆盖区间 0 m 的最少线段数 接下 来若干行表示选择的线段 给出线段的坐标 按左端 Li 排序 程序不处理 0 0 若无解 即 0 m 不可能被给出的线段覆盖 则输出 0 没有引号 在两个连续的测试用例之间输出一个空行 样例输入样例输入样例输出样例输出 2 1 1 0 5 3 2 5 0 0 1 1 0 0 1 0 0 0 1 0 1 注 注 试题来源 试题来源 USU Internal Contest March 2004 在线测试 在线测试 UVA 10020 Ural 1303 提示提示 把所有线段按左端点为第一关键字 右端点为第 2 关键字递增排序 Li Li 1 Li Li 1 i tot i for int j i 1 j tot j len min T i 的串长 T j 的串长 for int k 0 kmove x y d 1 则 最佳路径为 xs ys x y x y move x y d move x y d 1 ans x y d ans x y d d 方向对应字符 在箱子沿 d 方向推入 x y 的被推次数 沿 d 方向推入 x y 的被推次数 1 push x y d push x y d 1 的情况下 则最佳路径为先沿 d 方向将箱子推入 x y 再沿 d 方向推一次箱子 push x y d push x y d 1 move x y d move x y d 1 ans x y d ans x y d d 方向对应字符 另换一个方向推 若沿 d 方向推动箱子 则人必须在箱子位置 x y 的 d 方向的相邻格 x y 若 改为 i 方向推箱子 0 i 3 i d 则必须步行到 x y 的 i 方向的相邻格 x y 计算方法如下 设 x y 有障碍 P x y false 从 x y 出发进行 BFS 计算所有可达的格子 并将到达这些格子的行走方向序列记入 way BFS x y 恢复 x y 的无障碍状态 P x y true 搜索除 d 外的每个方向 i 0 i 3 i d 计算 x y 的 i 方向上的相邻格 x y 若 x y 为界内的一个无障碍格 且由 x y 可达 则分析 若箱子未沿 i 方向推入 x y push x y i 则 x y 和方向 i 进入队列 在箱子沿 i 方向推入 x y 的被推次数 沿 d 方向推入 x y 的被推次数的情 况下 push x y i push x y d 若人从 xs ys 出发 进入 x y 的总步 数大于进入 x y 的总步数 x y 走至 x y 的总步数 move x y i m ove x y d way x y 的长度 则最佳路径为 xs ys x y x y move x y i move x y d way x y 的长度 ans x y i ans x y d way x y 在箱子沿 i 方向推入 x y 的被推次数 沿 d 方向推入 x y 的被推次数的情 况 下 push x y i push x y d 则最佳路径为 xs ys x y x y move x y i move x y d way x y 的长度 ans x y i ans x y d way x y 箱子推至 x y 的被推次数推至 x y 的被推次数 push x y i pus h x y d 输出结果 通过上述 BFS 求出了箱子由 4 个方向推入 xt yt 的最少被推次数 push xt yt i 人从 xs ys 出发沿 4 个方向进入 xt yt 的最少步数 move xt yt i 0 i 3 最佳方 案中最后的推动方向 d 必须满足如下条件 箱子沿 d 方向推入 xt yt push xt yt d 并且满足下述两个条件之一 箱子被推次数是最少的 push xt yt d min 30 iytxtpush i 若被推次数最少的方案有多个 则 move xt yt d 是最小的 计算方法如下 d 1 最佳方向初始化 for int i 0 i push XT YT i push XT YT d push XT YT i if d 1 箱子未能推入 xt yt print Impossible n n else print ans xt yt d n n 输出输出推的数目最小化的序列 22 Basic Wall Maze 在这个你要解决问题中 有一个非常简单的迷宫 组成如下 一个 6 6 的方格组成的正方形 长度在 1 到 6 的 3 面墙 沿着方格 水平或者垂直放置 以分隔方格 一个开始标志和一个结束标志 迷宫形为图 图 你要寻找从开始位置到结束位置的最短路 仅允许在邻接的方格间移动 所谓邻接就 是指两个方格有一条公共边 并且它们没有被墙隔开 不允许离开正方形 输入 输入 输入由若干测试用例组成 每个测试用例由 5 行组成 第一行给出开始位置的列和行 的值 第二行给出结束位置的列和行的值 第 3 4 5 行给出 3 面墙的位置 墙的位置或 者是先给出左边的位置点 再给出右边的位置点 如果是水平的墙 或者是先给出上方位 置点 然后再给出下方位置点 如果是垂直墙 墙端点的位置是以点与正方形左边的距离 后面跟点与正方形上方位置的距离给出 输出 输出 3 面墙可以在方格的某一点上相交 但彼此不交叉 墙的端点在方格上 而且 从开始 标志到结束标志一定会有合法的路 样例输入说明上图给出的迷宫 最后一个测试数据后跟着一行 包含了两个零 样例输入样例输入样例输出样例输出 1 6 2 6 0 0 1 0 1 5 1 6 1 5 3 5 NEEESWW 0 0 注 注 试题来源 试题来源 Ulm 2006 在线测试 在线测试 POJ 2935 提示 由于墙是沿方格线的一条线段 因此不仅要将方格作为节点 而且也要将方格线也作 为节点 使得迷宫扩展为 12 12 的矩阵 显然 方格线的坐标值为偶数 通道的坐标值为奇 数 如图 11 5 5 图 墙所在的节点设访问标志 visit 避免出现 翻墙而过 的情况 显然对四周的边墙 visit 0 0 visit 1 0 visit 12 0 true visit 0 0 visit 0 1 visit 0 12 true visit 0 12 visit 1 12 visit 12 12 true visit 12 0 visit 12 1 visit 12 12 true 对由方格 x1 y1 至方格 x2 y2 的垂直墙 x1 x2 visit 2 y1 2 x1 visit 2 y1 1 2 x1 visit 2 y2 2 x1 true 对由方格 x1 y1 至方格 x2 y2 的水平墙 y1 y2 visit 2 y1 2 x1 visit 2 y1 2 x1 1 visit 2 y1 2 x2 true 入口方格 sx sy 对应节点的坐标为 sx 2 1 sy sy 2 1 出口方格 ex ey 对应节点的坐标 为 ex 2 1 ey 2 1 有了上述图 我们便可以使用宽度优先搜索计算起点至各节点的最短路的方向序列 其中队列 Q 存储已访问节点的坐标位置 除墙外 prev 存储队列中每个节点访问时的 移动方向 既然有了起点至目标节点的最短路的方向序列 我们就可以从目标节点出发 沿 prev 指针的指示追溯目标节点至起始节点的路径 取出当前节点的方向数 d prev x y 若 x 和 y 为奇数 则 d 对应的方向字符填入路径串 path 首部 x d 方向的水平增量 y d 方向的垂直增量 依次类推 直至 x y 为起点坐标为止 最后输出路径串 path 23 Firetruck 中央城消防部门与交通部门协作 一起维护反映城市街道当前状况的地图 在某一天 一些街道由于修补或施工而被封闭 消防队员需要能够选择从消防站到火警地点的不经过 被封闭街道的路线 中央城被划分为互不重叠的消防区域 每个区域设有一个消防站 当火警发生时 中 央调度向火警地点所在的消防站发出警报 并向该消防站提供一个从消防站到火警地点的 可能路线的列表 请您编写一个程序 中央调度可以使用这个程序产生从区域的消防站到 火警地点的路线 输入 输入 城市的每个消防区域有一个独立的地图 每张地图的街区用小于 21 的正整数标识 消 防站总是在编号为 1 的街区 输入给出若干测试用例 每个测试用例表示在不同的区域发 生的不同的火警 测试用例的第一行给出一个整数 表示离火警最近的街区的编号 后面的若干行每行由空格分开的正整数对组成 表示未封闭街道连接的相邻的街区 例如 如果在一行给出一对数 4 7 那么在街区 4 和 7 之间的街道未被封闭 且在街区 4 和 7 的路段上没有其他街区 每个测试用例的最后一行由一对 0 组成 输出 输出 对于每个测试用例 在输出中用数字来标识 CASE 1 CASE 2 等等 在一行中 输出一条路线 按路线中出现的顺序 依次输出街区 输出还要给出从消防站到火警地点 的所有路线的总数 其中只包括那些不经过重复街区的路线 由于显而易见的理由 消防 部门不希望他们的车子兜圈子 不同的测试用例在不同的行上输出 在样例输入和样例输出中 给出了两个测试用例 样例输入样例输入样例输出样例输出 6 1 2 1 3 3 4 3 5 4 6 5 6 2 3 2 4 0 0 4 2 3 3 4 5 1 CASE 1 1 2 3 4 6 1 2 3 5 6 1 2 4 3 5 6 1 2 4 6 1 3 2 4 6 1 3 4 6 1 3 5 6 There are 7 routes from the firestation to streetcorner 6 CASE 2 1 3 2 5 7 8 9 6 4 1 3 4 1 5 2 3 4 1 5 7 8 9 6 4 1 6 7 8 8 9 2 5 5 7 3 1 1 8 4 6 6 9 0 0 1 6 4 1 6 9 8 7 5 2 3 4 1 8 7 5 2 3 4 1 8 9 6 4 There are 8 routes from the firestation to streetcorner 4 注 注 试题来源试题来源 1991 ACM World Finals 在线测试 在线测试 UVA 208 UVA 5147 提示 我们将街区作为节点 未封闭街道连接的相邻街区间连边 构造一个无向图 路线的 起点为节点 1 即消防站所在的街区 1 终点为离火警最近的街区编号 en 试题要求计算 这样的路线有多少条以及所有的路线方案 显然可以用回溯法计算所有可能的路线 但需要注意的是 在扩展路线时 新节点 y 不仅要满足与路线尾节点 x 相邻和未访问的约束条件 还要满足 y 是否与终点 en 连通的约 束条件 否则消防车无法途径 y 到达火警地点 为了提高搜索效率 我们可以预先通过计 算传递闭包的 Warshall 算法 计算出节点 2 节点 n 中每个节点与节点 en 的连通性 设传 递闭包为 p 其中 p i j 为节点 i 与节点 j 间连通的标志 P 初始化为相邻矩阵 for int i 1 i n i p i i 1 设定对角线元素 for int k 2 k n k 枚举路径的中间节点 k for int i 2 i n i 枚举路径的起点 i if p i k for int j 2 j n j p i j p k j 枚举路径的终点 j 确定 i 可否途 径 k 到达 j for int i 2 i n i if p i en cut i 1 记录节点 i 与终点 en 不连通 这样 我们就可以将 cut y 作为关键的剪枝条件了 即新节点 y 必须同时满足条件 相邻于路线尾节点 x if x y z 为终点 ex ey ez return if d ex ey ez return 重要剪枝 若当前点与终点的ezzeyyexx 曼哈顿距离过长则跳出 分析 x y z 的六个方向上的相邻格 分情形递归 若当前方向的相邻格 x y z 满足如下条件 x y z 在界内 int dy 2 2 1 1 1 1 2 2 26 Children of the Candy Corn 玉米田迷宫是一种流行的万圣节快乐活动 访问者在进入入口之后 要通过面对僵尸 挥舞着电锯精神病患者 嬉皮士 以及其他恐怖手段的迷宫 最后找到出口 有一种保证游客最终找到出口的流行的迷宫行走策略 只要选择是沿着左面的墙或者 右面的墙 并一直走下去 当然 不能保证向左或者向右哪一个策略会更好 而且所走的 路径很少是最有效的 如果出口不是在边缘上 这一策略就不起作用 但这一类的迷宫不 是本题所论述的 作为一个玉米田迷宫的所有者 你想有一个计算机程序确定除了最短路径外的向左和 向右路径 使得你可以计算出哪一种布局有最好的惊吓访问者的机会 输入 输入 问题输入的第一行给出整数 n 表示迷宫的数量 每个迷宫的第一行给出宽度 w 和高 度 h 3 w h 40 后面的 h 行 每行有 w 个字符 每个表示迷宫的布局 墙用哈希标记 表示 空区域用 表示 开始用 S 表示 出口用 E 表示 在每个迷宫中仅有一个 S 和一个 E 它们位于迷宫的边墙 不在墙角 迷宫的四 面是墙 还有 S 和 E S 和 E 之间至少有一个 将他们分开 从起点到终点是可达的 输出 输出 对于输入的每个迷宫 输出一行 按序给出沿靠左行走 靠右行走 最短路径行走一 个人经过的方块 不一定是唯一的 的数量 包括 S 和 E 用空格分开 从一个方 块到另一个方块的移动仅允许水平和垂直方向 不允许对角线方向移动 样例输入样例输入样例输出样例输出 2 8 8 37 5 5 17 17 9 S E 9 5 S E 注 注 试题来源 试题来源 ACM South Central USA 2006 在线测试 在线测试 POJ 3083 ZOJ 2787 UVA 3631 提示 试题的难度是怎样计算游客沿左面墙或者右面墙一直走下去的路线 设方向 1 方向 4 如图 图 方向 t 逆时针转 90 后的方向为 t1 t 3 4 顺时针转 90 后的方向为 t2 t 1 4 我们设计一个递归函数 dfs left x y t 从游客沿 t 方向走入 x y 的状态出发 计算 沿左面墙走至出口的步数 step dfs left x y t 若 x y 为边墙 x y 在界外 或内墙 x y 为 则返回 2 步数 step 1 若 x y 为出口 则返回 1 成功标志 flag 初始化为 0 计算 t 逆时针转 90 后的方向 tt t 3 4 for int i 0 i 10 k ans 则退出程序 枚举 x y 的 4 个方向上的相邻格 x y 若 x y 为非同行或非同列上的阻塞 则去除 从 x y 递归下去 dfs x y k 1 恢复递归前相邻格的阻塞状态 否则若 x y 为目标位置 则更新答案 ans min ans k 1 并退出程序 我们从开始位置 xs ys 出发 递归调用 dfs xs ys 0 若得出的 ans 仍为初始值 11 则说明无解 否则 ans 即为最少移动次数 28 Shredding Company 您为碎纸机公司负责开发一种新的碎纸机 一台 一般 的碎纸机仅仅将纸张切成小 碎片 使得其内容不可读 而这种新的碎纸机需要有以下不同寻常的基本特性 1 你的碎纸机要以一个目标数作为输入 并在要粉碎的那一张纸上写有一个数字 2 你的碎纸机将纸张粉碎 或切割 成碎片 每张碎片上都有这个数字的一位或若 干位 3 每张碎片上数字的总和要尽可能地接近目标数 但不能超过目标数 例如 假设目标数为 50 而纸张上数字为 12346 碎纸机将纸张切碎成四张 第一张 碎片上是 1 第二张上是 2 第三张上是 34 第四张是 6 它们的总和是 43 1 2 34 6 是所有可能的组合中最接近目标数 50 但不超过 50 如图 例如 组合 1 23 4 和 6 则不成立 因为这个组合的总和是 34 1 23 4 6 小于上一个组合的总和 43 组合 12 34 和 6 也不成立 因为 52 12 34 6 大于目标数 50 图 此外 还有 3 条特定的规则 1 如果目标数和纸张上的数字相同 则这张纸就不要粉碎 例如 如果目标数是 100 而 纸张上的数字也是 100 则纸张不会被粉碎 2 如果任何组合的总和不可能小于或等于目标数 则输出 error 例如 如果目标数是 1 而在纸张上的数字是 123 那么不可能存在可以成立的组合 因为具有最小和的组 合是 1 2 和 3 它们的和是 6 大于目标数 所以要输出 error 3 如果有多于一个总和最接近但没有超过目标数的组合 输出 rejected 例如 如果目 标数是 15 在纸张上的数字是 111 则有两个最高是 12 的组合 a 1 和 11 b 11 和 1 所以输出 rejected 为了开发这样的碎纸机 请您编写一个小程序来模拟上述的 特性和规则 给出两个数 第一个数是目标数 第二个数是写在要被粉碎的纸张上的 数 程序要计算出碎纸机如何 切割 第二个数 输入输入 输入由若干测试用例组成 每个测试用例一行 形式如下 t1 num1 t2 num2 tn numn 0 0 每个测试用例由两个正整数组成 用一个空格分开 1 第一个整数 上面标识为 ti 是目标数 2 第二个整数 上面标识为 numi 是要粉碎的纸张上的数字 两个数不能将 0 作为第一位 例如 123 可以 但 0123 则不可以 可以设定两个整数长 度最多 6 位 以一行中给出两个 0 作为输入结束 输出输出 对于输入中的每个测试用例 相应输出为下述 3 种类型之一 sum part1 part2 rejected error 在第一种类型中 partj和 sum 的含义如下 1 每个 partj是一个在一张碎纸片上的一个数 partj的次序相应于在纸张上原来的数字的 次序 2 sum 是纸张被粉碎后数字和 即 sum part1 part2 每个数字用一个空格分开 如果不可能产生组合 输出 error 如果存在一个以上的组合 输出 rejected 在每行的开始和结束 没有其他的字符 包括空格 样例输入样例输入样例输出样例输出 50 12346 376 18 3312 9 3142 25 1299 111 33333 103 6 1104 0 0 43 1 2 34 6 283 144 139 18 3 3 12 error 21 1 2 9 9 rejected 103 86 2 15 0 rejected 注 注 试题来源试题来源 ACM Japan 2002 Kanazawa 在线测试 在线测试 POJ 1416 ZOJ 1694 UVA 2570 提示 设目标数为 limit 纸张上的数字为 n 目前所有碎纸片上的最佳数字和为 Max 试题要 求将 n 按位的顺序拆分成若干个数 使其数和 Max 为不超过 limit 的最大数 并判断出数 和为 Max 的拆分方案数 r 是 1 还是大于 1 或者是根本无法拆分 r 0 那么 怎样求最佳数字和 Max 呢 我们从 n 的最低位开始由右而左拆分 若当前拆分出 i 位数 则 n 10i为当前碎纸片上 的数字 剩余数字待拆分 拆分有两种情况 i n 10 不断开情况 当前碎纸片上的数字需继续向左扩展 断开情况 拆分出当前碎纸片上的数字 显然 我们可以采用回溯法分头递归这两种情况 设递归函数 dfs n sum now k p 其中 n 为待拆分的数字 sum 为已经拆分出的数和 当前待拆分出的一个数字为 now 准 备填入第 k 张碎纸片 p 为下一个十进制位的权 dfs n sum now k p if n 0 若拆分完毕 则最后拆分出的数字 now 填入第 k 张纸条 更新答案并回 溯 t k now if sum now limit return 若拆分出的数和大于目标数 则退出 if sum now Max r 若拆分出的数和相同于 Max 则数和为 Max 的组合个数 1 else if sum now Max 若拆分出的数和更佳 则调整为 max Max sum now r 1 数和为 Max 的组合数为 1 ansk k 已填数的碎纸片数和各张碎纸片数的填数记入最佳方案 for int i 1 i1 则说明拆分出数和为 Max 不止 1 个 若 r 1 则 max 为最 佳数字和 拆分出的数字为 ans ansk ans 1 29 Be Wary of Roses 您为您获奖的玫瑰园非常骄傲 然而 一些嫉妒的同行园丁要不择手段地对付您 他 们绑架了您 将您蒙上眼睛 并给您戴上手铐 然后将您丢在您所珍爱的玫瑰花丛中 您 要逃出去 但您不能确保您可以不践踏珍贵的花朵 幸运的是 您将您花园的布局记在脑中 这是一个 N N 的平方图 N 为奇数 在其 中的一些方格中种有玫瑰 您正好是站在平方图正中心的大理石基座上 不幸的是 你已 经完全迷失了方向 而且不知道您所面对的方向 大理石的基座可以让您调整您的方向 使得您朝向北 东 南 或西 但你没有办法知道您当前朝哪个方向 无论您最初面朝哪个方向 您必须想出一个践踏尽可能少的玫瑰的逃离路径 您的路 径必须从中心开始 只能水平和垂直移动 以离开方格作为结束 输入 输入 每个测试用例首先在一行中给出平方图的大小 N 1 N 21 然后 N 行 每行 N 个 字符 用于描述花园 表示方格中没有玫瑰 R 表示方格中有玫瑰 而 P 代表在中心的 大理石基座 输入以 N 0 为结束标志 程序不必进行处理 输出 输出 对于每个测试用例 输出一行 给出在您逃离的时候要踩在玫瑰上的最少的次数 样例输入样例输入样例输出样例输出 5 RRR R R R R P R R R R RRR 0 At most 2 rose s trampled 注 注 试题来源试题来源 在线测试 在线测试 UVA 10798 提示 由于大理石的基座调整有四个方向 因此设 a k i j 为地图旋转 270180900 k 1 时 i j 的状态 若 i j 方格中有玫瑰 则 a k i j 1 否则 a k i j 90 0 假设被踩玫瑰数的上限为 limit 怎样判断你能否在踩到的玫瑰数不超过 limit 的情况下 成功逃离玫瑰园呢 设 f x y r1 r2 r3 r4 为行至 x y 时 4 个方向上踩到的玫瑰数分别为 r1 r2 r3 r4 的访问标志 v x y 为已经过 x y 的标志 flag 为成功逃离的标志 我们通过递归过程 dfs x y r1 r2 r3 r4 计算 flag 其中 x y 为目前行至的方格位置 4 个方向上踩到的玫瑰数分别为 r1 r2 r3 r4 显然经过 x y 后 4 个方向上踩到的玫 瑰数增加至 r1 a 1 x y r2 a 2 x y r3 a 3 x y r4 a 4 x y dfs x y r1 r2 r3 r4 的 计算过程如下 dfs x y r1 r2 r3 r4 if flag return 成功退出 if v x y return 若先前经过 x y 则回溯 if max r1 r2 r3 r4 limit return 若任一方向上踩到的玫瑰数超过上限 则回溯 if out x y 若逃离玫瑰园 则成功退出 flag 1 return if f x y r1 r2 r3 r4 return 若行至 x y 4 个方向上踩到的玫瑰数为 r1 r2 r3 r4 的状态已访问 则回溯 f x y r1 r2 r3 r4 1 设行至 x y 4 个方向上踩到的玫瑰数为 r1 r2 r3 r4 的状态已访问 v x y 1 设 x y 已经过标志 dfs x 1 y r1 a 1 x y r2 a 2 x y r3 a 3 x y r4 a 4 x y 递归 x y 的四个 相邻方向 dfs x 1 y r1 a 1 x y r2 a 2 x y r3 a 3 x y r4 a 4 x y dfs x y 1 r1 a 1 x y r2 a 2 x y r3 a 3 x y r4 a 4 x y dfs x y 1 r1 a 1 x y r2 a 2 x y r3 a 3 x y r4 a 4 x y v x y 0 撤去 x y 的经过标志 在 dfs x y r1 r2 r3 r4 的基础上 便可以计算逃离时踩到的最少玫瑰数 计算出发位置 ox oy ox n 2 1 oy n 2 1 成功标 flag 志初始化为 0 被踩玫瑰数的上限 limit 初始化为 1 while flag 若未成功逃离 则被踩玫瑰数的上限 1 limit f 和 v 清零 memset f 0 sizeof f memset v 0 sizeof v dfs ox oy 0 0 0 0 从图正中心出发 递归计算在被踩玫瑰数不超过上限 的情况下逃离玫瑰园的可能性 输出逃离时踩到的最少玫瑰数 limit 30 Monitoring the Amazon 一个由独立的 用电池供电的 用于数据采集的站所组成的网络已经建成 用于监测 Amazon 地区的气候 发布指令的站将启动指令传输到测控站 使得它们改变其当前的参 数 为了避免电池过载 每个站 包括发布指令的站 只能传送指令给另外两个站 通常 是选择与这个站最近的两个站 如果有多个站符合条件 则首先选择地图上的最西边 左 边 的站 其次选择的最南端 在地图的最下方 的站 你受 Amazon 州政府委托 编写一个程序 给出每个站的位置 确定是否信息可以传 达到所有的站 输入 输入 输入给出一个整数 N 后面给出 N 对整数 Xi Yi 表示每个站的定位坐标 第一对坐标 给出发布指令的站的位置 而剩下的 N 1 对是其他站的坐标 给出下述限制 20 Xi Yi 20 以及 1 N 1000 输入以 N 0 结束 输出 输出 对每个给出的表达式 输出一行 指出是否所有的站都可以到达 见样例输出的格式 样例输入样例输入样例输出样例输出 4 1 0 0 1 1 0 0 1 8 1 0 1 1 0 1 1 1 1 0 1 1 0 1 1 1 6 0 3 0 4 1 3 1 3 1 4 2 5 0 All stations are reachable All stations are reachable There are stations that are unreachable 注 注 试题来源 试题来源 2004 Federal University of Rio Grande do Norte Classifying Contest Round 1 在线测试 在线测试 UVA 10687 提示 设测控站为节点 根据题意 选择与这个站最近的两个站 如果有多个站符合条件 则首先选择地图上的最西边 左边 的站 其次选择的最南端 在地图的最下方 的站 每个节点 k 0 k n 1 的出度为 2 若仅有一个测控站 则出度为 1 按照下述方法计 算节点 k 的出边 按照与节点 k 的欧式距离为第 1 关键字 x 坐标为第 2 关键字 y 坐标为第 3 关键字 的递增顺序排列坐标序列 w 节点 k 分别向节点 w 1 和节点 w 2 连边 若仅有一个测控站 则连边 k w 1 构造出有向图后 使用回溯法计算节点 1 发布指令的站 可达的节点集合 若该集合 囊括了除节点 1 外的所有节点 则表明信息可以传达到所有的站 否则表明存在未能接受 信息的站 31 Graph Connectivity 考虑一个无向图 G 初始时图中无边 请写一程序判断两个不同节点间是否 连通 程序还要有插入和删除边的功能 输入输入 输入的第一行给出整数 N 2 N 1000 表示图 G 中的节点数 第二行给出指令数 Q 1 Q 20000 后面的 Q 行每行给出一条指令 有三类指令 I u v 插入边 u v 并保证在执行这一指令时 在节点 u 和 v 之间没有边 D u v 删除已有的边 u v 并保证在执行这一指令时 在节点 u 和 v 之间存在边 Q u v 查询指令 在节点 u 和 v 之间是否连通 节点的编号从 1 到 N 输出输出 对每条查询指令输出一行 如果两个节点是连通的 输出 Y 否则输出 N 样例输入样例输入样例输出样例输出 3 7 Q 1 2 I 1 2 I 2 3 Q 1 3 D 1 2 Q 1 3 Q 1 1 N Y N Y 注 注 试题来源 试题来源 POJ Monthly 2006 06 25 Zheng Zhao 在线测试 在线测试 POJ 2838 提示 由于无向图是动态生成的 因此该图的存储结构采用邻接表为宜 我们按照下述方法 依次处理每条命令 若为插边指令 I x y y 插入 x 的邻接表 x 的邻接表长 1 x 插入 y 的邻接表 y 的邻 接表长 1 若为删边指令 D x y 在 x 的邻接表中搜索 y 用表尾节点覆盖该位置 x 的邻接表长 度 1 在 y 的邻接表中搜索 x 用表尾节点覆盖该位置 y 的邻接表长度 1 若为查询指令 Q x y 若 x y 则 x 和 y 之间连通 否则从 x 出发 通过 BFS 搜索计 算 x 的所有可达节点 若 y 为可达节点 则节点 x 和 y 之间连通 否则不连通 32 The Net 现在考虑 Internet 上一个感兴趣的问题 快速的信息传送已经成为必须 信息传送工作 由位于网络节点上的路由器实现 每个路由器有它自己的一个路由器列表 给出它可以直 接到达的路由器 也被称为 传输表 很明显 信息传送要求经过的路由器最少 也被 称为 跳数 对于给出的网络 要求程序发现从信息源头到目标节点的最佳路线 最少跳数 输入输入 第一行给出网络中路由器的个数 n 后面的 n 行给出网络的描述 每行给出路由器 ID 然后是一个连字符以及用逗号分开的 可以直接到达的路由器的 ID 列表 这一列表 按升序排列 下一行给出信息传送要走的路线数目 m 后面连续的 m 行给出用一个空格 分开的路线的起始路由器和终点路由器 输入数据包含了多个网络的描述 输出输出 对输入中给出的每个网络 先输出一行 5 个连字符 然后对每条路线 输出信息从起 始路由器传送到目的路由器要经过的路由器列表 如果不可能进行信息传送 起始路由器 和目的路由器不连通 输出字符串 connection impossible 如果存在多条有相同 跳数 的路线 输出低 ID 的路线 由路由器 1 到 2 的路线是 1 3 2 和 1 4 2 则输出 1 3 2 数据范围设定为 网络中路由器的数目不超过 300 并且至少有 2 个路由器 每个路由 器最多和 50 个路由器直接相连 样例输入样例输入样例输出样例输出 6 1 2 3 4 2 1 3 3 1 2 5 6 4 1 5 5 3 4 6 6 3 5 6 1 6 1 5 2 4 2 5 3 6 2 1 10 1 2 2 3 4 4 8 5 1 6 2 7 3 9 8 10 9 5 6 7 10 8 3 9 10 5 9 1 3 6 1 3 5 2 1 4 2 3 5 3 6 2 1 9 7 3 4 8 10 connection impossible 9 6 2 9 2 注 注 试题来源 试题来源 在线测试 在线测试 UVA 627 提示 将路由器看作节点 则试题给出的路由器列表实际上是图的邻接表 我们可以使用 flyed 算法计算任意节点对之间的最短路矩阵 dist 最短路矩阵中元素的初始值为 计算 跳线 实际上就是计算指定节点对 x 和 y 间的一条最短路 有了最短路矩阵 dist 计算便变得十分容易 若 dist x y 为初始值 则 x 路由器和 y 由器不连通 否则 x 路由器和 y 由器连 通 我们可按照下述方法计算和输出低 ID 的信息传送路线 输出路线上的首节点 x while dist x y 1 若 y 非最短路的尾节点 for int k 1 k N k 按照 ID 递增的顺序搜索最短路上 x 的相邻节点 k if dist x k 1 继续找最短路上 k 的相邻节点 break 输出最短路上的尾节点 y 33 The Warehouse 特工 007 找到了疯狂的科学家 Dr Matroid 的秘密武器仓库 仓库里放满了大箱子 可 能致命武器就在箱子内 在对仓库进行检查的时候 007 意外地触发了警报系统 仓库有 一种针对入侵者的非常有效的保护 如果触发警报 那么地板上就充满了致命的酸 因此 007 可以逃脱的唯一的办法是爬到箱子上面 并达到在顶部的出口 出口是一个在天花板 上的洞 如果 007 可以爬上通过这个洞 他便可以使用停在屋顶上的直升机逃脱 在洞的 下方 有一个梯子和一个箱子 因此 目标就是到达这个箱子 仓库的地板可视为 n n 单元格的一个网格 每个单元格的大小为 1 米 1 米 每个单元 格或者是完全被一个箱子占用或没有放东西 每个箱子是长方体 占据地面的大小为 1 米 1 米 高度可以是 2 米 3 米 或者 4 米 在图 a 中 可以看到一个仓库的实例 数 字表示箱子的高度 E 表示出口 圆表示特工 007 目前在该箱子的顶部 图 007 可以做两件事 如果他正站在一个箱子的顶部 并在相邻的单元格中还有另外一个箱子 那么他可以 移动到另一个箱子的顶部 例如 在图 a 所示的情况中 他可以向北部或向东移动 但 不能向西或向南移动 请注意 只允许这四个方向的移动 对角线方向移动是不允许的 两个盒子之间的高度差并不重要 007 能够做的第二件事情是他能够向 4 个方向推倒他所站的箱子 用一个例子来表示推 倒箱子的情况 007 的情况如图 b 所示 他可以向西推翻箱子 如图 c 所示 或 向北推倒箱子 如图 d 所示 如果箱子的高度为 H 向北 或向西 向南 等等 推 倒箱子 则箱子在向北 或者向西 向南 等等 方向上占据连续的 H 个单元格 箱子原 来占据的位置将被空置 但还可以推翻另外的箱子 重新占据这个位置 如果在箱子倒下 的位置上没有被其他箱子占据 箱子才可以朝这个方向被推倒 例如 在 a 中 007 所 站的箱子不能朝任何一个方向被推倒 推倒了一个箱子