[AMPPZ2014]The Lawyer

记录每天结束的最早的会议以及开始的最晚的会议即可。

#include
     
      #define N 500010int n,m,i,d,a[N],b[N],st[21],en[21];inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}int main(){  for(read(n),read(m),i=1;i<=n;i++){    read(a[i]),read(b[i]),read(d);    if(!en[d]||b[en[d]]>b[i])en[d]=i;    if(!st[d]||a[st[d]]
      
       =a[st[i]])puts("NIE");else printf("TAK %d %d\n",en[i],st[i]);  return 0;}
      
     

　　

[AMPPZ2014]Petrol

一遍spfa求出d[x]表示离x最近的加油站到x的距离。

对于每条边(x,y,w)，将边权重置为d[x]+d[y]+w。

然后将边和询问按照权值从小到大排序，每次将所有边权小于等于询问的边加入，查询两点是否连通，用并查集维护。

#include
     
      #include
      
       const int N=200010,M=1048575,inf=~0U>>1;int n,s,m,T,i,x,c[N],g[N],nxt[N<<1],v[N<<1],w[N<<1],ed,h=1,t,size,q[M+1],in[N],d[N],f[N],ans[N];struct E{int x,y,z,id;}e[N],Q[N];inline bool cmp(E a,E b){return a.z
       
        ='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}int main(){  for(read(n),read(s),read(m),i=1;i<=s;i++)read(c[i]);  for(i=1;i<=m;i++)read(e[i].x),read(e[i].y),read(e[i].z),add(e[i].x,e[i].y,e[i].z),add(e[i].y,e[i].x,e[i].z);  for(i=1;i<=n;i++)d[i]=inf,f[i]=i;  for(i=1;i<=s;i++)d[c[i]]=0,in[c[i]]=1,q[++t]=c[i],size++;  while(size)for(i=g[x=q[h++]],h&=M,size--,in[x]=0;i;i=nxt[i])if(d[x]+w[i]
       
      
     

　　

[AMPPZ2014]The Prices

f[S]=在一家店里购买S集合的价格的最小值

g[S]=购买S集合的价格的最小值

g[i]=min(f[j]+g[i^j]),j是i的子集

时间复杂度为$O(n2^m+3^m)$。

#include
     
      int n,m,i,j,a[16],f[1<<16],g[1<<16],inf=1000000000;inline void min(int&a,int b){if(a>b)a=b;}void dfs(int x,int sum,int S){min(f[S],sum);for(;x
      
       <
      
     

　　

[AMPPZ2014]Divisors

设f[i]=i出现次数，则ans=sum(f[i]*f[j],i|j)-n，时间复杂度为$O(n\log n)$。

#include
     
      int n,i,j,k,f[2000001];long long ans;inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}int main(){  for(read(n),ans=-n;n--;f[i]++)read(i),k=k>i?k:i;  for(i=1;i<=k;i++)for(j=i;j<=k;j+=i)ans+=(long long)f[i]*f[j];  return printf("%lld",ans),0;}
     

　　

[AMPPZ2014]Euclidean Nim

如果gcd(p,q)不整除n，则永远不会停止

若p==q，则p必胜

否则p,q,n/=gcd，假设p<q

若q是先手且n<q，则q必败

若p是先手且n>=p，则p必胜

若p是先手且n<p，则当(q-p)|n时p必败，否则p必胜

若q是先手且n>=q，设z=n%q，若(q-p)|z且z<p，则q必胜否则q必败

#include
     
      int T,p,q,n,g;int gcd(int a,int b){return b?gcd(b,a%b):a;}void work(){  g=gcd(p,q);  if(n%g){puts("R");return;}  if(p==q){puts("E");return;}  p/=g,q/=g,n/=g;  if(p
      
       =p){puts("E");return;}    if(n%(q-p)==0)puts("P");else puts("E");  }else{    if(n
      
     

　　

[AMPPZ2014]Pillars

首先无视障碍物构造一组解，然后根据障碍物的位置调整，时间复杂度为$O(nm+f)$。

#include
     
      int n,m,f,i,j,x,y;char a[1010][1010];int main(){  scanf("%d%d%d",&n,&m,&f);  for(i=1;i<=n;i++)for(j=1;j<=m;j++)a[i][j]=i&1?'D':'G';  for(i=1;i<=n;i++){    if(i
      
       1&&(i&1))a[i][2]='L';    if(!(i&1))a[i][m]='L';  }  for(i=0;i
      
     

　　

[AMPPZ2014]Global Warming

[l1[i],r1[i]]里i是唯一的最小值，[l2[i],r2[i]]里i是唯一的最大值，用单调队列$O(n)$求出。

枚举最小值的位置i，则最大值的位置j须满足l1[i]<=j<=r1[i]，l2[j]<=l1[i]，r2[j]>=i

求出满足条件的最大的r2[j]，则此时区间长度为min(r1[i],r2[j])-l1[i]+1，开头为l1[i]

排序后用线段树维护，然后将l1[i]与l2[i]交换、r1[i]与r2[i]交换再求一次即可求出最优解

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

#include
     
      const int N=500010,M=1048577;int n,i,j,a[N],q[N],t,l1[N],r1[N],l2[N],r2[N],len=1,st=1,v[M];struct E{int v,w;E*nxt;}pool[N<<1],*cur=pool,*g[N],*h[N],*p;inline void addg(int x,int y,int z){p=cur++;p->v=y;p->w=z;p->nxt=g[x];g[x]=p;}inline void addh(int x,int y,int z){p=cur++;p->v=y;p->w=z;p->nxt=h[x];h[x]=p;}inline void read(int&a){  char c;bool f=0;a=0;  while(!((((c=getchar())>='0')&&(c<='9'))||(c=='-')));  if(c!='-')a=c-'0';else f=1;  while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';  if(f)a=-a;}inline void swap(int&a,int&b){int c=a;a=b;b=c;}inline void max(int&a,int b){if(a
      
       >1,x<<=1;    if(c<=mid)b=mid;else x|=1,a=mid+1;  }}void ask(int x,int a,int b,int c,int d){  if(c<=a&&b<=d){max(j,v[x]);return;}  int mid=(a+b)>>1;  if(c<=mid)ask(x<<1,a,mid,c,d);  if(d>mid)ask(x<<1|1,mid+1,b,c,d);}void work(){  for(i=1;i<=n;i++)addg(l1[i],i,r1[i]),addh(l2[i],i,r2[i]);  for(i=1;i<=n;i++){    for(p=h[i];p;p=p->nxt)ins(p->v,p->w);    for(p=g[i];p;p=p->nxt){      j=0,ask(1,1,n,i,p->w);      if(j
       
        v)continue;      if((t=(p->w
        
         w:j)-i+1)>len)len=t,st=i;else if(t==len&&i
         
          a[i])t--;    l1[i]=q[t]+1;  }  for(q[t=0]=n+1,i=n;i;q[++t]=i--){    while(t&&a[q[t]]>a[i])t--;    r1[i]=q[t]-1;  }  for(q[t=0]=0,i=1;i<=n;q[++t]=i++){    while(t&&a[q[t]]
         
        
       
      
     

　　

[AMPPZ2014]Hit of the Season

首先如果左半边'*'更多，那么把整个串翻转过来。

从小到大枚举长度$L$，设$f[i]$表示从$i$开始匹配是否成功。

如果$L+L\geq n$，那么只需要看看$f[n-L+1]$是否为1即可。

否则，暴力搜索模板串中的'*'，每填一个就更新一下所有匹配位置，如果$n-L+1$失配或者相邻距离大于$L$，则不可行。

时间复杂度$O(n(n+3^{10}))$。

#include
     
      #include
      
       #include
       
        using namespace std;const int N=3010,M=12;int T,n,m,L,i,all,rev,f[N],b[M],q[M][N],t[M];char a[N],ans[N];inline bool check(char a,char b){return a==b||a=='*'||b=='*';}bool dfs(int x){  int i;  if(q[x][t[x]]
        
         L)return 0;  if(x==m)return 1;  ans[b[x+1]]='R',t[x+1]=0;  for(i=1;i<=t[x];i++)if(check(a[q[x][i]+b[x+1]-1],'R'))q[x+1][++t[x+1]]=q[x][i];  if(dfs(x+1))return 1;  ans[b[x+1]]='G',t[x+1]=0;  for(i=1;i<=t[x];i++)if(check(a[q[x][i]+b[x+1]-1],'G'))q[x+1][++t[x+1]]=q[x][i];  if(dfs(x+1))return 1;  ans[b[x+1]]='B',t[x+1]=0;  for(i=1;i<=t[x];i++)if(check(a[q[x][i]+b[x+1]-1],'B'))q[x+1][++t[x+1]]=q[x][i];  return dfs(x+1);}void solve(){  scanf("%s",a+1);n=strlen(a+1);  for(all=0,i=1;i<=n;i++)if(a[i]=='*')all++;  for(i=1;i<=n/2;i++)if(a[i]=='*')all-=2;  if(all<0)rev=1,reverse(a+1,a+n+1);else rev=0;  for(i=1;i<=n;i++)f[i]=1,ans[i]=a[i];  for(m=0,L=1;L<=n;L++){    for(i=1;i<=n-L+1;i++)if(f[i])if(!check(a[L],a[i+L-1]))f[i]=0;    if(L+L>=n){      if(f[n-L+1]){        for(i=1;i<=L;i++)if(a[i]=='*')ans[i]=a[n-L+i];        break;      }    }else{      if(a[L]=='*')b[++m]=L;      for(t[0]=0,i=1;i<=n-L+1;i++)if(f[i])q[0][++t[0]]=i;      if(dfs(0))break;    }  }  if(rev)reverse(ans+1,ans+L+1);  for(i=1;i<=L;i++)putchar(ans[i]=='*'?'R':ans[i]);puts("");}int main(){  scanf("%d",&T);  while(T--)solve();  return 0;}
        
       
      
     

　　

[AMPPZ2014]The Staging

首先求出所有的环，破环成链，每个环互相独立

对于一个环，要求出最终存活的人数，则需要先找到第一个开枪的人x

那么第x+1个人一定不能开枪，而且一定不能存活

所以需要查询区间[x+1,x+len]中，左端点的人不开枪且不存活时的存活人数

用线段树维护每个环，每个节点维护如下信息：

l,r:区间左右端点

val.x区间内开枪时间的最小值

val.y区间内开枪时间的最小值来自哪里

v[i][j]l开枪状态为i，存活状态为j时的存活人数

s[i][j]l开枪状态为i，存活状态为j时r的存活状态

时间复杂度为$O(q\log n)$。

#include
     
      #define N 200010int n,m,q,i,j,x,y,p[N],u[N<<1],pos[N<<1],flag;int cnt,from[N],loc[N],st[N],len[N],rem[N],all;struct PI{  int x,y;  PI(){}  PI(int _x,int _y){x=_x,y=_y;}  inline PI operator+(PI b){return x
      
       >=1;x;x>>=1)val[x]=val[x<<1]+val[x<<1|1];}void asku(int x,int a,int b,int c,int d){  if(c<=a&&b<=d){    if(flag)fir=fir+val[x];else flag=1,fir=val[x];    return;  }  int mid=(a+b)>>1;  if(c<=mid)asku(x<<1,a,mid,c,d);  if(d>mid)asku(x<<1|1,mid+1,b,c,d);}struct P{  int l,r,v[2][2],f[2][2];  P(){}  P(int x){    l=r=x;    v[0][0]=v[1][0]=f[0][0]=f[0][1]=0;    v[0][1]=v[1][1]=f[1][0]=f[1][1]=1;  }  inline P operator+(P b){    P c;    c.l=l,c.r=b.r;    c.v[0][0]=v[0][0]+b.v[u[b.l]
       
        >1;  build(x<<1,a,mid),build(x<<1|1,mid+1,b);  v[x]=v[x<<1]+v[x<<1|1],val[x]=val[x<<1]+val[x<<1|1];}void ask(int x,int a,int b,int c,int d){  if(c<=a&&b<=d){    if(flag)ans=ans+v[x];else flag=1,ans=v[x];    return;  }  int mid=(a+b)>>1;  if(c<=mid)ask(x<<1,a,mid,c,d);  if(d>mid)ask(x<<1|1,mid+1,b,c,d);}inline void change(int x,int y){  u[x]=y;  for(x=pos[x]>>1;x;x>>=1)v[x]=v[x<<1]+v[x<<1|1];}inline void query(int x){//查询第x个环的答案  all-=rem[x];  flag=0,asku(1,1,m,st[x],st[x]+len[x]-1);  flag=0,ask(1,1,m,fir.y+1,fir.y+len[x]);  rem[x]=ans.v[0][0];  all+=rem[x];}inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}int main(){  read(n);m=n*2;  for(i=1;i<=n;i++)read(p[i]);  for(i=0,j=1;j<=n;j++)if(!loc[j]){    st[++cnt]=loc[j]=++i,len[cnt]=1,from[j]=cnt;    for(x=p[j];x!=j;x=p[x])loc[x]=++i,len[cnt]++,from[x]=cnt;    i+=len[cnt];  }  for(i=1;i<=n;i++)read(x),u[loc[i]]=u[loc[i]+len[from[i]]]=x;  build(1,1,m);  for(i=1;i<=cnt;i++)query(i);  printf("%d\n",all);  for(read(q);q--;printf("%d\n",all)){    read(x),read(y);    changeu(loc[x],y);    change(loc[x],y),change(loc[x]+len[from[x]],y);    query(from[x]);  }  return 0;}
       
      
     

　　

[AMPPZ2014]The Cave

1号点到答案点的距离为$\max(0,\frac{dis(1,a_i)+dis(1,b_i)-d_i}{2})$，

找到距离最大的那条限制，则如果有解，那么满足那条限制的离1号点最近的点一定可行。

时间复杂度为$O(n+m)$。

#include
     
      #define N 300010int T,n,m,i,x,y,t,g[N],nxt[N<<1],v[N<<1],ed,a[N],b[N],d[N],dis[3][N];inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}void dfs(int x,int y,int z,int p){  dis[p][x]=z++;  for(int i=g[x];i;i=nxt[i])if(v[i]!=y)dfs(v[i],x,z,p);}int main(){  for(read(T);T--;){    read(n),read(m);    for(ed=0,i=1;i<=n;i++)g[i]=0;    for(i=1;i
      
       y)x=i,y=t;    }    dfs(a[x],0,0,1),dfs(b[x],0,0,2);    for(t=0,i=1;i<=n;i++)if(dis[1][i]+dis[2][i]<=d[x])if(!t||dis[0][i]
       
        d[i]){t=0;break;}    if(t)printf("TAK %d\n",t);else puts("NIE");  }  return 0;}
       
      
     

　　

[AMPPZ2014]The Captain

考虑代价为|a.x-b.x|的情况，将点按x排序后，只有相邻两个点之间的边有用。

于是连出4n条边，然后跑Dijkstra，求出1到n的最短路即可。

#include
     
      #include
      
       using namespace std;const int N=200010,M=1048575,inf=~0U>>1;int n,i,x,g[N],nxt[N<<2],v[N<<2],w[N<<2],ed,d[N];struct P{int x,y,id;}a[N];inline bool cmpx(P a,P b){return a.x
       
        0?x:-x;}inline void add(int x,int y,int z){  v[++ed]=y;w[ed]=z;nxt[ed]=g[x];g[x]=ed;  v[++ed]=x;w[ed]=z;nxt[ed]=g[y];g[y]=ed;}inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}struct PI{  int x,y;  PI(){}  PI(int _x,int _y){x=_x,y=_y;}  inline PI operator+(PI b){return x
        
         >1;  build(x<<1,a,mid),build(x<<1|1,mid+1,b);}inline void change(int x,int a,int b,int c,int d){  if(a==b){val[x].x=d;return;}  int mid=(a+b)>>1;  c<=mid?change(x<<1,a,mid,c,d):change(x<<1|1,mid+1,b,c,d);  val[x]=val[x<<1]+val[x<<1|1];}int main(){  for(read(n),i=1;i<=n;i++)read(a[i].x),read(a[i].y),a[i].id=i;  for(sort(a+1,a+n+1,cmpx),i=1;i
         
          <=abs(a[i].y-a[i+1].y))add(a[i].id,a[i+1].id,a[i+1].x-a[i].x);  for(sort(a+1,a+n+1,cmpy),i=1;i
          
           <=abs(a[i].x-a[i+1].x))add(a[i].id,a[i+1].id,a[i+1].y-a[i].y); for(i=2;i<=n;i++)d[i]=inf; build(1,1,n),change(1,1,n,1,0); while(val[1].x