noip多校模拟31

考试过程:首先看T1,是个推柿子题,推了一会没什么思路,就直接打了暴力走人。然后是T2,一个数据结构题,我想了一种复杂度为\(o(链长)\)的一种复杂度优于暴力的做法,在随机数据下跑的挺快,但是后两组构造出来的数据就把我卡死了。
然后是T3,想了一会只想到了用二维差分,能获得\(40pts\),最后一题没时间打了,但是听说暴力分有\(30\),挺亏的。
考试总结:时间分配再均匀一些,至少花上20分钟把暴力分拿到。

T1 法阵

咕了

T2 连通块

我在考场上的思路是统计出每个点每个出边所能达到的最大深度,然后统计答案就暴力跳\(father\),修改时就暴力修改\(fa\)链,这样的话只要数据是随的都能跑的很快。
正解:把问题倒过来做,因为删边不好维护,所以把删边改为加边,用并查集维护连通块
求最远点无异于求直径,一个点到最远点的距离一定是到直径某个端点的距离
在维护连通块时,同样可以维护直径,新的直径两个端点一定在原先的4个端点之中
代码如下:

AC_code

#include<bits/stdc++.h>
#define re int
#define ii inline int
#define iv inline void
#define next netet
#define head heaeae
#define f() cout<<"rp++"<<endl
using namespace std;
const int N=2e5+10;
struct QUE
{
	int dis,x,y;
	friend bool operator < (QUE a,QUE b) {return a.dis<b.dis;}
};
priority_queue<QUE> Q;
struct node
{
	int opt,u,ans;
}cun[N];
vector<int> v[N],zj[N];
int n,m,tot,d,dian;
int to[N<<1],next[N<<1],pos[N<<1],head[N],md[N<<1];
int be[N],fa[N][30],deep[N];
bool ban[N],vis[N];
ii read()
{
	int x=0; char ch=getchar(); bool f=1;
	while(ch<'0' or ch>'9')
	{
		if(ch=='-') f=0;
		ch=getchar();
	}
	while(ch>='0' and ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return f?x:(-x);
}
iv add(int x,int y,int z)
{
	to[++tot]=y;
	next[tot]=head[x];
	head[x]=tot;
	pos[tot]=z;
}
ii gett(int x) {return x==be[x]?x:be[x]=gett(be[x]);}
ii dfs(int z,int st,int f)
{
	be[st]=z;
	v[z].push_back(st);
	fa[st][0]=f;
	deep[st]=deep[f]+1;
	int my=st;
	for(re i=1;i<=25;i++) fa[st][i]=fa[fa[st][i-1]][i-1];
	for(re i=head[st];i;i=next[i])
	{
		int p=to[i];
		if(p==f or ban[pos[i]]) continue;
		md[i]=dfs(z,p,st);
		if(deep[md[i]]>deep[my]) my=md[i];
	}
	return my;
}
iv find_len(int st,int las,int oth)
{
	int now=deep[oth]-deep[st];
	if(now>=d) d=now,dian=st;
	for(re i=head[st];i;i=next[i])
	{
		int p=to[i];
		if(p==fa[st][0] or p==las or ban[pos[i]]) continue;
		if(d<deep[md[i]]-deep[st]+deep[oth]-deep[st])
		{
			d=deep[md[i]]-deep[st]+deep[oth]-deep[st];
			dian=md[i];	
		}
	}
	if(fa[st][0]) find_len(fa[st][0],st,oth);
}
iv upd(int st,int f,int zu)
{
	be[st]=zu;
	v[zu].push_back(st);
	fa[st][0]=f;
	deep[st]=deep[f]+1;
	for(re i=1;i<=25;i++) fa[st][i]=fa[fa[st][i-1]][i-1];
	for(re i=head[st];i;i=next[i])
	{
		int p=to[i];
		if(p==f or ban[pos[i]]) continue;
		upd(p,st,zu);
	}
}
ii LCA(int x,int y)
{
	if(deep[x]<deep[y]) swap(x,y);
	int d=deep[x]-deep[y];
	for(re i=0;(1<<i)<=d;i++) if((1<<i)&d) x=fa[x][i];
	if(x==y) return x;
	for(re i=23;i>=0;i--)
	{
		if(fa[x][i]!=fa[y][i])
		{
			x=fa[x][i];
			y=fa[y][i];
		}
	}
	return fa[x][0];
}
signed main()
{
	freopen("block.in","r",stdin);
	freopen("block.out","w",stdout);
	n=read(),m=read();
	deep[0]=-1;
	int opt,x,y,u;
	for(re i=1;i<n;i++)
	{
		x=read(),y=read();
		add(x,y,i),add(y,x,i);
	}
	for(re i=1;i<=m;i++)
	{
		opt=read(),x=read();
		cun[i]=(node){opt,x};
		if(opt==1) ban[x]=1;
	}
	for(re i=1;i<=n;i++) be[i]=i;
	for(re i=1;i<=n;i++)
	{
		int fx=gett(i);
		if(vis[fx]) continue;
		vis[fx]=1;
		int p=dfs(i,i,0);
		zj[fx].push_back(p);
		d=0,dian=0;
		find_len(p,0,p);
		zj[fx].push_back(dian);
		
	}
	for(re i=m;i;i--)
	{
		opt=cun[i].opt,u=cun[i].u;
		if(opt==1)
		{
			while(Q.size()) Q.pop();
			ban[u]=0;
			x=to[u*2-1],y=to[u*2];
			
			int fx=gett(x),fy=gett(y);
			if(fx==fy) continue;
			if(v[fx].size()<v[fy].size()) swap(x,y),swap(fx,fy);
			
			upd(y,x,fx);
			int lca=LCA(zj[fx][0],zj[fx][1]);
			int ds=deep[zj[fx][0]]+deep[zj[fx][1]]-2*deep[lca];
			Q.push((QUE){ds,zj[fx][0],zj[fx][1]});
			
			lca=LCA(zj[fy][0],zj[fy][1]);
			ds=deep[zj[fy][0]]+deep[zj[fy][1]]-2*deep[lca];
			Q.push((QUE){ds,zj[fy][0],zj[fy][1]});
			
			for(re j=0;j<zj[fx].size();j++)
			{
				for(re k=0;k<zj[fy].size();k++)
				{
					int lca=LCA(zj[fx][j],zj[fy][k]);
					int ds=deep[zj[fx][j]]+deep[zj[fy][k]]-2*deep[lca];
					Q.push((QUE){ds,zj[fx][j],zj[fy][k]});
				}
			}
			zj[fx].clear(),zj[fy].clear();
			v[fy].clear();
			
			zj[fx].push_back(Q.top().x),zj[fx].push_back(Q.top().y);
		}
		else
		{
			int fx=gett(u);
			while(Q.size()) Q.pop();
			for(re j=0;j<zj[fx].size();j++)
			{
				int lca=LCA(u,zj[fx][j]);
				int ds=deep[u]+deep[zj[fx][j]]-2*deep[lca];
				Q.push((QUE){ds,u,zj[fx][j]});
			}
			cun[i].ans=Q.top().dis;
		}
	}
	for(re i=1;i<=m;i++) if(cun[i].opt==2) printf("%d\n",cun[i].ans);
	return 0;
}


T3 军队

思路:解决这道题主要有两大操作:
1.如何快速计算出每一行的雄性个数
2.如何快速统计答案。
对于1,我们可以用扫描线处理,把所有太阳以横坐标为第一关键字排序,再开一个线段树维护整个区间前\(k\)小的数的数值和个数。
对于2,设每行有\(a_i\)个雄性,那么\(b_i=min(a_i,m-a_i)\),设我要在每一行取\(y\)个,那么\(my=y/2\),所以最优答案即为\(min(my,b_i)\times (y-min(my,b_i))\)
那么根据\(b_i\)与\(my\)的大小关系我们可以利用前缀和\(o(log)\)求出答案。

代码如下:

AC_code

#include<bits/stdc++.h>
#define int long long
#define ll long long
#define re int
#define ii inline int
#define iv inline void
#define next netet
#define head heaeae
#define f() cout<<"rp++"<<endl
using namespace std;
const int N=3e5+10;
struct node
{
	int x,l,r,val;
}cun[N<<1];
int n,m,c,k,q,cnt;
int men[N];
ll pf[N],pg[N];
priority_queue<int> Q;
ii read()
{
	int x=0; char ch=getchar(); bool f=1;
	while(ch<'0' or ch>'9')
	{
		if(ch=='-') f=0;
		ch=getchar();
	}
	while(ch>='0' and ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return f?x:(-x);
}
inline bool com(node a,node b) {return a.x<b.x;}
struct Segment_Tree
{
	#define mid ((l+r)>>1)
	#define lc (rt<<1)
	#define rc (rt<<1|1)
	int sum[N<<2][12][2],lazy[N<<2],lim[N<<2];
	iv build(int rt,int l,int r)
	{
		sum[rt][1][0]=0,sum[rt][1][1]=r-l+1;
		lim[rt]=1;
		if(l==r) return;
		build(lc,l,mid),build(rc,mid+1,r);
	}
	iv pd(int rt)
	{
		for(re i=1;i<=lim[lc];i++) sum[lc][i][0]+=lazy[rt];
		for(re i=1;i<=lim[rc];i++) sum[rc][i][0]+=lazy[rt];
		lazy[lc]+=lazy[rt];
		lazy[rc]+=lazy[rt];
		lazy[rt]=0;
	}
	iv pp(int rt)
	{
		int l=1,r=1,num=1;
		while(num<=k)
		{
			if(l<=lim[lc] and r<=lim[rc])
			{
				if(sum[lc][l][0]==sum[rc][r][0])
				{
					sum[rt][num][0]=sum[lc][l][0];
					sum[rt][num][1]=sum[lc][l][1]+sum[rc][r][1];
					++l,++r;
				}
				else if(sum[lc][l][0]<sum[rc][r][0])
				{
					sum[rt][num][0]=sum[lc][l][0];
					sum[rt][num][1]=sum[lc][l][1];
					++l;
				}
				else
				{
					sum[rt][num][0]=sum[rc][r][0];
					sum[rt][num][1]=sum[rc][r][1];
					++r;
				}
			}
			else if(l<=lim[lc])
			{
				sum[rt][num][0]=sum[lc][l][0];
				sum[rt][num][1]=sum[lc][l][1];
				++l;
			}
			else if(r<=lim[rc])
			{
				sum[rt][num][0]=sum[rc][r][0];
				sum[rt][num][1]=sum[rc][r][1];
				++r;
			}
			else break;
			++num;
		}
		lim[rt]=num-1;
		return;
	}
	iv insert(int rt,int l,int r,int L,int R,int z)
	{
		if(L>R) return;
		if(L<=l and r<=R)
		{
			for(re i=1;i<=lim[rt];i++)
				sum[rt][i][0]+=z;
			lazy[rt]+=z;
			return;
		}
		if(lazy[rt]) pd(rt);
		if(mid>=L) insert(lc,l,mid,L,R,z);
		if(mid<R) insert(rc,mid+1,r,L,R,z);
		pp(rt);
	}
	#undef mid
	#undef lc
	#undef rc
}T;
signed main()
{
	freopen("army.in","r",stdin);
	freopen("army.out","w",stdout);
	n=read(),m=read(),c=read(),k=read(),q=read();
	int x,y,x2,y2;
	for(re i=1;i<=c;i++)
	{
		x=read(),y=read(),x2=read(),y2=read();
		cun[++cnt]=(node){x,y,y2,1};
		cun[++cnt]=(node){x2+1,y,y2,-1};
	}
	sort(cun+1,cun+cnt+1,com);
	T.build(1,1,m);
	for(re i=1;i<=cnt;)
	{
		int x=cun[i].x;
		while(cun[i].x==x)
		{
			T.insert(1,1,m,cun[i].l,cun[i].r,cun[i].val);
			++i;
		}
		int num=0;
		for(re j=1;j<=T.lim[1];j++)
		{
			if(T.sum[1][j][0]>=k) break;
			num+=T.sum[1][j][1];
		}
		for(re j=x;j<cun[i].x;j++) men[j]=min(num,m-num);
	}
	sort(men+1,men+n+1);
	for(re i=n;i;i--) pf[i]=pf[i+1]-men[i]*men[i],pg[i]=pg[i+1]+men[i];
	while(q--)
	{
		ll ans=0;
		x=read(),y=read();
		int my=y/2;
		int p=lower_bound(men+1,men+n+1,my)-men;
		if(n-p+1>=x)
		{
			ans=1ll*x*my*(y-my);
			printf("%lld\n",ans);
		}
		else
		{
			ans=1ll*(n-p+1)*my*(y-my);
			ans+=(pf[n-x+1]-pf[n-(n-p+1)+1])+1ll*y*(pg[n-x+1]-pg[n-(n-p+1)+1]);
			printf("%lld\n",ans);
		}
	}
	return 0;
}


上一篇:面试常考算法题之并查集问题


下一篇:支配(灭绝)树学习笔记 暨 P2597 [ZJOI2012]灾难 题解