比赛来源

A题

题意

每组给定10个数，若这些数中同时含有17和18，输出both；只含有17，输出Zack；只含有18，输出Mack；既没有17又没有18，输出none。

思路

开两个变量分别记录是否出现17和18，然后根据值判断输出即可。

代码

1
#include<iostream>
2
#include<cstdio>
3
using namespace std;
4
int a[15];
5
int main(){
6
	int i,j,k,m,n,t;bool f1,f2;
7
	scanf("%d",&t);
8
	while(t--){
9
		f1=f2=0;
10
		for(i=1;i<=10;i++){
11
			scanf("%d",&a[i]);
12
			if(a[i]==17) f1=1;
13
			else if(a[i]==18) f2=1;
14
		}
15
		for(i=1;i<=10;i++) printf(i==10?"%d":"%d ",a[i]);
16
		printf("\n");
17
		if(f1){
18
			if(f2) printf("both\n");
19
			else printf("zack\n");
20
		}
21
		else{
22
			if(f2) printf("mack\n");
23
			else printf("none\n");
24
		}
25
		printf("\n");
26
	}
27
	return 0;
28
}

B题

题意

分别给出美国和俄罗斯的金、银、铜牌数量，同时有两种决定排名的方式，count（奖牌数多的靠前）和color（依次金银铜牌的数量，首先出现某种奖牌多的靠前），问美国通过哪种方式排名可以领先俄罗斯，两种都不能输出none，两种都能输出both。

思路

分别通过两种方式比较并用变量标记结果，最后根据变量的不同值进行输出。

代码

1
#include<iostream>
2
#include<cstdio>
3
using namespace std;
4
struct MD{
5
	int g,s,b,sum;
6
}a[2];
7
bool operator==(const MD &x,const MD &y){
8
	if(x.g==y.g&&x.s==y.s&&x.b==y.b) return 1;
9
	else return 0;
10
}
11
bool operator>(const MD &x,const MD &y){
12
	if(x.g!=y.g) return x.g>y.g;
13
	if(x.s!=y.s) return x.s>y.s;
14
	return x.b>y.b;
15
}
16
int main(){
17
	int i,j,k,m,n,t;
18
	scanf("%d",&t);
19
	while(t--){
20
		k=0;
21
		for(i=0;i<=1;i++){
22
			scanf("%d%d%d",&a[i].g,&a[i].s,&a[i].b);
23
			a[i].sum=a[i].g+a[i].s+a[i].b;
24
		}
25
		printf("%d %d %d ",a[0].g,a[0].s,a[0].b);
26
		printf("%d %d %d\n",a[1].g,a[1].s,a[1].b);
27
		if(a[0].sum>a[1].sum) k=1;
28
		if(a[0]>a[1]) k+=2;
29
		switch (k){
30
			case 0:printf("none\n");break;
31
			case 1:printf("count\n");break;
32
			case 2:printf("color\n");break;
33
			case 3:printf("both\n");break;
34
		}
35
		printf("\n");
36
	}
37
	return 0;
38
}

C题

题意

初始有n块蛋糕，会有m波学生来分，对于每一波学生若当前蛋糕数量小于等于学生数量，就把剩下的每块蛋糕都切开，即蛋糕数量翻倍。输出每波蛋糕分过后剩余蛋糕的数量。

思路

模拟即可。

代码

1
#include<iostream>
2
#include<cstdio>
3
using namespace std;
4
int main(){
5
	int i,j,k,m,n,t,g,l;
6
	scanf("%d",&t);
7
	for(k=1;k<=t;k++){
8
		scanf("%d%d",&n,&m);
9
		printf("Practice #%d: %d %d\n",k,n,m);
10
		scanf("%d",&g);
11
		while(g--){
12
			scanf("%d",&l);
13
			while(l>=m) m*=2;
14
			m-=l;
15
			printf("%d %d\n",l,m);
16
		}
17
		printf("\n");
18
	}
19
	return 0;
20
}

D题

题意

