Round 1201 (Codeforces Round #577(div.2)) 题解

Problem A

题意

有 \(n\) 个学生正在考试。这场考试有 \(m\) 道单选题。第 \(i\) 道单选题的分值为 \(a_i\)。

\(n\) 个学生已经回答了所有的单选题。问这 \(n\) 个学生在最好情况下能获得的总分是多少。

思路

暴力即可。对于每一道试题枚举所有可能的答案，计算该道题所有学生总分，取一个最大的加到总答案当中去。

# include <bits/stdc++.h>
# define rr register
const int N=1010;
int n,m;
int val[N];
char a[N][N];
char ans[10]={' ','A','B','C','D','E'};
int sum;
int main(void){
	scanf("%d%d",&n,&m);
	for(rr int i=1;i<=n;++i){
		for(rr int j=1;j<=m;++j){
			std::cin>>a[i][j];
		}
	}
	for(rr int i=1;i<=m;++i){
		scanf("%d",&val[i]);
	}
	for(rr int i=1,maxx,tmp;i<=m;++i){
		maxx=-1e9;
		for(rr int k=1;k<=5;++k){
			tmp=0;
			for(rr int j=1;j<=n;++j){
				if(a[j][i]==ans[k]){
					tmp+=val[i];
				}
			}
			maxx=std::max(maxx,tmp);			
		}
		sum+=maxx;
	}
	printf("%d",sum);
	return 0;
}

Problem B

题意

给你一个长度为 \(n\) 的数组 \(a\)，数组元素都是正整数。每次可以选择两个不同的元素，将它们都减 \(1\)。问经过若干次操作后能不能将整个数组的元素都变成 \(0\)。

思路

噩梦开始...这道题交了 \(3\) 次才过，罚了 \(100\) 分。心疼

来看一个例子：\(n=3,a=[1,1,1]\)。对于这组数据，是不可以把 \(a\) 变为 \([0,0,0]\) 的。因为每次操作必然使得数组元素和减少 \(2\)，那么如果数组元素和为奇数，是不行的。

诶，这样就行了？Too Young Too Simple（指我自己）

欸欸欸怎么 Wrong Answer On Pretest 9 啊？！不科学啊！

然后过了 \(3\) 分钟，我找到了一组 hack 数据......

\(n=3,a=[4,1,1]\)。

这玩意怎么搞啊...我是要特判这种 \(a[n]>\sum_{i=1}^{n-1} a[i]\)的情况吗！？

哎算了破罐子破摔***一发，WA 了无所谓了...

？？？就...过了？！

于是就是判断数组元素和的奇偶性，再加上一个特判就行了...

# include <bits/stdc++.h>
# define rr register
# define int long long
const int N=200010;
int a[N];
int b[N];
int sum;
int n;
signed main(void){
	scanf("%I64d",&n);
	for(rr int i=1;i<=n;++i){
		scanf("%I64d",&a[i]);
		sum+=a[i];
	}
	std::sort(a+1,a+1+n);
	if(sum%2||a[n]>(sum-a[n])){
		printf("NO");
		return 0;
	}else{
		printf("YES");
		return 0;
	}
	return 0;
}

Problem C

懒得讲了。

Problem D,E1,E2

看都没看。太难了。