A. Hacker Cups and Balls

二分答案，将$\geq mid$的数看成$1$，$<mid$的数看成$0$，用线段树进行区间排序检查即可。时间复杂度$O(n\log^2n)$。

#include
     
      #include
      
       using namespace std;const int N=100010,M=262150;int n,m,i,a[N],e[N][2],l,r,MID,ans;int len[M],c1[M],tag[M];inline void tag1(int x,int p){  c1[x]=p?len[x]:0;  tag[x]=p;}inline void pb(int x){  if(~tag[x]){    tag1(x<<1,tag[x]);    tag1(x<<1|1,tag[x]);    tag[x]=-1;  }}inline void up(int x){  c1[x]=c1[x<<1]+c1[x<<1|1];}void build(int x,int a,int b){  len[x]=b-a+1;  tag[x]=-1;  if(a==b){    c1[x]=::a[a]>=MID;    return;  }  int mid=(a+b)>>1;  build(x<<1,a,mid),build(x<<1|1,mid+1,b);  up(x);}int ask(int x,int a,int b,int c,int d){  if(c<=a&&b<=d)return c1[x];  pb(x);  int mid=(a+b)>>1,t=0;  if(c<=mid)t=ask(x<<1,a,mid,c,d);  if(d>mid)t+=ask(x<<1|1,mid+1,b,c,d);  return t;}void change(int x,int a,int b,int c,int d,int p){  if(c<=a&&b<=d){tag1(x,p);return;}  pb(x);  int mid=(a+b)>>1;  if(c<=mid)change(x<<1,a,mid,c,d,p);  if(d>mid)change(x<<1|1,mid+1,b,c,d,p);  up(x);}bool check(){  build(1,1,n);  for(i=1;i<=m;i++){    int l=e[i][0],r=e[i][1];    bool u=l
       
        r)swap(l,r);    int len=r-l+1;    int cnt=ask(1,1,n,l,r);    change(1,1,n,l,r,0);    if(!cnt)continue;    if(u)change(1,1,n,r-cnt+1,r,1);    else change(1,1,n,l,l+cnt-1,1);  }  return ask(1,1,n,(n+1)/2,(n+1)/2);}int main(){  scanf("%d%d",&n,&m);  for(i=1;i<=n;i++)scanf("%d",&a[i]);  for(i=1;i<=m;i++)scanf("%d%d",&e[i][0],&e[i][1]);  l=1,r=n;  while(l<=r){    MID=(l+r)>>1;    if(check())l=(ans=MID)+1;else r=MID-1;  }  printf("%d",ans);}
       
      
     

　　

B. Bored Dreamoon

设$f[i]$表示$i$的横坐标。对于$h[i]<h[j]$，若$j$在$i$前面则无解，若$i$在$j$前面则$f[j]\geq f[i]$，否则$f[j]<f[i]$。若存在环则无解，递推求出所有$f$即可。时间复杂度$O(n^2)$。

