2019 SWUST ACM Final招新赛题解

2019 SWUST ACM Final招新赛题解

由于种种原因,这场比赛的题目质量还是有些问题,不过比上一次好了许多。。。


A 喜欢奇的肖姐姐

Description

肖姐姐喜欢吃鸡,他第一个星期在寝室偷偷养了一只鸡(室友并不知道),过了n个星期,漂亮的姚涵学姐发现肖姐姐在偷偷在寝室养鸡,但是这个时候这只鸡已经生了很多的蛋并且这只鸡居然被肖姐姐吃了(居然还没有分给室友),由于肖姐姐有点不好意思,于是她把蛋平均分给了寝室的四个人(包括自己),但是达妹发现这些蛋不一定会平均分给每个人,于是经过大家的讨论决定最后剩下几个蛋就让肖姐姐唱几首歌(谁叫肖姐姐要偷偷养鸡呢)。

Input

输入两个整数m,n(2<=m,n<=1e9+7),表示生的蛋是\(m^n\)个,其中n保证为偶数。

Output

输出一个整数,表示小姐姐的唱歌数

Sample Input

1
2 2

Sample Output

1
0

思路

找规律 奇数的偶次方%4==1,偶数的偶次方%4==0

代码

1
2
3
4
5
6
7
#include <stdio.h>
int main(void){
int n, m;
scanf("%d %d",&m,&n);
printf("%d\n",m%2);
return 0;
}

B 神犇的终极防AK题2

Description

在ACM国庆招新赛中

通过神犇的终极防AK题

相信各位都会求一个数组里面的第二大值了

姚涵学姐现在不想知道第二大值

但是她想知道n个数字里面第三大的值是多少,你能帮她找出来吗??

注意:本题只能使用纯C语言提交

Input

第一行输入一个数字\(n(3 \leq n \leq 10^7)\)

第二行一共n个数字\(a_1, a_2 ... a_n\),用空格隔开\((0 \leq a_i \leq 2*10^7)\)

输入数据保证n个数字没有重复的。

Output

输出这n个数字中第三大的值

Sample Input

1
2
3
4
5
3
3 2 1

4
6 7 8 9

Sample Output

1
2
3
1

7

思路

这个题我们直接用三个变量存一下输入每个数字时的前三大的数然后输出就行了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
int main(void){
int n,temp;
int Fir = 0,Sec = 0,Thi = 0;
scanf("%d",&n);
for(int i = 1;i <= n;i++){
scanf("%d",&temp);
if(temp > Fir){
Thi = Sec;
Sec = Fir;
Fir = temp;
}else if(temp > Sec){
Thi = Sec;
Sec = temp;
}else if(temp > Thi)
Thi = temp;
}
printf("%d\n",Thi);
return 0;
}

C 假如室友欺骗了你?

Description

作为东6B-204的两大奥斯卡得主张荣鑫以及罗应华,他们为了防止对方学习每天都上演着年度大戏,花式表演“颓狗“。一天张荣鑫为了知道罗应华是否欺骗了他,他问了罗应华看B站,打球,撩学妹花的时间。分别是a,b,c分钟,又让蔡洪浩去问罗应华看B站,打球,撩学妹花的时间。得到了分别为d,e,f分钟。如果a=d,b=e,c=f那么就输出"good man" 否则输出"cnm !!!"。

保证0<=(a,b,c,d,e,f)<1000000000000。

请你输出结果。

Input

第一行输入a,b,c

第二行输入d,e,f

Output

输出结果

Sample Input

1
2
3
4
5
1 2 3
1 2 3

1 2 1
1 2 0

Sample Output

1
2
3
good man

cnm !!!

思路

这个题题意已经很明显了,如果a = d,b = e,c = f,那么就输出“good man”,否则就输出“cnm !!!”。

代码

1
2
3
4
5
6
7
8
9
10
#include <stdio.h>
int main(void){
int a,b,c,d,e,f;
scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f);
if(a==d&&b==e&&c==f)
printf("good man\n");
else
printf("cnm !!!");
return 0;
}

