CF #577 div 2 解题报告

Codeforces Round #577 (Div. 2)

这场比赛在北京时间8月5号凌晨打，实在是吃不消，就没有打。只能补题：目前只补了ABC。

A题一发，B题wa了一次（wa   test9 ），C题wa了一次（wa  test4），对于C题，感觉还是思维僵硬，如果不是面向测试点编程，可能会想不到。

A. Important Exam

传送门

题意：

N个学生，M个题目，考试，每个题目有ABCDE选项，学生选对了会获得分数，求学生获得分数最大值。

思路：

统计出题目答案出现次数最多的选项乘以分值，求和一下。

AC代码：

/***********************************************
 * @Author:      miniLCT
 * @DateTime:    2019-08-05 11:37:04
 * @Description: You build it, You run it.  
 ***********************************************/
#include <bits/stdc++.h>
#define ll long long
const int maxn = 1e6+10;
#define eps 1e-8
using namespace std;
int n,m;
string s;
int dp[maxn][10];
int max__(int a, int b, int c,int d ,int e){
	return max(a,max(b,max(c,max(d,e))));
}
int main()
{
	int ans = 0;
	cin>>n>>m;
	for(int i = 1;i <= n;i++){
		cin>>s;
		for(int  j = 1; j <= m;j++)
			dp[j][s[j-1]-'A']++;
	}
	for(int  i = 1; i <= m;i++){
		int kk;
		cin>>kk;
		ans += max__(dp[i][0],dp[i][1],dp[i][2],dp[i][3],dp[i][4])*kk;
	}
	cout<<ans<<endl;
}

B.Zero Array

传送门

题意：

给n个数，两个下标不同的数同时减去 数值较小的数，问这n个数经过一系列不可描述操作后，能否实现，这n个数都变成零。

思路：

容易看出，∑ ai 必须是偶数。

仅仅这个还不够，还有一个点就是，这n个数中的max必须小于等于(∑ai) /2，这样才能保证所有数都能为零。

AC代码：

/***********************************************
 * @Author:      miniLCT
 * @DateTime:    2019-08-05 11:46:15
 * @Description: You build it, You run it.  
 ***********************************************/
#include <bits/stdc++.h>
#define ll long long
#define int long long
const int maxn = 1e6+10;
#define eps 1e-8
using namespace std;
int n;
int a[maxn];
int sum;
main()
{
	cin>>n;
	for(int i = 0; i < n;i++){
		cin>>a[i];
		sum +=a[i];
	}
	int kk = *max_element(a,a+n);
	if(sum&1||kk>sum/2)cout<<"NO"<<endl;
	else cout<<"YES"<<endl;
}

C. Maximum Median

传送门

题意：

给定n,k,数组。数组中n个数字，你可以操作k次，每次操作使得数组中某个元素+1，求k次操作后这个（有序数组）的中位数的最大可能值。

思路：

首先可以肯定 操作要往大的数字操作，那么就是中位数位置往后操作，才能尽可能的大，用数组b来记录中位数往后的a[i+1] - a[i] 的值，每次都” 填平 “那种 感觉去让中位数尽可能大。

第一次写wa 了，想了好一会儿也不知道哪里出问题，看了测试样例之后发现是1 1 1 这种情况，当n = 1时，我的代码有问题，没有数组b，就不会执行。感觉个人局限性还是很大，不借助测试点我可能很难想到n==1这种情况。个人局限性还是很大，还得多练习，开阔思路。。

AC代码：

/***********************************************
 * @Author:      miniLCT
 * @DateTime:    2019-08-05 12:08:13
 * @Description: You build it, You run it.  
 ***********************************************/
#include <bits/stdc++.h>
#define ll long long
#define int long long 
const int maxn = 1e6+10;
#define eps 1e-8
using namespace std;
int a[maxn];
int b[maxn];
int n,k;
main()
{
	cin>>n>>k;
	for(int i = 0;i < n;i++)
		cin>>a[i];
	if(n == 1){cout<<a[0]+k<<endl;return 0;}  //wa 4 
	sort(a,a+n);
	//中位数a[n/2];
	int tmp = 1;
	for (int i = n/2; i <n-1 ;i++){
		b[tmp++] = a[i+1] - a[i];
	}
	int tmpp = 1;
	while(k > tmpp * b[tmpp] ){
		k -= tmpp * b[tmpp] ;
		a[n/2] += b[tmpp];
		tmpp++;
		if(tmp == tmpp)break;
	}
	//if(tmp == tmpp) a[n/2] += (k - sum)/(tmpp-1);
	a[n/2] += k/tmpp;
	cout<<a[n/2]<<endl;
}

D题还没写，，等有空再补题把。