2019-2020 ICPC Asia Hong Kong Regional Contest

题解：

https://files.cnblogs.com/files/clrs97/19HKEditorial-V1.zip

Code：（Part）

A. Axis of Symmetry

#include<cstdio>

#include<algorithm>

#include<vector>

using namespace std;

typedef long long ll;

const int N=100010,inf=1000000010;

int Case,n,cl,ce,cp,i,j,k,xmi,xma,ymi,yma,ama,ami,sma,smi;vector<vector<int> >ans;

struct Rect{int xl,xr,yl,yr;}rect[N];

struct Line{

  int x1,y1,x2,y2;

  Line(){}

  Line(int _x1,int _y1,int _x2,int _y2){

    x1=_x1,y1=_y1,x2=_x2,y2=_y2;

    fix();

  }

  void fix(){

    if(x1>x2)swap(x1,x2),swap(y1,y2);

    if(x1==x2&&y1>y2)swap(y1,y2);

  }

}a[N<<2],b[N<<2];

inline bool cmpl(const Line&a,const Line&b){

  if(a.x1!=b.x1)return a.x1<b.x1;

  if(a.y1!=b.y1)return a.y1<b.y1;

  if(a.x2!=b.x2)return a.x2<b.x2;

  return a.y2<b.y2;

}

struct E{int x,y,t;E(){}E(int _x,int _y,int _t){x=_x,y=_y,t=_t;}}e[N<<2];

struct P{int l,r;P(){}P(int _l,int _r){l=_l,r=_r;}}pool[N];

inline bool cmpe(const E&a,const E&b){

  if(a.x!=b.x)return a.x<b.x;

  return a.y<b.y;

}

inline void solve(int l,int r){

  int i,j,s=0,L=-inf,R=-inf;

  for(cp=0,i=l;i<=r;i=j){

    if(s==1)R=e[i].y;

    else{

      if(L<R)pool[++cp]=P(L,R);

      L=e[i].y;

    }

    for(j=i;j<=r&&e[i].y==e[j].y;j++)s+=e[j].t;

  }

  if(L<R)pool[++cp]=P(L,R);

}

inline void umin(int&a,int b){a>b?(a=b):0;}

inline void umax(int&a,int b){a<b?(a=b):0;}

inline void check(ll A,ll B,ll C){

  int i,d=A*A+B*B;ll x,y,X,Y;

  for(i=1;i<=cl;i++){

    x=a[i].x1,y=a[i].y1;

    X=2*A*(A*x+B*y-C),Y=2*B*(A*x+B*y-C);

    if(X%d||Y%d)return;

    b[i].x1=x-X/d,b[i].y1=y-Y/d;

    x=a[i].x2,y=a[i].y2;

    X=2*A*(A*x+B*y-C),Y=2*B*(A*x+B*y-C);

    if(X%d||Y%d)return;

    b[i].x2=x-X/d,b[i].y2=y-Y/d;

    b[i].fix();

  }

  sort(b+1,b+cl+1,cmpl);

  for(i=1;i<=cl;i++){

    if(a[i].x1!=b[i].x1)return;

    if(a[i].y1!=b[i].y1)return;

    if(a[i].x2!=b[i].x2)return;

    if(a[i].y2!=b[i].y2)return;

  }

  if(C%2==0)C/=2;else A*=2,B*=2;

  vector<int>v;

  v.push_back(A);

  v.push_back(B);

  v.push_back(C);

  ans.push_back(v);

}

inline void up(int x,int y){

  umax(xma,x);

  umin(xmi,x);

  umax(yma,y);

  umin(ymi,y);

  umax(ama,x+y);

  umin(ami,x+y);

  umax(sma,x-y);

  umin(smi,x-y);

}

