T3 蚂蚁和瓢虫 题意比较坑，首先第三点条件的意思是把该蚂蚁和目标点连线上只要有蚂蚁就不动，第四点条件是进入同一个点的大标号蚂蚁不动，然后只要每次BFS一遍，按距离第一关键字编号第二关键字排序，模拟这个过程，在这个过程中对经过的边标号，就能快速模拟，时间复杂度$O(nlgnl)$

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 5050
using namespace std;
int n,k,T,i,x,y,h,t,st,tot,d[N],q[N],w[N],v[N],to[N],pos[N],fir[N],pre[N],eat[N],path[N],la[N<<1],ne[N<<1];
struct P{int x,y;}p[N];bool ff;
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
bool cmp(P a,P b){return a.x<b.x||a.x==b.x&&a.y<b.y;}
void cha(int x,int y,int z){
	path[y]=x;
	if(!v[x])v[x]=y,cha(pre[x],y+1,z);
	else if(!ff&&x==st)ff=1,pos[z]=st,to[st]=z;
	else if(y==v[x])pos[z]=path[y-1],to[pos[z]]=z;
	else if(y>v[x]){
		pos[z]=path[v[x]];to[pos[z]]=z;
		for(int i=v[x]+1;i<y;i++)v[path[i]]=v[x];
	}
}
int main(){
	for(scanf("%d",&n),i=1;i<n;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
	for(scanf("%d",&k),i=1;i<=k;i++)scanf("%d",&pos[i]),to[pos[i]]=i;
	for(scanf("%d",&T);T--;ff=0){
		for(memset(v,0,sizeof(v)),scanf("%d",&st),h=d[q[t=1]=st]=0,v[st]=1;h^t;)
			for(i=fir[x=q[++h]];i;i=ne[i])if(!v[la[i]])v[q[++t]=la[i]]=1,d[la[i]]=d[pre[la[i]]=x]+1;
		for(i=1;i<=k;i++)p[i].y=to[pos[i]],p[i].x=d[pos[i]];sort(p+1,p+k+1,cmp);eat[p[1].y]++;
		for(memset(v,0,sizeof(v)),v[st]=d[pos[p[1].y]]+1,i=1;i<=k;i++)cha(pos[p[i].y],1,p[i].y);
	}
	for(i=1;i<=k;i++)printf("%d %d\n",pos[i],eat[i]);
}

T4 基环树判同构。。我连树同构都不会判啊QAQ

T5 Goldmine 把矿石按$x$坐标轴排序，对$y$坐标轴进行扫描线处理，支持单点修改，求所有一段区间的最大值，可以转化一下改为区间修改和所有最大值，最简单的线段树就可以解决了

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 666666
using namespace std;
int x,y,i,j,n,ans,L=-30000,R=40000;
struct P{int x,y;}p[N];struct T{int lz,v;}t[N];
bool cmp(P a,P b){return a.x<b.x;}
void ins(int k,int l,int r,int x,int y,int z){
	if(t[k].lz)t[k<<1].v+=t[k].lz,t[k<<1|1].v+=t[k].lz,t[k<<1].lz+=t[k].lz,t[k<<1|1].lz+=t[k].lz,t[k].lz=0;
	if(x<=l&&r<=y){t[k].lz+=z,t[k].v+=z;return;}
	int mid=l+r>>1;
	if(x<=mid)ins(k<<1,l,mid,x,y,z);
	if(y>mid)ins(k<<1|1,mid+1,r,x,y,z);
	t[k].v=max(t[k<<1].v,t[k<<1|1].v);
}
int main(){
	for(scanf("%d%d%d",&x,&y,&n),i=1;i<=n;i++)scanf("%d%d",&p[i].x,&p[i].y);
	for(sort(p+1,p+n+1,cmp),i=j=1;i<=n;ans=max(ans,t[1].v),i++)
		for(ins(1,L,R,p[i].y,p[i].y+y,1);p[i].x-p[j].x>x;j++)ins(1,L,R,p[j].y,p[j].y+y,-1);
	printf("%d",ans);
}

• 相关文章推荐
• 全局相关文章