D 达数

Description

达妹特别喜欢玩数字,同时作为数学家的达妹,定义了一种数字叫做达数

定义如下:

  1. 这个数字只能由有限个"1", "14", "114"直接组合而成(一定要连续的"1", "14", "114")
  2. 这个数字除了"1", "14", "114"以外没有别的数字。

例如:"14114", "141414"和"1411"是达数但是"1444", "514"和"414"并不是。

现在达妹手上有一个数字,达妹不知道这个数字是不是达数。

你能够帮助达妹判断这个数字是否是达数?

Input

一个数字\(n(1 \leq n \leq 10^9)\),这个数字不包含前导零

Output

如果这个数字是达数,输出"YES"(不包括双引号)

否则输出"NO"(不包括双引号)

Sample Input

1
2
3
114114
1111
441231

Sample Output

1
2
3
YES
YES
NO

思路

这个题我们直接从第一位开始遍历数字的每一位,如果遇到不是‘1’或‘4’那么我们直接输出“NO”,如果遇到一个‘4’,我们就判断一下这一位的前一位是不是‘1’,不是的话就输出“NO”,如果没有满足不是达数的位数那么我们最后输出“YES”就行了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <stdio.h>
#include <string.h>
int main(void){
char ch[100];
scanf("%s",ch);
bool mark = true;
int len = strlen(ch);
for(int i=0;i<len;i++){
if(ch[0]!='1'){
mark = false;
break;
}
if(ch[i]!='1'&&ch[i]!='4'){
mark = false;
break;
}
if(ch[i]=='4'&&ch[i-1]!='1'){
mark = false;
break;
}
}
if(mark)
printf("YES\n");
else
printf("NO\n");
return 0;
}

E Function

Description

对于一个递归函数w(a,b,c)w(a,b,c)

  • 如果a<=0 or b<=0 or c<=0,就返回值1。
  • 如果a > 20 or b > 20 or c>20,就返回w(20,20,20)。
  • 如果a<b并且b<c就返回w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c)。
  • 其它的情况就返回w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1)。

这是个简单的递归函数,但实现起来可能会有些问题。当a,b,c均为15时,调用的次数将非常的多。你要想个办法才行。

/*

比如w(30,-1,0)既满足条件1又满足条件2

这种时候我们就按最上面的条件来算

所以答案为1

*/

Input

保证输入的数在[-9223372036854775808,9223372036854775807]之间,并且是整数。

Output

输出若干行,每一行格式:

w(1, 1, 1) = 2

注意空格。

Sample Input

1
2
1 1 1
2 2 2

Sample Output

1
2
w(1, 1, 1) = 2
w(2, 2, 2) = 4

思路

题目明确给出递归条件和方法,我们先根据题目写出标准的递归程序,但明显会超时,因为递归次数太多了。我们发现在递归过程中明显有很多的w(a,b,c)被重复计算,我们可以考虑用两个三维的数组,一个用来标记,一个用来存w(a,b,c)的值,我们就可以在下次跑到相同的w(a,b,c)时就可以知道它被标记过了,我们就可以直接return 这个值就可以了,可以节省很多时间,避免了重复计算。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
#include <string.h>
long long dp[21][21][21];
long long fun(long long a, long long b, long long c){
if(a<=0||b<=0||c<=0)
return 1;
else if(a>20||b>20||c>20)
return fun(20, 20, 20);
else if(dp[a][b][c]!=-1)
return dp[a][b][c];
else if(a<b&&b<c)
return dp[a][b][c] = fun(a, b, c-1)+fun(a, b-1, c-1)-fun(a, b-1, c);
else
return dp[a][b][c] = fun(a-1,b,c)+fun(a-1,b-1,c)+fun(a-1,b,c-1)-fun(a-1,b-1,c-1);
}
int main(void){
long long a, b, c;
memset(dp,-1,sizeof(dp));
scanf("%lld%lld%lld", &a, &b, &c);
printf("w(%lld, %lld, %lld) = ",a,b,c);
long long sum=fun(a, b, c);
printf("%lld\n", sum);
return 0;
}

