华南师范大学软件学院第一届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

参考思路

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

参考代码 做法一：

#include<stdio.h> int n[11]; //because it starts from zero int main() { int a; for(int i=1;i<=9;i++) { scanf("%d",&a); n[a]=1; } for(int i=1;i<=10;i++) { if(!n[i]) //find the answer!!! { printf("The missing integer is:%d",i); break; } } return 0; }

做法二：

#include<stdio.h> int main() { int a; int result=55; //the total sum int t=9; while(t--) { scanf("%d",&a); result-=a; } printf("The missing integer is:%d",result); return 0; }

易错点解析

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

B.协助工作

---

Description

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

Input

输入包括多组数据，每组数据包含 $4$ 个正整数 $h,w,a,b$（$0<h,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.

参考思路

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

参考代码

#include <stdio.h> int main() { int h,w,a,b,c; while((scanf("%d%d%d%d",&h,&w,&a,&b))!=EOF) { c=h*h+w*w; if(c>=a*a || c>=b*b) printf("Just do it.\n"); else printf("We have a problem.\n"); } return 0; }

易错点解析

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

C.找女朋友

---

Description

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

Input

多组数据。 第一行 $T$，表示有 $T$ 组数据。（$T\le 10$） 对于每一组数据： 第一行给出 $n,m$（$1\le n,m<100$)，表示地图有 $n$ 行 $m$ 列； 第二行给出 $x1,y1$，表示 FS 在 $x1$ 行 $y1$ 列； 第三行给出 $x2,y2$，表示女生在 $x2$ 行 $y2$ 列。 （注意：行和列均从 $1$ 开始标号） 数据保证：输入的 $x1,y1$ 与 $x2,y2$ 一定在 $n\ast 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!"

参考代码

#include<stdio.h> int main(){ int T,N,M,x1,y1,x2,y2; scanf("%d",&T); while(T--) { scanf("%d%d",&N,&M); scanf("%d%d",&x1,&y1); //input FS x1 and y1 scanf("%d%d",&x2,&y2); //input girl x2 and y2 if(x2>=x1&&y2>=y1) //if girl located at bottom or right of FS printf("%d\n",(x2-x1)+(y2-y1)); //if yes output step else printf("Single dog!\n"); //if no output string } return 0; }

易错点解析

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

D.炒股

---

Description

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

Input

输入分两行。 第一行：一个整数 $N$。($1\le N\le 1000$) 第二行：$N$ 个用空格隔开的整数，表示连续 $N$ 天的股价。（$1\le 股价\le 20000$，保证相邻两天股价一定有变化）

Output

输出只有一行。 输出一个整数，代表最高股价连续上升的天数。

Sample Input

10 15 1 2 20 5 13 2 15 9 1

Sample Output

3

参考思路

题意很简单，求的其实就是最长上升子串。 可以使用数组来存储数据，也可以直接使用一次循环解决，前者需要多耗费时间、空间进行读取操作。

参考代码

#include <stdio.h> #include <stdlib.h> int main() { int n,t,cnt=0,ans=0,pre=-1; scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d",&t); if(t>pre) //price is rising { ++cnt; ans = ans>cnt?ans:cnt; //if cnt is bigger update the answer } else //price drop down { cnt = 1; //restart cnt } pre = t; //update pre to continue next loop } printf("%d\n",ans); return 0; }

易错点解析

算法实现细节不注意。大部分人都能想到解法，但在实现时有很多细节没有注意好。例如回调累加值 cnt 时设为 0 而不是 1，初始化 cnt 时设为 1 而不是 0，重置 cnt 值时忘记判断与维护的最大值 ans 的关系，比较值未赋初值导致比较时与一个随机大数进行比较，最后一次连续串长度未与 ans 进行比较等。算法与题意不符。题目要求的是连续上升子串，部分提交没有持续维护一个连续的值，而是维护由第一个元素为起点的不连续串或者只维护了第一个连续串导致答案不符。还有比较有意思的加了个排序算法，看来是以为日期也可以各种重整，今天的股价第二天就变成昨天更高的股价，学到了，以后我也要靠排序算法炒股发家致富。//逃更为奇葩的语法问题。见识到了用缩进表示代码块的 Cthon 语言，非常精妙。还有一些常见的数组越界问题。日常出现的检测数据问题。

