本次比赛共240名同学提交代码，其中238名同学通过1题以上，最高通过题数为7题，共一人。

写在前面

本次比赛面向19级新生，考察的知识点有：分支、循环、数组、排序、最大公约数。
题目考察的知识点较为简单，不涉及较难算法，更多得是考察19级新生的思维和逻辑能力。

题解

A题-盘古开天地

Problem Description

很久很久以前，天和地还没有分开，宇宙混沌一片。有个叫盘古的巨人，在这混沌之中，一直睡了一万八千年。
有一天，盘古突然醒了。他见周围一片漆黑，就抡起大斧头，朝眼前的黑暗猛劈过去。只听一声巨响，混沌一片的东西渐渐分开了。轻而清的东西，缓缓上升，变成了天；重而浊的东西，慢慢下降，变成了地。
天和地分开以后，盘古怕它们还会合在一起，就头顶着天，用脚使劲蹬着地。天每天升高一丈，盘古也随着越长越高。这样不知过多少年，天和地逐渐成形了，盘古也累得倒了下去。
盘古倒下后，他的身体发生了巨大的变化。他呼出的气息，变成了四季的风和飘动的云；他发出的声音，化作了隆隆的雷声。他的双眼变成了太阳和月亮；他的四肢，变成了大地上的东、西、南、北四极；他的肌肤，变成了辽阔的大地，他的血液，变成了奔流不息的江河，他的汗，变成了滋润万物的雨露......

Input

输入包含一个正整数N（1≤N≤100000000）

Output

输出一行。
当输入为1时，请输出盘古沉睡的年数，即18000
当输入为其他时，请输出0

Sample Input 1

1

Sample Output 1

18000

Sample Input 2

2

Sample Output 2

0

Hint

无

思路：

签到题

参考代码：

#include <stdio.h>
int main()
{
    int n;
    scanf("%d",&n);
    if(n==1)
        printf("18000");
    else
        printf("0");
    return 0;
}

易错点分析

1、只要学会了分支和熟悉SCNUOJ的输入输出之后，相信A、B题没有什么难度，是两道合格的签到题。

B题-猜拳

Problem Description

猜拳！你要赢，明白吗！用1代表剪刀，2代表石头，3代表布！电脑出什么，你就要输出对应赢的手势！什么，你不明白？石头赢剪刀，布赢石头，剪刀赢布！你一定要赢过电脑呀！

Input

输入1，2或3，代表对应的手势。

Output

输出1，2或3，表示能赢过输入的手势。

Sample Input 1

1

Sample Output 1

2

Hint

无

思路：

签到题。

参考代码：

#include<stdio.h>
int main()
{
    int a;
    scanf("%d",&a);
    printf("%d",(a%3)+1);
    return 0;
}

易错点分析

同A题。

C题-抢红包

Problem Description

背景

发红包是中国春节的传统习俗。每逢春节拜年，长辈都要将事先准备好的压岁钱以红包的形式分给晚辈，寓意好运连连。随着互联网的发展，电子红包逐渐代替了传统的纸质红包，微信红包逐渐成为了一种“新年俗”。

具体描述

每年春节，SLF都会在微信群上抢红包，赚得盆满钵满（那是不可能的），但也因为一直守在微信上抢红包，每年SLF都会被父母指责在饭桌上没有和亲戚朋友多聊天。这不，春节又到了，正当SLF为此而苦恼时，LWH找上门来了。
LWH自己用C语言写了一个自动抢红包的辅助工具，想为SLF解决烦恼，但条件是：
（1）SLF必须用5块钱买这个工具。
（2）SLF使用该工具抢红包时，一旦抢到的金额不小于10块钱，就必须分给LWH 1块钱。
但SLF觉得自己不划算，于是LWH又提出了另一种条件：
（1）SLF免费使用这个工具。
（2）SLF使用该工具抢红包时，一旦抢到的金额不小于5块钱，就必须分给LWH 1块钱。
于是SLF决定分别计算2种条件下必须给LWH的金额，并选择给LWH其中较少的金额，但是好景不长，与SLF多次抢同一红包的XZJ马上发现了蹊跷，并在SLF抢完第n个红包后举报了SLF，此后SLF的工具便失效。
由于SLF抽不出时间计算最终要给LWH的金额，便想请你帮忙设计一个程序完成这个任务。

Input

第1行，一个整数n（0<=n<=100）。
接下来n行，每行一个整数m，表示SLF使用工具抢到的金额。

Output

一个整数，表示SLF最终需要给LWH的金额。

Sample Input 1

3
7
3
15

Sample Output 1

2

