目录

---

2018.9.1 Test

时间：3.5h

实际得分：40+50+20

T1直接忽略了，刚了3小时T2(暴力写法不好，直接乘逆元就行→_→)，算是有点成果吧。。

然后20分钟写完T1、T3。感觉T3也算可做的。

A(凸壳 单调栈)

注意到\(c_i=0\)，即二次函数对称轴都为y轴，但是好像还是很难做。。

但是这样我们可以把一个x提出来，变成\(x(ax+b)\)。

所以\(x>0\)时，我们要求\(\max{a_i*x+b_i}\)，即维护一个上凸壳；\(x<0\)时，维护一个下凸壳。

求法都一样，还是对斜率排序，用单调栈维护。更新时看i,sk[top],sk[top-1]间的关系。

求出凸壳后，可以在这些直线中二分出最大最小值是哪条直线。可以将求min时的直线乘-1，询问时再取反，就可以只写一个Find_Max的二分了(随意)。

还是用上/下凸壳指直线斜率递增/递减吧（凸函数）。。和图形反着。

只求了个上凸壳，在上面二分最小值直线是。。是错的。

#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=5e5+5;int n;LL ans[32330*2];char IN[MAXIN],*SS=IN,*TT=IN;struct Line{    int k,b;    Line() {}    Line(int k,int b):k(k),b(b) {}    bool operator <(const Line &x)const{        return k==x.k?b>x.b:k
       
        1 && Check(l[i],sk[top-1],sk[top])) --top;        sk[++top]=l[i];    }}#define F(i,x) (line[i].k*x+line[i].b)LL Find_Max(Line *line,int r,int x){    int l=1,mid;    while(l
        
         >1;        if(F(mid,x)>F(mid+1,x)) r=mid;        else l=mid+1;    }    return 1ll*x*F(l,x);}int main(){    n=read(); int Q=read();    for(int i=1,a,b; i<=n; ++i)        a=read(),b=read(),lu[i]=Line(a,b),ld[i]=Line(-a,-b);    int cntu,cntd;    Convex(lu,cu,cntu), Convex(ld,cd,cntd);    for(int x; Q--; )    {        x=read();        if(!x) puts("0");        else if(ans[x+32323]) printf("%lld\n",ans[x+32323]);        else if(x>0) printf("%lld\n",ans[x+32323]=Find_Max(cu,cntu,x));        else printf("%lld\n",ans[x+32323]=-Find_Max(cd,cntd,x));    }    return 0;}
        
       
      
     
    

B(思路 独立 期望)

答案就是所有元素期望被减的次数。（当然\(a_1\)是一定会被减掉的）

考虑某一局面，\(i(i\neq1)\)被减的期望次数是多少。所有元素被减的概率都是相同的。因为次数只与当前的\(a_1,a_i\)有关，且无论其它元素怎么变，1和i被减的概率都相同。

即其它元素对考虑它们没有影响，这个问题就等价于只有两个元素的原问题。（等价很厉害啊，与其它无关且概率相同概率就都是\(\frac{1}{2}\)了）

因此元素之间是独立的。对每个\(a_i\)计算答案求和就可以了。

对于只有两个元素的问题，相当于从点\((a_1,a_2)\)出发，每次等概率向左或向下走一步，直至走到坐标轴。若走到\((0,x)\)，则对答案贡献\(a_2-x\)；若走到\((x,0)\)，则对答案贡献\(a_2\)。

或者考虑枚举\(a_2\)在\(a_1\)被减到0前减了多少次。

\[\sum_{i=0}^{a_2-1}i*\frac{C_{a_1-1+i}^i}{2^{a_1+i}}+a_2(1-\sum_{i=0}^{a_2-1}\frac{C_{a_1-1+i}^i}{2^{a_1+i}})\]

前面是\(a_2\)未被减至0的期望次数，后面是被减至0的期望次数（概率用\(1-\sum_{i=0}^{a_2-1}\frac{C_{a_1-1+i}^i}{2^{a_1+i}}\)就可以啊）。

\(a_2\)每次增加1，前后都只会增加1项。算的时候直接用到\(a_2\)的前缀和也对，因为前后正好消掉。

复杂度\(O(a+n)\)。

#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++)#define mod 323232323typedef long long LL;const int N=1e6+5;int n,A[N>>1],fac[N],inv[N],inv2[N],f[N],p[N];char IN[MAXIN],*SS=IN,*TT=IN;#define C(n,m) (1ll*fac[(n)]*inv[(m)]%mod*inv[(n)-(m)]%mod)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;}inline int FP(int x,int k){    int t=1;    for(; k; k>>=1,x=1ll*x*x%mod)        if(k&1) t=1ll*t*x%mod;    return t;}int main(){    n=read(); int mx=0;    for(int i=1; i<=n; ++i) mx=std::max(mx,A[i]=read());    int a1=A[1], lim=a1+mx; fac[0]=1;    for(int i=1; i<=lim; ++i) fac[i]=1ll*fac[i-1]*i%mod;    inv[lim]=FP(fac[lim],mod-2);    for(int i=lim-1; ~i; --i) inv[i]=1ll*inv[i+1]*(i+1)%mod;    int i2=FP(2,mod-2); inv2[0]=1;    for(int i=1; i<=lim; ++i) inv2[i]=1ll*inv2[i-1]*i2%mod;//2^{-i}    p[0]=inv2[a1];    for(int i=1; i<=mx; ++i)    {        p[i]=1ll*C(a1+i-1,i)*inv2[a1+i]%mod, f[i]=1ll*i*p[i]%mod;        p[i]+=p[i-1], p[i]>=mod&&(p[i]-=mod);        f[i]+=f[i-1], f[i]>=mod&&(f[i]-=mod);    }    LL ans=a1;    for(int i=2; i<=n; ++i) ans+=f[A[i]/*-1*/]+1ll*A[i]*(mod+1-p[A[i]/*-1*/])%mod;    printf("%d\n",(int)(ans%mod));    return 0;}
      
     
    