F 发车了发车了

Description

众所周知,新生群里面有许多老司机,每人都有一辆车,但是总共的车的种数只有四种,分别是拖拉机、独轮车、玩具车、婴儿车。现在有2*n-2个停车位,现在某人十分无聊,想要知道在所有车位都停完之后,有且仅有n辆相同种类的车停在一起有多少种方案。

Input

多组测试样例。

每组测试样例输入一个整数n(3<=n<=30)。

Output

对于每组测试样例输出对应的方案数

Sample Input

1
3

Sample Output

1
24

思路

这个题对于连续n辆汽车的摆放可以分为两种情况,一种是这n辆汽车放在最开头,一种是这n辆汽车放在中间位置,与这n辆汽车相邻的位置车辆的选择只有三种,然后把两种情况的方法数算出来加起来就行了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>
#include <math.h>
int main(void){
long long n;
while(~scanf("%lld",&n)){
long long a = pow(4,n-3),b = 0;
if(n > 3)
b = a/4;
printf("%lld\n",4*(2*3*a+(n-3)*9*b));
}
return 0;
}

G AR的空间点

Description

题目很简单,现在在一个二维空间当中有许许多多的点(n个点)。

它们的坐标为(x1,y1) , (x2,y2) , (x3,y3) …… (xn,yn) 。

它们的点有一个很特别的地方,那就是x坐标是连续的,并且为1,2,3,4……n 。

现在敖睿学长有一个问题,空间当中n个点,两两之间关联,会产生一些价值。

定义两两点之间的价值为value = (y2 - y1) / (x2 - x1)。(x1,y1,x2,y2)是任意选两个不同的点的坐标,可以随意选择任意点为(x1,y1),任意点为(x2,y2) 。

任意选择两个点,最多会有n*(n-1)/2种价值,那么在这些价值中,最大的价值是多少呢?

Input

第一行输入一个N,表示有N个点。

然后有N个行,每行两个数字为点的坐标(先输入x再输入y)

1 <= N <= 1e6(10的6次方)

1 <= x <= N

1 <= y <= 1e9(10的9次方)

Output

输出为一个整数,能够获得的最大价值 value。

Sample Input

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

3
1 1
2 1
3 1

Sample Output

1
2
3
1

0

思路

这个题我们看到(y2 - y1) / (x2 - x1)可以想到斜率,然后我们把这个n个点画在纸上可以发现这n个点中斜率最大的两个点肯定是相邻的两个点,然后我们判断一下取最大的就行了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
const int MAXN = 1e6+7;
int x[MAXN],y[MAXN];
int main(void){
int n;
scanf("%d",&n);
int res = 0;
for(int i = 1;i <= n;i++)
scanf("%d %d",x+i,y+i);
for(int i = 1;i < n;i++)
if(res < y[i+1]-y[i])
res = y[i+1]-y[i];
printf("%d\n",res);
return 0;
}

H 达妹的签到题

Description

达妹由于心态爆炸不想出题了,所以她就拿了一道签到题来水一水。现在她获得了几块糖,每块糖有一个甜蜜度。她把这些糖放在一个盒子里。

有一天,她决定从这些盒子里挑两块糖。首先,她先从盒子中随机挑选一块糖,并将其命名为甜蜜A, 接着,在没有将A放回盒子中的情况下,她从盒子中随机拿出了另外一块糖,并将其命名为甜蜜B。

如果甜蜜A的甜蜜度大于甜蜜B的甜蜜度,她就会感到开心。

现在,你知道了每块糖的甜蜜度。请你帮达妹计算一下让她感到高兴的概率。

Input

第一行一个整数t,表示测试数据的组数。

