ZROIDay4-比赛解题报告
扯闲话
感觉这个出题人的题做起来全都没感觉啊，今天又凉了，T1完全不知道什么意思，T2只会暴力，T3现在还不懂什么意思，真的太菜了
A
题意半天没搞懂爆零GG了,讲了一下才知道什么意思，还是比较有趣的一道题，一位大佬20分钟就切了
设默认押法国队本金是$v$，则期望收益$pvx$,当$pxv-v>=0$时，即$p*x >= 1$他才会押法国队,克罗地亚队类似。从这可以看到会押本金的人在排序后一定是一个前缀
然后容易发现,若法国队赔率一定，你的收益与克罗地亚队成一个单峰函数关系，因为法国队赢了，你要用他们押克罗地亚的本钱去偿还他们的赌金,然而赔率一旦过大，克罗地亚赢的话同理
于是我们枚举押法国队赢的人数（相当于枚举赔率），再二分出押克罗地亚队的最佳人数（相当于二分最佳赔率），然后枚举法国队赢或输你的收益，最后统计答案即可。当然正如第一个样例一样还可能出现所有人都不押才是最佳的情况。
还有这题读入巨大，要用double的读入优化
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
| #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);
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
题目看不懂，还要特征多项式！？