LG-P3552 [POI2013]SPA-Walk Solution

更好的阅读体验戳此进入

（建议您从上方链接进入我的个人网站查看此 Blog，在 Luogu 中图片会被墙掉，部分 Markdown 也会失效）

题面

存在 $2^n$$2^n$ 个长度为 $n$$n$ 的 $01$$01$ 串，两个 $01$$01$ 串之间有边当且仅当两者之间仅有一位不同，或者说 $x,y$$x, y$ 之间有边当且仅当 $x\oplus y=2^t$$x \oplus y = 2^t$。我们称这样的一个图为 $n$$n$ 维超立方体（n-dimensional hipercube）。现在从这其中去掉 $k$$k$ 个串 $s_1,s_2,\cdots ,s_k$$s_1, s_2, \cdots, s_k$，给定两个串 $S,T$$S, T$，求两者之间是否能够到达。

能到达输出 TAK，反之输出 NIE。

$1\le n\le 60,0\le k\le min({10}^6,2^n-1),n\times k\le 5\times {10}^6$$1 \le n \le 60, 0 \le k \le \min(10^6, 2^n - 1), n \times k \le 5 \times 10^6$。

输入格式

n k

S T

$s_1$$s_1$

$s_2$$s_2$

$\cdots$$\cdots$

$s_k$$s_k$

（偷个懒就不写文字叙述了。。。）

Solution

