ZROIDay4-比赛解题报告

ZROIDay4-比赛解题报告

扯闲话

感觉这个出题人的题做起来全都没感觉啊，今天又凉了，T1完全不知道什么意思，T2只会暴力，T3现在还不懂什么意思，真的太菜了

A

题意半天没搞懂爆零GG了,讲了一下才知道什么意思，还是比较有趣的一道题，一位大佬20分钟就切了

设默认押法国队本金是\(v\)，则期望收益\(p*vx\),当\(p*xv-v>=0\)时，即\(p*x >= 1\)他才会押法国队,克罗地亚队类似。从这可以看到会押本金的人在排序后一定是一个前缀

然后容易发现,若法国队赔率一定，你的收益与克罗地亚队成一个单峰函数关系，因为法国队赢了，你要用他们押克罗地亚的本钱去偿还他们的赌金,然而赔率一旦过大，克罗地亚赢的话同理

于是我们枚举押法国队赢的人数（相当于枚举赔率），再二分出押克罗地亚队的最佳人数（相当于二分最佳赔率），然后枚举法国队赢或输你的收益，最后统计答案即可。当然正如第一个样例一样还可能出现所有人都不押才是最佳的情况。

还有这题读入巨大，要用double的读入优化

代码：

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <cctype>

#include <cmath>

#include <queue>

#define ll long long

#define ri register int

using std::sort;

using std::min;

using std::max;

template <class T>inline void read(T &x){

	x=0;int ne=0,xx=0;char c;

	while(!isdigit(c=getchar()))ne=c=='-';

	xx=c-48;

	while(isdigit(c=getchar()))xx=(xx<<3)+(xx<<1)+c-48;

	if(c!='.'){

	    x=ne?-xx:xx;

	    return ;

	}

	int tot=1;double ans=1.0*xx;

	double y=getchar()-48;

	while(isdigit(c=getchar())){y=y*10+c-48;tot++;}

	while(tot--){y=y/10;}

	x=ne?-(ans+y):(ans+y);

}

const int maxn=1000005;

const int inf=0x7fffffff;

struct Dat{

	double a,p,x,y,sumx,sumy;

	Dat(){x=y=0;}

}dat[maxn];

inline	bool cmpx(const Dat &a,const Dat &b){

		return a.x<b.x;

	}

inline	bool cmpy(const Dat &a,const Dat &b){

	    return a.y<b.y;

	}

int n;

int main(){

	read(n);

	for(ri i=1;i<=n;i++){

		read(dat[i].a),read(dat[i].p);

		//printf("%lf %lf\n",dat[i].a,dat[i].p);

		dat[i].x=1/dat[i].p,dat[i].y=1/(1-dat[i].p);

	}

	sort(dat+1,dat+1+n,cmpx);

	for(ri i=1;i<=n;i++)dat[i].sumx=dat[i-1].sumx+dat[i].a;

	sort(dat+1,dat+1+n,cmpy);

	for(ri i=1;i<=n;i++)dat[i].sumy=dat[i-1].sumy+dat[i].a;

	double tmp1,tmp2,ans=-inf;

	for(ri i=0;i<=n;i++){

		int l=0,r=n,mid;

		while(l<=r){

			mid=(l+r)>>1;

			tmp1=dat[i].sumx*(1-dat[i].x)+dat[mid].sumy;

			tmp2=dat[i].sumx+dat[mid].sumy*(1-dat[mid].y);

			ans=max(ans,min(tmp1,tmp2));

			if(tmp1<tmp2)l=mid+1;

			else r=mid-1;

		}

	}

	printf("%lf\n",ans);

	return 0;

}

B

毒瘤数据结构，不会

C

题目看不懂，还要特征多项式！？