Codeforces Round #415 (Div. 2)酱油记


第一次打比赛就突然临时改时间……凌晨2点比赛我也是很崩溃的啊……

只看完3道,T3还想错了……都拍出来了就我在哪里推……


A:暴力出奇迹

题目大意:一个序列中至少还需要加入多少个数使得最终平均数为X。

喜闻乐见的A……直接一个一个往里加,每次加入就判断一下就可以了……据说某人还写挂了23333

#include <bits/stdc++.h>
int n,k,a[1000010],sum,num,ans;
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;++i) scanf("%d",a+i);
	for(int i=1;i<=n;++i) sum+=a[i];
	num=n;
	while(sum*1.0/num<k-0.5)
	{
		sum+=k;
		num++;
		ans++;
	}
	printf("%d",ans);
	return 0;
}

T2:暴力出奇迹2.0

题目大意:给你两个数列,你可以将第一个数列中的N个元素x2,之后与第二个数列中的元素求最小值,问最大的最小值之和是多少。

我们把翻倍带来的收益sort一下取前N个即可。

没开longlongWA死了……注意用Long long!

#include <bits/stdc++.h>
using namespace std;
int n,f,k[100010],l[100010],up[100010];
long long ans;
int main()
{
	scanf("%d%d",&n,&f);
	for(int i=1;i<=n;++i)
	{
		scanf("%d%d",k+i,l+i);
		ans+=min(k[i],l[i]);
		up[i]=min((k[i]<<1),l[i])-min(k[i],l[i]);
		if(up[i]<0) up[i]=0;
	}
	sort(up+1,up+n+1);
	for(int i=0;i<f;++i)
		ans+=up[n-i];
	printf("%lld",ans);
	return 0;
}

C:数学

题目大意:求对于一个数列所有可能元素组成的集合中所有max-min的和。

既然无法暴力求出的话,我们可以直接计算贡献。

首先排序(这是必须的)

排序之后第i个数对答案有两种形式的贡献:可能做为最大值可能做为最小值。

最为最大值的贡献就是做为最大值的方案个数x它本身,作为最小值的贡献就是负的作为最小值的方案个数x它本身。

之后我们进行一番处理就可以了。

记得longlong,记得%,记得它俩都用上……

#include <bits/stdc++.h>
using namespace std;
const int ha=1000000007;
long long n,a[300010],cf[300010],ans;
int main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;++i) scanf("%lld",a+i);
	cf[0]=1;
	for(int i=1;i<=n;++i) cf[i]=(cf[i-1]<<1)%ha;
	sort(a+1,a+n+1);
	for(int i=1;i<=n;++i)
		ans=(ans+((cf[i-1]-1)*a[i])%ha)%ha;
	for(int i=n;i;--i)
		ans=((ans-(cf[n-i]-1)*a[i])%ha+ha)%ha;
	printf("%lld",ans);
}

 

声明:TonyZhao's Home|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - Codeforces Round #415 (Div. 2)酱油记


不骗了,不骗了。
A Simple OIer fighting tooth and nail.