华南师范大学软件学院第三届 AK 杯于 2020 年 10 月 25 日成功举行，有效参赛人数为 $435$ ，共有 $433$ 人通过 $1$ 题或以上。

本次比赛面向 20 级新生，考察的方向偏思维和逻辑，不涉及复杂算法，具体包括：各种数据类型的读入和输出、基本算术运算、分支和循环、数组的基本使用、字符和字符串的简单处理、排序、贪心等。

A. 一鸣师兄女装

完整题面

题意：

• 给定一个字符串，输出这个字符串。

分析与思路：

• 读入字符串并输出即可。

参考代码：

#include <stdio.h>

int main()
{
    puts("yiming shixiong nvzhuang");
    return 0;
}

易错点分析：

• 极少数同学做错是因为自己输入字符串而输错了。

B. 一鸣师姐的粤语课

完整题面

题意：

• 给定若干个数，按要求的格式输出它们的和与积。

分析与思路：

• 计算所有数相加和相乘的结果输出即可，但相乘的结果较大，如果用 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 但在计算过程中没有进行数据类型的强制转换。
• 没有按题目要求的格式输出。

C. 一鸣师姐的作业题

完整题面

题意：

• 输入一个 $n$ ，找到一个最小的正整数 $x$ 使得 $x$ 每个数位上的数字之和等于 $n$

分析与思路：

• 首先看到 $n$ 的大小最大为 $25$ ，是比较小的，同时可以想到 $999$ 的数位和已经达到 $27$ ，因此要找的 $x$ 一定在 $1000$ 以内，可以用暴力的方法来做，只需要从 $1$ 开始枚举，对于每个数求出数位上的和，若和为 $n$ ，输出并结束程序。
• 如果 $n$ 较大，用以上暴力枚举的做法将会超时，其实本题还有更优的方法。可以发现一个数位上的数能为数位和贡献的最大值为 $9$ ，为了使得找到的数尽量小，可以从低位往高位放置若干个 $9$ 直到剩余的和小于或等于 $9$ ，再将这个数放到最高位即可。

参考代码：

暴力枚举:

#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;
}

易错点分析：

• 对拆解数位的方法不熟悉。
• 想到贪心的思路，但仅仅只是考虑了结果为两位数的情况，不少同学的出错代码是因为样例 $n=19$ ，也就是结果为三位数的时候出错。

D. 一鸣师姐与新生

完整题面

题意：

• 给定 $n$ 个数及一个正整数 $k$ ，判断 $n$ 个数是否大于或等于 $k$ ，最后判断 $n$ 个数中是否有大于或等于 $k$ 的数。

分析与思路：

• 只需要遍历所有数，对于每个数判断它是否大于或等于 $k$ ，并在遍历过程中维护整个数列的最大值。

参考代码：

#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;
}

易错点分析：

• 粗心大意，在判断时使用大于而不是大于等于。
• 维护最大值不够熟悉，见到许多奇怪的方式，而且还错了。

E. 一鸣师姐种田

完整题面

题意：

• 给定一个 $n\times m$ 的矩形区域，选择若干正方形覆盖这个区域，其中正方形不能互相重叠，也不能覆盖矩形区域外的部分。每个正方形的花费是它的周长，要求使得花费最小，求这个最小花费是多少。

分析与思路：

• 对于剩余需要覆盖的区域，用当前可以选择的最大的正方形紧贴矩形区域的最小三条边进行覆盖，直到全部区域都被覆盖为止。
• 这里给出证明：假设 $S$ 为需要覆盖的区域面积， $cost$ 为花费， $k_i$ 为其中一个正方形的边长，那么就可以列出关系： $\frac{S}{cost}=\frac{k_1^2+k_2^2+\dots+k_c^2}{4k_1+4k_2+\dots+4k_c}$ ，其中 $c$ 为覆盖整个区域所需的正方形个数， $S$ 不变，要使得 $cost$ 尽量小，那么就要令式子右边部分尽量大，而且可以发现分子部分增速会比分母快，但每个 $k_i$ 都并不是可以无限大的，因此不妨令每个 $k_i$ 尽可能地大，整个计算过程就是令 $k_1$ 尽量大，确定 $k_1$ ，令 $k_2$ 尽量大，确定 $k_2$ ，以此类推，直到 $k_1^2+k_2^2+\dots+k_c^2=S$ 为止。

参考代码：

递归写法:

#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;
}

易错点分析：

• 没有找到程序结束的出口，导致超时或运行时错误。

F. 一鸣师姐买糖果

完整题面

题意：

• 给定 $n$ 个数，统计所有数的数位出现的次数，找到出现最多的次数，求出这个最多次数与所有出现过的数的差值之和。

分析与思路：