C

考试代码

A

#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=5e5+5;int n,Q,A[N],B[N];LL ans[32323*4];char IN[MAXIN],*SS=IN,*TT=IN;inline int read(){    int now=0,f=1;register char c=gc();    for(;!isdigit(c);c=='-'&&(f=-1),c=gc());    for(;isdigit(c);now=now*10+c-'0',c=gc());    return now*f;}inline LL F(int x){    int xx=x*x;    LL res=1ll*A[1]*xx+(LL)B[1]*x;    for(int i=2; i<=n; ++i) res=std::max(res,1ll*A[i]*xx+(LL)B[i]*x);    return res;}int main(){//  freopen(".in","r",stdin);//  freopen(".out","w",stdout);    n=read(), Q=read();    for(int i=1; i<=n; ++i) A[i]=read(),B[i]=read();    for(int i=1,x; i<=Q; ++i)    {        x=read();        if(ans[x+32323]) printf("%lld\n",ans[x+32323]);        else printf("%lld\n",ans[x+32323]=F(x));    }    return 0;}
      
     
    

B

#include 
    
     #include 
     
      #include 
      
       #define gc() getchar()#define mod 323232323typedef long long LL;const int N=5e5+5;int n,A[N],fac[N<<1],inv[N<<1],i2[N<<1];struct Fraction{    LL x,y;    Fraction() {x=0, y=1;}    Fraction(LL x,LL y):x(x),y(y) {}    LL Gcd(LL x,LL y){        return y?Gcd(y,x%y):x;    }    void Exgcd(LL a,LL b,LL &x,LL &y)    {        if(!b) x=1, y=0;        else Exgcd(b,a%b,y,x),y-=a/b*x;    }    void Fix() {LL g=Gcd(x,y); x/=g, y/=g;}    Fraction operator +(const Fraction &f)    {        LL a=x*f.y+y*f.x,b=y*f.y,g=Gcd(a,b);//      printf("%I64d/%I64d + %I64d/%I64d = %I64d/%I64d\n",x,y,f.x,f.y,a/g,b/g);        return Fraction(a/g,b/g);    }    Fraction operator +(LL f)    {        LL a=f*y+x,g=Gcd(a,y);        return Fraction(a/g,y/g);    }    Fraction operator *(LL f)    {        LL a=x*f,g=Gcd(a,y);        return Fraction(a/g,y/g);    }//  Fraction operator *(const Fraction &f)//  {//      LL a=x*f.x,b=y*f.y,g=Gcd(a,b);//      return Fraction(a/g,b/g);//  }    void Print()    {        LL a,b; Exgcd(y,mod,a,b);        a=(a%mod+mod)%mod;//!//      printf("\n%I64d/%I64d=",x,y);        printf("%d\n",(int)(a*x%mod));    }}Ans;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;}inline int FP(int x,int k){    int t=1;    for(; k; k>>=1,x=1ll*x*x%mod)        if(k&1) t=1ll*t*x%mod;    return t;}void DFS(int x,int t,LL p){    if(!A[1])    {//      printf("%d %d*1/%I64d\n",x,t,p);        Ans=Ans+Fraction(1,p)*t;        return;    }    for(int i=1; i<=n; ++i)        if(A[i]) --A[i], DFS(x+!A[i],t+1,p*(n-x)%mod), ++A[i];}bool Check2(){    for(int i=1; i<=n; ++i) if(A[i]>1) return 0;    return 1;}#define C(n,m) (1ll*fac[(n)]*inv[(m)]%mod*inv[(n)-(m)]%mod)//int c[1005][1005];//int C(int n,int m) {return c[n][m];}void Solve3(){//  c[0][0]=1;//  for(int i=1; i<1000; ++i)//  {//      c[i][0]=c[i][i]=1;//      for(int j=1; j
      
     
    

C

#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=3e5+5;int n,Q,A[N],dis[N],Enum,H[N],nxt[N<<1],to[N<<1],top[N],dep[N],fa[N],sz[N],son[N],dgr[N];LL Ans[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;}inline void AddEdge(int u,int v){    ++dgr[v], to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum;    ++dgr[u], to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum;}inline int LCA(int u,int v){    while(top[u]!=top[v]) dep[top[u]]>dep[top[v]]?u=fa[top[u]]:v=fa[top[v]];    return dep[u]>dep[v]?v:u;}void DFS1(int x){    int mx=0; sz[x]=1;    for(int v,i=H[x]; i; i=nxt[i])        if((v=to[i])!=fa[x])        {            dis[v]=dis[x]+1, fa[v]=x, dep[v]=dep[x]+1, DFS1(v), sz[x]+=sz[v];            if(mx
       
        5000) {Spec(); return 0;}    DFS1(1), DFS2(1,1);    for(int u,v,w; Q--; )    {        u=read(), v=read(), w=LCA(u,v);        LL ans=A[w]|(dis[u]-dis[w]);        for(int x=u,d=0; x!=w; x=fa[x],++d) ans+=A[x]|d;        for(int x=v,d=dis[u]+dis[v]-(dis[w]<<1); x!=w; x=fa[x],--d) ans+=A[x]|d;        printf("%lld\n",ans);    }    return 0;}