自动搬运

查看原文

来自洛谷，原作者为

	DYYqwq 奇迹不是免费的，如果你祈求了希望，也会散播出同等的绝望。 || 圣火昭昭⭐圣光耀耀⭐凡我弟子⭐喵喵喵喵 || 2025年8月23日17时35分

搬运于2025-08-24 21:50:07，当前版本为作者最后更新于2024-09-27 11:51:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这是我的 1000 通过喵！

看 $2^n$，自然联想到 $n$ 维超立方体。

这里偷一张机房同学的图。

首先有一个很厉害的定理，原题中给出了，但是你谷没搬过来。

• 对于一个 $n$ 维超立方体的点，将其划分为两个不交集合，则两个集合之间的边数不少于两集合大小的 $\min$。

证明：

首先定义一个东西叫做“特殊路径”，表示什么呢，就是从 $u \rightarrow v$，从前往后依次更改不相同的二进制位置所形成的路径。

比如说 $1001011 \rightarrow 1101100$ 的特殊路径实际上就是 $1001011 \rightarrow 1101011 \rightarrow 1101111 \rightarrow 1101101 \rightarrow 1101100$。

考虑一条 $u \rightarrow v$ 的边，显然经过它的“特殊路径”有 $2^{n-1}$ 条。因为相当于用这条边固定了一个位置，所有只有 $n-1$ 个位置可以随便选。

对于我们分出的两个集合 $S_1,S_2$，我们先不妨设 $|S_2|\ge|S_1|$，那自然集合之间的特殊路径数为两个集合大小乘积，即 $|S_1||S_2|=|S_1|(2^n-|S_1|)$。

然后显然 $|S_1| \leq \frac{2^n}{2}=2^{n-1}$。一条集合之间的路径必然经过集合之间的边（别笑，这是很重要的！），因此边数 $\ge \frac{总特殊路径边数}{2^{n-1}}=\frac{|S_1|(2^{n-1}-|S_1|)}{2^{n-1}}\ge\frac{|S_1|2^{n-1}}{2^{n-1}}=|S_1|$。证毕。

这是第一个定理，但是远远不够！我们还需自己找到一个性质。

• 在 $n$ 维超立方体上删除 $k$ 条边以后，最多只有一个 $n \times k$ 个点以上的连通块。

这个是好证的。

证明：假设存在两个连通块的大小都 $> n \times k$，根据我们最开始的定理，他们之间的边数也必然 $\ge n \times k + 1$。但是你只能删 $n \times k$ 个边啊！这两个连通块之间肯定有边连接的！但是这和我们的假设矛盾了欸，于是就这么水灵灵的证完了！

根据以上两个定理（主要是第二个，第一个是用于证明第二个的），我们就可以从 $S$ 和 $T$ 开始走，如果发现找到了 $> n \times k$ 个节点，那就说明在最大的连通块中。如果双方都是在最大的连通块中，那必然可以到达。如果一个在一个不在，那必然不行。否则的话有可能在同一个小连通块内，但是这种情况必然能直接走到终点。然后就是这样。

我看大家说 unordered_map 和 gp_hash_table 以及 cc_hash_table 都会被卡掉，需要手写哈希表。

但是其实 unordered_set 是可以过的。因为 unordered_map 是两个键值，而 unordered_set 只有一个值，显然更快。

但是我也手写了哈希表。

这是手写哈希表代码。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf = 1333331;
struct hsb
{
	struct node
	{
		int to , nxt;
	}e[5000010];
	int head[1333341] , tot;
	void add(int v)
	{
		int u = v % inf;
		++ tot;
		e[tot].to = v;
		e[tot].nxt = head[u];
		head[u] = tot;
	}
	bool fnd(int v)
	{
		int u = v % inf;
		for(int i = head[u] ; i != 0 ; i = e[i].nxt)
		{
			int vv = e[i].to;
			if(v == vv) return 1; 
		}
		return 0;
	}
	hsb()
	{
		tot = 0;
		memset(head , 0 , sizeof(head));
	}
}hsh;
int n , k , s , t , a[1000010];
queue<int> q;
int read()
{
	int date = 0 , w = 1;
	char c = 0;
	while(c < '0' || c > '9')
	{
		if(c == '-') w = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9')
	{
		date = ((date << 1) | (c ^ 48));
		c = getchar();
	}
	return date * w;
}
bool bfs(int st , int nd)
{
	if(st == nd)
	{
// 		puts("-1?");
		return 1;
	}
	while(!q.empty()) q.pop();
	hsh = hsb();
	for(int i = 1 ; i <= k ; i ++) hsh.add(a[i]);
	q.push(st) , hsh.add(st);
	int cnt = 1;
	while(!q.empty())
	{
		int u = q.front();
		q.pop();
		for(int i = 0 ; i < n ; i ++) // 找到所有连接它的边。由于只有一位有变化，所以只需考虑这一位。
		{
			int v = (u ^ (1ll << i));
			if(v == nd)
			{
				// puts("-1");
				return 1;
			}
			if(hsh.fnd(v)) continue;
			if((++ cnt) > n * k)
			{
				// puts("111");
				return 1;
			}
			q.push(v) , hsh.add(v);
		}
	}
	return 0;
}
signed main()
{
	scanf("%lld%lld" , &n , &k);
	s = read() , t = read();
	for(int i = 1 ; i <= k ; i ++) a[i] = read();
	printf((bfs(s , t) && bfs(t , s)) ? "TAK" : "NIE");
	return 0;
}

下面是 unordered_set 做法。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf = 1333331;
int n , k , s , t , a[1000010];
int read()
{
	int date = 0 , w = 1;
	char c = 0;
	while(c < '0' || c > '9')
	{
		if(c == '-') w = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9')
	{
		date = ((date << 1) | (c ^ 48));
		c = getchar();
	}
	return date * w;
}
bool bfs(int st , int nd)
{
	if(st == nd) return 1;
	unordered_set<int> s;
	queue<int> q;
	for(int i = 1 ; i <= k ; i ++) s.insert(a[i]);
	q.push(st) , s.insert(st);
	int cnt = 1;
	while(!q.empty())
	{
		int u = q.front();
		q.pop();
		for(int i = 0 ; i < n ; i ++)
		{
			int v = (u ^ (1ll << i));
			if(v == nd) return 1;
			if(s.count(v)) continue;
			if((++ cnt) > n * k) return 1;
			q.push(v) , s.insert(v);
		}
	}
	return 0;
}
signed main()
{
	scanf("%lld%lld" , &n , &k);
	s = read() , t = read();
	for(int i = 1 ; i <= k ; i ++) a[i] = read();
	printf((bfs(s , t) && bfs(t , s)) ? "TAK" : "NIE");
	return 0;
}