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

= 5 = 计算机考研复试上机指导全书习题集试读版 1001. A+B Format (20) Time Limit: 400 MS Memory Limit: 65536 KB 题意题意 给出两个整数 a、b（不超过 109） ，求 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中就是 num0 = 3、num1 = 2、num2 = 1，即 sum 的低位存储到 num的低位） ，之后从高位开始输出数组元素，每输出 3 个数字输出 1 个逗号，最后 3 个数字后面不输出。 注意点注意点 Note 1: 把 sum 存放到数组时，如果是用 while 写的话，就要注意 0 这个数据需要特殊处理，否则 while 循环进不去，导致 len 会等于 0；而如果用 do while 循环写的话，则可以不用考虑。 /使用 while 的写法 int len = 0; if(sum = 0) numlen+ = 0; while(sum) numlen = sum % 10; sum /= 10; +len; /使用 do.while 的写法 = 6 = int len = 0; do numlen = 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 num10; int main() int a, b, sum; scanf(“%d%d“, sum = a + b; /将 a+b 赋值给 sum if(sum = 0; k-) /从高位开始输出 printf(“%d“, numk); 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; window20; 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; /队列 window20; int ansmaxNode, needTimemaxNode; /服务结束时间、服务需要时间 int main() int inIndex = 0; /当前第一个未入队的客户编号 scanf(“%d%d%d%d“, /窗口数、窗口人数上限、客户数、查询数 for(int i = 0; i 成立，于是有+ + 成立，因此结点 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长） ，因此假设不 成立。公共重合区间的证明同理。因此所有直径一定有一段公共重合区间或一个公共点，形成类似 下右图的结构，其中 A1Am与 B1Bk为所有直径的端点，且 A1Am与结点 P 的距离相等，B1Bk与结 点 Q 的距离相等，直径为 A1Am到达 B1Bk的任意组合。 = 63 = (3) 证明证明两次遍历结果的并集为所求的根结点集合两次遍历结果的并集为所求的根结点集合。 若第一次遍历选择的初始结点在 PQ 之间， 那么最深结点显然是 A1Am或者 B1Bk中的其中一组 （或者全部） ，而在第二次遍历时任取一个根结点即可遍历完整另外一侧的所有最深结点。同理， 若第一次遍历选择的初始结点在 P 的左侧（或 Q 的右侧） ，那么最深结点一定是 B1Bk（或 A1Am） ， 这样在第二次遍历时任取一个根结点同样可以遍历完整另外一侧的所有最深结点，命题得证。 注意点注意点 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 GN; /邻接表 bool isRootN; /记录每个结点是否作为某个集合的根结点 int fatherN; int findFather(int x) /查找 x 所在集合的根结点 int a = x; while(x != fatherx) x = fatherx; /路径压缩（可不写） = 64 = while(a != fathera) int z = a; a = fathera; fatherz = x; return x; void Union(int a, int b) /合并 a 和 b 所在的集合 int faA = findFather(a); int faB = findFather(b); if(faA != faB) fatherfaA = faB; void init(int n) /并查集初始化 for(int i = 1; i 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 a Union(a, b); /合并 a 和 b 所在的集合 int Block = calBlock(n); /计算集合数目 if(Block != 1) /不止一个连通块 printf(“Error: %d componentsn“, Block); else DFS(1, 1, -1); /从 1 号结点开始 DFS，初始高度为 1 Ans = temp; /temp 为集合 A，赋给 Ans DFS(Ans0, 1, -1); /从任意一个根结点开始遍历 for(int i = 0; i temp.size(); i+) Ans.push_back(tempi); /此时 temp 为集合 B，将其加到 Ans 中 sort(Ans.begin(), Ans.end(); /按编号从小到大排序 printf(“%dn“, Ans0); for(int i = 1; i Ans.size(); i+) if(Ansi != Ansi - 1) /重复编号不输出 printf(“%dn“, Ansi); 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 型数组 table128表示字符是否在第二个字符串中出现。其中 tablei = true 表示 ASCII 码为 i 的字符在第二个字符串中出现；而令 tablei = false 表示 ASCII 码为 i 的字符没有在第二个字 符串中出现。初始状态下 table 数组中元素均为 false。 Step 2 枚举第二个字符串 str2，对 str2 中的每一个字符 str2i，令 tablestr2i = true，表示 stri在第 二个字符串中出现。 Step 3 枚举第一个字符串str1， 对str1中的每一个字符str1i， 如果tablestr1i = false， 则输出str1i； 如果 tablestr1i = 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 循环枚举的时候把循环条件写成 i strlen(str)。 这是因为 strlen 函数 的内部实现是使用一个循环扫描数组来累计长度，直到遇到0结束，所以 strlen 本身就有 O(N)的复 杂度，这样会使得 Step2 跟 Step3 中遍历字符串的复杂度从 O(N)上升到 O(N2)，导致超时。恰当的 做法是在 for 循环之前就定义 int 型变量 len 来记录 str 的长度，即 int len=strlen(str)。这样在 for 循 环的时候循环条件可以直接写 i len，省去了每次都要计算 strlen(str)的时间。 Note 4: 如果你在引用了 iostream 或者 vector， 又加了 using namespace std;这条语句的时候尽量不要 使用 hash 这样的变量名，因为这样会跟