C

目录

---

2018.8.7 正睿暑期集训营 Day4

时间：5h(实际)

期望得分：...

实际得分：...

_(:зゝ∠)_

A 世界杯(贪心)

设法国队赔率为x，克罗地亚赔率为y，则一个人会在x>=1/p时下注法国队（\(x*pi*ai\geq ai\)）。

那么按1/p从小到大排序，下注法国的一定是一个前缀。同理，下注克罗地亚队的一定是一个后缀（1/(1-p)）。

一个人下注相当于得到ai收益，但是可能会付 \(赔率*ai\) 的代价。当x增大时，法国赢了时代价就会变大，要让y适当增大来获得收益。

即y随x增大而增大。可以枚举x。

设投法国收益为w1，代价cost1=w1x；克罗地亚收益w2，代价cost2=w2x。

某种情况的收益是min(w1-cost2, w2-cost1)，x增大w1,cost1增大，要最大化min就要增大w2，即y一定单调增大。

三分套三分套二分为什么WA呢。。

//365ms 16532kb(rank2 800+ms 学了一波double read() 233)#include 
    
     #include 
     
      #include 
      
       //#define gc() getchar()#define MAXIN 400000#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)const int N=1e6+5;int n;char IN[MAXIN],*SS=IN,*TT=IN;struct Node{    double a,p;    bool operator <(const Node &node)const{        return p>node.p;    }}A[N];inline double read(){    double x=0,y=0.1; register char c=gc();    for(; !isdigit(c)&&c!='.'; c=gc());    for(; isdigit(c); x=x*10+c-'0',c=gc());    for(c=='.'&&(c=gc()); isdigit(c); x+=(c-'0')*y,y*=0.1,c=gc());    return x;}int main(){//  freopen("a.in","r",stdin);//  freopen("a.out","w",stdout);    n=read();    for(int i=1; i<=n; ++i) A[i].a=read(), A[i].p=read();//scanf("%lf%lf",&A[i].a,&A[i].p);    std::sort(A+1,A+1+n);    double Ans=0,s1=0,s2=A[n].a/*初始肯定有的啊(or 0)*/,x,y1,y2;    for(int i=1,j=n; i<=n; ++i)    {        s1+=A[i].a, x=1.0/A[i].p;        y1=1.0/(1-A[j].p);        while(j>1)        {            y2=1.0/(1-A[j-1].p);            if(std::min(s1-(y1-1)*s2,s2-(x-1)*s1)
      
     
    

B 数组(线段树)

暴力的话，枚举每个左端点，然后找到\(\min\{nxt_j\}-1\)，加上这段区间长度。（枚举右端点，求\(max\{las_j\}+1\)也一样）

如果不考虑区间内其它数的限制（只考虑本身重复的限制），如果我们能维护每个位置上次出现的位置\(las\)（set就可以），以\(i\)为右端点的区间长度就为\(i-las+1\)。

如果是算非法区间个数的话，\(las\)就是\(i\)的答案，so直接算非法的好了(这样枚举右端点更方便些)。

现在考虑区间\([las_i,i-1]\)内其它数对\(i\)延伸距离的限制，记其中最靠右的它第二次(从右往左)出现的位置为\(right\)（就是\(\max\{las_j\}\)）。

若\(right<las_i\)，则答案就是\(las_i\)；否则会将\(i\)拦住，\(i\)的答案就为\(right\)。

对于一个区间\(i\)，答案的更新同理，只是在\(right[before\ i]<right[i]\)时，答案的更新可能分成几部分，一部分会被\(right[before\ i]\)限制，一部分其区间本身限制。递归即可。

用线段树维护。

记\(sum[rt](l,r)\)为只考虑\([l,r]\)中数的限制，右端点\(i\in [l,r]\)时它们的贡献和，\(sum[1]\)就是全局非法区间数。

复杂度\(O(n\log^2n)\)。