int main(){

  scanf("%d",&Case);

  while(Case--){

    scanf("%d",&n);

    cl=0;

    xma=yma=ama=sma=-inf;

    xmi=ymi=ami=smi=inf;

    for(i=1;i<=n;i++){

      scanf("%d%d%d%d",&rect[i].xl,&rect[i].yl,&rect[i].xr,&rect[i].yr);

      rect[i].xl*=2;

      rect[i].yl*=2;

      rect[i].xr*=2;

      rect[i].yr*=2;

      up(rect[i].xl,rect[i].yl);

      up(rect[i].xl,rect[i].yr);

      up(rect[i].xr,rect[i].yl);

      up(rect[i].xr,rect[i].yr);

    }

    ce=0;

    for(i=1;i<=n;i++){

      e[++ce]=E(rect[i].xl,rect[i].yl,1);

      e[++ce]=E(rect[i].xl,rect[i].yr,-1);

      e[++ce]=E(rect[i].xr,rect[i].yl,1);

      e[++ce]=E(rect[i].xr,rect[i].yr,-1);

    }

    sort(e+1,e+ce+1,cmpe);

    for(i=1;i<=ce;i=j){

      for(j=i;j<=ce&&e[i].x==e[j].x;j++);

      solve(i,j-1);

      for(k=1;k<=cp;k++)a[++cl]=Line(e[i].x,pool[k].l,e[i].x,pool[k].r);

    }

    ce=0;

    for(i=1;i<=n;i++){

      e[++ce]=E(rect[i].yl,rect[i].xl,1);

      e[++ce]=E(rect[i].yl,rect[i].xr,-1);

      e[++ce]=E(rect[i].yr,rect[i].xl,1);

      e[++ce]=E(rect[i].yr,rect[i].xr,-1);

    }

    sort(e+1,e+ce+1,cmpe);

    for(i=1;i<=ce;i=j){

      for(j=i;j<=ce&&e[i].x==e[j].x;j++);

      solve(i,j-1);

      for(k=1;k<=cp;k++)a[++cl]=Line(pool[k].l,e[i].x,pool[k].r,e[i].x);

    }

    sort(a+1,a+cl+1,cmpl);

    ans.clear();

    check(1,1,(ami+ama)/2);

    check(1,0,(xmi+xma)/2);

    check(1,-1,(smi+sma)/2);

    check(0,1,(ymi+yma)/2);

    printf("%d\n",(int)ans.size());

    sort(ans.begin(),ans.end());

    reverse(ans.begin(),ans.end());

    for(i=0;i<ans.size();i++)for(j=0;j<3;j++){

      if(i||j)putchar(' ');

      printf("%d",ans[i][j]);

    }

    puts("");

  }

}

B. Binary Tree

#include<cstdio>

int Case,n,i,x,y;

int main(){

  scanf("%d",&Case);

  while(Case--){

    scanf("%d",&n);

    for(i=1;i<n;i++)scanf("%d%d",&x,&y);

    puts(n&1?"Alice":"Bob");

  }

}

D. Defining Labels

#include<cstdio>

int Case,k,x;

void print(int x){

  if(x>k)print((x-1)/k);

  x%=k;

  if(!x)x=k;

  printf("%d",x+9-k);

}

int main(){

  scanf("%d",&Case);

  while(Case--){

    scanf("%d%d",&k,&x);

    print(x);

    puts("");

  }

}

G. Game Design

#include<cstdio>

const int N=100010;

int k,tot,i,f[N],c[N],g[N];

int solve(int k,int o){

  int x=++tot;

  f[x]=o;

  if(k<=2){

    int y=++tot;

    f[y]=x;

    c[y]=1;

    g[x]=1;

    c[x]=3-k;

    return g[x]=1;

  }

  g[x]=solve(k/2,x)+solve(2,x);

  c[x]=g[x]+(k%2==0);

  return g[x];

}

int main(){

  scanf("%d",&k);

  solve(k,0);

  printf("%d\n",tot);

  for(i=2;i<=tot;i++)printf("%d%c",f[i],i<tot?' ':'\n');

  for(i=1;i<=tot;i++)printf("%d%c",c[i],i<tot?' ':'\n');

}

H. Hold the Line

#include<cstdio>

#include<algorithm>

using namespace std;

const int N=500010,M=1000010,K=2100005,inf=~0U>>1;

int Case,n,m,i,j,op,x,y,z,pool[M],cp,e[M][4],val[N],ap[N];

int pos[M],st[K],en[K],q[11000005],cq,cnt[M];

int g[N],nxt[M],ans[M],L,H,T,ANS,TMP;

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

  st[x]=cq+1;

  en[x]=cq;

  cq+=cnt[b]-cnt[a-1];

  if(a==b){

    pos[a]=x;

    return;

  }

  int mid=(a+b)>>1;

  build(x<<1,a,mid),build(x<<1|1,mid+1,b);

}

inline void ins(int x){

  int y=ap[x];

  if(y>m)return;

  for(int o=pos[val[x]];o;o>>=1){

    int S=st[o],T=en[o];

    while(S<=T&&ap[q[T]]>=y)T--;

    q[++T]=x;

    en[o]=T;

  }

}