E.模具制造

---

Description

SLF 正在经营着一家大型模具制造厂，但他每天要为许多模具打孔以适配多种工具，但这些模具需要打孔的深度不一，打孔的深度由每一道工序共同决定。 为了简化起见，模具看作由 $X$ 条不同长度的木条组成，每个模具都要通过 $S$ 道工序，每一道工序有 $X$ 个操作，第 $i$ 步操作是对模具里的第 $i$ 块木条进行打孔操作，并且无论木条现在长度为多少，一定是从整个模具的固定高度 $Y$ 开始进行打孔的。（所有模具都有同一个固定高度） 因为模具和工序实在是太多了，现在 SLF 只想知道这些模具最后的状态。

Input

第一行给出两个整数 $W,S$，其中 $W$ 代表模具的数量，$S$ 代表由多少道改造工序（$1\le W,S\le 10000$） 接下来的一行给出两个整数 $X,Y$，其中 $X$ 代表模具的固定宽度（即模具由多少块木条组成），$Y$ 代表模具的固定高度（$1\le X,Y\le 100$） 接下来有 $W$ 行，每一行描述一个模具。对于每一个模具，用 $X$ 个整数表示模具里的每一块木条的高度。 接下来有 $S$ 行，每一行描述一道工序。对于每一道工序，有 $X$ 个整数，第 $i$ 个整数表示对模具里的第 $i$ 条木条研磨的深度。 数据保证每一道工序的研磨深度都不会深于模具的固定高度。

Output

对于每一个模具，输出一行包含 $X$ 个整数，表示所有工序完成后模具里每一条木条的高度。

Sample Input

2 1 3 4 4 4 4 4 2 3 2 3 0

Sample Output

2 1 4 2 1 3

Hint

对于样例中的第二个模具，如下：

参考思路

给出模具不同位置的长度，和对应位置的研磨深度，求出最后模具的各位置的长度。按题意模拟，如果 研磨最深深度+当前模具在该位置的长度<固定最大高度，则相当于没操作，否则，该位置长度取 固定最大高度-研磨最深深度。

参考代码

#include <stdio.h> #include <string.h> int pro[10010][110],work[110]; int main() { int W,S,X,Y; scanf("%d%d",&W,&S); scanf("%d%d",&X,&Y); for(int i=1;i<=W;i++) { for(int j=1;j<=X;j++) { scanf("%d",&pro[i][j]); } } memset(work,0,sizeof(work)); int temp; for(int i=1;i<=S;i++) { for(int j=1;j<=X;j++) { scanf("%d",&temp); work[j]=temp>work[j]?temp:work[j]; //get the max depth } } for(int j=1;j<=W;j++) { for(int k=1;k<=X;k++) { //set the depth, the min of (pro[j][k]) and (Y-work[k]) pro[j][k]=pro[j][k]>(Y-work[k])?(Y-work[k]):pro[j][k]; } } for(int i=1;i<=W;i++) { for(int j=1;j<=X;j++) { printf("%d%s",pro[i][j],j==X?"":" "); } printf("\n"); } return 0; }

易错点解析

题意理解有误。每次打孔并不是在当前高度继续打孔，而是在整个模具的固定高度上往下打孔，所以当原本高度小于固定高度与打孔深度的差值时，无论如何打孔也无济于事。部分提交中打孔是连续往下打的，导致答案错误。输出格式不规范。输出的每个模具中的木条高度之间应有一个空格，且模具中的最后一根木条长度后面应不跟空格。

