2018 软件学院 AK 杯 题解

华南师范大学软件学院第一届AK杯于 2018 年 10 月 25 日成功举行，共有 275 名同学有效参赛（提交过代码），209 人 AC 1 题以上，最高过题数为 4 题，共 11 人。

前言

本次比赛仅供软院 18 级参加，题目趋近于入门难度。
由于新生尚未完全完成语法学习，所以出题倾向注重思维逻辑的解法。

题解

A.The missing integer

Description

题目很简单，现在有 $⑨$ 个整数，这 $⑨$ 个整数都在 $1$ 到 $10$ 之间，而且每个整数只出现了一次。因此，肯定会有一个整数缺失。现在把这个艰难的任务交给你，让你找到缺失的整数。

Input

1 行，$⑨$ 个在 $1$ 到 $10$ 之间的整数。
数据保证输入的 $⑨$ 个整数互不相等。

Output

先输出语句 “The missing integer is:”（不含引 ），后面再跟上缺失的那个整数。

Sample Input

9 2 4 8 6 1 7 3 5

Sample Output

The missing integer is:10

参考思路

1. 为这 $10$ 个数开辟一个数组，初值为 $0$。然后输入 $9$ 个数，把下标为该数字的值设为 $1$。这样一来，没有输入的那个数对应数组里面的值还是 $0$，所以再遍历这个数组，找到数组元素值为 $0$ 的下标就是缺少的那个数。
2. 既然它是连续的 $1$ 到 $10$ 的整数，而且又不是很大，那我们可以先求出这 $10$ 个数的和（等差数列），然后又重新减去另外 $9$ 个数，这样不就可以得到剩下的那个数了。这种方法代码少，还能省内存，不用开数组。

参考代码
做法一：

做法二：

易错点解析

• 看题不仔细。输出要求中明确写出先输出语句 “The missing integer is:”，后面再跟上缺失的那个整数，没有输出这条语句或者这条语句复制错误的居多。
• 语法掌握不牢固。如使用 scanf 语句输入不加取地址符 &，头文件缺失（评测姬小姐姐虽然可爱但不能自动帮你加头文件(⊙o⊙)），各种关键词的拼写错误，没写 int main()，main 函数末尾缺少 return 0。当然还有一些独创的 C 语言语法，可能是谭浩强门下弟子，看得我一愣一愣的。
• 检测数据。这个不能算错误哈，但是是一个没有任何必要的举动。后台的判题数据是经过各位出题人严格检验过的，只要是题目中保证了的输入范围，判题数据一定不会越过这个范围。理论上如果在程序中加入检验是不会出现问题的，关键在于有时候可能没掌握好范围，把在范围内的数据也排除了就收到红红的答案错误啦(≧▽≦)。
• 奇怪的解法。这个也不算错误哈，不过心疼各位写了 9 个长长的 if 语句或者 switch 的同学，辛苦了。

B.协助工作

Description

现在需要把若干块已知边长的黑板（厚度忽略不计）搬进教室，请设计程序判断黑板能否穿过教室的门。

Input

输入包括多组数据，每组数据包含 $4$ 个正整数 $h,w,a,b$（$0h,w,a,b\le 20$），$h,w$ 分别表示表示门的高度和宽度，$a,b$ 表示矩形黑板的两条边长。输入到文件结束为止。

Output

如果黑板能被搬进课室，输出 “Just do it.”。
否则，输出 “We have a problem.”。（不含引 ）

Sample Input

2 1 1 1
2 1 3 4

Sample Output

Just do it.
We have a problem.

参考思路

考察的知识点是勾股定理。要想判断一个厚度不计的黑板能不能搬进教室，只要判断教室门的对角线长度是否大于黑板的两条边长其中的一条即可。求出门的对角线长度后，与黑板的两条边长进行比对。

参考代码

易错点解析

• 黑板摆放问题。对于现实问题缺乏清楚的理解，一块物体如何穿过一个平面，应是使其尽可能以最小的边通过平面的最长对角线，长方形门的最长对角线就是以长和宽为直角边的直角三角形的斜边，然后再跟黑板的最短边进行比较。还有的黑板和门傻傻分不清楚，把门塞进黑板里了，反向 AC//然而并没有。
• 输入输出问题。本题输入包括多组数据，所以应处理多次输入，并注意到输入文件结尾为止，避免无限输出导致输出超限，且不同组别的输出应按题目要求换行。
• 语法语义不清楚。与或逻辑运算混淆，多重并列范围重叠 if 语句导致多次输出，使用 float 导致出现浮点数精度差异等。
• 日常出现的检测数据和编译问题。提醒一句啊，C 语言没有幂运算符！^ 是异或符 ！

C.找女朋友

Description

FS 最近天天看到朋友圈里面有人秀恩爱，寻思着也要去找个女朋友，所以尝试着去搭讪一下女生。有一个 $n?m$ 的地图，给你 FS 和女生的位置，FS 每一步可以向右或向下走一格，请你输出 FS 成功搭讪所需要的最少步数，若 FS 不能到达这个女生的位置，则输出 “Single dog!”（不带引 ）。

Input

多组数据。
第一行 $T$，表示有 $T$ 组数据。（$T\le 10$）
对于每一组数据：
第一行给出 $n,m$（$1\le n,m100$)，表示地图有 $n$ 行 $m$ 列；
第二行给出 $x1,y1$，表示 FS 在 $x1$ 行 $y1$ 列；
第三行给出 $x2,y2$，表示女生在 $x2$ 行 $y2$ 列。
（注意：行和列均从 $1$ 开始标 ）
数据保证：输入的 $x1,y1$ 与 $x2,y2$ 一定在 $n?m$ 的地图中。

Output

对于每一组数据，输出 FS 搭讪所需要的最少步数，若 FS 不能到达女生的位置，则输出 “Single dog!”（不带引 ）。
每组数据输出后换行。

Sample Input

2
3 3
1 1
2 2

5 5
1 1
2 3

Sample Output

2
3

参考思路

由题意得，FS 每次只能往下或者往右走一步所以 FS 一定不可能到达他上边或者左边的地方，所以只需判断一下女生位置是否在 FS 的右边或者下边即可。如果在则输出两者 xy 坐标的差值之和（两者 xy 差值之和即为步数！），
如果不在则输出”Single dog!”

参考代码

易错点解析

• 看题不仔细。部分提交没有考虑到只能向右和向下，直接取了两者的相对距离。
• 对图形的坐标不熟悉。普通行列坐标与数学上的坐标系第一象限不同，前者的行坐标由上至下，列坐标由左至右，后者的 x 坐标由左至右，y 坐标由下至上。而题目中恰恰指的是前者而不是后者。
• 语义问题。例如与或运算混淆、循环写成 [1,t) 导致遗漏最后一组样例等老问题。
• 日常出现的输入输出问题和检测数据问题。不展开讲了。

D.炒股

Description

小明很喜欢炒股，他记录了一段时间内一支股票股价的变化。现在小明想知道这支股票股价最高连续上升的天数。

Input