#include
     
      #include
      
       #include
       
        using namespace std;const int N=1010;int n,i,j,x,rk[N],s[N][N],ans;char ch[N];pair
        
         a[N];int h,t;int q[N],d[N],f[N],g[N],v[N*N],w[N*N],nxt[N*N],ed,vis[N];bool in[N];void NIE(){  puts("-1");  exit(0);}inline void add(int x,int y,int z){  v[++ed]=y;w[ed]=z;nxt[ed]=g[x];g[x]=ed;  d[y]++;}int main(){  scanf("%d",&n);  for(i=1;i<=n;i++)scanf("%d",&a[i].first),a[i].second=i;  sort(a+1,a+n+1);  for(i=1;i<=n;i++)rk[a[i].second]=i;  for(i=1;i<=n;i++){    scanf("%s",ch+1);    for(j=1;j<=n;j++){      s[rk[i]][rk[j]]=ch[j]-'0';    }  }  //s[i][j]=1 denotes j is in right front of i  for(i=1;i<=n;i++)for(j=i+1;j<=n;j++){    if(s[i][j])NIE();    //s[i][j]=0    if(s[j][i]){//i is in right front of j      add(i,j,0);      //f[j]>=f[i]    }else{      add(j,i,1);      //f[i]>=f[j]+1    }  }  for(h=i=1;i<=n;i++){    f[i]=1;    if(!d[i])q[++t]=i;  }  while(h<=t){    x=q[h++];    for(i=g[x];i;i=nxt[i]){      f[v[i]]=max(f[v[i]],f[x]+w[i]);      if(!(--d[v[i]]))q[++t]=v[i];    }  }  if(t
        
       
      
     

　　

C. Crazy Dreamoon

枚举横坐标，纵坐标对应的区间可以双指针。时间复杂度$O(n^2)$。

#include
     
      #include
      
       #include
       
        using namespace std;const int N=2050;const double eps=1e-9;int n,i,j,ans;bool f[N][N];int cnt;struct P{  int x,y;  P(){}  P(int _x,int _y){x=_x,y=_y;}  P operator-(const P&b){return P(x-b.x,y-b.y);}  int operator*(const P&b){return x*b.x+y*b.y;}}a,b,p,q;struct E{  double x,y;  E(){}  E(double _x,double _y){x=_x,y=_y;}}e[9];inline int sgnd(double x){  if(x>eps)return 1;  if(x<-eps)return -1;  return 0;}inline bool cmp(const E&a,const E&b){  if(sgnd(a.x-b.x))return a.x
        
         0)return 1;  if(x<0)return -1;  return 0;}inline int cross(const P&a,const P&b){  return a.x*b.y-a.y*b.x;}inline bool point_on_segment(P p,P a,P b){  return sgn(cross(b-a,p-a))==0&&sgn((p-a)*(p-b))<=0;}inline bool has_intersection(){  int d1=sgn(cross(b-a,p-a)),d2=sgn(cross(b-a,q-a));  int d3=sgn(cross(q-p,a-p)),d4=sgn(cross(q-p,b-p));  if(d1*d2<0&&d3*d4<0)return 1;  if(d1==0&&point_on_segment(p,a,b))return 1;  if(d2==0&&point_on_segment(q,a,b))return 1;  if(d3==0&&point_on_segment(a,p,q))return 1;  if(d4==0&&point_on_segment(b,p,q))return 1;  return 0;}inline void line_intersection(){  int U=cross(p-a,q-p);  int D=cross(b-a,q-p);  double t=1.0*U/D;  e[++cnt]=E(t*(b.x-a.x)+a.x,t*(b.y-a.y)+a.y);}inline bool check(int x,int y){  //printf("check %d %d:\n",x,y);  cnt=0;  p=P(x,y);  q=P(x+1,y);  if(has_intersection())line_intersection();  q=P(x,y+1);  if(has_intersection())line_intersection();  p=P(x+1,y);  q=P(x+1,y+1);  if(has_intersection())line_intersection();  p=P(x,y+1);  if(has_intersection())line_intersection();    /*for(int i=1;i<=cnt;i++){    printf("%.8f %.8f\n",e[i].x,e[i].y);  }*/    if(cnt<2)return 0;  sort(e+1,e+cnt+1,cmp);  int t=1;  for(int i=2;i<=cnt;i++)if(e[i].x>e[i-1].x+eps||e[i].y>e[i-1].y+eps)t++;  return t==2;}void solve(){  int A,B,C,D;  scanf("%d%d%d%d",&A,&B,&C,&D);  if(A==C||B==D)return;  if(A>C)swap(A,C),swap(B,D);  a=P(A,B);  b=P(C,D);  if(B
         
          =0&&!check(i,R))R--;      if(R<0)return;      if(L>R)L=R;      while(L>0&&check(i,L-1))L--;      for(int j=L;j<=R;j++)f[i][j]=1;    }  }}int main(){  scanf("%d",&n);  while(n--)solve();  for(i=0;i<=2000;i++)for(j=0;j<=2000;j++)if(f[i][j])ans++;  printf("%d",ans);}
         
        
       
      
     

　　

D. Forest Game

设$d(x,y)$为$x$到$y$路径上点的个数，则$ans=n!\sum_{i=1}^n\sum_{j=1}^n\frac{1}{d(i,j)}$。

利用树分治+FFT可以做到$O(n\log^2n)$。

