A. Explosions
注意到将炸弹按坐标排序后,每个炸弹直接引爆和间接引爆的都是连续的一段区间,因此只需要求出每个炸弹能间接炸到的最左和最右的炸弹即可。
建立图论模型,炸弹$i$向炸弹$j$连单向边表示$i$爆炸会直接引起$j$的爆炸,那么建完图后求出SCC缩点然后拓扑排序+DP即可求出答案。
直接建图的边数是$O(n^2)$的,因此用线段树优化建图即可,时间复杂度$O(nlog n)$。
#include<cstdio> #include<algorithm> #define N 100010 #define M 1700010 typedef long long ll; struct P{ll x,r;int id;}a[N]; inline bool cmp(P a,P b){return a.x<b.x;} int T,n,i,j,x,ans[N],id[N],l[N<<1],r[N<<1],tot; int g[3][N<<1],nxt[3][M],v[3][M],ed,f[N<<1],d[N<<1],vmin[N<<1],vmax[N<<1],q[N<<1],h,t; bool vis[N<<1]; inline void min(int&a,int b){if(a>b)a=b;} inline void max(int&a,int b){if(a<b)a=b;} inline void read(ll&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*=10LL)+=c-'0'; if(f)a=-a; } inline void add(int x,int y){ v[0][++ed]=y;nxt[0][ed]=g[0][x];g[0][x]=ed; v[1][ed]=x;nxt[1][ed]=g[1][y];g[1][y]=ed; } inline void ADD(int x,int y){d[y]++;v[2][++ed]=y;nxt[2][ed]=g[2][x];g[2][x]=ed;} void build(int a,int b){ int x=++tot; vmin[x]=a,vmax[x]=b; if(a==b){id[a]=x;return;} int mid=(a+b)>>1; add(l[x]=tot+1,x);build(a,mid); add(r[x]=tot+1,x);build(mid+1,b); } void add(int x,int a,int b,int c,int d,int p){ if(c<=a&&b<=d){add(x,p);return;} int mid=(a+b)>>1; if(c<=mid)add(l[x],a,mid,c,d,p); if(d>mid)add(r[x],mid+1,b,c,d,p); } inline int left(int p,ll x){ int l=1,r=p-1,mid,t=p; while(l<=r)if(a[mid=(l+r)>>1].x>=x)r=(t=mid)-1;else l=mid+1; return t; } inline int right(int p,ll x){ int l=p+1,r=n,mid,t=p; while(l<=r)if(a[mid=(l+r)>>1].x<=x)l=(t=mid)+1;else r=mid-1; return t; } void dfs1(int x){ vis[x]=1; for(int i=g[0][x];i;i=nxt[0][i])if(!vis[v[0][i]])dfs1(v[0][i]); q[++t]=x; } void dfs2(int x,int y){ vis[x]=0,f[x]=y; min(vmin[y],vmin[x]),max(vmax[y],vmax[x]); for(int i=g[1][x];i;i=nxt[1][i])if(vis[v[1][i]])dfs2(v[1][i],y); } void work(){ for(ed=0,i=1;i<=tot;i++)g[0][i]=g[1][i]=g[2][i]=d[i]=0;tot=0; for(i=1;i<=n;i++)read(a[i].x),read(a[i].r),a[i].id=i; std::sort(a+1,a+n+1,cmp); build(1,n); for(i=1;i<=n;i++)add(1,1,n,left(i,a[i].x-a[i].r),right(i,a[i].x+a[i].r),id[i]); for(i=1;i<=tot;i++)vis[i]=0; for(t=0,i=1;i<=tot;i++)if(!vis[i])dfs1(i); for(i=tot;i;i--)if(vis[q[i]])dfs2(q[i],q[i]); for(ed=0,i=1;i<=tot;i++)for(j=g[0][i];j;j=nxt[0][j])if(f[i]!=f[v[0][j]])ADD(f[i],f[v[0][j]]); for(h=i=1,t=0;i<=tot;i++)if(f[i]==i&&!d[i])q[++t]=i; while(h<=t)for(i=g[2][x=q[h++]];i;i=nxt[2][i]){ min(vmin[v[2][i]],vmin[x]),max(vmax[v[2][i]],vmax[x]); if(!(--d[v[2][i]]))q[++t]=v[2][i]; } for(i=1;i<=n;i++)ans[a[i].id]=vmax[f[id[i]]]-vmin[f[id[i]]]+1; for(i=1;i<n;i++)printf("%d ",ans[i]);printf("%d ",ans[n]); } int main(){ while(~scanf("%d",&n)){ if(!n)return 0; work(); } }
B. Flooding Fields
将图分成$h$份,每个点向下一层周围$4$个点以及当前点连边,然后求最大流即可。
C. Goat Ropes
设$r_i$表示第$i$个圆的半径,那么有$O(n^2)$个约束条件:$r_i+r_jleq dis(i,j)$,要最大化$sum_{i=1}^n r_i$。这显然是线性规划模型,单纯形求解即可。
#include<cstdio> #include<cmath> #include<algorithm> #include<cstring> #include<vector> using namespace std; const double eps=1e-9; typedef vector<double> VD; double simplex(vector<VD>A,VD b,VD c){ int n=A.size(),m=A[0].size()+1,r=n,s=m-1; vector<VD> D(n+2,VD(m+1,0)); vector<int> ix(n+m); for(int i=0;i<n+m;i++)ix[i]=i; for(int i=0;i<n;i++){ for(int j=0;j<m-1;j++)D[i][j]=-A[i][j]; D[i][m-1]=1;D[i][m]=b[i]; if(D[r][m]>D[i][m])r=i; } for(int j=0;j<m-1;j++)D[n][j]=c[j]; D[n+1][m-1]=-1; for(double d;;){ if(r<n){ int t=ix[s]; ix[s]=ix[r+m]; ix[r+m]=t; D[r][s]=1.0/D[r][s]; vector<int> speedUp; for(int j=0;j<=m;j++)if(j!=s){ D[r][j]*=-D[r][s]; if(D[r][j])speedUp.push_back(j); } for(int i=0;i<=n+1;i++)if(i!=r){ for(int j=0;j<speedUp.size();j++) D[i][speedUp[j]]+=D[r][speedUp[j]]*D[i][s]; D[i][s]*=D[r][s]; } } r=-1;s=-1; for(int j=0;j<m;j++)if(s<0||ix[s]>ix[j]) if(D[n+1][j]>eps||(D[n+1][j]>-eps&&D[n][j]>eps))s=j; if(s<0)break; for(int i=0;i<n;i++)if(D[i][s]<-eps) if(r<0||(d=D[r][m]/D[r][s]-D[i][m]/D[i][s])<-eps ||(d<eps&&ix[r+m]>ix[i+m]))r=i; if(r<0)return -1; } return D[n][m]; } double x[66],y[66]; inline double dis(int a,int b){ return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b])); } int main(){ int m; while(~scanf("%d",&m)){ if(!m)return 0; for(int i=0;i<m;i++)scanf("%lf%lf",&x[i],&y[i]); vector<VD>A; VD b; VD c; for(int i=0;i<m;i++)c.push_back(1); for(int i=0;i<m;i++)for(int j=0;j<i;j++){ VD v; for(int k=0;k<m;k++)v.push_back(0); v[i]=v[j]=1; A.push_back(v); b.push_back(dis(i,j)); } printf("%.2f ",simplex(A,b,c)); } }
D. Job Postings
显然的建图,跑最大费用最大流。
E. Overlapping Maps
考虑复数相乘的几何意义:模长相乘,极角相加。
因此在复数意义下列出一元一次方程然后直接求解即可。
F. 3D-printing
三维凸包模板题。
#include<stdio.h> #include<string.h> #include<math.h> #include<algorithm> using namespace std; #define PR 1e-8 #define N 1000 struct TPoint{ double x,y,z; TPoint(){} TPoint(double _x,double _y,double _z):x(_x),y(_y),z(_z){} TPoint operator-(const TPoint p){return TPoint(x-p.x,y-p.y,z-p.z);} TPoint operator*(const TPoint p){return TPoint(y*p.z-z*p.y,z*p.x-x*p.z,x*p.y-y*p.x);}//叉积 double operator^(const TPoint p){return x*p.x+y*p.y+z*p.z;}//点积 }; struct fac{ int a,b,c;//凸包一个面上的三个点的编号 bool ok;//该面是否是最终凸包中的面 }; struct T3dhull{ int n;//初始点数 TPoint ply[N];//初始点 int trianglecnt;//凸包上三角形数 fac tri[N];//凸包三角形 int vis[N][N];//点i到点j是属于哪个面 void clear(){n=0;} void newnode(){ scanf("%lf%lf%lf",&ply[n].x,&ply[n].y,&ply[n].z); n++; } double dist(TPoint a){return sqrt(a.x*a.x+a.y*a.y+a.z*a.z);}//两点长度 double area(TPoint a,TPoint b,TPoint c){return dist((b-a)*(c-a));}//三角形面积*2 double volume(TPoint a,TPoint b,TPoint c,TPoint d){return (b-a)*(c-a)^(d-a);}//四面体有向体积*6 double ptoplane(TPoint &p,fac &f){//正:点在面同向 TPoint m=ply[f.b]-ply[f.a],n=ply[f.c]-ply[f.a],t=p-ply[f.a]; return (m*n)^t; } void deal(int p,int a,int b){ int f=vis[a][b]; fac add; if(tri[f].ok){ if((ptoplane(ply[p],tri[f]))>PR)dfs(p,f);else{ add.a=b,add.b=a,add.c=p,add.ok=1; vis[p][b]=vis[a][p]=vis[b][a]=trianglecnt; tri[trianglecnt++]=add; } } } void dfs(int p,int cnt){//维护凸包,如果点p在凸包外更新凸包 tri[cnt].ok=0; deal(p,tri[cnt].b,tri[cnt].a); deal(p,tri[cnt].c,tri[cnt].b); deal(p,tri[cnt].a,tri[cnt].c); } bool same(int s,int e){//判断两个面是否为同一面 TPoint a=ply[tri[s].a],b=ply[tri[s].b],c=ply[tri[s].c]; return fabs(volume(a,b,c,ply[tri[e].a]))<PR &&fabs(volume(a,b,c,ply[tri[e].b]))<PR &&fabs(volume(a,b,c,ply[tri[e].c]))<PR; } void construct(){//构建凸包 int i,j; trianglecnt=0; if(n<4)return; bool tmp=1; for(i=1;i<n;i++){//前两点不共点 if((dist(ply[0]-ply[i]))>PR){ swap(ply[1],ply[i]);tmp=0;break; } } if(tmp)return; tmp=1; for(i=2;i<n;i++){//前三点不共线 if((dist((ply[0]-ply[1])*(ply[1]-ply[i])))>PR){ swap(ply[2],ply[i]); tmp=0; break; } } if(tmp)return; tmp=1; for(i=3;i<n;i++)//前四点不共面 if(fabs((ply[0]-ply[1])*(ply[1]-ply[2])^(ply[0]-ply[i]))>PR){ swap(ply[3],ply[i]);tmp=0;break; } if(tmp)return; fac add; for(i=0;i<4;i++){//构建初始四面体 add.a=(i+1)%4,add.b=(i+2)%4,add.c=(i+3)%4,add.ok=1; if((ptoplane(ply[i],add))>0) swap(add.b,add.c); vis[add.a][add.b]=vis[add.b][add.c]=vis[add.c][add.a]=trianglecnt; tri[trianglecnt++]=add; } for(i=4;i<n;i++){//构建更新凸包 for(j=0;j<trianglecnt;j++) if(tri[j].ok&&(ptoplane(ply[i],tri[j]))>PR){ dfs(i,j);break; } } int cnt=trianglecnt; trianglecnt=0; for(i=0;i<cnt;i++) if(tri[i].ok) tri[trianglecnt++]=tri[i]; } double area(){//表面积 double ret=0; for(int i=0;i<trianglecnt;i++)ret+=area(ply[tri[i].a],ply[tri[i].b],ply[tri[i].c]); return ret/2.0; } double volume(){//体积 TPoint p(0,0,0); double ret=0; for(int i=0;i<trianglecnt;i++)ret+=volume(p,ply[tri[i].a],ply[tri[i].b],ply[tri[i].c]); return fabs(ret/6); } int facetri(){return trianglecnt;}//表面三角形数 int facepolygon(){//表面多边形数 int ans=0,i,j,k; for(i=0;i<trianglecnt;i++){ for(j=0,k=1;j<i;j++){ if(same(i,j)){k=0;break;} } ans+=k; } return ans; } }hull; int main(){ int Case; while(~scanf("%d",&Case)){ if(!Case)return 0; double ans=0; while(Case--){ int m; hull.clear(); scanf("%d",&m); while(m--){ int k; scanf("%d",&k); while(k--)hull.newnode(); } hull.construct(); ans+=hull.volume(); } printf("%.3f ",ans); } return 0; }
G. Roads
对于询问$(u,v,w)$,显然只要求出这个图的最大生成树,然后判断$u$到$v$路径上的最小边是否不小于$w$即可。
注意到修改边权的操作不超过$2000$个,因此离线询问,将边权不会被修改的边拿出来求最大生成树,那么只有上面那$n-1$条边有用,每次修改的时候暴力用这$2000+n-1$条边重新求最小生成树即可。
对于询问,可以在求最小生成树的时候按秩合并,那么树高就是$O(log n)$的,暴力查询最小值即可。
时间复杂度$O(mlog m+elog n+2000(n+2000)log n)$。
#include<cstdio> #include<algorithm> using namespace std; const int N=100010,inf=~0U>>1; int n,m,i,Q,q[N][4],vip[N],b[N],cnt,c[N],f[N],d[N],g[N],dep[N],vis[N]; char op[9]; struct E{int u,v,w;}e[N]; inline bool cmp(int x,int y){return e[x].w>e[y].w;} int F(int x){return f[x]==x?x:f[x]=F(f[x]);} int getf(int x){return f[x]==x?x:getf(f[x]);} inline void merge(int x,int y,int z){ x=getf(x); y=getf(y); if(x==y)return; if(d[x]==d[y])d[x]++; if(d[x]<d[y])swap(x,y); f[y]=x; g[y]=z; } int dfs(int x){ if(vis[x])return dep[x]; vis[x]=1; if(f[x]==x)return dep[x]=0; return dep[x]=dfs(f[x])+1; } inline void build(){ int i; sort(c+1,c+cnt+1,cmp); for(i=1;i<=n;i++)f[i]=i,d[i]=0,g[i]=inf; for(i=1;i<=cnt;i++)merge(e[c[i]].u,e[c[i]].v,e[c[i]].w); for(i=1;i<=n;i++)vis[i]=0; for(i=1;i<=n;i++)dfs(i); } inline int ask(int x,int y){ if(getf(x)!=getf(y))return -1; int z=inf; while(x!=y){ if(dep[x]<dep[y])swap(x,y); z=min(z,g[x]); x=f[x]; } return z; } int main(){ while(~scanf("%d%d",&n,&m)){ if(!n)return 0; for(i=1;i<=m;i++)scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w); scanf("%d",&Q); for(i=1;i<=Q;i++){ scanf("%s",op); if(op[0]=='B'||op[0]=='R'){ q[i][0]=0; scanf("%d%d",&q[i][1],&q[i][2]); vip[q[i][1]]=1; }else{ q[i][0]=1; scanf("%d%d%d",&q[i][1],&q[i][2],&q[i][3]); } } for(i=1;i<=m;i++)b[i]=i; sort(b+1,b+m+1,cmp); for(i=1;i<=n;i++)f[i]=i; for(cnt=0,i=1;i<=m;i++)if(vip[i])c[++cnt]=i; for(i=1;i<=m;i++)if(!vip[b[i]])if(F(e[b[i]].u)!=F(e[b[i]].v)){ f[f[e[b[i]].u]]=f[e[b[i]].v]; c[++cnt]=b[i]; } build(); for(i=1;i<=Q;i++)if(q[i][0])puts(ask(q[i][1],q[i][2])>=q[i][3]?"1":"0"); else{ e[q[i][1]].w=q[i][2]; build(); } for(i=1;i<=m;i++)vip[i]=0; cnt=0; } }
H. Satisfaction Guaranteed
留坑。
I. Trading
对于每个询问,二分答案,然后用Hash值判断是否相等即可,时间复杂度$O(qlog n)$。
#include<cstdio> #include<cstring> typedef long long ll; const int N=100010,A=1000000007,B=1000000009; int n,m,i,x,y;char a[N];ll pa[N],pb[N],f[N],g[N]; inline ll hasha(int l,int r){return((f[r]-1LL*f[l-1]*pa[r-l+1]%A)%A+A)%A;} inline ll hashb(int l,int r){return((g[r]-1LL*g[l-1]*pb[r-l+1]%B)%B+B)%B;} inline int ask(int x,int y){ int l=1,r=n-y+1,mid,t=0; while(l<=r){ mid=(l+r)>>1; if(hasha(x,x+mid-1)==hasha(y,y+mid-1)&&hashb(x,x+mid-1)==hashb(y,y+mid-1))l=(t=mid)+1;else r=mid-1; } return t; } int main(){ for(pa[0]=i=1;i<N;i++)pa[i]=233LL*pa[i-1]%A; for(pb[0]=i=1;i<N;i++)pb[i]=233LL*pb[i-1]%B; while(~scanf("%s",a+1)){ if(a[1]=='*')return 0; n=strlen(a+1); for(i=1;i<=n;i++)f[i]=(233LL*f[i-1]+a[i])%A; for(i=1;i<=n;i++)g[i]=(233LL*g[i-1]+a[i])%B; scanf("%d",&m); while(m--)scanf("%d%d",&x,&y),printf("%d ",ask(x+1,y+1)); } }
J. Uniform Subtrees
注意到对于一棵大小为$n$的子树,答案只有$O(n)$个,所以自底向上合并答案,用Hash去重即可。
时间复杂度$O(n^2log n)$。
K. Unreal Estate
将坐标乘上$100$变成整数,然后用线段树求出矩形面积并即可。
时间复杂度$O(nlog n)$。
#include<cstdio> #include<cmath> #include<algorithm> using namespace std; const int N=600000; int n,m,i,v[N],tag[N];long long ans; struct E{int x,l,r,t;E(){}E(int _x,int _l,int _r,int _t){x=_x,l=_l,r=_r,t=_t;}}e[N]; inline bool cmp(const E&a,const E&b){return a.x<b.x;} void build(int x,int a,int b){ v[x]=tag[x]=0; if(a+1==b)return; int mid=(a+b)>>1; build(x<<1,a,mid); build(x<<1|1,mid,b); } inline void up(int x,int a,int b){ if(tag[x]){v[x]=b-a;return;} if(a+1==b)v[x]=0;else v[x]=v[x<<1]+v[x<<1|1]; } void change(int x,int a,int b,int c,int d,int p){ if(c<=a&&b<=d){ tag[x]+=p; up(x,a,b); return; } int mid=(a+b)>>1; if(c<mid)change(x<<1,a,mid,c,d,p); if(d>mid)change(x<<1|1,mid,b,c,d,p); up(x,a,b); } int main(){ while(~scanf("%d",&n)){ if(!n)return 0; m=0; for(i=1;i<=n;i++){ double x1,y1,x2,y2; scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); x1*=100;y1*=100;x2*=100;y2*=100; int X1=round(x1),X2=round(x2),Y1=round(y1),Y2=round(y2); Y1+=100000; Y2+=100000; //[0,200000] e[++m]=E(X1,Y1,Y2,1); e[++m]=E(X2,Y1,Y2,-1); } sort(e+1,e+m+1,cmp); build(1,0,200000); ans=0; for(i=1;i<m;i++){ change(1,0,200000,e[i].l,e[i].r,e[i].t); ans+=1LL*v[1]*(e[i+1].x-e[i].x); } double realans=ans/10000.0; printf("%.2f ",realans); } }