• 用一个大小为 $10$ 的数组 $cnt$ ，其中 $cnt[i]$ 表示数字 $i$ 出现的次数。
• 遍历所有数，对于每个数，将数位进行拆解，同时对出现的数进行计数。
• 最后找到 $cnt$ 数组的最大值 $maxa$ ，最后遍历 $cnt$ 数组，若 $cnt[i] > 0$ 则累加 $maxa-cnt[i]$ 。

参考代码：

#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;
}

易错点分析：

• 处理多组数据，每次处理时没有对变量初始化，用到的是上一次处理留下来的数据。
• 不熟悉数位拆解的方法，或暴力拆解时代码写得比较冗长且出错。

G. 一鸣师姐的期望

完整题面

题意：

• 给定一个字符串 $s$ ，判断是否存在一个非负整数 $x$ ，使得 $s$ 中每一个字符加上 $x$ 形成的新字符串中，不含有error和warning 。

分析与思路：

• 按照题目的规定， $x$ 取 $0$ 和 取 $26$ 是一样的，取 $1$ 和 取 $27$ 是一样的，以此类推，可以发现只需要考虑 $0\leq x \leq 25$ 即可。
• 因此在 $[0,25]$ 范围中枚举 $x$ ，对于每个 $x$ ，构造一个新的字符串，在新的字符串中检查是否不存在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;
}

易错点分析：

• 不理解题意中的是否存在，错认为需要保证对于每个 $x$ 构成的字符串都不含有error和warning。
• 不熟悉字符串库函数的使用方法，导致代码冗长，出现错位、访问越界等错误。

H. 一鸣师姐与阿枯城

完整题面

题意：

• 请直接看题面，因为是模拟题，所以题意就是题面了。

分析与思路：

• 所谓模拟题，就是对题意直接进行模拟，就能得到正确的程序过程，从而得到正确的答案。所以接下来只会讨论模拟实现中的某些过程的实现思路和同学们在答题中出现的某些错误。
• 由于怪物有各自的出现时间，所以我们在模拟的时候要根据怪物出现的时间来安排怪物出现的顺序。对于会使用排序的同学来说，可以用排序来解决这问题。对于还未学过排序的同学来说，可以使用每次选取最小值的方式来选择还未出现的怪物中时间最小的那个，同时用一个数组标记每个怪物是否已经出现。
• 此外对于未使用排序的同学来说，可以用一个额外变量来存储消灭上一个怪物后的时间，然后就可以将这个变量与当前怪物出现的时间做对比，来得出一鸣师姐的血量是否要进行恢复操作。

参考代码：

#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;
}

易错点分析：

• 在同学们的解答过程中，没有看清题面，遗漏或误会以下细节：
  • 并未说怪物的出现时间是按顺序的；
  • 每隔一秒攻击一次，不是只攻击一次；
  • 一鸣师姐休眠后阿枯城就沦陷了，并未要求考虑敌人的情况；
  • 一鸣师姐的增加血量在下轮攻击开始前只会增加一次血量，增加后的值不会超过一鸣师姐在一开始的血量。
• 模拟过程的实现有问题，有些过程即使满足条件也不一定会执行，请仔细检查。
• 打败一个怪物所需的时间应当是这个怪物的血量除以一鸣学姐的攻击力上取整，提供程序中的实现方式以及数学证明作为参考。
• 边界情况没有考虑充分。
• 部分代码超时主要是两个原因，一是写错程序，未考虑清楚跳出条件，导致有死循环的可能性；二是时间复杂度太高，对数量级为 $3000$ 的嵌套循环，最多套两层就够了。

I. 一鸣师姐的投资计划

完整题面

题意：

• 给定 $n$ 个长度为 $m$ 的数列，对于第 $i$ 个数列，求出这个数列最长的含有不重复数字的连续子序列长度，记为 $len[i]$ ，找到 $len$ 数组中的最大值 $maxa$ ，按从小到大的顺序输出所有满足 $len[i]=maxa$ 的 $i$ 。

分析与思路：