#include
     
      #include
      
       #include
       
        using namespace std;typedef long long ll;const int N=270000,P=1000000007;const double pi=acos(-1.0);struct comp{  double r,i;  comp(double _r=0,double _i=0){r=_r;i=_i;}  comp operator+(const comp&x){return comp(r+x.r,i+x.i);}  comp operator-(const comp&x){return comp(r-x.r,i-x.i);}  comp operator*(const comp&x){return comp(r*x.r-i*x.i,r*x.i+i*x.r);}}A[N],B[N];int n,m,i,x,y,ed,a[N],g[N],nxt[N],v[N],ok[N],son[N],f[N],size,now;int inv[N],ans;ll cnt[N];inline void add(int x,int y){v[++ed]=y,nxt[ed]=g[x],ok[ed]=1,g[x]=ed;}void findroot(int x,int pre){  son[x]=1;f[x]=0;  for(int i=g[x];i;i=nxt[i])if(ok[i]&&v[i]!=pre){    findroot(v[i],x);    son[x]+=son[v[i]];    if(son[v[i]]>f[x])f[x]=son[v[i]];  }  if(size-son[x]>f[x])f[x]=size-son[x];  if(f[x]
        
         >=1,~j&s;);    if(i
         
          0)cnt[i]+=o;else cnt[i]-=o;  }  for(i=1;i<=m;i++)a[i]=0;m=0;}void dfs(int x,int pre,int d){  a[d]++;if(d>m)m=d;  for(int i=g[x];i;i=nxt[i])if(ok[i]&&v[i]!=pre)dfs(v[i],x,d+1);}void solve(int x){  int i;  dfs(x,0,1),cal(1);  for(i=g[x];i;i=nxt[i])if(ok[i])dfs(v[i],x,2),cal(-1);  for(i=g[x];i;i=nxt[i])if(ok[i])ok[i^1]=0,f[0]=size=son[v[i]],findroot(v[i],now=0),solve(now);}int main(){  scanf("%d",&n);  for(ed=i=1;i
         
        
       
      
     

　　

E. Lines Game

等价于选一个递增序列，且任意两个相邻的点$(i,p[i]),(j,p[j])$中间的矩形内部没有任何点。

设$f[i]$表示考虑前$i$个点，且$i$必选的最小代价。

考虑cdq分治，将左右的点按纵坐标排序后从小到大加入，两边分别维护两个关于横坐标的单调栈，然后用线段树维护单调栈中的DP值。

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

#include
     
      #include
      
       using namespace std;const int N=100010,inf=~0U>>1;int n,i,a[N],w[N],f[N],v[262150];int ca,cb,qa[N],qb[N],ta,tb,sa[N],sb[N];inline bool cmp(int x,int y){return a[x]
       
        >1;  build(x<<1,a,mid),build(x<<1|1,mid+1,b);}void change(int x,int a,int b,int c,int p){  if(a==b){v[x]=p;return;}  int mid=(a+b)>>1;  c<=mid?change(x<<1,a,mid,c,p):change(x<<1|1,mid+1,b,c,p);  v[x]=min(v[x<<1],v[x<<1|1]);}int ask(int x,int a,int b,int c,int d){  if(c<=a&&b<=d)return v[x];  int mid=(a+b)>>1,t=inf;  if(c<=mid)t=ask(x<<1,a,mid,c,d);  if(d>mid)t=min(t,ask(x<<1|1,mid+1,b,c,d));  return t;}void solve(int l,int r){  if(l==r){    if(f[l]
        
         >1;  solve(l,mid);  int i,j;  ca=cb=0;  for(i=l;i<=mid;i++)qa[++ca]=i;  for(i=r;i>mid;i--)qb[++cb]=i;  sort(qa+1,qa+ca+1,cmp);  sort(qb+1,qb+cb+1,cmp);  ta=tb=0;  for(i=j=1;i<=cb;i++){    while(j<=ca&&a[qa[j]]
         
          sa[ta]){        change(1,0,n,a[sa[ta]],inf);        ta--;      }      sa[++ta]=qa[j];      change(1,0,n,a[qa[j]],f[qa[j]]);      j++;    }    while(tb&&qb[i]
         
        
       
      
     

　　

F. Lonely Dreamoon 2

将序列排序。

当$n$是偶数时从中间劈开，然后对应排名相互配对。

当$n$是奇数时枚举shift的次数，取最优的进行配对。

#include
     
      #include
      
       using namespace std;const int N=200010;int n,m,i,j,x,y,a[N],w[N];int main(){  scanf("%d",&n);  for(i=0;i
      
     

　　

G. Dreamoon and NightMarket

将食物从小到大排序，用堆记录$($代价$,$最贵的食物$)$，每次要么新加入一个更贵的食物，要么把最贵的换成更贵的。时间复杂度$O(n\log n+k\log k)$。

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;typedef long long ll;typedef pair
         
          P;int n,m,i,a[200010];P t;priority_queue
          
           
,greater
           
 >q;int main(){ scanf("%d%d",&n,&m); for(i=1;i<=n;i++)scanf("%d",&a[i]); sort(a+1,a+n+1); q.push(P(a[1],1)); while(m--){ t=q.top(); q.pop(); if(t.second==n)continue; q.push(P(t.first-a[t.second]+a[t.second+1],t.second+1)); q.push(P(t.first+a[t.second+1],t.second+1)); } printf("%I64d",t.first);}
          
         
        
       
      
     

　　

H. Split Game

把点极角排序之后扫描线，考虑每个角对区域个数的影响。时间复杂度$O(n\log n)$。

#include
     
      #include
      
       using namespace std;typedef long long ll;const int N=100010;int n,i,j,b[N],t,x,ans;struct P{  int x,y;  P(){}  P(int _x,int _y){x=_x,y=_y;}  P operator-(const P&b){return P(x-b.x,y-b.y);}}a[N];inline ll cross(const P&a,const P&b){return 1LL*a.x*b.y-1LL*a.y*b.x;}inline bool cmp(int x,int y){  return cross(a[x],a[y])>0;}int main(){  scanf("%d",&n);  for(i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y);  a[0]=a[n];  a[n+1]=a[1];  for(i=1;i<=n;i++)b[i]=i;  sort(b+1,b+n+1,cmp);  for(i=1;i<=n;i=j){    x=0;    for(j=i;j<=n&&!cross(a[b[i]],a[b[j]]);j++){      if(cross(a[b[j]+1],a[b[j]])>0&&cross(a[b[j]-1],a[b[j]])>=0){        if(cross(a[b[j]-1]-a[b[j]],a[b[j]+1]-a[b[j]])<0)t--;        else x--;      }      if(cross(a[b[j]-1],a[b[j]])<0&&cross(a[b[j]+1],a[b[j]])<=0){        if(cross(a[b[j]-1]-a[b[j]],a[b[j]+1]-a[b[j]])>0)t++;        else x++;      }    }    ans=max(ans,t);    t+=x;    ans=max(ans,t);  }  printf("%d",ans+1);}
      
     

　　

I. Tree Game

贪心，记录每个子树里尚未配对的叶子数。

若有多于两棵子树尚未配对的叶子数为$1$，那么这些只能配掉。

若有多于一棵子树尚未配对的叶子数为$2$，那么这些只能配掉。

若有多于一棵子树尚未配对的叶子数为$1$，那么先考虑能否去和叶子数为$2$的子树进行配对。

否则最多向父亲贡献$2$个叶子。

时间复杂度$O(n)$。

#include
     
      const int N=100010;int n,i,x,y,g[N],v[N<<1],nxt[N<<1],ed,d[N],ans;inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;d[x]++;}int dfs(int x,int y){  if(d[x]==1)return 1;  int A=0,B=0;  for(int i=g[x];i;i=nxt[i])if(v[i]!=y){    int t=dfs(v[i],x);    if(t==1)A++;    if(t==2)B++;  }  while(A>2)ans++,A-=2;  while(B>1)ans++,B-=2;  while(A>1&&B)ans++,A--,B--;  A+=B*2;  return A<2?A:2;}int main(){  scanf("%d",&n);  if(n<=3)return puts("1"),0;  for(i=1;i
      
       1){    if(dfs(i,0)==2)ans++;    return printf("%d",ans),0;  }}
      
     

　　

J. Zero Game

枚举一个区间，踢掉里面所有的$1$，然后剩下的机会都从外面拿$0$进来。

设$s[i]$表示前$i$个里有多少个$1$，那么对于区间$[l+1,r]$，首先要满足$s[r]-s[l]\leq k$，答案为$r-l-2(s[r]-s[l])+k$，即$(r-2s[r])-(l-2s[l])+k$。

枚举$l$，双指针出可行的$r$，然后用单调队列求出最优的$r$即可。

时间复杂度$O(nq)$。

#include
     
      #include
      
       #include
       
        using namespace std;const int N=1000010;int n,m,k,i,j,s[N],f[N],h,t,q[N],ans;char a[N];int main(){  scanf("%s",a+1);  n=strlen(a+1);  for(i=1;i<=n;i++)s[i]=s[i-1]+(a[i]=='1');  for(i=0;i<=n;i++)f[i]=i-s[i]*2;  scanf("%d",&m);  while(m--){    scanf("%d",&k);    h=1,t=0;    ans=-N*10;    for(i=j=0;i<=n;i++){      while(j<=n&&s[j]-s[i]<=k){        while(h<=t&&f[j]>=f[q[t]])t--;        q[++t]=j++;      }      while(h<=t&&q[h]<=i)h++;      if(h<=t)ans=max(ans,f[q[h]]-f[i]);    }    ans+=k;    ans=max(ans,0);    ans=min(ans,n-s[n]);    printf("%d\n",ans);  }}