华南师范大学软件学院第三届 AK 杯于 2020 年 10 月 25 日成功举行，有效参赛人数为 435 ，共有 433 人通过 1 题或以上。
本次比赛面向 20 级新生，考察的方向偏思维和逻辑，不涉及复杂算法，具体包括：各种数据类型的读入和输出、基本算术运算、分支和循环、数组的基本使用、字符和字符串的简单处理、排序、贪心等。
题意：
分析与思路：
参考代码：
#include <stdio.h>
int main()
{
puts("yiming shixiong nvzhuang");
return 0;
}
易错点分析：
题意：
分析与思路：
C/C++ 需要用到long long int 类型， Java 需要用 long 类型。参考代码：
#include <stdio.h>
int main()
{
int sum = 5 + 6 + 3 + 6 + 3 + 7 + 3 + 4 + 1 + 7 + 7 + 24 + 3 + 2 + 9 + 8;
// 一定要在计算过程中进行强制转换（括号部分）
long long product = (long long)5 * 6 * 3 * 6 * 3 * 7 * 3 * 4 * 1 * 7 * 7 * 24 * 3 * 2 * 9 * 8;
printf("Sum:%d\n", sum);
printf("Product:%lld\n", product);
return 0;
}
易错点分析：
int 。long long int 但在计算过程中没有进行数据类型的强制转换。题意：
分析与思路：
参考代码：
暴力枚举:
#include <stdio.h>
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; ; i ++ )
{
// 将 i 的每个数位上的数相加
int x = i, sum = 0;
while (x)
{
sum += x % 10;
x /= 10;
}
// 如果当前 i 的数位和等于 n
// 直接输出并退出程序
if (sum == n)
{
printf("%d\n", i);
return 0;
}
}
return 0;
}
贪心:
#include <stdio.h>
int main()
{
int n;
scanf("%d", &n);
// tail 为结果中末尾的若干个 9
// cnt 为 9 的个数
int tail = 0, cnt = 0;
while (n > 9)
{
tail = tail * 10 + 9;
cnt ++ ;
n -= 9;
}
// 需要将剩下的 n 乘以 10 的 cnt 次方
// 才能将 n 放在 tail 的前面
while (cnt -- ) n *= 10;
int res = n + tail;
printf("%d\n", res);
return 0;
}
易错点分析：
题意：
分析与思路：
参考代码：
#include <stdio.h>
#include <string.h>
int n, k;
int a[1010];
int main()
{
scanf("%d%d", &n, &k);
int maxa = 0;
for (int i = 0; i < n; i ++ )
{
int x;
scanf("%d", &x);
if (x >= k) puts("hao! hen you jing shen!");
else puts("ni bu gou jing shen!");
if (x > maxa) maxa = x;
}
if (maxa >= k) printf("%d\n", maxa);
else puts("I am angry!");
return 0;
}
易错点分析：
题意：
分析与思路：
参考代码：
递归写法:
#include <stdio.h>
int T;
int n, m;
int get(int n, int m)
{
// 为了降低程序实现复杂度
// 不妨令 n <= m 恒成立
// 若 n > m 则返回 get(m,n)
if (n > m) return get(m, n);
// 当 n == m 时候，剩余区域为正方形
// 可以直接返回
if (n == m) return 4 * n;
else
{
// 当 n == 1 时
// 显然只需要用 m 个边长为 1 的正方形来覆盖剩余区域
if (n == 1) return 4 * m;
else return 4 * n + get(m - n, n);
}
}
int main()
{
scanf("%d", &T);
while (T -- )
{
scanf("%d%d", &n, &m);
printf("%d\n", get(n, m));
}
return 0;
}
循环写法:
#include <stdio.h>
int T;
int n, m;
int main()
{
scanf("%d", &T);
while (T -- )
{
scanf("%d%d", &n, &m);
int res = 0;
while (1)
{
// 不妨令 n <= m 恒成立
// 若 n > m 则交换 n 和 m
if (n > m)
{
int t = n;
n = m;
m = t;
}
if (n == m)
{
res += 4 * n;
break;
}
else
{
if (n == 1)
{
res += 4 * m;
break;
}
res += 4 * n;
// 请注意这里也需要一个临时变量
// 否则会 m 的值就会失真
int t = n;
n = m - n;
m = t;
}
}
printf("%d\n", res);
}
return 0;
}
易错点分析：
题意：
分析与思路：
参考代码：
#include <stdio.h>
int T;
int n;
int cnt[10];
int main()
{
scanf("%d", &T);
while (T -- )
{
// 一定要将 cnt[] 清零
// 否则会使用上一轮处理的数据
for (int i = 0; i < 10; i ++ ) cnt[i] = 0;
scanf("%d", &n);
for (int i = 0; i < n; i ++ )
{
int x;
scanf("%d", &x);
// 将 x 每一个数位计数
while (x)
{
cnt[x % 10] ++ ;
x /= 10;
}
}
// 找到出现最多的数
int maxa = 0;
for (int i = 0; i < 10; i ++ )
if (cnt[i] > maxa)
maxa = cnt[i];
int res = 0;
for (int i = 0; i < 10; i ++ )
if (cnt[i])
res += maxa - cnt[i];
printf("%d\n", res);
}
return 0;
}
易错点分析：
题意：
error和warning 。分析与思路：
error以及warning，若满足，则最后可以判断为存在题目要求的 x ，否则继续枚举。参考代码：
#include <stdio.h>
#include <string.h>
int T;
int n;
char s[1010], t[1010];
char e[] = "error", w[] = "warning";
int main()
{
scanf("%d", &T);
while (T -- )
{
int flag = 0;
memset(t, 0, sizeof t);
scanf("%d%s", &n, s);
for (int i = 0; i < 26; i ++ )
{
for (int j = 0; j < n; j ++ )
t[j] = (s[j] - 'a' + i) % 26 + 'a';
// 查看 t 中是否含有 e 和 w 这两个子串
if (strstr(t, e) == NULL && strstr(t, w) == NULL)
flag = 1;
}
if (flag) puts("0 error(s), 0 warning(s)");
else puts("Oops!");
}
return 0;
}
易错点分析：
error和warning。题意：
分析与思路：
参考代码：
#include <stdio.h>
// 怪物数量
int n;
// 每个怪物的初始血量、攻击力、出现时间
int mh[10010], ma[10010], mt[10010];
// 记录怪物是否已经出现
// 0 表示还未出现，1 表示已经出现
int st[10010];
int min(int a, int b)
{
return a > b ? b : a;
}
int main()
{
int h, ark, k, kh;
scanf("%d%d%d%d", &h, &ark, &k, &kh);
// MAX_H为一鸣学姐的血量上限
const int MAX_H = h;
scanf("%d", &n);
for (int i = 1; i <= n; i ++ )
{
scanf("%d%d%d", &mh[i], &ma[i], &mt[i]);
st[i] = 0;
}
// 记录上一次攻击的时间
int pret = 0;
for (int i = 1; i <= n; i ++ )
{
// 在活着的怪物中找到下一个出现的怪物
int t = -1;
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || mt[t] > mt[j]))
t = j;
// 若某个怪物在打上一个怪物被打死之前就出现
// 则阿枯城沦陷
if (pret > mt[t])
{
puts("My Milk!");
return 0;
}
// 表示该怪物已出现
st[t] = 1;
// 若停止攻击时间足够长
// 则恢复血量
// 但不能超过血量的上限MAX_H
if (mt[t] - pret >= k) h = min(MAX_H, h + kh);
// 打败当前怪物所需时间
// 注意是上取整
int time = (mh[t] + ark - 1) / ark;
// 在所需时间内一鸣学姐受到的伤害
int damage = time * ma[t];
// 若受到的伤害会使得一鸣学姐的血量降到 0 或以下
// 则阿枯城沦陷
if (damage >= h)
{
puts("My Milk!");
return 0;
}
// 更新一鸣学姐的血量
// 减去受到的伤害
h -= damage;
// 更新停止攻击的时间
// 即怪物出现时间加上战斗时间
pret = mt[t] + time;
}
puts("Mission Complete.");
return 0;
}
C++（使用了结构体和排序函数）：
#include<iostream>
#include<algorithm>
using namespace std;
//存放怪物信息的结构体
struct Monster
{
int h,ark,t;
};
Monster mon[3005];
//排序要用的排序函数
bool cmp(Monster m1,Monster m2)
{
return m1.t<m2.t;
}
int main()
{
int h,ark,k,kh;
int n;
cin>>h>>ark>>k>>kh;
cin>>n;
int ih=h;
for(int i=0;i<n;i++)
{
cin>>mon[i].h>>mon[i].ark>>mon[i].t;
}
sort(mon,mon+n,cmp);//将怪物按时间顺序进行排序
int pret=0;//前一个怪物被消灭时的时间
for(int i=0;i<n;i++)
{
if(mon[i].t<pret)//同时有两个怪物的情况
{
cout<<"My Milk!";
return 0;
}
if(mon[i].t-pret>=k)h=min(ih,h+kh);//防止超过血量上限
pret=mon[i].t;
while(mon[i].h>0)//模拟双方相互攻击
{
mon[i].h-=ark;
h-=mon[i].ark;
pret++;
}
if(h<=0)//一鸣师姐休眠的情况
{
cout<<"My Milk!";
return 0;
}
}
cout<<"Mission Complete.";
return 0;
}
易错点分析：
题意：
分析与思路：
D. 一鸣师姐与新生是类似的，都是遍历，维护最大值，最后围绕最大值进行处理，但不同点是这里的最大值指的是最长的含有不重复数字的连续子序列长度。而且这道题的数据量很大，要求在 O(n) 的时间复杂度之内求出每个 len[i] ，这就是整道题的瓶颈所在。参考代码：
#include <stdio.h>
#include <string.h>
int n, m;
int a[2010][2010];
int cnt[2010];
int res[2010];
int max(int a, int b)
{
return a > b ? a : b;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
scanf("%d", &a[i][j]);
int maxa = 0;
for (int i = 1; i <= n; i ++ )
{
memset(cnt, 0, sizeof cnt);
int t = 0;
for (int j = 1, k = 1; j <= m; j ++ )
{
cnt[a[i][j]] ++ ;
while (k <= j && cnt[a[i][j]] > 1) cnt[a[i][k]] -- , k ++ ;
t = max(t, j - k + 1);
}
res[i] = t;
maxa = max(maxa, t);
}
printf("%d\n", maxa);
for (int i = 1; i <= n; i ++ )
if (maxa == res[i])
{
printf("%d", i);
if (i == n) printf("\n");
else printf(" ");
}
return 0;
}
易错点分析：
题意：
分析与思路：
(， t 就加 1 ，遇到字符)， t 就减 1 ，这个序列是合法的，当且仅当 t 在任何时候都是非负的，且遍历结束后， t=0 。待消耗的左括号的数量、待消耗的右括号的数量、待消耗左括号的数量减去待消耗的右括号的数量。对于一个序列，若 d\geq 0 ，说明待消耗的左括号数量较多，若 d<0 ，说明待消耗的右括号数量较多。直观地想， d\geq 0 的序列放在 d<0 的序列的左边可能会更好，另外一个合法的括号序列 d 显然应该等于 0 。我们可以猜想需要找到一种排列方式，使得最终的括号序列 d 尽可能接近于 0 。(()))， d_1=-1 ，第二个序列为))(((， d_2=1 ，其中第一个序列有 1 个右括号待消耗，第二个序列有 3 个左括号以及 2 个右括号待消耗，总共有 6 个括号待消耗， 如果直接拼接，得到的序列为(()))))(((，这个序列有 3 个左括号， 3 个右括号待消耗，总共有 6 个括号待消耗。如果将第二个序列放在前面，则得到))((((()))，那么这个序列有 2 个左括号，以及 2 个右括号待消耗，总共有 4 个括号待消耗。可以看出第二种排列方式会比第一种更好，因为它需要额外的括号更少。基于以上分析，我们首先将 d \geq 0 的括号序列放在左边， d<0 的序列放在右边。)))((以及))(，其中 l_1=2,r_1=3,l_2=1,r_2=2 ，它们的 d 都为负，第一个序列有 2 个右括号以及 3 个左括号待消耗，第二个序列有 1 个左括号以及 2 个右括号待消耗，总共有 8 个括号待消耗。如果直接拼接，得到)))(())(，有 1 个左括号，以及 3 个右括号待消耗，总共有 4 个括号待消耗。如果将第二个序列放在前面，得到))()))((，则有 2 个左括号，以及 4 个右括号待消耗，总共有 6 个括号待消耗，因此情况变差了，不如不交换。基于以上分析，假如两个序列的 d 均为负，令 l 较大者放左边。))((()以及)(((，其中 l_1=2,r_1=2,l_2=3,r_2=1 ，它们的 d 都为非负数，第一个序列有 2 个左括号以及 2 右括号待消耗，第二个序列有 3 个左括号和 1 个右括号待消耗，总共有 8 个括号待消耗，如果直接拼接，得到))((())(((，有 4 个左括号和 2 个右括号待消耗，总共有 6 个括号待消耗。如果将第二个序列放在前面，得到)((())((()，则有 3 个左括号以及 1 个右括号待消耗，总共有 4 个括号待消耗，因此第二种情况会更好。基于以上分析，假如两个序列的 d 均为非负数，令 r 较小者放左边。参考代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 10010;
int n;
struct Seq
{
int l, r, d, id;
string s;
}seq[N];
// 自定义比较函数
bool cmp(Seq &a, Seq &b)
{
if (a.d >= 0 && b.d < 0 || a.d < 0 && b.d >= 0) return a.d >= 0;
else if (a.d >= 0) return a.r < b.r;
else return a.l > b.l;
}
// 检查是否为一个合法的括号序列
bool check()
{
int t = 0;
for (int i = 1; i <= n; i ++ )
{
t -= seq[i].r;
if (t < 0) return false;
t += seq[i].l;
}
return !t;
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ )
{
int l = 0, r = 0;
string str;
cin >> str;
// 计算待消耗的左括号和右括号
for (auto u : str)
if (u == '(') l ++ ;
else
{
if (l) l -- ;
else r ++ ;
}
seq[i] = {l, r, l - r, i, str};
}
sort(seq + 1, seq + 1 + n, cmp);
if (check())
{ // 如果是个合法序列，则输出一个排列
cout << "YES\n";
for (int i = 1; i <= n; i ++ ) cout << seq[i].id << ' ';
cout << '\n';
}
else cout << "NO\n";
return 0;
}
易错点分析：
嗯，正经的题解到这里也就结束了，下面就是整个 AK 杯的非官方碎碎念式总结了。
写完这篇题解感觉还是挺累的主要原因可能还是没睡好吧感觉分分钟猝死，虽然平时会给自己的练习写题解，也给刚入门的新生讲过课，但要将每一个算法的思路写得通俗易懂，尽可能地降低编程小白的阅读难度，我想还是有一定难度吧，所以这篇题解肯定还有值得完善的地方，如有错漏或任何疑问，请大家在评论中提出，我会第一时间解决。
AK 杯已经举办三届了，今年吸引了非软件学院的同学参加，并且取得了很好的成绩，很高兴看见 AK 杯越来越受欢迎，希望后浪们能够再接再厉吧。
至于比赛本身，个人认为题目的层次感挺强的，在作业题和算法题之间做了很好的过渡，对于能力在不同层次的新生来说，应该都能找到自己的定位。
前四题无论从难度还是类型都趋近于程序设计的作业题，对于熟悉基础语法的同学来说可以很愉快地过掉， A 题粗略计算平均过题时间在 2 分钟，我猜就是打开 IDE 新建一个项目的时间吧。 B 题通过率骤降，最主要是因为大部分同学大意没有考虑爆int的情况，其实用计算器算一下直接输出就好了呀。 C 题用暴力枚举和贪心的同学都不少，说明同学们有利用计算机解决问题的思维。 D 题考察循环的基本运用，如果没有做出来的话，应该多加练习，熟悉基本语法。
中期的 E 、F 、G 题，同学们大部分的时间应该都花在这三题上了，其实这三题涉及的知识仍然不难，只是从读懂题目到想到做法这个过程中有一定的思维要求。 E 题的贪心思路大部分提交的同学都能想到，但对于循环或递归的分析不足导致部分同学听取 WA 声一片。 F 题我们从开场就觉得比 E 简单，也不知为何最后只有 45 人过。 G 题的话，我认为是一道有些枯燥的题目，它的 idea 不够有趣，但为了看看新生们处理字符串和边界问题的能力，我还是将它放在了这里，也起到了想要的效果，可以看出部分同学在理解题意和设计算法时没有冷静分析细节，还有那句No response的回复我也等了好久 hh 。
最后三题，能够做出 H 题大模拟的同学，可以说明思维缜密且有一定的码力，在压力环境下想到各种可能性并不简单。至于 I 题，涉及的方法是比较直观的，如果之前见过类似算法或赛场上灵光一闪，至少是能够想到一个 O(n^2) 复杂度的算法，嗯对，比赛的时候数据出了问题，没有完全卡掉 O(n^2) 哇难受啊，正解从 O(n^2) 优化到 O(n) 也不是个刁钻的算法，当然原意还是准备给提前了解过一些简单算法的同学的。其实真正为了防 AK 的只有压轴的 J 题，涉及到的自定义排序以及贪心证明虽并不复杂，但其中包含的思维跳跃和证明方法对于新生来讲的确有较高难度。
为了了解新生的代码水平，大部分的代码都过了一遍，意外地发现同学们写代码的习惯都还不错，大多能利用空格、空行、缩进来整理代码，提高代码的可读性，这个真的要养成好习惯呀。还有同学不熟悉 OJ 、不熟悉 IDE 的使用，各种奇妙想法：样例过了就是过了， WA 了就是数据有问题！我这个程序怎么会超时，要不加点时间？ RE 了程序强行停止，我这软件好像出问题了怎么办呀？
好吧，就写到这里了，希望新生们在算法比赛初体验中有所收获，溜了溜了。