[CF1879E] Interactive Game with Coloring 题解

很诡谲的一道题。

首先特判菊花，答案为

1

。

不难发现题目要求每次行动都往父亲走，这显然表明父亲边的颜色必须与这个点连的其他边不同，这个条件是必要的。

根据这个条件可以发现，如果树上没有链，即每个点要么是叶子要么有两个儿子，那么可以令

\text{col}_i=\text{dep}_i\bmod 2+1

，这样一定能赢。

如果有链，则可能出现多个点连边颜色可重集为

\{1,2\}

，同时这些点中有一些父亲边是

1

，有一些是

2

，这时无法判断怎么往父亲走。于是

k=2

不一定正确。调整发现

k=3

一定正确，令

\text{col}_i=\text{dep}_i\bmod 3+1

，则一个链上的点的颜色集合，与父亲边在哪一个颜色，是一一对应的。

现在问题在于如何判断能否

k=2

，不难发现

1

的所有子树相互独立，于是对每个子树分别判断。对于链上且不是端点的点，其颜色集合一定为

\{1,2\}

，不妨强制令其往颜色

1

走（注意这个强制是同时应用于整棵树的），这样链上的边颜色就有了明确的限制。然后枚举子树顶端向根

1

的连边涂

1

还是

2

，这样直接确定了一整颗子树的颜色，直接判能不能使得链上非端点的点满足上文的限制即可。

视实现，复杂度在

\mathcal{O}(n)\sim\mathcal{O}(n^2)

左右，不过这个东西并不重要。

code

CPP

#include<bits/stdc++.h>
#define pb emplace_back
#define mp make_pair
#define pob pop_back
using namespace std;
typedef long long ll;
const ll maxn=107,p=1e9+7,ee=1e18;
ll n,k,k1,k2,c[maxn],dep[maxn],buc[maxn],fs[maxn];
ll siz[maxn],dfn[maxn],L,R,dnt;
vector<ll> edge[maxn];
void dfs1(ll u){
	siz[u]=1,dfn[u]=++dnt;
	for(auto v:edge[u]) dep[v]=dep[u]+1,dfs1(v),siz[u]+=siz[v];
}
bool check(ll x){
	L=dfn[x],R=dfn[x]+siz[x]-1;
	for(ll i=1;i<=n;i++)if(L<=dfn[i]&&dfn[i]<=R) c[i]=(dep[i]&1)+1;
	ll flg=1;
	for(ll i=1;i<=n;i++)if(L<=dfn[i]&&dfn[i]<=R&&edge[i].size()==1&&c[i]!=1){flg=0; break;}
	if(flg) return 1;
	for(ll i=1;i<=n;i++)if(L<=dfn[i]&&dfn[i]<=R) c[i]=((dep[i]+1)&1)+1;
	flg=1;
	for(ll i=1;i<=n;i++)if(L<=dfn[i]&&dfn[i]<=R&&edge[i].size()==1&&c[i]!=1){flg=0; break;}
	return flg;
}
bool check2(void){
	for(auto x:edge[1])if(!check(x)) return 0;
	return 1;
}
int main(void){
	//freopen("data.in","r",stdin);
	//freopen("data.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n;
	for(ll i=2,u;i<=n;i++) cin>>u,fs[i]=u,edge[u].pb(i);
	dfs1(1);
	if(*max_element(fs+2,fs+1+n)==1){
		k=1;
		for(ll i=2;i<=n;i++) c[i]=1;
	}else{
		if(!check2()){
			k=3;
			for(ll i=1;i<=n;i++) c[i]=dep[i]%3+1;
		}else k=2;
	}
	cout<<k<<endl;
	for(ll i=2;i<=n;i++) cout<<c[i]<<" "; cout<<endl;
	for(ll st;;){
		cin>>st;
		if(st!=0) exit(0);
		for(ll i=1;i<=k;i++) cin>>buc[i];
		if(k==1) cout<<1<<endl;
		else if(k==2){
			if(!buc[1]) cout<<2<<endl;
			else if(!buc[2]) cout<<1<<endl;
			else if(buc[1]==1) cout<<1<<endl;
			else cout<<2<<endl;
		}else if(k==3){
			if(buc[1]&&buc[2]) cout<<1<<endl;
			else if(buc[1]&&buc[3]) cout<<3<<endl;
			else if(buc[2]&&buc[3]) cout<<2<<endl;
			else for(ll i=1;i<=k;i++)if(buc[i]==1){
				cout<<i<<endl;
				break;
			}
		}
	}
	return 0;
}

[CF1879E] Interactive Game with Coloring 题解

文章操作

相关推荐

评论

[CF1879E] Interactive Game with Coloring 题解