2016-2017 National Taiwan University World Final Team Selection Contest

A. Hacker Cups and Balls

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

#include<cstdio>

#include<algorithm>

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;

    if(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<cstdio>

#include<algorithm>

#include<cstdlib>

using namespace std;

const int N=1010;

int n,i,j,x,rk[N],s[N][N],ans;char ch[N];

pair<int,int>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<n)NIE();

  for(i=1;i<=n;i++)ans=max(ans,f[i]);

  printf("%d",ans);

}

C. Crazy Dreamoon

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

#include<cstdio>

#include<cmath>

#include<algorithm>

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<b.x;

  return a.y<b.y;

}

inline int sgn(int x){

  if(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<D){//up

    int L=B,R=B;

    //(i..i+1)(L..L+1)

    //(i..i+1)(R..R+1)

    for(int i=A;i<C;i++){

      while(L<2000&&!check(i,L))L++;

      if(L==2000)return;

      if(R<L)R=L;

      while(R<1999&&check(i,R+1))R++;

      for(int j=L;j<=R;j++)f[i][j]=1;

    }

  }else{//down

    int L=B-1,R=B-1;

    //(i..i+1)(L..L+1)

    //(i..i+1)(R..R+1)

    for(int i=A;i<C;i++){

      while(R>=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<cstdio>

#include<cmath>

#include<algorithm>

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]<f[now])now=x;

}

inline void FFT(comp a[],int n,int t){

  for(int i=1,j=0;i<n-1;i++){

    for(int s=n;j^=s>>=1,~j&s;);

    if(i<j)swap(a[i],a[j]);

  }

  for(int d=0;(1<<d)<n;d++){

    int m=1<<d,m2=m<<1;

    double o=pi/m*t;comp _w(cos(o),sin(o));

    for(int i=0;i<n;i+=m2){

      comp w(1,0);

      for(int j=0;j<m;j++){

        comp &A=a[i+j+m],&B=a[i+j],t=w*A;

        A=B-t;B=B+t;w=w*_w;

      }

    }

  }

  if(t==-1)for(int i=0;i<n;i++)a[i].r/=n;

}

inline void cal(int t){

  int i,k;

  for(k=1;k<m+m;k<<=1);

  for(i=0;i<k;i++)A[i]=B[i]=comp();

  for(i=1;i<=m;i++)A[i]=comp(a[i],0),B[i-1]=comp(a[i],0);

  FFT(A,k,1),FFT(B,k,1);

  for(i=0;i<k;i++)A[i]=A[i]*B[i];

  FFT(A,k,-1);

  for(i=2;i<m+m;i++){

    ll o=(ll)(A[i].r+0.5);

    if(t>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<n;i++)scanf("%d%d",&x,&y),add(x,y),add(y,x);

  f[0]=size=n,findroot(1,now=0),solve(now);

  for(ans=n,inv[1]=1,i=2;i<=n;i++){

    cnt[i]%=P;

    inv[i]=1LL*(P-inv[P%i])*(P/i)%P;

    ans=(cnt[i]*inv[i]+ans)%P;

  }

  for(i=2;i<=n;i++)ans=1LL*ans*i%P;

  printf("%d",ans);

}

E. Lines Game

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

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

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

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

#include<cstdio>

#include<algorithm>

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]<a[y];}

void build(int x,int a,int b){

  v[x]=inf;

  if(a==b)return;

  int mid=(a+b)>>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]<inf)f[l]+=w[l];

    return;

  }

  int mid=(l+r)>>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]]<a[qb[i]]){

      while(ta&&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]<sb[tb])tb--;

    f[qb[i]]=min(f[qb[i]],ask(1,0,n,a[sb[tb]],a[qb[i]]));

    sb[++tb]=qb[i];

  }

  for(i=1;i<=ta;i++)change(1,0,n,a[sa[i]],inf);

  solve(mid+1,r);

}

int main(){

  scanf("%d",&n);

  for(i=1;i<=n;i++)scanf("%d",&a[i]);

  for(i=1;i<=n;i++)scanf("%d",&w[i]);

  n++;

  a[n]=n;

  for(i=1;i<=n;i++)f[i]=inf;

  build(1,0,n);

  solve(0,n);

  printf("%d",f[n]);

}

F. Lonely Dreamoon 2

将序列排序。

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

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

#include<cstdio>

#include<algorithm>

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<n;i++)scanf("%d",&w[i]);

  sort(w,w+n);

  if(n&1){

    m=n/2;

    for(i=j=m;i<n;i++)if(w[i]-w[i-m]<w[j]-w[j-m])j=i;

    x=j,y=(x+m)%n;

    for(i=0;i<n;i+=2,x=(x+n-1)%n)a[i]=x;

    for(i=1;i<n;i+=2,y=(y+n-1)%n)a[i]=y;

  }else{

    for(i=1,j=0;i<n;i+=2,j++)a[i]=j;

    for(i=0;i<n;i+=2,j++)a[i]=j;

  }

  for(i=0;i<n;i++)printf("%d ",w[a[i]]);

}

G. Dreamoon and NightMarket

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

#include<cstdio>

#include<algorithm>

#include<queue>

#include<vector>

using namespace std;

typedef long long ll;

typedef pair<ll,int>P;

int n,m,i,a[200010];P t;priority_queue<P,vector<P>,greater<P> >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<cstdio>

#include<algorithm>

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<cstdio>

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<n;i++)scanf("%d%d",&x,&y),add(x,y),add(y,x);

  for(i=1;i<=n;i++)if(d[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<cstdio>

#include<cstring>

#include<algorithm>

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);

  }

}

巴特西

2016-2017 National Taiwan University World Final Team Selection Contest

最新文章

热门文章