F.守护长方形

---

Description

围棋大师 LXY 有一块传家宝棋盘，这块棋盘的方格数为 $N\ast M$，为了保证这块传家宝的安全，LXY 把这块棋盘交给他最信任的 CGY 来保管。 CGY 喜欢守护全世界最好的长方形，于是他想知道这块棋盘的方格包含多少个他不需要守护的正方形和他必须守护的长方形。 （在 CGY 看来，长方形是非正方形的矩形，即邻边不相等）

Input

输入一行，两个正整数 $N$ 和 $M$。（$0\le N,M\le 10000$）

Output

输出正方形个数和长方形个数，用一个空格隔开。

Sample Input

2 3

Sample Output

8 10

Hint

$2\ast 3$ 的网格中， 有 $6$ 个 $1\ast 1$ 和 $2$ 个 $2\ast 2$ 的正方形，共 $8$ 个正方形， 有 $4$ 个 $1\ast 2$，$3$ 个 $2\ast 1$，$2$ 个 $1\ast 3$ 以及 $1$ 个 $2\ast 3$ 的长方形，共 $10$ 个长方形。

参考思路

由提示可找到规律：大小为 $i\ast j$ 的矩形个数为 $(N-i+1)\ast (M-j+1)$。 由此规律可得方法有：

分别枚举 $i[1,N]$ 和 $j[1,M]$，当 $i$ 与 $j$ 相等时，该矩形为正方形，当 $i$ 与 $j$ 不相等时，该矩形为长方形，根据矩形大小分别对相应变量进行累加和，可得最终结果。时间复杂度为 $O(NM)$，由于 $N,M\le 1e4$，$O(NM)=1e8$ 勉强能过。矩形个数=长方形个数+正方形个数，由此规律可只枚举正方形个数，再用矩形个数减去即可得长方形个数。由于矩形是由四条直线（两条横向两条纵向）交叉而得，而整个棋盘共有 $N+1$ 条横向直线及 $M+1$ 条纵向直线，故矩形总个数为 $all=C_{N+1}^2\times C_{M+1}^2=\frac{N\ast M\ast (N+1)\ast (M+1)}{4}$，再枚举 $i[1,min(N,M)]$ 求正方形个数为 $square={\sum }_{i=1}^{min(N,M)}(N-i+1)(M-i+1)$，两者相减即为长方形个数。时间复杂度为 $O(min(N,M))$。与 $2.$ 中方法类似，但可将枚举正方形公式合并。设 $d=min(N,M)$，并将 $(N-i+1)(M-i+1)$ 展开为 $N\ast M-(i-1)\ast (N+M)+(i-1{)}^2$，则正方形个数公式可归纳为 $square={\sum }_{i=1}^d(N-i+1)(M-i+1)=d\ast N\ast M-\frac{d\ast (d-1)\ast (N+M)}{2}+\frac{d\ast (d-1)\ast (2\ast d-1)}{6}$。时间复杂度为 $O(1)$。（此处感谢 XXQ 提供的灵感）

参考代码 方法1：

#include <stdio.h> #include <stdlib.h> #include <math.h> #include <string.h> #include <ctype.h> long long n; long long m; long long square; long long rect; int main(void) { scanf("%lld%lld",&n,&m); for (int i=1;i<=n;++i) { for (int j=1;j<=m;++j) { if (i==j) { square+=(n-i+1)*(m-j+1); } else { rect+=(n-i+1)*(m-j+1); } } } printf("%lld %lld\n",square,rect); return 0; }

方法2：

#include <stdio.h> #include <stdlib.h> #include <math.h> #include <string.h> #include <ctype.h> long long n; long long m; long long all; long long square; int main(void) { scanf("%lld%lld",&n,&m); all=n*m*(n+1)*(m+1)/4; for (int i=1;i<=(n<m?n:m);++i) { square+=(n-i+1)*(m-i+1); } printf("%lld %lld\n",square,all-square); return 0; }

