The 13th Chinese Northeast Collegiate Programming Contest

题解：

solution

Code：

A. Apple Business

#include
#include
#include
using namespace std;
typedef long long ll;
const int N=100010;
int Case,len[N],n,m,i,mx,a[N],size[N],tmp[N];ll ans;
vectorv[N],f[N];
struct E{int u,v,c,w;}e[N];
inline bool cmp(const E&a,const E&b){return a.w>b.w;}
void dfs(int x,int y){
  if(x>n)return;
  if(y>mx)mx=y;
  tmp[y]=a[x];
  dfs(x<<1,y<<1);
  dfs(x<<1|1,y<<1|1);
}
inline void init(int o){
  mx=0;
  dfs(o,1);
  size[o]=mx;
  v[o].resize(mx+1);
  f[o].resize(mx+1);
  for(int i=1;i<=mx;i++)v[o][i]=f[o][i]=tmp[i];
}
inline int getid(int x,int y){
  int k=1<<(len[y]-len[x]);
  return (y&(k-1))|k;
}
inline void append(int A,int B,int C,int W){
  int x,y,o,t,m;
  for(x=A;x;x>>=1){
    o=getid(x,B);
    m=size[x];
    ll dp=f[x][o];
    for(y=o>>1;y;o=y,y>>=1){
      dp+=v[x][y];
      t=y<<1;
      if(t<=m&&t!=o&&f[x][t]<0)dp+=f[x][t];
      t=y<<1|1;
      if(t<=m&&t!=o&&f[x][t]<0)dp+=f[x][t];
    }
    if(dp>=1){
    o=getid(x,B);
    m=size[x];
    v[x][o]-=C;
    f[x][o]-=C;
    for(y=o>>1;y;y>>=1){
      f[x][y]=v[x][y];
      t=y<<1;
      if(t<=m&&f[x][t]<0)f[x][y]+=f[x][t];
      t=y<<1|1;
      if(t<=m&&f[x][t]<0)f[x][y]+=f[x][t];
    }
  }
}
int main(){
  for(i=1;i>1]+1;
  scanf("%d",&Case);
  while(Case--){
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)scanf("%d",&a[i]);
    for(i=1;i<=n;i++)init(i);
    for(i=1;i<=m;i++)scanf("%d%d%d%d",&e[i].u,&e[i].v,&e[i].c,&e[i].w);
    sort(e+1,e+m+1,cmp);
    ans=0;
    for(i=1;i<=m;i++)append(e[i].u,e[i].v,e[i].c,e[i].w);
    printf("%lld\n",ans);
  }
}

B. Balanced Diet

#include
#include
using namespace std;
typedef long long ll;
const int N=100010;
int T,n,m,i,j,k,l[N];ll f[N],s,A,B,d;
struct E{int a,b;}e[N];
inline bool cmp(const E&a,const E&b){return a.b==b.b?a.a>b.a:a.bl[e[i].b])f[k-i+1]+=e[k].a;
      }
    }
    for(i=1;i<=n;i++)f[i]+=f[i-1];
    A=f[1],B=1;
    for(i=2;i<=n;i++)if(f[i]*B>A*i)A=f[i],B=i;
    d=gcd(A,B);
    printf("%lld/%lld\n",A/d,B/d);
  }
}

C. Line-line Intersection

