A. Explosions
注意到将炸弹按坐标排序后，每个炸弹直接引爆和间接引爆的都是连续的一段区间，因此只需要求出每个炸弹能间接炸到的最左和最右的炸弹即可。
建立图论模型，炸弹$i$向炸弹$j$连单向边表示$i$爆炸会直接引起$j$的爆炸，那么建完图后求出SCC缩点然后拓扑排序+DP即可求出答案。
直接建图的边数是$O(n^2)$的，因此用线段树优化建图即可，时间复杂度$O(n\log 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\n",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_j\leq 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\n",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\n",ans);
}
return 0;
}
G. Roads
对于询问$(u,v,w)$，显然只要求出这个图的最大生成树，然后判断$u$到$v$路径上的最小边是否不小于$w$即可。
注意到修改边权的操作不超过$2000$个，因此离线询问，将边权不会被修改的边拿出来求最大生成树，那么只有上面那$n-1$条边有用，每次修改的时候暴力用这$2000+n-1$条边重新求最小生成树即可。
对于询问，可以在求最小生成树的时候按秩合并，那么树高就是$O(\log n)$的，暴力查询最小值即可。
时间复杂度$O(m\log m+e\log 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(q\log 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\n",ask(x+1,y+1));
}
}
J. Uniform Subtrees
注意到对于一棵大小为$n$的子树，答案只有$O(n)$个，所以自底向上合并答案，用Hash去重即可。
时间复杂度$O(n^2\log n)$。
K. Unreal Estate
将坐标乘上$100$变成整数，然后用线段树求出矩形面积并即可。
时间复杂度$O(n\log 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\n",realans);
}
}