t组输入,在每个测试样例中,第一行包含一个整数n,第二行包含n个以空格分隔的正整数ai,表示第i块糖上面的甜蜜度。(1≤t≤300,2≤n≤300,1≤ai≤300)

Output

对于每个测试用例,输出一个带6个小数位的小数。

Sample Input

1
2
3
4
5
2
3
1 2 3
3
100 100 100

Sample Output

1
2
0.500000
0.000000

思路

这个题因为题目数据只有300,我们可以直接暴力来做,算出a[i] > a[j]的情况有多少种,然后除以总的n个数字中选两个数字的种数结果保留6位小数就行了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
const int MAXN = 307;
int a[MAXN];
int main(void){
int t;
scanf("%d",&t);
while(t--){
int n, sum1 = 0, sum2 = 0;
double ans;
scanf("%d",&n);
for(int i = 1;i <= n;i++)
scanf("%d",a+i);
for(int i = 1;i <= n;i++)
for(int j = 1;j <= n;j++){
if(i==j)
continue;
if(a[i] > a[j])
sum1++;
}
sum2 = n * (n - 2 + 1);
printf("%.6lf\n",1.0*sum1/sum2);
}
return 0;
}

I 神仙打架

Description

众所周知,东6B204是演员集中地,我们都膜同一个目标:罗应华聚聚。当然他也非常的满足,好日子不长,对面寝室的敖睿也成功刷题上2000成为一名聚聚,但是一山不容二虎,东6只能有一个聚聚,他们决定互相出题来难死对方,让自己成为东6唯一的聚聚,是这样的。敖睿第一回合不准备留有余力,直接给大招准备带走罗应华,敖睿大招描述如下:给出一个只由‘O','R','Z',组成的字符串,其中有多少个”ORZ“子序列就能打出多少点伤害,敖睿觉得他能直接秒掉罗应华,所以直接没有计算伤害,但是罗应华比较害怕,想让你帮他计算一下他会承受多少点伤害。子序列的定义对于一个字符串ar,就是存在任意下标a<b<c,那么”ar[a]ar[b]ar[c]”就构成s的一个子序列,比如一个字符串"aef",它的子序列有"a","e","f","ae","af","ef","aef"。

Input

一个字符串ar,字符串保证只包含'O','R','Z'三种字符。字符串的长度1<=len<=1e5(10的5次方)。

Output

输出一个数字表示罗应华要承受的伤害。

Sample Input

1
ORZORZ

Sample Output

1
4

思路

这个题我们直接统计每一个‘R’前面有多少个‘O’,后面有多少个‘Z’,然后扫一遍,把每个‘R’前面‘O’的个数乘以后面‘Z’的个数然后累加就行了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <stdio.h>
#include <string.h>
const int MAXN = 1e5+7;
char ch[MAXN];
long long opre[MAXN],zsuf[MAXN];
int main(void){
scanf("%s",ch);
long long ans = 0;
int len = strlen(ch), onum = 0, znum = 0;
for(int i = 0,j = len-1;i < len;i++,j--){
if(ch[i]=='O')
onum++;
if(ch[i]=='R')
opre[i] = onum;
if(ch[j]=='Z')
znum++;
if(ch[j]=='R')
zsuf[j] = znum;
}
for(int i = 0;i < len;i++)
if(ch[i]=='R')
ans += opre[i]*zsuf[i];
printf("%lld\n",ans);
return 0;
}

J 就用这道题来防ac吧

Description

给出一个正整数n,输出大于n的最小回文数

Input

一个正整数n(n<1e6)

Output

一个大于n的最小回文数

Sample Input

1
2
3
808

2133

Sample Output

1
2
3
818

2222

思路

