【UOJ349】【WC2018】即时战略 LCT 动态点分治

2018/03/06 15:24
阅读数 19

这是一道交互题

题目大意

  有一棵$n$个点的树。最开始$1$号点是白的,其他点是黑的。

  每次你可以执行一个操作:$explore(x,y)$。要求$x$是一个白点。该函数会返回从$x$到$y$的路径上第二个点的坐标并把该点染白。

  要求你把所有点都染成白色。

  设操作次数为$t$。

  对于$30%$的数据:这棵树是一条链(不保证$1$在链的一端),$n=300000,t=O(n+\log n)$

  对于另外$70%$的数据:$n=300000,t=O(n\log n)$

题解

  数据范围告诉我们链的情况要分开做。

做法1

  有一个简单的做法:维护当前白色节点的两段,每次加入一个新的节点,如果这个节点是黑的,就先判断这个点在一号点的左边还是右边,在进行扩展。

  可以证明扩展次数是$2\ln n$

  记$E(n)$为一条长为$n+1$的链(有$n$个黑色节点),从左边开始扩展的期望次数(最左端是$1$号点)。 $$ \begin{align} E(0)&=0\ E(n)&=1+\frac{1}{n}\sum_{i=0}^{n-1}E(i)\ n(E(n)-1)&=(n-1)(E(n-1)-1)+E(n-1)\ nE(n)-n&=nE(n-1)-n+1-E(n-1)+1+E(n-1)\ nE(n)-nE(n-1)&=1\ E(n)-E(n-1)&=\frac{1}{n}\ E(n)&=\sum_{i=1}^n\frac{1}{i}\approx\ln n \end{align} $$   就是枚举$n$是第几个扩展的,把前面的离散化到$1\sim i-1$。

  因为这题的$1$号点不在一端,次数就要乘以$2$。

  期望操作次数是$n+2\ln n$

  但是这样很大概率拿不了满分。

  我们加入一个新的节点时,可以默认这个点是在$1$号点左边,扩展第一次时判断要扩展的点是否是白的。如果是白的就说明新加入的点在$1$号点右边。

  当然,加入新节点的第一次扩展要随机扩展左边或右边。

  这样期望扩展次数就是$\ln n$了,期望操作次数就是$n+\ln n$

做法2

  问题转化为:每次给你一个新的点,要你找出树上离这个点最近的节点。

  • 动态点分治:动态维护点分治树,在点分治树上面跳。

    时间复杂度:$O(n\log^2 n)$

    操作次数:$O(n\log n)$

  • LCT:每次从根往下在splay上跳,如果调到另一条链上就splay一下继续跳。

    时间复杂度:$O(n\log n)$

    操作次数:$O(n\log n)$

  这两种做法都可以拿到满分。

  如果你写的是动态点分治,你可能会被卡常。

  UPD:动态点分治跑的很快,LCT没写好会被卡操作常数。

代码

###LCT

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<ctime>
#include<cstdlib>
#include<utility>
#include"rts.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
void open(const char *s)
{
#ifndef ONLINE_JUDGE
    char str[100];
    sprintf(str,"%s.in",s);
    freopen(str,"r",stdin);
    sprintf(str,"%s.out",s);
    freopen(str,"w",stdout);
#endif
}
int n;
int b[300010];
int t;
int a[300010][2];
int f[300010];
int l[300010];
int r[300010];
int root(int x)
{
	return !f[x]||(a[f[x]][0]!=x&&a[f[x]][1]!=x);
}
void mt(int x)
{
	l[x]=r[x]=x;
	if(a[x][0])
		l[x]=l[a[x][0]];
	if(a[x][1])
		r[x]=r[a[x][1]];
}
void rotate(int x)
{
	int p=f[x];
	int q=f[p];
	int ps=(x==a[p][1]);
	int qs=(p==a[q][1]);
	int c=a[x][ps^1];
	if(!root(p))
		a[q][qs]=x;
	a[x][ps^1]=p;
	a[p][ps]=c;
	if(c)
		f[c]=p;
	f[p]=x;
	f[x]=q;
	mt(p);
	mt(x);
}
void splay(int x)
{
	while(!root(x))
	{
		int p=f[x];
		if(!root(p))
		{
			int q=f[p];
			if((p==a[q][1])==(x==a[p][1]))
				rotate(p);
			else
				rotate(x);
		}
		rotate(x);
	}
}
void access(int x)
{
	int y=x,t=0;
	while(x)
	{
		splay(x);
		a[x][1]=t;
		mt(x);
		t=x;
		x=f[x];
	}
	splay(y);
}
void gao(int x)
{
	int now=1,v;
	splay(now);
	while(!b[x])
	{
		v=explore(now,x);
		if(v==r[a[now][0]])
			now=a[now][0];
		else if(v==l[a[now][1]])
			now=a[now][1];
		else if(b[v])
		{
			splay(v);
			now=v;
		}
		else
		{
			b[v]=1;
			f[v]=now;
			now=v;
		}
	}
	access(x);
}
void gao1()
{
	int i;
	for(i=2;i<=n;i++)
		if(!b[i])
			gao(i);
}
void gao2()
{
	int x1=1,x2=1;
	int i;
	b[1]=1;
	for(i=2;i<=n;i++)
	{
		int x=i;
		if(b[x])
			continue;
		int v=explore(x1,x);
		if(!b[v])
		{
			b[v]=1;
			x1=v;
			while(x1!=x)
			{
				v=explore(x1,x);
				b[v]=1;
				x1=v;
			}
		}
		else
		{
			while(x2!=x)
			{
				v=explore(x2,x);
				b[v]=1;
				x2=v;
			}
		}
	}
}
void play(int _n,int _t,int type)
{
	n=_n;
	t=_t;
	if(type==3)
		gao2();
	else
		gao1();
}