Sample Input 2

6
9
5
6
7
8
5

Sample Output 2

5

Hint

无

思路：

1、设置2个变量记录2种条件下需要给出的金额，注意“记录条件1的变量”的初始值为5（表示花费5块钱购买辅助工具）。
2、因为抢红包是独立事件，事件之间互不影响，所以采用for循环结构处理每次抢红包操作。在每次循环中，若红包金额不小于10，则记录条件1的变量要加1（表示给出1块钱）；若红包金额不小于5，则记录条件2的变量要加1（表示给出1块钱）。
最后取这两个变量中的较小值输出即可。

参考代码：

#include<stdio.h>

int main()
{ 
    //n是红包个数，m是每次抢到的金额 
    int n,m;
    //输入红包个数 
    scanf("%d",&n);
    
    //sum1、sum2分别统计条件1、条件2下必须给出的总金额
    //sum1的初始值为5表示条件1下买辅助工具的花费 
    int sum1=5,sum2=0;
    //采用for循环获取每次抢红包操作 
    int i; 
    for(i=1;i<=n;i++)
    {
        //输入抢到金额 
        scanf("%d",&m);
        //判断条件1下红包是否满足要求 
        if(m>=10)
        {
            sum1=sum1+1;
        }
        //判断条件2下红包是否满足要求 
        if(m>=5)
        {
            sum2=sum2+1;    
        }   
    }   
    
    //输出2种条件下较小的金额 
    if(sum1>sum2){
        printf("%d",sum2);
    } 
    else
    {
        printf("%d",sum1);
    } 

    return 0;
} 

易错点分析

1、要注意条件1的sum1的初始值应该为5。
2、这两个条件的时间互为独立事件，所以应该是两条if语句判断。

D题-球魁

Problem Description

LWH十分喜欢打篮球，天天打球的他投篮百发百中，成为了南海校区的球魁，于是他开始嘲笑不会打球的LZH。为了捍卫自己的尊严，LZH进行了一个暑假的苦练，也达到了百发百中的投篮命中率，于是他向LWH挑战，一场球魁争夺赛开始了。
他们打算用罚球线投篮计分的方式一决胜负，规则如下：
①首先利用骰子的点数n来决定谁先投球，若是偶数，则LWH先投；若是奇数，则LZH先投。
②比赛分为r轮，一人投一轮，轮流投篮。(例如：若LWH先投，则第二轮LZH投，第三轮又轮到LWH投，依此类推，直至到第r轮结束)
③由于双方的投篮命中率都是百分百，所以每一轮他们都能投中，理论上投中一球得两分，但由于LWH受今年篮球世界杯中国男篮的影响，他每次投球都有一个心情值L，若L是素数，则他的得分仍为2分；特别地，当L为11时，他的得分变为3分；若L是合数，则他的得分变为1分，特别地，当L为15时，他的得分变为0分。而LZH忙着打算法比赛没看世界杯，所以不受影响（即每一球均为两分）。
现在，他们找你作为裁判为他们计分，并判断谁赢得比赛，而身为软工的大学生，你准备写个程序，让程序来算。

Input

第一行输入两个整数 r(1 <= r <= 2000) 和 n(1 <= n <= 6)，分别代表比赛的轮数和骰子的点数。
接下来输入一行，共 q 个正整数 L，用空格隔开。其中，q 代表 r 轮中 LWH 的轮数和，L 代表心情值(2 <= L <= 100)。
说明：
若轮到 LWH 投篮，则输入一个心情值 L；若轮到 LZH 投篮，则无需输入。
例如，当 r = 7, n = 2 时，q 为 4。因为 LWH 先发球，则轮到 LWH 投球的轮数有第一轮，第三轮，第五轮，第七轮，共四轮；

Output

输出一行，显示比赛结果：若是 LWH 赢，则输出 "lwh wins."；若是 LZH 赢，则输出 "lzh wins."；若是平局，则输出 "equal."
（说明：输出引号内的内容，不包括引号）

Sample Input 1

7 2
11 4 2 60

Sample Output 1

lwh wins.

Hint

无

思路：

1、根据总轮数r和骰子点数n来推算出q的数值，也就是LWH投的轮数。如果n为偶数q且r为奇数则q=r/2 + 1，其余情况为q=r/2。
2、每输入一个正整数L，判断L是否为11、15、素数、合数，然后加上相对应的分数。

参考代码：