如果所给的数全部由 9 组成,则输出 10…01 ,这里 0 的个数比 9 的个数少一个。 否则,如果所给的数只有一位数,则输出下一个数字。 否则,如果所给的数的左半边倒转过来大于右半边,则以左半边为基准输出回文数。 则,如果所给的数的位数是奇数,并且最中间一位数字小于 9 ,则将最中间一位数字加一,并以左半边为基准输出回文数。 否则,计算所给的数的左半边从低位算起的连续的 9 的个数,这些连续的 9 需要替换为 0 ,然后再将左半边最右侧的非 9 数字加一,以此为基准输出回文数。如果所给的数的位数是奇数,则最中间一位数字必定是 9,这个 9 也必须替换为 0 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <stdio.h>
#include <string.h>
const int MAXN = 1e5+5;
char s[MAXN];
int n, num[MAXN];
bool judge(){
for(int i = 0;i < n;i++){
if(num[i] < s[i]-'0')
return true;
else if(num[i] > s[i]-'0')
return false;
}
return true;
}
int main(void){
scanf("%s",s);
n = strlen(s);
if(n==1){
if(s[0]=='9')
printf("11\n");
else{
char f = s[0]+1;
printf("%c\n",f);
}
}else{
for(int i = n/2;i >= 0;i--)
num[i] = num[n-i-1] = s[i]-'0';
num[n] = 0;
if(judge()){
int st = n/2;
num[st]++;
for(int i = st;num[i] > 9;i++){
num[i] = 0;
num[i+1]++;
if(i==n-1)
n++;
}
for(int i = 0;i < st;i++)
num[i] = num[n-i-1];
}
for(int i = 0;i < n;i++)
printf("%d",num[i]);
printf("\n");
}
return 0;
}

K 新皇登基

Description

续上一个故事,罗应华非常幸运!他没有死!!但是他的血量也只有一点点了,意味着这一次进攻他必须成功,如果失败那么他就会死掉,他也不留余力准备放出最后的大招,大招描述如下:罗应华给出一个n和K,n代表有n个数字,K代表一个长度为K的数轴(1-K),数轴上每个点上含有一个能量值,每个点上的能量值就是对应的值(比如1对应的是1,2对应的是2。)罗应华需要从n个数中每次随便选择一个数字a(可以多次选同一个数字)然后向左走a步或者向右走a步,为了一击杀死敖睿,罗应华必须收集所有的能量来发元气弹。如果罗应华能集结所有的能量则输出他的元气弹的伤害值。否则输出"NO , I will die !"。(移动的时候可以移到负轴上再移动回正轴,并且可以选择是否收集能量,在游戏中因为要能量最大所以在负轴上的时候我们并不收集负轴的能量。)

Input

第一行输入两个数字n(1<=n<=100)和K(1<=K<=1e8)

第二行输入n个数字,a[1]一直到a[n],每个数字之间用一个空格隔开。

Output

如果能集结所有的能量则输出伤害值,否则输出"NO , I will die !"。

Sample Input

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

5 100
2 3 5 7 11

Sample Output

1
2
3
NO , I will die !

5050

思路

这个题假设我们从这n个数中选两个数一个为a,一个为b,如果这两个数字互质,那么我们总可以取到一对x和y满足ax+by=1,那么我们可以向左走(或向右走)xk次a步,向右走(或向左走)yk次b步,那么就可以走出k步走完1~k这个区间,那么我们就只需要找是否有两个数互质就行了。证明详情请见裴蜀定理

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
const int MAXN = 105;
long long gcd(long long a,long long b){
return b ? gcd(b,a%b):a;
}
long long a[MAXN];
int main(void){
long long n, tmp, k, ans;
scanf("%lld %lld",&n,&k);
for(int i = 1;i <= n;i++)
scanf("%lld",a+i);
tmp = a[1];
for(int i = 2;i <= n;i++)
tmp = gcd(tmp,a[i]);
if(tmp==1)
printf("%lld\n",(k+1)*k/2);
else
printf("NO , I will die !\n");
return 0;
}

本文标题:2019 SWUST ACM Final招新赛题解

文章作者:TSwifite

发布时间:2019年10月27日 - 21:10

最后更新:2019年10月27日 - 22:10

原始链接:http://tswiftie.com/2019-SWUST-ACM-Final招新赛题解/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%