• 这道题整体的思路和D. 一鸣师姐与新生是类似的，都是遍历，维护最大值，最后围绕最大值进行处理，但不同点是这里的最大值指的是最长的含有不重复数字的连续子序列长度。而且这道题的数据量很大，要求在 $O(n)$ 的时间复杂度之内求出每个 $len[i]$ ，这就是整道题的瓶颈所在。
• 基于以上分析，实际上需要使用一个叫双指针的算法，在本题的应用也叫滑动窗口。这个算法可以通过控制两个指针变量（注：此指针非C语言所指的指针，只是一个称呼）在一段数列中移动，维护这两个变量之间的数具有的一些性质，本题中两个指针变量维护的区间就具有区间内所有数不重复出现的性质。
• 具体的实现方法如下：现有一个数列 $a$ ，下标从 $0$ 开始，长度为 $m$ ，定义两个变量 $i=0$ ， $j=0$ ，我们需要维护的区间就是 $[j,i]$ 。再定义一个数组 $cnt$ ，假设 $x$ 为区间内的某一个数，其中 $cnt[x]$ 表示当前区间内 $x$ 的个数。循环的每一次， $i$ 都往前走一步，显然当前区间多了一个数 $a[i]$ ，此时要将 $cnt[a[i]]$ 加 $1$ ，接着如果 $cnt[a[i]] > 1$ ，说明区间 $[j,i]$ 内 $a[i]$ 出现超过了 $1$ 次，于是要将 $j$ 也往前走，每次往前走之前，注意要将当前的 $cnt[a[j]]$ 减 $1$ ，一直往前走，直到使得 $cnt[a[i]]$ 等于 $1$ 为止，此时区间 $[j,i]$ 重新满足了区间内所有数不重复出现的性质，用区间长度 $j-i+1$ 更新最大值即可。 如果发现以上分析看不懂，没关系，结合代码食用，并在纸上手写模拟一下样例，慢慢理解。

参考代码：

#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;
}

易错点分析：

• 使用了 $O(n^2)$ 时间复杂度的暴力算法，导致超时。
• 想到双指针的思路，但维护区间时边界细节处理出错。

J. 一鸣师姐与括号序列

完整题面

题意：

• 给定若干个括号序列，判断是否能将这些序列拼接成一个括号序列，使得这个序列是一个合法的括号序列。合法的定义请看完整题面。

分析与思路：

• 首先要看懂什么是合法的括号序列，然后将合法括号序列的判断过程转换为程序语言。对于任意一个括号序列，定义一个变量 $t$ ，从头遍历这个括号序列，遇到字符(， $t$ 就加 $1$ ，遇到字符)， $t$ 就减 $1$ ，这个序列是合法的，当且仅当 $t$ 在任何时候都是非负的，且遍历结束后， $t=0$ 。
• 对于本题而言，我们对给定的每个括号序列定义三个值 $l,r,d$ ，分别表示这个序列中待消耗的左括号的数量、待消耗的右括号的数量、待消耗左括号的数量减去待消耗的右括号的数量。对于一个序列，若 $d\geq 0$ ，说明待消耗的左括号数量较多，若 $d<0$ ，说明待消耗的右括号数量较多。直观地想， $d\geq 0$ 的序列放在 $d<0$ 的序列的左边可能会更好，另外一个合法的括号序列 $d$ 显然应该等于 $0$ 。我们可以猜想需要找到一种排列方式，使得最终的括号序列 $d$ 尽可能接近于 $0$ 。
• 假设现在有两个括号序列，其中 $d_1< 0$ ， $d_2\geq 0$ ，那么将第二个序列放在第一个之前，并不会令整个序列的情况变差。举个例子，设第一个序列为(()))， $d_1=-1$ ，第二个序列为))(((， $d_2=1$ ，其中第一个序列有 $1$ 个右括号待消耗，第二个序列有 $3$ 个左括号以及 $2$ 个右括号待消耗，总共有 $6$ 个括号待消耗， 如果直接拼接，得到的序列为(()))))(((，这个序列有 $3$ 个左括号， $3$ 个右括号待消耗，总共有 $6$ 个括号待消耗。如果将第二个序列放在前面，则得到))((((()))，那么这个序列有 $2$ 个左括号，以及 $2$ 个右括号待消耗，总共有 $4$ 个括号待消耗。可以看出第二种排列方式会比第一种更好，因为它需要额外的括号更少。基于以上分析，我们首先将 $d \geq 0$ 的括号序列放在左边， $d<0$ 的序列放在右边。
• 好了，如果两个括号序列的 $d$ 值同时为非负或同时为负，怎么排列会更好呢？我们同样用上面的方法来分析。
  • 先分析同时为负的情况。假设有两个括号序列)))((以及))(，其中 $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$ 较小者放左边。
• 总结以上的过程，排序时将 $d\geq 0$ 的放左边一堆， $d<0$ 的放右边一堆，然后分别再排序，左边的一堆里， $r$ 较小的放左边，右边一堆里， $l$ 较大的放左边。形成一个长括号序列，用一开始说的方法验证它是否为一个合法的括号序列。
• 以上算法叫贪心算法，使用的分析和证明方法叫邻值交换法。由于篇幅有限，分析过程中举的例子只是其中一两种情况，同学们可以思考更多例子，验证以上证明，并搜寻资料深入学习。
• 回到这道题中，如果能够形成一个合法序列，则最后输出一个排列，表示其中一组解的序号，因此可以在读入时给所有序列记录一个序号 $id$ ，排序处理结束后，从头输出每个序列的 $id$ 即可。

参考代码：

#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 了程序强行停止，我这软件好像出问题了怎么办呀？

好吧，就写到这里了，希望新生们在算法比赛初体验中有所收获，溜了溜了。