#include<stdio.h>
#include<math.h>
int solve(int x){//返回11、15、素数、合数对应的分数
    if(x==11) return 3;
    if(x==15) return 0;
    if(x==2) return 2;
    for(int i = 2;i<sqrt(x)+0.5;++i){
        if(x%i==0) return 1;
    }
    return 2;
}
int main(){
    int r,n,q;
    int ans1,ans2;//ans1代表lwh分数，ans2代表lzh分数
    scanf("%d%d",&r,&n);
    if(n%2==0 && r%2==1)//判断q的值
        q = r/2 + 1;
    else
        q = r/2;
    ans1 = 0; ans2 = (r-q)*2;//求出lzh对应的分数
    for(int i = 0;i<q;++i){
        int L;
        scanf("%d",&L);
        ans1+=solve(L);
    }
    if(ans1==ans2)     printf("equal.");
    else if(ans1>ans2) printf("lwh wins.");
    else               printf("lzh wins.");
}

易错点分析

1、要先判断q的值才能正确输入，否则会造成RE或者WA。
2、判断L对应的分数最好写成函数，这样代码结构清晰。如果写在循环里面的话要处理好每次得到分数之后要及时continue因为11也对应素数、15也对应合数。
3、这道题输入方式比较特殊，考察了选手们对于题意的理解和输入格式的灵活变换。
4、这道题提交次数最多但AC率较前三道题有明显得下降，说明这道题很好得起到了选拔的作用。

E题-性质判断

Problem Description

化学家 PP 在 9102 年发现可以将所有有机物用 26 个小写英文字母构成的字符串表示。并且，各种有机物对应的字符串中 aa, bb, cc, …, zz（从 a 到 z，共 26 种小写英文字母）出现的次数会反映出有机物的性质。然而，PP 并不需要具体的次数，只需要根据 aa, bb, cc, …, zz 在字符串中的出现次数将 aa, bb, cc, …, zz 排好序，PP 就可以判断有机物的性质，你能帮她将 aa, bb, cc, …, zz 排好序吗？

Input

输入为一行仅由小写英文字母构成的字符串，长度大于等于 1 且小于等于 5000。

Output

输出为一行，按 aa, bb, cc, …, zz 在字符串中的出现次数（计算出现次数时是可重叠的，即在字符串 "aaaa" 中，aa 出现了三次），从多到少，将 aa, bb, cc, …, zz 排序，不同字母间以一个空格隔开，忽略行末空格。（出现次数相同，则按照字典序升序排列，如 dd, ee 都出现 1 次，则 dd 放在 ee 前面）出现次数为 0 的不用输出。（如果 aa, bb, cc, …, zz 都没有出现过，则什么都不用输出）

Sample Input 1

bbaaqccc

Sample Output 1

cc aa bb

Hint

无

思路：

1、由于匹配得是aa、bb、cc等模式串，所以只需在循环里判断当前字符和后一个字符是否相等，需要特判一下轮到最后一个字符时不需要判断。
2、判断相等后用数组存储对应模式串的个数，然后对这个数组进行排序即可。
3、注意：排序的时候使用选择排序会较好，因为使用冒泡排序或者其他排序的话需要使用结构体。

参考代码：

#include<stdio.h>
#include<string.h>
char str[5005];//主串
int num[26]={0};//储存26个模式串的出现次数
int main()
{
    scanf("%s",str);
    int len=strlen(str);//主串长度
    int i,j;
    for(i=0;i<len-1;i++)
    {
        if(str[i]==str[i+1])
        {
            num[str[i]-'a']++;//当匹配成功时，对应的位置次数加1
        }
    }
    int maxx,maxid;
    for(i=0;i<26;i++)//由于最多在26个模式串排序，时间不长，选择简单的选择排序
    {
        maxx=0;
        for(j=0;j<26;j++)
        {
            if(num[j]>maxx)
            {
                maxx=num[j];
                maxid=j;//这趟排序最大数字对应的下标
            }
        }
        if(maxx==0)break;//出现次数都为0则跳出
        if(i!=0)printf(" ");
        printf("%c%c",maxid+'a',maxid+'a');
        num[maxid]=0;//每一趟将选出下标对应的数字清零
    }
    return 0;
}

易错点分析

1、考察了数组、字符串模拟、排序。
2、这道题因为匹配得是aa、bb、cc等模式串，所以开一个26长度的标记数组，则str[i]-'a'即使对应的下标，这也是常用的技巧。
3、此外，排序也需要多加注意，如果使用结构体，这道题在排序上不容易犯错。但如果没有使用结构体，最佳的方法就是选择排序，因为好写且简单。
4、这道题也是进入一等奖区的选拔题目，其实题目难度上不算难但许多选手缺乏比赛解题技巧，写代码容易将自己给绕进去。

F题-Matrix

