POI2013 Walk

POI2013 Walk

题目大意：

有$2^n-k$个点，每个点有一个独一无二的、长度为n的01串，但是有k个01串没有出现过。每两个点之间有连边当且仅当两个01串之间有且仅有一个位置是不同的。现在询问x和y两个字符串能不能互相到达。

$PS.$ 感谢commonc大神的题解，以下内容借鉴了他的题解。

commonc的题解

题解：

首先，这样的点所连的图与超立方体类似。

而对于超立方体有如下定理：

如果把所有顶点划分成为两个集合，这两个集合之间的边数至少是这两个点集中较小的那个的点的个数。

利用上述定理，我们可以利用反证法证明如下结论：

删去k个点后，一定至多存在一个连通块它的大小大于nk。

证明：

假设有两个独立的连通块S,T，它们的大小都大于nk。则有 $T \subseteq V - S $ ,即 $\mid V - S \mid \geq \mid T \mid \geq nk+1 $

由上述定理可知:$S$ 与$V-S$ 之间的边至少有nk+1条。

接着因为一共删掉了k个点，而每一个点向外连k条边，所以最多只能删掉nk+1条中的nk条边，也就是说$S$和$V-S$ 之间一定还有边相连。

这与S是一个独立集的假设矛盾，所以结论得证。

有了这个定理，我们可以直接BFS，当步数大于nk后，说明该点在最大的连通块内。

由此就可以快速判断两点是否在一个连通块内了。

Code：

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
typedef long long ll;
using namespace std;
const int N=5000001,M=9999991;
#define hash jksdafdjk
int n,k,tot_id,head[M+5];
char str[100];
struct Hash{
	ll id;int nxt;
}hash[N];
void add_id(ll p){
	int pos=p%M;
	hash[++tot_id]=(Hash){p,head[pos]};
	head[pos]=tot_id;
}
bool is_vis(ll p){
	int pos=p%M;
	for(int i=head[pos];i;i=hash[i].nxt)
		if(hash[i].id==p)return true;
	return false;
}
ll string_ll(){
	scanf("%s",str);
	ll res=0;
	for(int i=0;i<n;i++)
		res=res*2+(str[i]&15);	
	return res;
}
ll s,t,que[N+5];
int solve(ll cur){
	ll res=s+t-cur;
	int L=0,R=0;
	que[R++]=cur;
	add_id(cur);
	while(L<R){
		ll p=que[L++];
		for(int i=0;i<n;i++){
			ll nxt=p^(1LL<<i);
			if(nxt==res)return 1;
			if(!is_vis(nxt)){
				add_id(nxt);
				que[R++]=nxt;
				if(R>=n*k)return 2;
			}
		}
	}
	return 0;
}
ll val[1000005];
void YES(){
	puts("TAK");
	exit(0);
}
void NO(){
	puts("NIE");
	exit(0);
}
int main(){
	scanf("%d%d",&n,&k);
	s=string_ll(),t=string_ll();
	for(int i=1;i<=k;i++){
		val[i]=string_ll();
		add_id(val[i]);
	}
	int ans1=solve(s);
	if(ans1==1)YES();
	else if(ans1!=2)NO();
	memset(head,0,sizeof(head));tot_id=0;
	for(int i=1;i<=k;i++)add_id(val[i]);
	int ans2=solve(t);
	if(ans2==1||ans2==2)puts("TAK");
	else puts("NIE");
	return 0;
}