#include 
    
     #include 
     
      #include 
      
       #include 
       
        //#define gc() getchar()#define MAXIN 300000#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)typedef long long LL;const int N=1e5+5;int n,A[N],las[N],las_v[N];std::set
        
          st[N];char IN[MAXIN],*SS=IN,*TT=IN;struct Segment_Tree{    #define ls rt<<1    #define rs rt<<1|1    #define lson l,m,rt<<1    #define rson m+1,r,rt<<1|1    #define S N<<2    int right[S];    LL ans[S];    LL Calc(int l,int r,int rt,int Right)    {        if(l==r) return std::max(right[rt],Right);        int m=l+r>>1;        if(right[ls]
         
          =right[rs]) right[rt]=right[ls], ans[rt]=ans[ls]+1ll*(r-m)*right[ls]; else right[rt]=right[rs], ans[rt]=ans[ls]+Calc(m+1,r,rs,right[ls]); } void Build(int l,int r,int rt) { if(l==r) {ans[rt]=right[rt]=las[l]; return;} int m=l+r>>1; Build(lson), Build(rson), Update(l,r,m,rt); } void Modify(int l,int r,int rt,int p,int v) { if(l==r) {ans[rt]=right[rt]=v; return;} int m=l+r>>1; if(p<=m) Modify(lson,p,v); else Modify(rson,p,v); Update(l,r,m,rt); }}T;inline int read(){ int now=0;register char c=gc(); for(;!isdigit(c);c=gc()); for(;isdigit(c);now=now*10+c-'0',c=gc()); return now;}void Modify(int val,int pos){ static std::set
          
           ::iterator pre,nxt; int vp=A[pos]; pre=st[vp].lower_bound(pos), --pre; nxt=st[vp].upper_bound(pos); if(nxt!=st[vp].end()) T.Modify(1,n,1,*nxt,*pre); st[vp].erase(pos); pre=nxt=st[val].upper_bound(pos), --pre; st[val].insert(pos), T.Modify(1,n,1,pos,*pre); if(nxt!=st[val].end()) T.Modify(1,n,1,*nxt,pos); A[pos]=val;}int main(){// freopen("b.in","r",stdin);// freopen("my.out","w",stdout); n=read(); for(int i=1; i<=n; ++i) st[i].insert(0); for(int i=1,a; i<=n; ++i) a=A[i]=read(), st[a].insert(i), las[i]=las_v[a], las_v[a]=i; T.Build(1,n,1); LL tot=1ll*n*(n+1)>>1; for(int Q=read(); Q--; ) if(!read()) printf("%lld\n",tot-T.ans[1]); else Modify(read(),read()); return 0;}
          
         
        
       
      
     
    

C 淘汰赛

生成函数+倍增+常系数线性递推。。

考试代码

A

#include 
    
     #include 
     
      #define INF 1e14#define eps (1e-8)typedef long double ld;const int N=1e6+5;//#define double ldint n;struct Node{    double a,p;    bool operator <(const Node &x)const{        return p>x.p;    }}A[N];double sum[N],sum2[N],Ans,W1,C1,W2,C2;void Calc1(double x){    int l=1,r=n,mid,ans=0;    while(l<=r)    {        mid=l+r>>1;        if((ld)x*A[mid].p>=1) ans=mid, l=mid+1;        else r=mid-1;    }    W1=sum[ans], C1=W1-x*sum[ans];}void Calc2(double x){    int l=1,r=n,mid,ans=0;    while(l<=r)    {        mid=l+r>>1;        if((ld)x*(1-A[mid].p)>=1) ans=mid, r=mid-1;        else l=mid+1;    }    W2=sum2[ans], C2=W2-x*sum2[ans];}inline double Get_Ans(double x){    Calc2(x); Ans=std::max(Ans,std::min(C1+W2,C2+W1));    return std::min(C1+W2,C2+W1);}inline double Get_Ans2(double x){    Calc1(x);    double l=0,r=1e7,lmid,rmid;    while(r-l>eps)    {        lmid = l+(r-l)/3, rmid = r-(r-l)/3;        if(Get_Ans(lmid)>Get_Ans(rmid)) r=rmid;        else l=lmid;    }    return Get_Ans(l);}int main(){//  freopen("a2.in","r",stdin);//  freopen("a.out","w",stdout);    scanf("%d",&n);    for(int i=1; i<=n; ++i) scanf("%lf%lf",&A[i].a,&A[i].p);    std::sort(A+1,A+1+n);    for(int i=1; i<=n; ++i) sum[i]=sum[i-1]+A[i].a;    for(int i=n; i; --i) sum2[i]=sum2[i+1]+A[i].a;    double l=0,r=1e7,lmid,rmid;    while(r-l>eps)    {        lmid = l+(r-l)/3, rmid = r-(r-l)/3;        if(Get_Ans2(lmid)>Get_Ans2(rmid)) r=rmid;        else l=lmid;    }    printf("%.6lf\n",Ans);    return 0;}
     
    

B

#include 
    
     #include 
     
      #include 
      
       #include 
       
        //#define gc() getchar()#define MAXIN 400000#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)typedef long long LL;const int N=1e5+5;int n,A[N];char IN[MAXIN],*SS=IN,*TT=IN;inline int read(){    int now=0;register char c=gc();    for(;!isdigit(c);c=gc());    for(;isdigit(c);now=now*10+c-'0',c=gc());    return now;}namespace Subtask1{    bool vis[N];    inline void Query()    {        vis[A[n+1]]=1;//n+1        LL res=0;        for(int i=1; i<=n; ++i)        {            int j=i;            while(!vis[A[j]]) vis[A[j++]]=1;            res+=j-i;            for(int k=i; k