Problem Description

Veggie 最近深深地迷恋上了 Matrix，现在他手上有一个 N × N 的矩阵，矩阵中的元素都是数字，他希望可以从不同角度欣赏矩阵之美。但是 Veggie 道行尚浅，只能请求好友 SLF 帮他完成对矩阵的变换，矩阵的变换法则如下：
法则 1：将矩阵顺时针旋转 90 度，例如：

1 2 3         7 4 1
4 5 6    →    8 5 2
7 8 9         9 6 3

法则 2：将矩阵逆时针旋转 90 度，例如：

1 2 3         3 6 9
4 5 6    →    2 5 8
7 8 9         1 4 7 

法则 3：矩阵的中央元素不变，将其他元素与 "以中央元素为中心对称的元素" 互换，例如：

1 2 3        9 8 7
4 5 6    →   6 5 4
7 8 9        3 2 1

不料 SLF 二话不说把这个差事安排给了你，现在请你编程帮 Veggie 完成矩阵的变换。

Input

第一行输入正整数 N（N 为奇数，且1 ≤ N ≤ 25）和 M(0 ≤ M ≤ 20) 中间以空格隔开，其中 N 如题目，M 表示矩阵变换的次数。
接下来 N 行，每行输入 N 个在 int 类型范围内的整数，中间以空格隔开，表示矩阵的各元素。
最后 M 行，每行输入一个整数 t(1 ≤ t ≤ 3)，表示要进行变换的法则编号。

Output

输出每次变换后的矩阵，每次输出完需要多打印一个空行。（详情可以参照输出样例 1）
注意：每输入一个变换法则编号，视为一次变换
注意：行末多余空格会影响正确答案！

Sample Input 1

3 2
1 2 3
4 5 6
7 8 9
2
3

Sample Output 1

3 6 9
2 5 8
1 4 7

7 4 1
8 5 2
9 6 3

Hint

无

思路：

1、推出每个变换规则对应的规律,其中(matrix代表变换后数组，temp代表原来数组):
法则一：matrix[j][n-i+1]=temp[i][j]
法则二：matrix[n-j+1][i]=temp[i][j]
法则三：matrix[n-i+1][n-j+1]=temp[i][j]
2、判断输入数字然后进行对应转换即可。

参考代码：

#include<stdio.h>
#include <string.h>
int main(){
    int matrix[30][30],temp[30][30];
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i = 1;i<=n;++i)
        for(int j = 1;j<=n;++j)
            scanf("%d",&matrix[i][j]);
    for(int k = 1;k<=m;++k){
        int x;
        scanf("%d",&x);
        memcpy(temp,matrix,sizeof(matrix));//复制函数：将matrix数组内容复制到temp数组中
        for(int i = 1;i<=n;++i){
            for(int j = 1;j<=n;++j){
                switch(x){
                    case 1:
                        matrix[j][n-i+1] = temp[i][j];//法则1
                        break;
                    case 2:
                        matrix[n-j+1][i] = temp[i][j];//法则2
                        break;
                    case 3:
                        matrix[n-i+1][n-j+1] = temp[i][j];//法则3
                        break;
                }
            }
        }
        for(int i = 1;i<=n;++i){
            for(int j = 1;j<=n;++j){
                printf("%d",matrix[i][j]);//输出
                if(j!=n) printf(" ");//注意:最后一个数字后面不要带空格
            }
            printf("\n");
        }
        printf("\n");
    }
    return 0;
}

易错点分析

1、考察了二维数组、规律演算。
2、只要推出了对应的规律之后，这道题代码就相当简单。
3、如果直接暴力模拟也可以，但是代码较长且容易出错。

G题-简单的RC签到题

Problem Description

给定素数a,b,c,d,求1到n中的整数中至少能整除这4个元素中的一个的数有几个？

Input

输入两行：
第一行为一个整数n（1≤n≤1e18）
第二行为四个数a,b,c,d（abc*d＜1e18，数据保证a,b,c,d为互不相同的素数）

Output

仅一行，输出答案即可。

Sample Input 1

1000
2 13 17 41

Sample Output 1

575

Hint

无

思路：

1、考虑数据范围最大到1e18，暴力枚举会超时，所以要用容斥原理。
2、将分别整除a，b，c，d的数分为四个集合，设为A，B，C，D，我们的目标就是求A∪B∪C∪D，所以用以下公式求解:

image.png

3、所以有：A∪B∪C∪D=A+B+C+D-AB-AC-AD-BC-BD-CD+ABC+ABD+ACD+BCD-ABCD
因为A，B，C，D都是素数，所以A=n/a，……，ABCD=n/(a*b*c*d)，代入求解即可。

