普及组试题和解答.pdf

普及组试题和解答 付浩 fuch 目录目录 A 矩阵乘法 2 B GPA 4 C GAP 7 D 材质贴图 9 E 货币兑换 11 F 网页浏览器 13 A 矩阵乘法矩阵乘法 题目描述 矩阵乘法是线性代数中最基本的运算之一 给定三个矩阵 ijp qijr sijn m AaBbCc 请编写程序判断A BC 是否成立 输入格式 输入包含多组数据 每组数据的格式如下 第一行包括两个整数 p 和 q 表示矩阵 A 的大小 后继 p 行 每行有 q 个整数 表示矩阵 A 的元素内容 紧接着用相同的格式给出矩阵 B 和矩阵 C 输入数据的最后一行是两个 0 你的程序处理到这里时就应该退出了 输入数据中所有的整数绝对值都不超过 100 输出格式 对每一组输入数据 你的程序都要输出单独一行字符 如果A BC 成立则输出 Yes 如果 A 和 B 根本不能相乘 或A BC 不成立 则输出 No 注意大小写 输入样例 2 3 1 2 3 4 5 6 3 2 1 2 3 4 5 6 2 2 22 28 49 64 1 2 1 2 2 1 2 1 2 2 2 4 1 2 1 2 1 2 1 1 1 1 1 1 0 0 输出样例 Yes No No 解答 此题考察线性代数基本概念 请参阅线性代数教材 B GPA 题目描述 科大的学生都很重视 GPA 所以我们来编写一个成绩管理系统吧 大多数高校都使用平均成绩绩点 Grade Point Average 简称 GPA 来评估学生成绩 科大 的百分制成绩与绩点的对应关系如下 百分制 绩点 100 95 4 3 94 90 4 0 89 85 3 7 84 82 3 3 81 78 3 0 77 75 2 7 74 72 2 3 71 68 2 0 67 65 1 7 64 1 5 63 61 1 3 60 1 0 59 0 0 0 一个学生的平均分为各门课程百分制成绩的加权平均值 课程成绩 课程学分 平均分 课程学分 同样地 平均成绩绩点为各门课程绩点的加权平均值 GPA 课程绩点 课程学分 课程学分 请编写一个成绩管理系统处理成绩的录入 计算和查询等操作 输入格式 输入数据只有一组 第一行包括三个整数 学生总数 n 1 n 500 课程总数 m 1 m 500 操作总数 q 1 q 100000 接下来的 n 行每行为一个仅包含字母和数字的字符串 表示各个学生的学号 接下来的 m 行每行为一个仅包含字母和数字的字符串 表示各个课程的编号 以及一个正 整数 表示该课程的学分 最后 q 行每行描述一次操作 各操作的格式和功能如下 操作 功能 score a b s 学号为a的学生的课程 b 的百分制成绩为s 把该成绩登记录入系统 成绩不会重复录入 student a 根据当前系统中的数据 输出学号为 a 的学生百分制平均成绩和 GPA 用单个空格隔开 四舍五入到小数点后两位 course b 根据当前系统中的数据 输出课程 b 的百分制平均成绩 四舍五入到 小数点后两位 query a b 输出学号为a的学生的课程b的百分制成绩和绩点 用单个空格隔开 该成绩一定已经录入到系统中 学号和课程编号长度不超过 10 个字符 输出格式 对于操作 student course 和 query 按照上述描述输出 输入输出具体格式请参阅输入输出 样例 输入样例 5 3 10 PB09123456 PB09654321 SA09123456 SA09654321 PB07010101 ABCDEFGHIJ 1 0123456789 2 0101010101 2 score PB09123456 0101010101 64 score PB09123456 0123456789 100 query PB09123456 0101010101 score SA09654321 0101010101 90 student PB09123456 course 0101010101 student PB07010101 course ABCDEFGHIJ score PB09654321 0101010101 85 course 0101010101 输出样例 64 1 50 82 00 2 90 77 00 0 00 0 00 0 00 79 67 提示 请尽可能地优化你的程序 否则难以在规定时间内完成所有操作 C 语言可以用 printf 2lf n s 四舍五入到小数点后两位输出 double 类型 解答 首先 需要给各个学号和课程号分配一个整数的编号以方便操作 按照输入数据中的顺序来 编号其实就可以了 如果事先对输入进行排序 每次使用二分查找来确定编号会更快 为了快速地完成各项查询操作 每次录入成绩时我们需要保存如下信息 一个二维数组储存每个学生对应课程的成绩 三个一维数组储存每个学生获得的总学分 百分制成绩加权和 绩点加权和 两个一维数组储存每门课程已有成绩的学生人数 百分制成绩总和 C GAP 题目描述 最近经常下雨 泥泞的道路已经让人不爽 如果不小心踩到水沟 gap 里就相当刺激了 某位热爱科学的无聊闷骚科大猥琐男想到了这样一个问题 水沟里有多少水 为了简化问题 我们只需求出给定的一个纵切面上雨水所占的面积即可 如图所示 假设在这个纵切面上 水沟的轮廓可以用一条抛物线描述 2 0 yaxbxc a 水平面位于 y 0 换言之 由 y 0 和 2 0 yaxbxc a 两条曲线围成的区域就是雨水 所在的区域 输入格式 输入包括多组数据 每组数据仅占一行 包括三个浮点数 a b c a 0 当输入的 a 小于 0 时则表示输入结束 你 的程序应该到此结束 并且不要处理这组数据 输出格式 对于每组数据 输出一行包括所求的面积 四舍五入到小数点后四位 15 10 5 0 5 10 15 20 6 4 20246 轮廓 水平面 输入样例 0 5 4 0 6 0 1 0 1 0 1 0 1 0 0 0 2 5 1 0 2 0 1 0 1 0 0 0 0 0 输出样例 5 3333 0 0000 5 2705 0 0000 提示 C 语言可以用 printf 4lf n s 四舍五入到小数点后四位输出 double 类型 解答 解答此题需分两步 首先 求解两曲线的交点 易见这是一个简单地一元二次方程 如果方程无实数解那么面积 为零 最后 由积分 1 2 23322 121212 32 x x ab Saxbxc dxxxxxc xx 求得面积 D 材质贴图材质贴图 题目描述 3D 游戏中的场景经常用材质贴图来表现 例如石头 水面等 通常 材质贴图是一张正方形的位图 上下边界的像素对应相同 左右边界的像素也对应相 同 例如下图中 左边是一张材质贴图 而右边的不是 左右边界不同 255 192 120 255 255 192 120 255 31 119 3 31 31 119 3 31 76 214 0 76 77 214 0 76 255 192 120 255 255 192 120 255 给定一张 n n 的位图 请在这张位图中寻找一块材质贴图 使得材质贴图尺寸最大 下图 中黄色区域就是最大的材质贴图 虽然黄色区域左上角 2 2 的位图也是材质贴图 但不是 最大的 5 251 127 11 195 23 13 0 13 23 211 0 13 0 67 211 13 0 13 23 1 251 127 11 47 输入格式 输入包含多组数据 每组数据第一行是一个整数 n 1 n 50 表示位图的大小 然后 n 行每行 n 个在 0 到 255 之间的整数 描述位图的内容 输入数据以 n 0 结束 不要处理这组数据 输出格式 对每组数据输出最大的材质贴图的边长 请注意 1 1 的位图也是材质贴图 输入样例 2 255 0 0 127 5 5 251 127 11 195 23 13 0 13 23 211 0 13 0 67 211 13 0 13 23 1 251 127 11 47 0 输出样例 1 3 解答 一重循环按从大到小的顺序枚举材质贴图的大小 再两重循环枚举材质贴图左上角的坐标 最后一重循环判断是否是材质贴图 首次发现的材质贴图就是最大的 E 货币兑换货币兑换 题目描述 招商银行遇到一位很奇怪的顾客 这位顾客起初用一些人民兑换了另一种货币 然后不断地 用一种货币兑换另一种货币 最后又换回人民币 令人惊奇的是 最后换回的人民币居然比 他最初带来的多了一些 例如这样一个兑换过程 假设 1 单位人民币兑换 6 89 单位火星币 1 单位火星币兑换 0 18 单位水星币 1 单位水星 币兑换 0 81 单位人民币 我们用 1 20 单位人民兑换得 8 27 单位火星币 然后用这 8 27 单位火星币兑换得 1 49 单位 水星币 最后用 1 49 单位水星币兑换到 1 21 单位人民币 奇迹就这样发生了 聪明的你一定已经发现了 这都是四舍五入的功劳 当然这种事情在现实中是不可能的 但我们还是来研究一下这个问题 假设共有 n 种货币 编号从 1 到 n 我们最初持有 m 单位的货币 1 已知各种货币之间兑换 比率 每次兑换后都四舍五入到小数点后两位 请问兑换 k 次且换回到货币 1 后 最多能让 我们持有的货币增加多少单位 输入格式 输入包含多组数据 每组数据第一行包含两个整数 n 1 n 100 k 0 k 100 第二行为一个实数 m 0 m 100 精确到小数点后两位 这三个数的含义如上所述 然后是 n 行 每行 n 个数 第 i 行的第 j 个数 aij表示可以用单位货币 i 兑换 aij单位的货币 j 注意 不一定能反向兑换 若 aij 0 则表示不能直接用货币 i 兑换货币 j 显然不能用货币 i 换货币 i 这样没有意义 输入以 n k 0 结束 输出格式 对每组数据输出我们持有的货币 1 最多能增值多少 精确到小数点后两位 如果不可能增值 则输出 0 00 输入样例 3 3 1 20 0 00 6 89 0 00 0 00 0 00 0 18 0 81 0 00 0 00 1 0 1 00 0 00 0 0 输出样例 0 01 0 00 解答 设 n fi为 n 次兑换后 我们所拥有的货币 i 的最大数量 边界条件 0 1 01 mi fi i 并且有递推式 1 max 1 kk ji fifjak 上式中 运算表示四舍五入到小数点后两位的乘法 利用上面的公式 按照 k 递增的顺序计算即可 F 网页浏览器网页浏览器 题目描述 Making System Incredible Exhausted MSIE 是一款 Windows 上常见的网页浏览器 它让您每 一天的网上冲浪更快捷 更简单 更安全 并且充满乐趣 新版 MSIE9 即将推出 然而还有一个重要的导航模块没有编写完毕 它的开发者请求你的 帮助 正如上图所示 导航模块要接受用户的后退 前进 进入用户输入的网址以及清空浏览记录 等操作 输入格式 为了简化问题 用户所有的操作都以字符的形式从标准输入读入 每一行描述一个操作 各 操作的格式和功能如下所示 操作操作 功能功能 back 如果当前页面不是第一个页面 则跳到到前一个页面 并输出这个页面 的网址 forward 如果当前页面不是最后一个页面 则跳到到后一个页面 并输出这个页 面的网址 url 网址 跳转到用户输入的网址 网址不含空格 并输出这个网址 clear 清空浏览记录 当前页面除外 exit 退出浏览器 浏览器启动时默认进入科大的主页 输出格式 对于每一个需要输出网址的操作 输出对应