2.19日周赛

T2.彩旗

• 题意：有n棵树第i棵要种在xi或yi处，求最小距离的最大值
• 思路：首先二分+2-SAT。关键是建图，我没有写线段树优化建图，因为太菜了。
  然后就搞了一个算法（因为线段树优化建图的数据范围都很小），搞了70分，数组开小了其实可以搞85分的。
  就是先把所有的x,y搞在一起排序，然后得到新数组p[1...2n],然后再在p中选n个点最小距离最大（这个直接二分判断即可），因此就找到的这个值就是二分的上界up。
  这个上界优化非常致命，我不会证明，考场上随机也没有卡掉自己，甚至跑的飞快。不过理论上up最大为\(10^5\),当分布均匀不过这种情况好像连的边又很少。我猜是那种一堆很紧密然后少量很稀疏的，不过还是想的不是很明白……
  线段树优化建图要两棵线段树，一棵出数（叶子为p[]），一棵入树（叶子节点为_[p[]]）当然线段树加上上界优化就更完美了。
• code

#include
using namespace std;
const int N=1e6+5;
const int M=2e7+5;
struct fc {int x,y;}b[N];
struct node {int x,id;}a[N];
struct seg {int l,r;}T[N];
int dta,lf1[N],lf2[N];
int nxt[M],to[M],head[N],ecnt;
int _[N],up,n,val[N],nn,m;
void add_edge(int u,int v) {nxt[++ecnt]=head[u];to[ecnt]=v;head[u]=ecnt;}
bool cmp(node u,node v) {return u.x>1,ls=x<<1,rs=ls|1;
	add_edge(ls,x),add_edge(rs,x),add_edge(x+dta,ls+dta),add_edge(x+dta,rs+dta);
	_llaa(ls,l,mid),_llaa(rs,mid+1,r);
}
void _Link(int x,int l,int r,int fr) {
	if(l<=T[x].l&&T[x].r<=r) {add_edge(lf1[fr],x+dta);return;}
	int mid=(T[x].l+T[x].r)>>1;
	if(l<=mid)_Link(x<<1,l,r,fr);
	if(r>mid)_Link(x<<1|1,l,r,fr);
}
void Link_(int x,int l,int r,int tto) {
	if(l<=T[x].l&&T[x].r<=r) {add_edge(x,lf2[tto]);return;}
	int mid=(T[x].l+T[x].r)>>1;
	if(l<=mid)Link_(x<<1,l,r,tto);
	if(r>mid)Link_(x<<1|1,l,r,tto);
}
void init_tree() {
	_llaa(1,1,nn);
	for(int i=1;i<=nn;i++) add_edge(lf2[i],lf1[i]);
}
bool check(int mid) {
	int lst=a[1].x,cnt=1;
	for(int i=2;i<=nn;i++) {
		if(a[i].x>=lst+mid) {
			++cnt;lst=a[i].x;if(cnt>=n)return 1;
		}
	}
	return (cnt>=n);
}
void gt_up() {
	int l=0,r=1e9;
	while(l<=r) {
		int mid=(l+r)>>1;
		if(check(mid))up=mid,l=mid+1;
		else r=mid-1;
	}
//	printf("!%d\n",up);
}
int Bl[N],SCC,dfn[N],low[N],Time,tp,st[N];
bool In_s[N];
void Tarjan(int u) {
	dfn[u]=low[u]=++Time;st[++tp]=u;In_s[u]=1;
	for(int i=head[u];i;i=nxt[i]) {
		int v=to[i];
		if(!dfn[v]) {Tarjan(v);low[u]=min(low[u],low[v]);}
		else if(In_s[v])low[u]=min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u]) {
		++SCC;int v;
		do {
			v=st[tp--];In_s[v]=0;Bl[v]=SCC;
		}while(u!=v);
	}
}

bool _rd() {for(int i=1;i<=n;i++)if(Bl[lf2[i]]==Bl[lf2[_[i]]])return 0;return 1;}
void Build(int mid) {
	init_tree();
	int j=1;
	for(int i=1;i<=nn;i++) {
		while(j>1;
		Build(mid);
		if(_rd()) best=mid,l=mid+1;
		else r=mid-1;
		Clear();
	}
	printf("%d",best);
}
int main() {
	scanf("%d",&n);nn=n<<1;dta=nn<<2;
	for(int i=1;i<=n;i++) scanf("%d%d",&b[i].x,&b[i].y),a[(i<<1)-1]=(node){b[i].x,i},a[i<<1]=(node){b[i].y,i+n},_[i]=i+n,_[i+n]=i;
	sort(a+1,a+1+nn,cmp);
	gt_up();
	solve();
	return 0;
}

T3.改色找根

• 题意：问你最少的步数存在一个跟，使得所有颜色为c[rt]的点到跟上没有!=c[rt]的点
• 思路：点分治，对于当前子树根，找到c[rt]的所有点（如果有子树外的话，就结束因为存在包含所有该颜色的根的更优），枚举每个点往上跳，如果遇到新的颜色就再看新的颜色的所有点到根又有没有新的颜色（同前）……发现是个递归问题吧。bfs就可以了，队列里面存颜色，每个颜色按上面的操作把新颜色又推进队列，当前答案就是新的颜色个数，每个颜色只需要入队一次这样也保证了子树\(O(sz)\)的复杂度。点分治复杂度\(O(nlog_2n)\)
• code:

#include
using namespace std;
const int N=1e6+5;
vector V[N];
int f[N],ans=1e9,root,sz[N],c[N],nxt[N],to[N],head[N],ecnt,cnt[N],st[N],tp,smx[N];
bool vis[N],mark[N];
void add_edge(int u,int v) {nxt[++ecnt]=head[u];to[ecnt]=v;head[u]=ecnt;}
void gt_sz(int u,int fa) {
	sz[u]=1;
	for(int i=head[u];i;i=nxt[i]) {
		int v=to[i];if(vis[v]||v==fa)continue;
		gt_sz(v,u);sz[u]+=sz[v];
	}
}
void gt_rt(int u,int fa,int tot) {
	smx[u]=tot-sz[u];
	for(int i=head[u];i;i=nxt[i]) {
		int v=to[i];if(vis[v]||v==fa)continue;
		gt_rt(v,u,tot);smx[u]=max(smx[u],sz[v]);
	}
	if(smx[u]