这道题我本来还以为是和 LG-P7966 [COCI2021-2022#2] Hiperkocka 差不多的题，该题题解，按照那道题的思路想了一下然后假了，改了一下之后 T 掉了，寄，和之前的题关系不是很大，只是定义一样。

Lemma 1：对于一个 $n$$n$ 维超立方体，令点集为 $S$$S$，将其所有的点分为两个点集 $S_1,S_2$$S_1, S_2$，$S_1\cup S_2=S,S_1\cap S2=\varphi$$S_1 \cup S_2 = S, S_1 \cap S2 = \phi$，则两点集之间的边集的大小一定不小于两点集之间较小者的大小，也就是 $|\{(u,v)|u\in S_1,v\in S_2,u\oplus v=2^t\}|=min(\left|S_1\right|,\left|S_2\right|)$$\left\vert \{ (u, v) \vert u \in S_1, v \in S_2, u \oplus v = 2^t \} \right\vert = \min(\left\vert S_1 \right\vert, \left\vert S_2 \right\vert)$。

证明：A proof is left to the reader.

证明：这东西大多数地方都没有人证明，甚至官方题解，感觉可以当成一个已知结论记住，关于严谨证明网上也找到了个大佬的证明（看不懂），戳此进入。

Lemma 2：对于一个 $n$$n$ 维超立方体，将其删去 $k$$k$ 个点后，最多仅能够形成 $1$$1$ 个点集大小大于 $n\times k$$n \times k$ 的连通块。

证明：假设我们现在有两个连通块，其点集分别为 $S_1,S_2$$S_1, S_2$，显然 $S_1\cap S_2=\varphi$$S_1 \cap S_2 = \phi$，我们设 $\left|S_1\right|,\left|S_2\right|\ge n\times k$$\left\vert S_1 \right\vert, \left\vert S_2 \right\vert \ge n \times k$，令点的全集为 $S$$S$，则显然 $S_2\subset S\cap \overline{S_1}$$S_2 \subset S \cap \overline{S_1}$。我们又可以通过 Lemma 1 知道 $S_1$$S_1$ 和 $S_2\subset S\cap \overline{S_1}$$S_2 \subset S \cap \overline{S_1}$ 之间的边集大小不小于 $min(\left|S_1\right|,|S\cap \overline{S_1}|)$$\min(\left\vert S_1 \right\vert, \left\vert S \cap \overline{S_1} \right\vert)$，也就是其边集 $E$$E$ 满足 $E\ge n\times k+1$$E \ge n \times k + 1$，也就是说如果我们想要形成这两个连通块就必须要断开至少 $n\times k+1$$n \times k + 1$ 条边，而我们去掉 $k$$k$ 个点只能断开 $n\times k$$n \times k$ 条边，无法形成这两个连通块，$◻$$\square$。

于是只要有了 Lemma 2，我们就可以很容易想到，令出发点和终点分别为 $S,T$$S, T$，如果两者可以互通，那么他们要么都在唯一的大于 $n\times k$$n \times k$ 的连通块内，要么在某一个小于等于 $n\times k$$n \times k$ 的连通块内，所以我们只需要搜至多 $n\times k$$n \times k$ 的点数，如果两者都不在小于 $n\times k$$n \times k$ 的连通块中，那么一定同在唯一的大连通块中，反之如果在同一个连通块内那么一定可以被搜到。

于是我们分别从 $S,T$$S, T$ 进行爆搜，各自维护一个 unordered_set 记录其所在连通块有哪些点，如果从搜索过程中遇到另一个点了，则两者同在一个小连通块中，直接输出连通然后 exit，如果连通块大小超过 $n\times k$$n \times k$ 了那么直接标记一下然后 return。两者都搜完后如果两个连通块都超过 $n\times k$$n \times k$ 了那么一定同在一个大块，反之则一定不在同一个块，不连通。

另外个人建议把二进制转成 long long 再存，否则还会存在一个 hash 的复杂度，虽然我感觉好像嗯搞也能过？？？

然后写位移的时候记得写成 1ll。

这个的复杂度大概是 $O(n^{2}k)$$O(n^2k)$ 级别的，但是常数可能会很大，然后我不太确定这玩意能不能被卡成类似 $O(2^n)$$O(2^n)$ 级别的，但是因为有 $n\times k$$n \times k$ 这个限制感觉似乎是可以被严谨证明的，我不会。

A proof is left to the reader.

然后。。。Luogu 评测记录

unordered_set 寄了，cc_hash_table 寄的更多，经典被卡常，调了亿会怎么 Luogu 上都是两个点 TLE，一个点 MLE，于是开始手搓 hash 挂链，队列之类的，最终终于在 Luogu 上把这破题给卡过去了。。。

Code

xxxxxxxxxx
116
1
#define _USE_MATH_DEFINES
2
#include <bits/extc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
/******************************
12
abbr
13
uex => unexist
14
******************************/
15

16
using namespace std;
17
using namespace __gnu_pbds;
18

19
mt19937 rnd(random_device{}());
20
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
21
bool rnddd(int x){return rndd(1, 100) <= x;}
22

23
typedef unsigned int uint;
24
typedef unsigned long long unll;
25
typedef long long ll;
26
typedef long double ld;
27

28
template<typename T = int>
29
inline T read(void);
30

31
ll str2ll(char* s, int n){
32
    ll ret(0), base(0);
33
    for(int i = n - 1; i >= 0; --i)
34
        ret += (1ll << (base++)) * (s[i] == '0' ? 0 : 1);
35
    return ret;
36
}
37
#define MOD 2737321
38
struct Edge{
39
    Edge* nxt;
40
    ll val;
41
    OPNEW;
42
}eData[4145149];
43
ROPNEW(eData);
44
Edge* head[2737330];
45
void clear(void){memset(head, 0, sizeof(head));}
46
void Add(ll val){
47
    int idx = val % MOD;
48
    head[idx] = new Edge{head[idx], val};
49
}
50
bool Check(ll val){
51
    int idx = val % MOD;
52
    for(auto i = head[idx]; i; i = i->nxt)
53
        if(i->val == val)return true;
54
    return false;
55
}
56

57
ll S, T;
58
int N, K;
59
ll cur[5100000];
60
int fnt(0), til(0);
61
void bfs(ll S, ll T){
62
    fnt = til = 0;
63
    cur[til++] = S;
64
    Add(S);
65
    while(fnt < til){
66
        ll tp = cur[fnt++];
67
        for(int base = 0; base <= N - 1; ++base){
68
            ll val = tp ^ (1ll << base);
69
            if(val == T)printf("TAK\n"), exit(0);
70
            if(Check(val))continue;
71
            else{
72
                Add(val);
73
                cur[til++] = val;
74
            }
75
        }
76
        if(til > N * K)return;
77
    }
78
    printf("NIE\n"); exit(0);
79
}
80
char c[65];
81
vector < ll > values;
82
int main(){
83
    // freopen("in.txt", "r", stdin);
84
    N = read(), K = read();
85
    scanf("%s", c); S = str2ll(c, N);
86
    scanf("%s", c); T = str2ll(c, N);
87
    if(S == T)printf("TAK\n"), exit(0);
88
    for(int i = 1; i <= K; ++i){
89
        scanf("%s", c); ll tmpp = str2ll(c, N);
90
        values.push_back(tmpp);
91
    }
92
    for(auto i : values)Add(i);
93
    bfs(S, T);
94
    clear();
95
    for(auto i : values)Add(i);
96
    bfs(T, S);
97
    printf("TAK\n");
98
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
99
    return 0;
100
}
101

102
template<typename T>
103
inline T read(void){
104
    T ret(0);
105
    short flag(1);
106
    char c = getchar();
107
    while(c != '-' && !isdigit(c))c = getchar();
108
    if(c == '-')flag = -1, c = getchar();
109
    while(isdigit(c)){
110
        ret *= 10;
111
        ret += int(c - '0');
112
        c = getchar();
113
    }
114
    ret *= flag;
115
    return ret;
116
}

UPD

update-2022_09_27 初稿