inline bool check(int x){

  int l=st[x],r=en[x],mid;

  while(l<=r){

    mid=(l+r)>>1;

    if(q[mid]>=L&&ap[q[mid]]<=T)return 1;

    if(q[mid]<L)l=mid+1;else r=mid-1;

  }

  return 0;

}

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

  if(TMP||st[x]>en[x])return;

  if(b<=H){

    if(!check(x))return;

    if(a==b){

      TMP=a;

      return;

    }

  }

  int mid=(a+b)>>1;

  if(H>mid)askl(x<<1|1,mid+1,b);

  askl(x<<1,a,mid);

}

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

  if(TMP||st[x]>en[x])return;

  if(H<=a){

    if(!check(x))return;

    if(a==b){

      TMP=a;

      return;

    }

  }

  int mid=(a+b)>>1;

  if(H<=mid)askr(x<<1,a,mid);

  askr(x<<1|1,mid+1,b);

}

inline void query(int x){

  L=e[x][1];

  H=e[x][3];

  T=x;

  ANS=inf;

  TMP=0;

  askl(1,1,cp);

  if(TMP)ANS=pool[H]-pool[TMP];

  TMP=0;

  askr(1,1,cp);

  if(TMP)ANS=min(ANS,pool[TMP]-pool[H]);

  ans[x]=ANS<inf?ANS:-1;

}

int main(){

  scanf("%d",&Case);

  while(Case--){

    scanf("%d%d",&n,&m);

    for(i=1;i<=n;i++)ap[i]=m+1,g[i]=0;

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

      scanf("%d%d",&op,&x);

      if(op==0)scanf("%d",&z);else scanf("%d%d",&y,&z);

      e[i][0]=op;

      e[i][1]=x;

      e[i][2]=y;

      e[i][3]=z;

      pool[i]=z;

    }

    sort(pool+1,pool+m+1);

    for(cp=0,i=1;i<=m;i++)if(pool[i]>pool[i-1])pool[++cp]=pool[i];

    for(i=1;i<=cp;i++)cnt[i]=0;

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

      e[i][3]=lower_bound(pool+1,pool+cp+1,e[i][3])-pool;

      x=e[i][1];

      y=e[i][2];

      z=e[i][3];

      if(e[i][0]==0){

        val[x]=z;

        ap[x]=i;

        cnt[z]++;

      }else{

        nxt[i]=g[y];

        g[y]=i;

      }

    }

    for(i=1;i<=cp;i++)cnt[i]+=cnt[i-1];

    cq=0;

    build(1,1,cp);

    for(i=1;i<=n;i++){

      ins(i);

      for(j=g[i];j;j=nxt[j])query(j);

    }

    for(i=1;i<=m;i++)if(e[i][0]==1)printf("%d\n",ans[i]);

  }

}

I. Incoming Asteroids

#include<cstdio>

#include<queue>

#include<vector>

#include<algorithm>

using namespace std;

typedef long long ll;

typedef pair<int,int>P;

typedef pair<ll,P>PI;

const int N=200010,M=200010;

int n,m,tot,cnt,op,i,x,y,pool[M],cp;

int num[M],e[M][3],goal[M],ver[M];ll base[M][3];bool del[M];

priority_queue<PI,vector<PI>,greater<PI> >f[N];ll tag[N];

inline void deploy(int x){

  if(del[x])return;

  int deg=num[x];

  ll now=0;

  for(int i=0;i<deg;i++)now+=tag[e[x][i]]-base[x][i];

  if(now>=goal[x]){

    del[x]=1;

    pool[++cp]=x;

    return;

  }

  goal[x]-=now;

  ver[x]=++cnt;

  int o=(goal[x]+deg-1)/deg;

  for(int i=0;i<deg;i++){

    int y=e[x][i];

    base[x][i]=tag[y];

    f[y].push(PI(tag[y]+o,P(x,cnt)));

  }

}

inline void maketag(int x,int y){

  tag[x]+=y;

  while(!f[x].empty()){

    PI t=f[x].top();

    if(t.first>tag[x])return;

    f[x].pop();

    if(t.second.second==ver[t.second.first])deploy(t.second.first);

  }

}

int main(){

  scanf("%d%d",&n,&m);

  while(m--){

    scanf("%d",&op);

    if(op==1){

      tot++;

      scanf("%d%d",&goal[tot],&num[tot]);

      goal[tot]^=cp;

      for(i=0;i<num[tot];i++){

        scanf("%d",&e[tot][i]);

        e[tot][i]^=cp;

        base[tot][i]=tag[e[tot][i]];

      }

      deploy(tot);

    }else{

      scanf("%d%d",&x,&y);

      x^=cp,y^=cp;

      cp=0;

      maketag(x,y);

      printf("%d",cp);

      sort(pool+1,pool+cp+1);

      for(i=1;i<=cp;i++)printf(" %d",pool[i]);

      puts("");

    }

  }

}