###动态点分治

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<ctime>
#include<cstdlib>
#include<utility>
#include<vector>
#include"rts.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
void open(const char *s)
{
#ifndef ONLINE_JUDGE
    char str[100];
    sprintf(str,"%s.in",s);
    freopen(str,"r",stdin);
    sprintf(str,"%s.out",s);
    freopen(str,"w",stdout);
#endif
}
vector<int> g[300010];
const double alpha=0.8;
int n;
int b[300010];
int t;
int d[300010];
int f[300010];
int s[300010];
int rebuild;
void gao(int now,int x)
{
	if(now==x)
		return;
	int v=explore(now,x);
	if(b[v])
	{
		while(f[v]!=now)
			v=f[v];
		s[now]-=s[v];
		gao(v,x);
		s[now]+=s[v];
	}
	else
	{
		b[v]=1;
		g[now].push_back(v);
		g[v].push_back(now);
		d[v]=d[now]+1;
		s[v]=1;
		f[v]=now;
		gao(v,x);
		s[now]+=s[v];
	}
	if(s[v]>s[now]*alpha)
		rebuild=now;
}
void dfs(int x,int dep)
{
	b[x]=0;
	for(auto v:g[x])
		if(b[v]&&d[v]>=dep)
			dfs(v,dep);
}
int ss[300010];
void dfs1(int x,int fa)
{
	ss[x]=1;
	for(auto v:g[x])
		if(v!=fa&&!b[v])
		{
			dfs1(v,x);
			ss[x]+=ss[v];
		}
}
int rt,rtsz,num;
void dfs2(int x,int fa)
{
	int mx=0;
	for(auto v:g[x])
		if(!b[v]&&v!=fa)
		{
			dfs2(v,x);
			mx=max(mx,ss[v]);
		}
	mx=max(mx,num-ss[x]);
	if(mx<rtsz)
	{
		rtsz=mx;
		rt=x;
	}
}
int build(int x,int dep,int fa,int mi)
{
	dfs1(x,0);
	num=ss[x];
	rtsz=0x7fffffff;
	dfs2(x,0);
	x=rt;
	b[x]=1;
	d[x]=dep;
	f[x]=fa;
	s[x]=1;
	for(auto v:g[x])
		if(!b[v])
		{
			int rr=build(v,dep+1,x,mi);
			s[x]+=s[rr];
		}
	return x;
}
int cc[300010];
void gao1()
{
	int i;
	for(i=1;i<=n;i++)
		cc[i]=i;
	srand(time(0));
	random_shuffle(cc+1,cc+n+1);
	b[1]=1;
	d[1]=0;
	s[1]=1;
	f[1]=0;
	int r=1;
	for(i=1;i<=n;i++)
		if(!b[cc[i]])
//		if(!b[i])
		{
			gao(r,cc[i]);
//			gao(r,i);
			if(rebuild)
			{
				dfs(rebuild,d[rebuild]);
				int rr=build(rebuild,d[rebuild],f[rebuild],d[rebuild]);
				if(rebuild==r)
					r=rr;
				rebuild=0;
			}
		}
}
void gao3()
{
	int x1=1,x2=1;
	int i;
	b[1]=1;
	for(i=1;i<=n;i++)
		cc[i]=i;
	srand(time(0));
	random_shuffle(cc+1,cc+n+1);
	for(i=1;i<=n;i++)
	{
		int x=cc[i];
		if(b[x])
			continue;
		int v=explore(x1,x);
		if(!b[v])
		{
			b[v]=1;
			x1=v;
			while(x1!=x)
			{
				v=explore(x1,x);
				b[v]=1;
				x1=v;
			}
		}
		else
		{
			while(x2!=x)
			{
				v=explore(x2,x);
				b[v]=1;
				x2=v;
			}
		}
	}
}
void gao2()
{
	int i,v;
	for(i=2;i<=n;i++)
	{
		int x=1;
		while((v=explore(x,i))!=i)
			x=v;
	}
}
void play(int _n,int _t,int type)
{
	n=_n;
	t=_t;
	if(type==3)
		gao3();
	else if(type==2)
		gao2();
	else
		gao1();
}
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部