参考代码：

#include <stdio.h>
int main(){
    long long n;
    scanf("%lld",&n);
    long long a,b,c,d,ans = 0;
    scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
    ans += n/a + n/b + n/c + n/d;
    ans -= n/(a*b) + n/(a*c) + n/(a*d) + n/(b*c) + n/(b*d) + n/(c*d);
    ans += n/(a*b*c) + n/(a*b*d) + n/(a*c*d) + n/(b*c*d);
    ans -= n/(a*b*c*d);
    printf("%lld",ans);
    return 0;
}

易错点分析

1、很多同学没有注意到数据范围，直接暴力枚举，导致超时。
2、在写容斥的时候容易漏掉一些情况，例如少了abc、abd等等。
3、容斥公式是奇数项相加、偶数项相减。

H题-强迫症患者

Problem Description

cgy是一个很有强迫症的人，他一看到小数就浑身难受。然而有一天，他碰到了这么一条只有整数和除号构成的式子：1/2/4/16，他的强迫症又来了，加上了括号让式子变成了 （1/2）/（4/16）=2把它变成了整数。但是走着走着，他又碰到了一个墙上写满了这个风格的式子，cgy突然发现有些式子可以通过加括号来让结果变为整数，有些却不行。但是他手边没有纸和笔，于是就没有把这个想法写下来，现在你能通过这一系列数字来判断他们是否可以通过加括号变成整数么?

Input

一个整数n(n<=100)表示有几组数据
接下来输入m(1<=m<=10000)表示有m个数字，再下去一行输入m个正整数(每个数字不大于100000），表示式子中的数字。

Output

对于每一行输入，如果可以通过加括号变成整数就输出Yes，否则输出No。

Sample Input 1

3
3
1 2 4
4
1 5 6 9
4
1 4 2 2

Sample Output 1

Yes
No
Yes

Hint

对于样例一中的第一组数据:1/2/4 → 1/(2/4) = 2，Yes。
第二组数据:1/5/6/9不能通过加括号转化成整数，No。
第三组数据:1/4/2/2 → 1/((4/2)/2) = 1，Yes。

思路：

1、在除法表达式X1/X2/X3/.../Xk里，我们可以知道第一个数字一定是分子，第二个数字一定是分母。
2、其他数字我们可以通过添加括号使得它们成为分子或者分母，既然要求整除，所以让它们成为分子更好，因为这样就可以尽可能得整除分母(也就是第二个数字)。
3、所以我们只需判断X1*X3*...*Xk是否整除X2即可。
4、考虑到最多有(1e4 - 1)个不大于1e5数字的相乘，这样会爆掉longlong的存储范围，所以我们考虑可以让当前分母除于每个分子与它的最大公约数gcd，只要最后分母为1就表示可以整除。
5、最后需要注意一点就是需要特判m==1的情况，如果m为1就直接输出"Yes"。

参考代码：

#include <stdio.h>
int gcd(int x,int y){//求最大公约数gcd
    return y==0?x:gcd(y,x%y);
}
int main(){
    int n,m;
    scanf("%d",&n);
    while(n--){
        int x,x2;
        scanf("%d",&m);
        if(m==1){//特判m==1的情况
            scanf("%d",&x);
            printf("Yes\n");
            continue;
        }
        scanf("%d%d",&x,&x2);
        x2 /= gcd(x,x2);//x2除于gcd(x,x2)
        for(int i = 2;i<m;++i){
            scanf("%d",&x);
            x2 /= gcd(x,x2);//x2不断除于gcd(x,x2)
        }
        if(x2==1) printf("Yes\n");//x2==1表明最后式子能够整除
        else      printf("No\n");
    }
    return 0;
}

易错点分析

1、有的同学已经想出整除表达式可以使得X2作为分母，其它数字相乘作为分母了，但是没有考虑到其他数字相乘会爆掉longlong，痛失AK的机会。//手动滑稽
2、这道题加了一个Hack：m==1，这个需要特判一下，不然会WA或者RE。
3、这道题加强了数据，所以用JAVA大数或者Python暴力相乘会TLE。

写到最后：

1、特别感谢CGY来监赛和讲题解。//边缘ob的感觉真好hhh
2、这次AK杯比赛的结果我们还是比较满意的，结果也基本符合我们之前的预期。
排名的梯度比较明显，也可能是因为今年题目变多了，大家选择的余地会大一点。
3、可惜rjl只差一点点就能完成AK成就，看来明年比赛名应该要改成《不能AK的AK杯》hhh。