方法3：

#include <stdio.h> #include <stdlib.h> #include <math.h> #include <string.h> #include <ctype.h> long long n; long long m; long long all; long long square; int main(void) { scanf("%lld%lld",&n,&m); all=n*m*(n+1)*(m+1)/4; long long d=n<m?n:m; square=d*n*m-d*(d-1)*(n+m)/2+d*(d-1)*(2*d-1)/6; printf("%lld %lld",square,all-square); return 0; }

易错点解析

数据范围衡量有误。当 $N=M=10000$ 时，可算得矩形总个数 $all=N\ast M\ast (N+1)\ast (M+1)=10002000100000000$，无论哪种做法此时 int 一定无法存储，但 long long 可以//手动滑稽。好几个接近正确的提交都这个上面折戟沉沙了，实在可惜。

统计数据

题号题目AC 率（正确/提交）AThe missing integer30.43%（203/667）B协助工作1.70%（30/1762）C找女朋友7.11%（46/647）D炒股11.17%（42/376）E模具制造1.82%（1/55）F守护长方形0.00%（0/85）

总结

终于写到这里了，好辛苦啊（伸懒腰 为了认真地完成这份题解我已经看了上千份 代码风格无法让人直视的代码了orz 以后写题解还是一天写完吧不然会忘记当天的情况

还是好好总结一下： 18 新生总体代码水平还算可以，就凭超越教学进度且代码长度略长的 E 题都有人过就大致可以肯定了。但是从某种角度来说还没有非常严密的逻辑思维，例如 B 题的黑板摆放以及 D 题层出不穷的算法实现细节问题来说，在一定压力下的 coding 中，很多同学仍然难以保持一份平和的心态。 A 题能保持 30% 的 AC 率和 74% 的通过率表明这是一道合格的签到题，可以说是肥肠良心了。 B 题是一如既往的新生绞肉机，虽然很多人在这题上落马，但不得不承认的是这题在我看来仍然值得放在这个位置。毕竟这 1700+ 的提交里面，有不少是 CE 或是多组样例输入输出没有掌握的问题，抛除这些，这题确实非常考验思维和心态，也符合我们出题时的基本思路。 C 题的数据出现了一个小问题，导致有部分进行数据检验的提交无法通过，赛后我们已经对 C 题的数据进行了更改并对 C 题的所有提交进行了一次重测，部分同学可能会因此受到影响，在此我代表出题人团队对所有受到影响的同学致歉，本题的出题人已经被我们祭天了请各位放心食用。 D 题也出得非常好，甚至我可以不吝美言地说，这题或许是出得最好的一题，可能这么说有点马后炮了，但从数据和代码呈现来看，确实在六题里试出了一些不一样的东西。 E 题……都是 FS 语文老师的错！不，是体育老师的错！其实这题要是把工序和模具的输入顺序反过来就舒服多了，然而既然要考点语法，为了尽可能引出二维数组这么做也没有办法啦～OVO F 题嘛，自己出的题 0 AC 总是正常的//逃 F 题说实话已经很良心了，如果将数据范围从 $1e4$ 改成 $1e5$ 的话，$O(n^2)$ 的做法就……嘿嘿嘿……//住口！你不改也没人过

赞美之词就说到这里，接下来是日常吐槽 //输入输出不会当然是 no response 的啦 //A+B 输入输出专题里面涵盖了所有的多样例输入输出方式 //不去做结果不会我也没有办法的啦 //已经被去年的代码漂移给练出了火眼金睛了 //今年面对什么鬼缩进都面如平湖了 //所以应该再也不会看新生代码了 //再也不看！ //哎呀真香！ //所以什么时候我院才会有 OIer 大驾光临啊嘤嘤嘤

（本文若有言论不得当，为作者一人之过） （本文纯属瞎搞，一个字也不要信，包括代码）//逃