题解：P3552 [POI2013] SPA-Walk

· · 题解

这是我的 1000 通过喵！

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

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

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

证明：

首先定义一个东西叫做“特殊路径”，表示什么呢，就是从 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 \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;
}