你开了一家柠檬店。已知制作一杯柠檬汁需要x个柠檬和s盎司糖，给出d天时间每天需要制作的柠檬水数量和当天每个柠檬和每5磅糖的价格，问在满足这d天需求的情况下购入柠檬和糖的最小花费。

思路

贪心，每天先将前面剩下的糖先用完，然后以这天及之前中最低的价格购入能满足最小需要的柠檬和糖，并记录剩余数量供之后使用

代码

1
#include<iostream>
2
#include<cstdio>
3
using namespace std;
4
int main(){
5
	int i,j,k,m,n,t,d,x,s,c,pl,ps,nl,ns,ls=0,upl=10000,ups=10000,cst=0;
6
	scanf("%d",&t);
7
	while(t--){
8
		scanf("%d%d%d",&d,&x,&s);
9
		cst=0;
10
		upl=ups=10000;ls=0;
11
		for(i=1;i<=d;i++){
12
			scanf("%d%d%d",&c,&pl,&ps);
13
			if(upl>pl) upl=pl;
14
			if(ups>ps) ups=ps;
15
			int u;
16
			nl=c*x;
17
			if(s*c>ls){
18
				ns=s*c-ls;
19
				ls=0;
20
				u=(ns-1)/80+1;
21
			}
22
			else{
23
				ns=0;
24
				u=0;
25
				ls-=s*c;
26
			}
27
			cst+=nl*upl+u*ups;
28
			ls+=u*80-ns;
29
		}
30
		printf("%d\n",cst);
31
	}
32
	return 0;
33
}

E题

题意

给出一个圆的半径r与一个正方形的边长s，两者中心重合，问圆和正方形重叠部分的面积。

思路

（1）当 $2r \ge \sqrt 2L$ 时，重合部分面积等于 $S_{正方形}=L^2$ 。

（2）当$2r \le L$ 时，重合部分面积等于 $S_圆 = \pi R^2$ 。

（3）其它情况：$𝑆 = \pi 𝑅^2 − 4(\frac{2 \theta }{2 \pi }𝜋𝑅^2 − \frac{1}{2} 𝑅 \cos 𝜃 × 2𝑅 \sin 𝜃)$ (其中$\theta = \arccos \frac{𝐿}{2R}$)

代码

1
#include<iostream>
2
#include<cstdio>
3
#include<cmath>
4
using namespace std;
5
const double pi=3.14159265358979;
6
int main(){
7
	int i,j,k,m,n,t,s,r;
8
	scanf("%d",&t);
9
	while(t--){
10
		scanf("%d%d",&s,&r);
11
		if(s<=sqrt(2)*r) printf("%.2lf\n",(double)s*s);
12
		else if(s>=2*r) printf("%.2lf\n",pi*r*r);
13
		else{
14
			double ans=(double)s*sqrt(4*r*r-s*s)+(pi-4*acos((double)s/(2*r)))*r*r;
15
			printf("%.2lf\n",ans);
16
		}
17
	}
18
	return 0;
19
}

F题

将 $a,e,i,o,u,y$ 认为是元音字母，其他字母为辅音字母。现给出一个由小写字母和 $?$ 组成的字符串,在每个 $?$ 处可以填充任意一个字母，问有多少种填充方案可以使得该字符串的任意偶数长度的子串的元音和辅音字母个数相同。

思路

分析可知要使字符串满足条件，字符串必须是元音辅音交错的形式，因此可以以假设元音开头和辅音开头分别进行dfs，如遇到 $?$ 则将方案数乘以相应字母的数量（元音乘6，辅音乘20），如果遇到某个已填字母与应填字母类型不同的则返回0，表示不存在。

代码

1
#include<iostream>
2
#include<cstdio>
3
using namespace std;
4
int a[105],l;
5
string s;
6
int pd(char c){
7
	if(c=='?') return -1;
8
	if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u'||c=='y') return 0;
9
	return 1;
10
}
11
long long w[]={6,20};
12
long long dfs(int x,int f){
13
	if(x==l) return 1;
14
	long long ea=1;
15
	if(a[x]==1-f) return 0;
16
	if(a[x]==-1){
17
		ea*=w[f];
18
	}
19
	ea*=dfs(x+1,1-f);
20
	return ea;
21
}
22
int main(){
23
	int i,j,k,m,n,t;long long ans=0;
24
	scanf("%d",&t);
25
	for(k=1;k<=t;k++){
26
		cin>>s;
27
		ans=0;
28
		l=s.size();
29
		for(i=0;i<l;i++){
30
			a[i]=pd(s[i]);
31
		}
32
		for(i=0;i<=1;i++) ans+=dfs(0,i);
33
		printf("String #%d: %lld\n\n",k,ans);
34
	}
35
	return 0;
36
}