#include
#include
using namespace std;
typedef long long ll;
const int N=100010;
int Case,n,i;pair >f[N],g[N];
inline ll myabs(ll x){return x>0?x:-x;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline ll cal(pair >f[]){
  int i,j;
  ll ret=0;
  sort(f+1,f+n+1);
  for(i=1;i<=n;i=j){
    for(j=i;j<=n&&f[i]==f[j];j++);
    ret+=1LL*(j-i)*(j-i-1);
  }
  return ret/2;
}
int main(){
  scanf("%d",&Case);
  while(Case--){
    scanf("%d",&n);
    for(i=1;i<=n;i++){
      int x1,y1,x2,y2;
      scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
      int dx=x2-x1,dy=y2-y1;
      ll a,b,c;
      if(dx==0){
        a=1;
        b=0;
        c=-x1;
      }else{
        a=-dy;
        b=dx;
        c=1LL*dy*x1-1LL*dx*y1;
      }
      if(a<0)a=-a,b=-b,c=-c;
      if(a==0&&b<0)b=-b,c=-c;
      ll d=gcd(myabs(a),gcd(myabs(b),myabs(c)));
      a/=d,b/=d,c/=d;
      f[i].first=a,f[i].second.first=b,f[i].second.second=c;
      d=gcd(myabs(a),myabs(b));
      a/=d,b/=d;
      g[i].first=a,g[i].second.first=b,g[i].second.second=0;
    }
    printf("%lld\n",1LL*n*(n-1)/2-cal(g)+cal(f));
  }
}

D. Master of Data Structure

#include
#include
#include
const int N=500010,M=2010,K=M*4,inf=~0U>>1;
int Case,n,m,i,o,x,y,z,root,op[M][4];
int vip[N],g[N],v[N<<1],nxt[N<<1],ed,f[N],d[N],id[N],cnt;
int at[K],G[K],W[K],NXT[K],F[K],D[K];
int vv[K],ve[K];
inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}
inline void addedge(int x,int y,int z){NXT[y]=G[x];G[x]=y;W[y]=z;}
inline void umin(int&a,int b){a>b?(a=b):0;}
inline void umax(int&a,int b){a0?x:-x;}
inline void swap(int&a,int&b){int c=a;a=b;b=c;}
void dfs(int x){
  int deg=0;
  for(int i=g[x];i;i=nxt[i]){
    int u=v[i];
    if(u==f[x])continue;
    f[u]=x;
    d[u]=d[x]+1;
    dfs(u);
    if(!id[u])continue;
    deg++;
    id[x]^=id[u];
  }
  if(deg>1)vip[x]=1;
  if(!vip[x])return;
  id[x]=++cnt;
  at[cnt]=x;
  for(int i=g[x];i;i=nxt[i]){
    int u=v[i];
    if(u==f[x])continue;
    u=id[u];
    if(!u)continue;
    addedge(cnt,u,d[at[u]]-d[x]-1);
  }
}
void dfs2(int x,int y){
  F[x]=y;
  D[x]=D[y]+1;
  for(int i=G[x];i;i=NXT[i])dfs2(i,x);
}
int main(){
  scanf("%d",&Case);
  while(Case--){
    scanf("%d%d",&n,&m);
    for(ed=cnt=i=0;i<=n;i++)f[i]=d[i]=id[i]=vip[i]=g[i]=0;
    memset(G,0,sizeof G);
    memset(W,0,sizeof W);
    memset(F,0,sizeof F);
    memset(D,0,sizeof D);
    memset(vv,0,sizeof vv);
    memset(ve,0,sizeof ve);
    for(i=1;i=z)vv[x]-=z;
          if(ve[x]>=z)ve[x]-=z;
          x=F[x];
        }
        if(vv[x]>=z)vv[x]-=z;
      }
      if(o==4){
        long long ans=0;
        while(x!=y){
          if(D[x]


E. Minimum Spanning Tree

#include
#include
#include
using namespace std;
typedef long long ll;
const int N=100010;
int Case,n,i,j,x,y,z;vectorf[N];ll ans;
int main(){
  scanf("%d",&Case);
  while(Case--){
    scanf("%d",&n);
    for(i=1;i<=n;i++)f[i].clear();
    for(i=1;i1){
      sort(f[i].begin(),f[i].end());
      for(j=1;j


F. Mini-game Before Contest

#include
const int N=100010,M=200010,K=1<<24;
int Case,n,m,i,j,k,S,A,B,x,y,z,o,deg[N],g[N],v[M],nxt[M],ed;
bool isactor[6],isa[6],ismin[6];
char tmp[9];
int f[N][6],w[N][6][3];
int q[K+5],h,t;
inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}
inline void ext(int x,int y,int B){
  int A=f[x][y];
  if(A==B)return;
  t=(t+1)&(K-1);
  q[t]=(x<<7)|(y<<4)|(A<<2)|B;
  f[x][y]=B;
}
inline void check(int x,int y){
  int ret;
  if(ismin[y]){
    if(w[x][y][0])ret=0;
    else if(w[x][y][1])ret=1;
    else ret=2;
  }else{
    if(w[x][y][2])ret=2;
    else if(w[x][y][1])ret=1;
    else ret=0;
  }
  ext(x,y,ret);
}
int main(){
  scanf("%d",&Case);
  while(Case--){
    scanf("%d%d",&n,&m);
    for(ed=i=0;i<=n;i++)deg[i]=g[i]=0;
    while(m--)scanf("%d%d",&x,&y),deg[x]++,add(y,x);
    scanf("%s",tmp);
    for(i=0;i<6;i++)isa[i]=tmp[i]=='A';
    scanf("%s",tmp);
    for(i=0;i<6;i++)isactor[i]=tmp[i]=='1';
    for(i=0;i<6;i++)ismin[i]=isa[i]^isactor[i];
    for(i=1;i<=n;i++)for(j=0;j<6;j++){
      f[i][j]=1;
      for(k=0;k<3;k++)w[i][j][k]=0;
      w[i][j][1]=deg[i];
    }
    h=1,t=0;
    for(i=1;i<=n;i++)if(!deg[i])for(j=0;j<6;j++){
      if(isa[j])ext(i,j,2);
      else ext(i,j,0);
    }
    while(h!=((t+1)&(K-1))){
      S=q[h];
      h=(h+1)&(K-1);
      x=S>>7,y=S>>4&7,A=S>>2&3,B=S&3;
      o=(y+5)%6;
      for(i=g[x];i;i=nxt[i]){
        z=v[i];
        w[z][o][A]--;
        w[z][o][B]++;
        check(z,o);
      }
    }
    for(i=1;i<=n;i++){
      if(f[i][0]==0)putchar('A');
      if(f[i][0]==1)putchar('D');
      if(f[i][0]==2)putchar('B');
    }
    puts("");
  }
}



G. Radar Scanner

#include
#include
using namespace std;
typedef long long ll;
const int N=100010;
int Case,n,m,i,j,e[N<<1];
struct P{int l,r;}a[N],b[N];
inline ll solve(P*a){
  m=0;
  ll ans=0;
  for(i=1;i<=n;i++){
    e[++m]=a[i].l;
    e[++m]=a[i].r;
    ans-=a[i].r-a[i].l;
  }
  sort(e+1,e+m+1);
  for(i=1;i<=m;i++)ans+=abs(e[i]-e[n]);
  return ans/2;
}
int main(){
  scanf("%d",&Case);
  while(Case--){
    scanf("%d",&n);
    for(i=1;i<=n;i++)scanf("%d%d%d%d",&a[i].l,&b[i].l,&a[i].r,&b[i].r);
    printf("%lld\n",solve(a)+solve(b));
  }
}



H. Skyscraper

#include
typedef long long ll;
const int N=100010;
int Case,n,m,i,op,x,y;ll z,a[N],b[N],f[N],g[N];
inline void ins(ll*f,int x,ll p){for(;x<=n;x+=x&-x)f[x]+=p;}
inline ll ask(ll*f,int x){ll t=0;for(;x;x-=x&-x)t+=f[x];return t;}
int main(){
  scanf("%d",&Case);
  while(Case--){
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)scanf("%lld",&a[i]);
    for(i=1;i<=n;i++)b[i]=a[i]-a[i-1];
    for(i=1;i<=n;i++)f[i]=g[i]=0;
    for(i=1;i<=n;i++){
      ins(f,i,b[i]);
      if(b[i]>0)ins(g,i,b[i]);
    }
    while(m--){
      scanf("%d%d%d",&op,&x,&y);
      if(op==1){
        y++;
        scanf("%lld",&z);
        ins(f,x,z);
        ins(f,y,-z);
        if(b[x]>0)ins(g,x,-b[x]);
        if(b[y]>0)ins(g,y,-b[y]);
        b[x]+=z;
        b[y]-=z;
        if(b[x]>0)ins(g,x,b[x]);
        if(b[y]>0)ins(g,y,b[y]);
      }else{
        printf("%lld\n",ask(f,x)+ask(g,y)-ask(g,x));
      }
    }
  }
}



I. Temperature Survey

#include
#include
#include