《计算机考研复试上机指导全书习题集》试读版.pdf

5 计算机考研复试上机指导全书习题集 试读版 1001 A B Format 20 Time Limit 400 MS Memory Limit 65536 KB 题意题意 给出两个整数 a b 不超过 10 9 求 a b 的值 并按照 xxx xxx xxx xxx 的格式输出 样例解释样例解释 Sample One 1000000 9 999991 按照格式输出为 999 991 考察点考察点 字符串处理 思路思路 Step 1 对输入的两个数字 a 与 b 进行累加 并赋值给 sum 之后判断累加后得到的 sum 是否为负数 如果是负数 则负号先行输出 并令 sum sum 来取正 Step2 把 sum 的每一位存到数组中 例如 123 存到数组 num 中就是 num 0 3 num 1 2 num 2 1 即 sum 的低位存储到 num 的低位 之后从高位开始输出数组元素 每输出 3 个数字输出 1 个逗号 最后 3 个数字后面不输出 注意点注意点 Note 1 把 sum 存放到数组时 如果是用 while 写的话 就要注意 0 这个数据需要特殊处理 否则 while 循环进不去 导致 len 会等于 0 而如果用 do while 循环写的话 则可以不用考虑 使用 while 的写法 int len 0 if sum 0 num len 0 while sum num len sum 10 sum 10 len 使用 do while 的写法 6 int len 0 do num len sum 10 sum 10 len while sum Note 2 注意最低位后面是不需要输出逗号的 所以需要在输出逗号时判断是否是最低位 Note 3 这题还可以采用下面的写法 不妨拓宽下思路 省略 Step1 的步骤 在 printf 的格式化输出中 3d 表示输出三位整数 不满三位的高位补空格 而 03 表示输出三位 整数 不满三位的高位补 0 于是可以得到下面这个简洁的写法 不妨好好理解一下 if sum 1000000 printf d 03d 03d sum 1000000 sum 1000000 1000 sum 1000 else if sum 1000 printf d 03d sum 1000 sum 1000 else printf d sum 参考代码参考代码 include int num 10 int main int a b sum scanf d d sum a b 将 a b 赋值给 sum if sum 0 k 从高位开始输出 printf d num k if k 0 每三位一个逗号 最后一位除外 return 0 37 1014 Waiting in Line 30 Time Limit 400 MS Memory Limit 65536 KB 题意题意 某银行有 N 个窗口 每个窗口前最多可以排 M 个人 现在有 K 位客户需要服务 每位客户的 服务时长已知 假设所有客户均在 08 00 时刻按按客户编号客户编号次序次序等在黄线外 且如果有窗口的排队人 数没有排满 没有达到 M 人 当前在黄线外的第一个客户就会选择这样的窗口中排队人数最少的 窗口去排队 排队人数相同时 选择窗口序号最小的窗口去排队 给出 Q 个查询 每个查询给出 一位客户的编号 输出这位客户的服务结束时间 注意 如果一个客户在 17 00 之后 含 17 00 还 没有被服务 则不再服务 输出 Sorry 而如果一个客户在 17 00 之前被服务 那么无论他的服务时 长有多长 都会服务完整 样例解释样例解释 Sample One 有两个窗口 每个窗口前最多排两个人 初始状态下 7 个客户都在黄线外 然后按照选择窗口 的规则进行排队 得到如图的排队情况 其中每个客户右下角的中括号中的数字表示该客户当前剩 余的服务时间 由于 1 号客户的剩余服务时间比 2 号客户更短 因此 1 号客户在 08 01 时先行服务完毕 5 号 客户排到 1 号窗口后面 同时 2 号客户的剩余服务时间减少 1 分钟 得到下图 08 01 的状态图 接 下来的步骤过程与此类似 这里不再赘述 读者可以从图中得到整个过程 其中在 17 00 时 7 号客 户将无法被服务 因此 7 号客户应当输出 Sorry 38 考察点考察点 排队问题 思路思路 Step 1 考虑一个事实 当一位客户进入某一窗口的队列时 他的服务结束时间就已经确定了 即当前当一位客户进入某一窗口的队列时 他的服务结束时间就已经确定了 即当前 在该窗口排队的所有人的服务时间之和在该窗口排队的所有人的服务时间之和 而在所有窗口排满后 剩余客户能够去排队的时间点是所 有窗口最早结束的队首客户 也就是说 在所有窗口排满的情况下 每当有一个窗口的队首客户服在所有窗口排满的情况下 每当有一个窗口的队首客户服 务结束务结束 结束时间相同的 窗口 结束时间相同的 窗口 ID 小的视为先结束 小的视为先结束 剩余客户的第一个就会排到那个窗口最后面 剩余客户的第一个就会排到那个窗口最后面 去去 于是我们可以为窗口建立一个结构体 Window 存放该窗口当前队伍的最后服务时间 endTime 和队首客户的服务结束时间 popTime 并维护一个该窗口的排队队列 q 如下所示 struct Window int endTime popTime queue q window 20 Step 2 在 08 00 时刻 只要窗口的队列没满 就把客户按照窗口编号为 0 1 2 n 1 0 1 2 n 1 0 1 2 的循环顺序进行入队 且在安排的过程中不断更新窗口的 endTime 和 popTime 其中 endTime 将直接作为刚入队客户的服务结束时间 即作为答案 保存下来 而 popTime 仅在安排每个窗口的 第一客户时更新 Step 3 如果 Step 2 中已经把所有窗口排满 显然如果没有排满 就不存在剩余在黄线外的客户 那 么在该步中将剩下的客户想办法入队 由 Step 1 可以知道 在所有窗口排满的情况下 每当有一个 窗口的队首客户服务结束 结束时间相同的 窗口 ID 小的视为先结束 剩余客户的第一个就会排 到那个窗口最后面去 这样对每一个剩余的客户 我们可以选出当前所有窗口中 popTime 最小的窗 口 popTime 相同的选择窗口 ID 较小的 将客户排到该窗口的队列后面 并更新该窗口的 endTime 和 popTime 其中 endTime 将作为刚入队的客户的服务结束时间 即作为答案 保存下来 Step 4 对每一个输入的查询客户编号 如果他的服务开始时间在 17 00 之后 含 17 00 则输出 Sorry 否则输出他的服务结束时间 注意点注意点 Note 1 在 17 00 之后 含 17 00 开始服务的客户应当输出 Sorry 否则都应当输出服务结束时间 即 便服务结束时间超过了 17 00 Note 2 当一个客户服务结束时 下一个客户的服务将立即开始 剩余客户也立即入队 中间无缝 对接 不产生额外时间 Note 3 关于时间的处理有一个小小的技巧 就是把时间都转换为分钟 即把 hh mm 形式的时间全 部转换为分钟数 hh 60 mm 以便于时间的处理和比较 39 参考代码参考代码 include include include using namespace std const int maxNode 1111 int n m k query q int convertToMinute int h int m return h 60 m 转换时间为分钟 方便时间处理 struct Window int endTime popTime 窗口当前队伍的最后服务时间 队首客户的服务结束时间 queue q 队列 window 20 int ans maxNode needTime maxNode 服务结束时间 服务需要时间 int main int inIndex 0 当前第一个未入队的客户编号 scanf d d d d 窗口数 窗口人数上限 客户数 查询数 for int i 0 i k i scanf d 读入服务需要时间 for int i 0 i n i 初始化每个窗口的 popTime 和 endTime 为 08 00 window i popTime window i endTime convertToMinute 8 0 for int i 0 i min n m k i 注意是 min n m k 循环入队 window inIndex n q push inIndex 更新窗口的服务结束时间 endTime window inIndex n endTime needTime inIndex 对窗口的第一个客户 更新 popTime if inIndex n window inIndex popTime needTime inIndex 当前入队的客户的服务结束时间直接保存作为答案 ans inIndex window inIndex n endTime inIndex for inIndex k inIndex 处理剩余客户的入队 int idx 1 minPopTime 1 30 寻找所有窗口的最小 popTime for int i 0 i n i if window i popTime minPopTime idx i minPopTime window i popTime 40 找到最小 popTime 的窗口编号为 idx 下面更新该窗口的队列情况 Window 引用 下文中用 W 代替 window idx 行文更清晰 W q pop 队首客户离开 W q push inIndex 客户 inIndex 入队 W endTime needTime inIndex 更新该窗口队列的 endTime W popTime needTime W q front 更新该窗口的 popTime ans inIndex W endTime 客户 inIndex 的服务结束时间为该窗口的 endTime for int i 0 i convertToMinute 17 0 printf Sorry n 服务开始时间达到 17 00 输出 Sorry else 否则输出服务结束时间 printf 02d 02d n ans q 1 60 ans q 1 60 return 0 1015 Reversible Primes 20 Time Limit 400 MS Memory Limit 65536 KB 题意题意 给出正整数 N 和进制 radix 如果 N 是素数 且 N 在 radix 进制下反转后的数在十进制下也是素 数 则输出 Yes 否则输出 No 样例解释样例解释 Sample One 73 是素数 在十进制下反转后得到的 37 也是素数 所以输出 Yes Sample Two 23 是素数 其二进制表示为 10111 反转后得到的 11101 在十进制下为 29 也是素数 所以输 出 Yes 但是在 10 进制下为 32 不是素数 所以输出 No Sample Three 23 是素数 但在十进制下反转后得到的 32 不是素数 所以输出 No 56 1019 General Palindromic Number 20 Time Limit 400 MS Memory Limit 65536 KB 题意题意 给出两个整数 n b 问十进制整数 n 在 b 进制下是否是回文数 是则输出 Yes 否则输出 No 在那之后 输出 n 在 b 进制下的表示 样例解释样例解释 Sample One 27 在二进制下的表示为 11011 是回文数 因此输出 Yes Sample Two 121 在 5 进制下的表示为 441 不是回文数 因此输出 No 考察点考察点 进制转换 思路思路 Step 1 将整数 n 转换为 b 进制 进制转换过程可以使用在指导全书中讲解的模板 int z 40 num 0 do z num y Q y y Q while y 0 Step 2 判断 b 进制下的 n 是否为回文数 即比较位置 i 与其对称位置 num 1 i 的数字是否相同 而只 要有一对位置不相同 说明非回文 bool Judge int z int num 判断数组 z 所存的数是否回文 num 为位数 for int i 0 i num 2 i if z i z num 1 i 如果位置 i 与其对称位置 num 1 i 不相同 return false return true 所有对称位置都相同 注意点注意点 Note 1 注意边界数据 0 的输出 57 0 2 output Yes 0 参考代码参考代码 include bool Judge int z int num 判断数组 z 所存的数是否回文 num 为位数 for int i 0 i 0 i 输出数组 z printf d z i if i 0 printf return 0 61 1021 Deepest Root 25 Time Limit 1500 MS Memory Limit 65536 KB 题意题意 给出 N 个结点与 N 1 条边 问它们能否形成一棵 N 个结点的树 如果可以 则从中选出结点作 为树根 使得整棵树的高度最大 输出所有满足要求的可以作为树根的结点 样例解释样例解释 Sample One 五个结点分别作为树根时 树的形态如下 可以得出结论 以 3 4 5 号结点为树根时 可以 得到的树的高度最大 Sample Two 根据数据作出的图形如下 可以得出结论 该组数据形成了两个连通块 无法构成树 考察点考察点 并查集 树的遍历 思路思路 Step 1 由于连通 边数为 N 1 的图一定是一棵树 因此我们需要先判断给定的数据能否使图连通 而 这点可以很容易用并查集判断 具体做法为 每读入一条边的两个端点 判断这两个端点是否属于 相同的集合 即集合的根结点是否相同 如果不同 则将它们合并到一个集合中 这样 当处理 完所有边后就可以根据最终产生的集合个数是否为 1 来判断给定的图是否连通 即讲解并查集时介 62 绍的的番长亚历山大的例子 Step 2 当图连通时 由于题目保证只有 N 1 条边 因此一定能确定是一棵树 下面的任务就是选择合 适的根结点 使得树的高度最大 做法是 先任意选择一个结点 从该结点开始遍历整棵树 获取 能达到的最深的顶点 记为结点集合 A 然后从集合 A 中任意一个结点出发遍历整棵树 获取能达 到的最深的顶点 记为结点集合 B 这样集合 A 与集合 B 的并集即为所求的使树高最大的根结点 证明 证明分为三步 第一步证明最重要 1 证明从任意结点出发进行遍历 得到的最深结点一定是所求的根结点集合的一部分证明从任意结点出发进行遍历 得到的最深结点一定是所求的根结点集合的一部分 已知一棵树的使树高最大的根结点为 R 那么存在某个叶子结点 L 使得从 R 到 L 的长度即为树 的最大树高 显然 R 与 L 同为所求根结点集合的一部分 我们把 R 和 L 的路径拉成一条直线 称 为树的直径直径 下同 如下图所示 从某个结点 X 开始进行遍历 图中省略了不必要的结点 以线 段的概念长度代表结点之间的距离 下同 假设遍历得到的最深结点最深结点是 Y 而 Y 既不是 R 也不是 L 那么一定有 成立 于是有 成立 因此结点 Y 才是以 R 为根结点的产生 最大树高的叶子结点 而这违背了之前给定的前提 R 到 L 的长度是树的最大树高 因此假设 遍 历得到的最深结点 Y 既不是 R 也不是 L 不成立 得出结论 从任意结点 X 进行树的遍历 得到的 最深结点一定是 R 或者 L 即所求根结点集合的一部分 2 证明证明所有直径一定有一段公共重合区间 或是交于一个公共点 所有直径一定有一段公共重合区间 或是交于一个公共点 先证明任意两条直径一定相交 假设存在两条不相交的直径 X Y 与 W Z 长度相同 如下图所示 由于树是连通的结构 因此 在 X Y 中一定存在一点 P 在 W Z 中一定存在一点 Q 使得 PQ 是互相可以到达的 这样我们就可以 利用 P Q 拼接出一条更长的直径 而这与 X Y W Z 是直径矛盾 因此假设不成立 任意两条直径一 定相交 再证明所有直径一定有一段公共重合区间或一个公共点 假设三条直径 X1 Y1 X2 Y2 X3 Y3相互相交 但不交于同一点 设交点分别为 P Q R 如下 左图所示 显然可以通过 P Q R 来拼接出更长的直径 例如 X1 P Q R Y1比 X1 Y1长 因此假设不 成立 公共重合区间的证明同理 因此所有直径一定有一段公共重合区间或一个公共点 形成类似 下右图的结构 其中 A1 Am与 B1 Bk为所有直径的端点 且 A1 Am与结点 P 的距离相等 B1 Bk与结 点 Q 的距离相等 直径为 A1 Am到达 B1 Bk的任意组合 63 3 证明证明两次遍历结果的并集为所求的根结点集合两次遍历结果的并集为所求的根结点集合 若第一次遍历选择的初始结点在 PQ 之间 那么最深结点显然是 A1 Am或者 B1 Bk中的其中一组 或者全部 而在第二次遍历时任取一个根结点即可遍历完整另外一侧的所有最深结点 同理 若第一次遍历选择的初始结点在 P 的左侧 或 Q 的右侧 那么最深结点一定是 B1 Bk 或 A1 Am 这样在第二次遍历时任取一个根结点同样可以遍历完整另外一侧的所有最深结点 命题得证 注意点注意点 Note 1 由于题目给定的是无向图 因此在邻接表中会同时存放两个方向的边 所以在使用 DFS BFS 进行树的遍历时 需要记录当前结点的前驱结点 以避免出现 走回头路 的情况 Note 2 程序必须能处理 N 1 的特殊数据 即当输入 1 时 应当输出 1 Note 3 如果使用 set 来代替 vector 则不需要进行排序和去重 读者不妨进行尝试练习 Note 4 邻接矩阵会超内存 因此只能使用邻接表存储 参考代码参考代码 include include include include using namespace std const int N 100010 vector G N 邻接表 bool isRoot N 记录每个结点是否作为某个集合的根结点 int father N int findFather int x 查找 x 所在集合的根结点 int a x while x father x x father x 路径压缩 可不写 64 while a father a int z a a father a father z x return x void Union int a int b 合并 a 和 b 所在的集合 int faA findFather a int faB findFather b if faA faB father faA faB void init int n 并查集初始化 for int i 1 i n i father i i int calBlock int n 计算连通块个数 int Block 0 for int i 1 i n i isRoot findFather i true i 的根结点是 findFather i for int i 1 i n i Block isRoot i 累加根结点个数 return Block int maxH 0 最大高度 vector temp Ans temp 临时存放 DFS 的最远结点结果 Ans 保存答案 DFS 函数 u 为当前访问结点编号 Height 为当前树高 pre 为 u 的父结点 void DFS int u int Height int pre if Height maxH 如果获得了更大的树高 temp clear 清空 temp temp push back u 将当前结点 u 加入 temp 中 maxH Height 最大树高赋给 maxH else if Height maxH 如果树高等于最大树高 temp push back u 将当前结点加入 temp 中 for int i 0 i G u size i 遍历 u 的所有子结点 65 if G u i pre continue 由于邻接表中存放无向图 因此需要跳过回去的边 DFS G u i Height 1 u 访问子结点 int main int a b n scanf d init n 并查集初始化 for int i 1 i b G b push back a 边 b a Union a b 合并 a 和 b 所在的集合 int Block calBlock n 计算集合数目 if Block 1 不止一个连通块 printf Error d components n Block else DFS 1 1 1 从 1 号结点开始 DFS 初始高度为 1 Ans temp temp 为集合 A 赋给 Ans DFS Ans 0 1 1 从任意一个根结点开始遍历 for int i 0 i temp size i Ans push back temp i 此时 temp 为集合 B 将其加到 Ans 中 sort Ans begin Ans end 按编号从小到大排序 printf d n Ans 0 for int i 1 i Ans size i if Ans i Ans i 1 重复编号不输出 printf d n Ans i return 0 147 1050 String Subtraction 20 Time Limit 10 MS Memory Limit 65536 KB 题意题意 给出两个字符串 在第一个字符串中删去第二个字符串中出现过的所有字符并输出 样例解释样例解释 Sample One 在第一个字符串中删去 aeiou 之后如下所示 下划线 表示被删去 They are students Th y r st d nts 去掉下划线 后整合在一起 并保留原先就有的空格 就可以得到下面的字符串 Thy r stdnts 考察点考察点 哈希 思路思路 虽然说是 删去 但是实际操作的时候可以用哈希的思想使问题的解决更容易 Step 1 令 bool 型数组 table 128 表示字符是否在第二个字符串中出现 其中 table i true 表示 ASCII 码为 i 的字符在第二个字符串中出现 而令 table i false 表示 ASCII 码为 i 的字符没有在第二个字 符串中出现 初始状态下 table 数组中元素均为 false Step 2 枚举第二个字符串 str2 对 str2 中的每一个字符 str2 i 令 table str2 i true 表示 str i 在第 二个字符串中出现 Step 3 枚举第一个字符串str1 对str1中的每一个字符str1 i 如果table str1 i false 则输出str1 i 如果 table str1 i true 则不输出 注意点注意点 Note 1 题意中的删去不是数学里面的 5 3 2 而是和集合里面的减法一样 从集合 A 中减去所有集 合 B 存在的元素 所以如果第一个字符串是 aaaabbbbcccc 而第二个字符串是 ac 那么最后得到的 字符串应该是 bbbb 而不是 aaabbbbccc Note 2 visible ASCII codes 可见 ASCII 字符 先解释不可见 ASCII 字符 即属于 ASCII 码中的控制字 符 也即 ASCII 码在 0 到 31 之间 以及 ASCII 为 127 的字符 这些控制字符中还会有能发出声音的 大家可以试试这句 printf c char 7 不出意外的话你的电脑会响一下 148 所以 visible ASCII codes 就是除了不可见 ASCII 字符外的字符 我们平时使用的数字 0 9 大小写英 文字母都是可见 ASCII 字符 Note 3 有个习惯很不好 在 for 循环