G题

题意

给出一个 $N*N$ 的棋盘，初始时在 $(1,1)$ 位置有一个 $d$ 层的汉诺塔，现要求把该塔按照原来的顺序移动到右下角所需的最小步数，要求每次只能将一个圆盘向右或向下移动一格，除了左上角和右下角的格子外每个格子只能放一个圆盘，大圆盘只能放小圆盘下面。

思路

经过分析，每个圆盘从左上角移动到右下角需要的步数最少也只能为 $2n-2$ 步，所以若有解，则解必然为 $2d(n-1)$。

再考虑无解的情况，由于最底层的圆盘要先放入右下角， 每个格子只能放一个圆盘，同时需要留出一条能够从左上角到右下角的通路，所以当 $d-1>(N-1)^2$ 时无解。

代码

1
#include<iostream>
2
#include<cstdio>
3
using namespace std;
4
int main(){
5
	int i,j,k,m,n,t,d;
6
	scanf("%d",&t);
7
	for(i=1;i<=t;i++){
8
		scanf("%d%d",&d,&n);
9
		int ans=d*2*(n-1);
10
		if((n-1)*(n-1)<d-1) printf("Grid #%d: impossible\n\n",i);
11
		else printf("Grid #%d: %d\n\n",i,ans);
12
	}
13
	return 0;
14
}

H题

题意

有一个如图形状的印章，黑色部分会蘸有涂料。 给你一个𝑟行𝑐列的图像（ $1 ≤ 𝑟, 𝑐 ≤ 9 $），要求用该印章敲出这个图像，求最少的 操作步数。

思路

待补题

代码

待补题

I题

题意

给出一个 $𝑛(𝑛 ≤ 500)$ 个点的有向图，任意两个点之间有且仅一条有向边。 求一条不重复经过一个点的最长的简单路径。

思路

待补题

代码

待补题

J题

题意

有$𝑛(𝑛 ≤ 50)$个学生，要分配到两个班级。给出每个学生在两个班级中能通过考试的概率。 而且若学生 $𝑖$ 和 $𝑗$ 在同一个班级中，学生 $𝑖$ 通过考试的概率将会增加 $𝑎_{𝑖𝑗}$ 。 给出每个 $𝑎_{𝑖𝑗}$ ，且保证无论怎样分配，任意一个学生通过考试的概率都在 $[0,1]$ 范围内。

思路

待补题

代码

待补题

K题

题意

给定正整数 $𝑋$ 和 $𝑁$ （$1 ≤ 𝑋, 𝑁 < 2^{31}$），定义集合 $𝑇 = {𝑇_𝑖 |1 ≤ 𝑖 ≤ 𝑁 + 1}, 𝑇_𝑖 = ( ^{𝑁} _{𝑖−1} )𝑋^{𝑖−1}$ 。 要求选出 $𝑇$ 的一个非空子集 $𝑆$ ，使得$∏_{𝑖∈𝑆} 𝑇_𝑖 ≡ 2 (𝑚𝑜𝑑 4)$ ，并最大化 $∑_{𝑖∈𝑆}i$ 。 输出最大的 $∑_{𝑖∈𝑆}i$ 。若不存在，输出 0。

思路

待补题

代码

待补题

总结

这场比赛的总体难度较低，但在解题过程中仍出现了像输出格式错误，变量打错等一些细节上的问题。同时，在对英文题面的阅读和理解上效率较低，有些题敲到一般才发现理解错了题意，导致浪费了很多时间。另外，接触的难题比较少，因此还需要接触更多的算法和通过更多的练习来积累经验。