2008年上学期程序设计实践(兴).doc

2008 年上学期年上学期 程序设计实践程序设计实践 说明说明 A 所有的题目的输入为标准输入 所有的输出为标准输出 B 编写程序时请自行编写数据文件做测试 提交时只需提交源程序 无需提交测试用的数据文件或其他 文件 C 请不要在程序结束时中加入 system pause getch 之类等待用户输入的语句 这样会导致你的提 交源程序被判定为错误答案 D 所有的题目都有时间限制 如果你提交的源程序经编译 连接生成的可执行程序 运行超过这个时 间 会被系统判定为错误答案 超时 上机安排上机安排 时间 第 5 9 周 星期二上午 第 14 16 周 星期二上午 地点 工科楼六楼 题目题目 1 小明的数学题小明的数学题 小明是个小学五年级的学生 为了早点去看自己爱看的卡通 他想快点把作业做完 可是可恶的数学 老师今天却布置了一道难题 小明想了很久也不知道该怎么做 你的任务就是帮小明解决掉这道数学题 题目是这样子的 有一个整数 a 231 a 231 1 计算它的整数幂 an 其中 1 n 99 输入 第一行是一个整数 K 表示有多少个测试用例 以后每行一个测试用例 每行有两个整数 a n 输出 每行输出一个测试用例的结果 Sample Input 2 3 5 2 5 Sample Output 243 32 2 小明的数学题小明的数学题 小明是个小学五年级的学生 为了早点去看自己爱看的卡通 他想快点把作业做完 可是可恶的数学 老师今天却布置了一道难题 小明想了很久也不知道该怎么做 你的任务就是帮小明解决掉这道数学题 题目是这样子的 有一个正整数 n 1 n 100 计算它的阶乘 n 输入 第一行是一个整数 K 表示有多少个测试用例 以后每行一个测试用例 每行有一个整数 n 输出 每行输出一个测试用例的结果 Sample Input 2 5 20 Sample Output 120 2432902008176640000 3 小明的数学题小明的数学题 小明是个小学五年级的学生 为了早点去看自己爱看的卡通 他想快点把作业做完 可是可恶的数学 老师今天却布置了一道难题 小明想了很久也不知道该怎么做 你的任务就是帮小明解决掉这道数学题 题目是这样子的 有两个实数 a b 计算 a b 要求保留小数点后面 n 位 0 n 100 四舍五入 输入 第一行是一个整数 K 表示有多少个测试用例 以后每行一个测试用例 每行有三个数 a b n a b 都是形如 1 02 或者 2 的数 不采用科学计数法表示 也不会有 5 或者 2 之类的方法表示 输出 每行输出一个测试用例的结果 Sample Input 2 5 0 2 0 4 23 1 4 7 10 Sample Output 2 5000 4 9148936170 4 小明的数学题小明的数学题 小明是个小学五年级的学生 为了早点去看自己爱看的卡通 他想快点把作业做完 可是可恶的数学 老师今天却布置了一道难题 小明想了很久也不知道该怎么做 你的任务就是帮小明解决掉这道数学题 题目是这样子的 有两个实数 a b 计算 a b 输入 第一行是一个整数 K 表示有多少个测试用例 以后每行一个测试用例 每行有三个数 a b n a b 都是形如 1 02 或者 2 的数 不采用科学计数法表示 也不会有 5 或者 2 之类的方法表示 输出 每行输出一个测试用例的结果 如果小数部分为 0 不需要输出小数部分 Sample Input 2 5 0 2 0 1 23456789 9 87654321 Sample Output 10 12 1932631112635269 5 列车长的烦恼 John 是个小列车站的站长 每次列车在这里重新编组时他就很烦恼 因为站上只有一个人字形的编 组轨道 如图 所有的列车车厢都是从人字轨的左边依次进去 从右边出来 但有一些编组顺序 John 总 编不出来 John 怀疑有些编组顺序是不可能完成的 可 John 又找不出那些是顺序是可以编组出 那些不 可以 请你写一个程序帮助 John 辨别哪些编组可以完成 哪些不能完成 输入 第一行是一个整数 K 表示有多少个测试用例 以后每行一个测试用例 每行为 n 1 个整数 第一个整数为 n 表示有多少节车厢 后面 n 个整数表示需要编组成的顺序 比如说 3 节车厢 按照 1 2 3 依次入轨编组 可以在右边形成 1 2 3 1 3 2 2 1 3 2 3 1 321 输出 每行输出一个测试用例的结果 如果可以编组输出 Yes 否则输出 No Sample Input 2 3 3 1 2 4 1 2 3 4 Sample Output No Yes 6 远古文明的算术题远古文明的算术题 考古人员发现地球在一亿年以前曾经存在一个高级文明叫做 Delta 而且发现这个文明的具有文字和 语言 经过艰苦卓绝的工作 专家们破译了其中的一些文字和表示方法 他们使用 表示加运算 表示减运算 表示乘运算 表示整数除运算 表示取模运算 但算术式的表示和我们不同 他们 把要计算的数放到前面 运算符放在计算对象的后面 比如 1 2 表示 1 2 1 12 3 4 表示 1 12 3 4 考古人员希望你帮助他们编写一个程序 计算出这些计算式的值 输入 第一行是一个整数 K 表示有多少个测试用例 以后每行一个测试用例 每行为一个字符串 长度不超过 200 个字符 数和数 数和运算符 运算符和运算符之间分别用一个空格隔开 数都 为非负整数 且小于或等于 231 1 所有计算式都符合计算规则 不会出现不可计算的计算式 且结果 都为非负整数 且小于或等于 231 1 输出 每行输出一个测试用例的结果 使用一个字符串表示计算以后的结果 Sample Input 2 1 2 1 12 3 4 Sample Output 3 91 7 成对的字符串成对的字符串 有些字符串 如果满足下面的性质 则称为成对的字符串 a 所有的字符在字符串中出现偶数次 b 每一对相同的字符之间不会有出现奇数次的字符 现在给你一些字符串 请判断这些字符串是否为成对的字符串 输入 第一行是一个整数 K 表示有多少个测试用例 以后每行一个测试用例 每行为一个字符串 长度不超过 1000 个字符 输出 每行输出一个测试用例的结果 如果是 输出 Yes 否则输出 No 提示 字符串只有英文字母 大小写敏感 Sample Input 2 aAbbAaaabbcc abcdefghijklmn Sample Output Yes No 8 括号编码括号编码 S s1 s2 s2n 是一个符合格式的括号的字符串 S 能按下面两种方式编码 P 编码 编码是一个整数序列 P p1 p2 pn pi是第 i 个右括号之前的左括号的数目 W 编码 编码是一个整数序列 W p1 p2 pn wi是第 i 个右括号的编码值 它等于这个右括号到与之 匹配的左括号之间的右括号的数目 包括它自己 比如 请写 一个程序 将 P 序列 转换成 W 序列 输入 第一行是一个整数 K 表示有多少个测试用例 以后每两行一个测试用例 每个测试用例第 一行为一个整数 n 1 n 20 表示 P 序列长度 每个测试用例第二行 n 个非负整数 每个整 数之间有一个空格分隔 输出 每行输出一个测试用例的结果 每行包括 n 个整数 每个整数之间用一个空格分隔 Sample Input 2 6 4 5 6 6 6 6 9 4 6 6 6 6 8 9 9 9 Sample Output 1 1 1 4 5 6 1 1 2 4 5 1 1 3 9 9 恺撒的密码恺撒的密码 恺撒时代充满了动荡和危险 恺撒为了保证在战争中传递秘密消息 发明了一种密码 他在所 有的信件中将所有的字符按字母顺序向后移动了 5 个位置 比如说 原文中是 A 那么密信中就为 F 密信中字母和原文中字母的对应关系如下 密文 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 原文 V W X Y Z A B C D E F G H I J K L M N O P Q R S T U 只有字母被替换 而且所有字母都是大写的 输入 第一行是一个整数 K 表示有多少个测试用例 以后每行一个测试用例 每行为一个字符串 长度不超过 1000 个字符 输出 每行输出一个测试用例的结果 Sample Input 3 NS BFW JAJSYX TK NRUTWYFSHJ FWJ YMJ WJXZQY TK YWNANFQ HFZXJX N BTZQI WFYMJW GJ KNWXY NS F QNYYQJ NGJWNFS ANQQFLJ YMFS XJHTSI NS WTRJ IFSLJW PSTBX KZQQ BJQQ YMFY HFJXFW NX RTWJ IFSLJWTZX YMFS MJ Sample Output S P456666 W111456 IN WAR EVENTS OF IMPORTANCE ARE THE RESULT OF TRIVIAL CAUSES I WOULD RATHER BE FIRST IN A LITTLE IBERIAN VILLAGE THAN SECOND IN ROME DANGER KNOWS FULL WELL THAT CAESAR IS MORE DANGEROUS THAN HE 10 零件零件 有一种工业零件 分成左右两半 它们的形状由 X 和空格表示的二维图形表示 比如 左半的 零件形状如下 XXXXX XXX XXXX XXX 右半的零件的形状如下 XXX XXXX XXXX XXXXX 所有的左半边的零件的左边第一列都是 X 所有右半的零件的右边第一列都是 X 把这样的左右两个零件紧密地拼在一起 则可能存在空洞 零件本身也可能有空洞 但不会存在断 裂的零件 每个空洞为一个空格 要求你写一个程序求出空洞的大小 空格的数目 输入 第一行是一个整数 K 表示有多少个测试用例 以后每一个测试用例占 2n 1 行 每个测试用 例的第一行为一个整数 n 1 n 20 从第 2 行到 n 1 行为左半零件的二维图形 从第 n 2 行到 2n 1 行为右半零件 左半零件左对齐 最长一行不超过 25 列 右半零件右对齐 最长一行不超过 25 列 输出 每行输出一个测试用例的结果 Sample Input 2 4 XXXXX XXX XXXX XXX XXX XXXX XXXX XXXXX 2 XXXXX X XXXXX XXX Sample Out 1 6 11 狼群战术狼群战术 二战中德军潜艇使用狼群战术使得盟军的运输线遭受重大的损失 盟军截获了德军潜艇的通信电报 但电报显然是加了密的 经过盟军解密人员和情报人员的努力 终于解密了德军的密码 其编码方 式如下 使用一个 5 5 的矩阵 纵和横坐标都依次为 ABCDE 上面分别写有除 V 以外的 25 个字母 然后每个字母使用横纵坐标的字母表示 V 使用 FF 表示 具体矩阵如下 QWERT YUIOP ASDFG HJKLZ XCBNM 比如说 A 的密文为 CA M 的密文为 EE 请你写一个程序翻译密文 输入 第一行是一个整数 K 表示有多少个测试用例 以后每行一个测试用例 每个测试用例为一 个字符串 最大长度不超过 1000 字符串为大写英文和标点组成的 输出 每行输出一个测试用例的结果 请输出对应的明文 Sample Input 2 CAAEAECAEB ECADBCAEBCCBDACBDABCBE ADACAEBBADED AEBD ECACCBAC EBCABEAECABCED Sample Output ATTACK BRITISH SHIP RETURN TO BASE CAPTAIN 12 非前缀编码非前缀编码 有很多方法可以实现使用 2 进制序列对字符进行编码 比如典型的 Huffman 编码 如果在对字符的 2 进制编码中不存在某一个字符的编码是另一个字符编码的前缀 那么就称这种编码方式为非前缀编 码 Huffman 编码就是一种非前缀编码 比如 A 00 B 10 C 0100 D 0101 则这种编码为非前缀 编码 A 01 B 10 C 010 D 0000 则这种编码为前缀编码 请写一个程序 判断编码是前缀编码还是非前缀编码 输入 第一行是一个整数 K 表示有多少个测试用例 以后每行一个测试用例 每个测试用例为若 干个字符串 字符串之间有空格隔开 最大长度不超过 1000 输出 每行输出一个测试用例的结果 如果是非前缀编码输出 Yes 否则输出 No Sample Input 2 01 10 0010 0000 01 10 010 0000 Sample Output Yes No 13 节约每一个字节节约每一个字节 John 在做一个项目 项目对存储容量有着近乎苛刻的要求 为此 John 需要对一些东西进行压缩存储 John 的第一个问题就是一大堆的字符串 存储它们太占地方了 为此他想了一个办法 如果字符串 具有相同的后缀 那么就把这么字符串的相同后缀和在一起 这样就能节约一点空间了 比如说有 两个字符串分别为 Programming 和 Something 这样它们有相同的后缀 ing 这时候就能省去三个 字母了 请写一个程序 计算 John 这样做能够省去多少个字母 输入 第一行是一个整数 K 表示有多少个测试用例 以后每个测试用例占 n 1 行 每个测试用例 的第一行为一个整数 n 1 n 20 从第二行开始依次为 n 个字符串 字符串由英文字母组成 大小 写敏感 输出 每行输出一个测试用例的结果 输出总共节省了多少个字母 Sample Input 2 2 Programming Something 3 John AJohn BJehn Sample Output 3 6 14 John 的农场的农场 John 是一个农场主 他有几个牧场 为了好好照顾他的牛 他必须在几个牧场之间来回 可糟糕的 天气往往使得道路非常泥泞 为此 John 准备在牧场之间铺一些石子路 这样在下雨天也能快速地从 一个牧场到另外一个牧场 但 John 的资金有限 为了自己能从任一个牧场都通过石子路到达另外一 个牧场 他需要好好设计一下线路 请帮助 John 设计好线路 使得 John 能从任一个牧场都通过石子 路到达另外一个牧场 且线路的费用最低 输入 第一行是一个整数 K 表示有多少个测试用例 以后每个测试用例占 n 1 行 每个测试用例 的第一行为一个整数 n 3 n 20 表示有多少个牧场 从第二行开始为一个 n n 的矩阵 矩阵元 素 aij表示从 i 个牧场到 j 个牧场的铺路费用 输出 每行输出一个测试用例的最小铺路费用 Sample Input 2 6 0 6 1 5 0 0 6 0 5 0 3 0 1 5 0 5 6 4 5 0 5 0 0 2 0 3 6 0 0 6 0 0 4 2 6 0 4 0 1 2 3 1 0 3 4 2 3 0 1 3 4 1 0 Sample Out 15 4 15 唯一的最小生成树唯一的最小生成树 求一个非负权边的无向连通图的最小生成树 如果这个无向图存在两个或两个以上的最小生成树 就输出 Not Unique 否则输出最小生成树的边的权值和 输入 第一行是一个整数 K 表示有多少个测试用例 以后每个测试用例占 m 1 行 每个测试用例 的第一行为两个整数 n m 3 n 100 表示图的顶点数和边数 从第二行开始每行为三个整数 i j w 表示从 i 到 j 顶点的权值 输出 每行输出一个测试用例的结果 如果这个无向图存在两个或两个以上的最小生成树 就输出 Not Unique 否则输出最小生成树的边的权值和 Sample Input 2 3 3 1 2 1 2 3 2 3 1 3 4 4 1 2 2 2 3 2 3 4 2 4 1 2 Sample Out 3 Not Unique 16 重构二叉树重构二叉树 根据输入的二叉树前序和中序遍历序列重构二叉树 输出对应节点的左右子节点 输入 第一行是一个整数 N 1 N 20 表示有多少个测试例子 以下每个测试例子的第一行是 本测试例子的二叉树的前序遍历 第二行是中序遍历 第三行首先是一个整数 M 表示要求输出结果的 数目 以后有 M 个节点 每个中间由一个空格隔开 数据输出 每行输出一个例子的所有结果 如果其子节点为空则输出字符 同一例子的不同节点的输出结果之 间用一个空格隔开 Sample Input 1 ABCDEF CBEDFA 3 A B C Sample Output B CD 17 食物链食物链 动物王国中有三类动物 A B C 这三类动物的食物链构成了有趣的环形 A 吃 B B 吃 C C 吃 A 现有 N 个动物 以 1 N 编号 每个动物都是 A B C 中的一种 但是我们并不知道它到底是哪一种 有人用两种说法对这 N 个动物所构成的食物链关系进行描述 第一种说法是 1 X Y 表示 X 和 Y 是同类 第二种说法是 2 X Y 表示 X 吃 Y 此人对 N 个动物 用上述两种说法 一句接一句地说出 K 句话 这 K 句话有的是真的 有的是假的 当一句话满足下列三条之一时 这句话就是假话 否则就是真话 1 当前的话与前面的某些真的话冲突 就是假话 2 当前的话中 X 或 Y 比 N 大 就是假话 3 当前的话表示 X 吃 X 就是假话 你的任务是根据给定的 N 1 N 50 000 和 K 句话 0 K 100 000 输出假话的总数 输入 第一行是两个整数 N 和 K 以一个空格分隔 以下 K 行每行是三个正整数 D X Y 两数之间用一个空格隔开 其中 D 表示说法的种类 若 D 1 则表示 X 和 Y 是同类 若 D 2 则表示 X 吃 Y 输出 只有一个整数 表示假话的数目 Sample Input 100 7 1 101 1 2 1 2 2 2 3 2 3 3 1 1 3 2 3 1 1 5 5 Sample Output 3 18 黑箱子 有一个黑箱子 里面会按升序存储整数 你可以对黑箱子下达下面的指令 a ADD n 将 n 加入黑箱子 b Get 获得一个数 这个数在黑箱子里的序号 从 0 开始计数 是 Get 的出现次数 黑箱子中最初存了一个数 0 现给你一个操作序列 要你输出 Get 命令时获的那个数 输入 每行是一个命令 如果命令是 ADD 则后面空一格 有一个整