J. Junior Mathematician

#include<cstdio>

#include<cstring>

const int N=5105,M=65,P=1000000007;

int Case,m,n,i,j,k,o,x,no,tmp,ret,f[N][M][M][2],p[N];char a[N],b[N];

inline void up(int&a,int b){a=a+b<P?a+b:a+b-P;}

inline int solve(char*a,int r){

  n=strlen(a);

  for(i=0;i<n;i++)a[i]-='0';

  for(p[0]=i=1;i<=n;i++)p[i]=10*p[i-1]%m;

  for(i=1;i<=n;i++)for(j=0;j<m;j++)for(k=0;k<m;k++)for(o=0;o<2;o++)f[i][j][k][o]=0;

  f[0][0][0][1]=1;

  for(i=0;i<n;i++)for(j=0;j<m;j++)for(k=0;k<m;k++)for(o=0;o<2;o++){

    tmp=f[i][j][k][o];

    if(!tmp)continue;

    for(x=0;x<10;x++){

      if(o){

        if(x>a[i])break;

        no=x==a[i];

      }else no=0;

      up(f[i+1][((j+x*(k-p[n-i-1]))%m+m)%m][(k+x)%m][no],tmp);

    }

  }

  for(ret=j=0;j<m;j++)for(k=0;k<=r;k++)up(ret,f[n][0][j][k]);

  return ret;

}

int main(){

  scanf("%d",&Case);

  while(Case--){

    scanf("%s%s%d",a,b,&m);

    printf("%d\n",(solve(b,1)-solve(a,0)+P)%P);

  }

}

K. Key Project

#include<cstdio>

#include<algorithm>

#include<vector>

using namespace std;

typedef long long ll;

const int N=805,inf=1000000010;

int n,m,i,x,y,ca[N],cb[N],ata[N],atb[N],va[N],vb[N];

int d[N],fl[N],fr[N];

vector<int>a[N],b[N];

long long ans;

inline void fix(int x){

  if(ata[x]>=ca[x])va[x]=inf;else va[x]=a[x][ata[x]];

  if(atb[x]>=cb[x])vb[x]=inf;else vb[x]=b[x][atb[x]];

}

inline void aug(){

  int i,best=inf,A,B,o,tmp;

  //A->B

  for(tmp=inf,i=1;i<=n;i++){

    //i as A

    if(va[i]<tmp){

      tmp=va[i];

      o=i;

    }

    //i as B

    if(tmp+vb[i]<best){

      best=tmp+vb[i];

      A=o;

      B=i;

    }

    //move right

    if(tmp<inf&&i<n){

      if(fr[i])tmp-=d[i];

      else tmp+=d[i];

    }

  }

  //B<-A

  for(tmp=inf,i=n;i;i--){

    //i as A

    if(va[i]<tmp){

      tmp=va[i];

      o=i;

    }

    //i as B

    if(tmp+vb[i]<best){

      best=tmp+vb[i];

      A=o;

      B=i;

    }

    //move right

    if(tmp<inf&&i>1){

      if(fl[i-1])tmp-=d[i-1];

      else tmp+=d[i-1];

    }

  }

  ans+=best;

  printf("%lld\n",ans);

  ata[A]++,atb[B]++;

  fix(A),fix(B);

  if(A<B)for(i=A;i<B;i++){

    if(fr[i])fr[i]--;

    else fl[i]++;

  }

  if(A>B)for(i=B;i<A;i++){

    if(fl[i])fl[i]--;

    else fr[i]++;

  }

}

//f>0 means it is -

int main(){

  scanf("%d%d",&n,&m);

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

  for(i=1;i<=m;i++)scanf("%d%d",&x,&y),a[x].push_back(y);//1e8

  for(i=1;i<=m;i++)scanf("%d%d",&x,&y),b[x].push_back(y);//1e8

  for(i=1;i<=n;i++){

    sort(a[i].begin(),a[i].end());

    sort(b[i].begin(),b[i].end());

    ca[i]=a[i].size();

    cb[i]=b[i].size();

    fix(i);

  }

  while(m--)aug();

}

巴特西

2019-2020 ICPC Asia Hong Kong Regional Contest

最新文章

热门文章