AND-MEX Walk

Yorg / 2024-10-06 / 原文

算法

性质

首先容易观察到

\[\text{mex} (w_1, w_1 \And w_2, w_1 \And w_2 \And w_3,\cdots , w_1 \And w_2 \And w_3 \And \cdots w_k) \]

中集合

\[{w_1, w_1 \And w_2, w_1 \And w_2 \And w_3,\cdots , w_1 \And w_2 \And w_3 \And \cdots w_k} \]

显然是单调不增的

显然答案取决于集合的后几位
考虑拆位

拆位

答案为 $0$

当集合中不存在 $0$ 时, 答案显然为 $0$
即存在一条路使得路径上的边权集合, 有一位都为 $1$
考虑用并查集实现

对每一位, 如果当位为 $1$ , 那么加入并查集
判断答案是否为 $0$ , 即为判断两点是否连通, 若连通则必有一方法使得 $0$ 不在集合中

答案为 $1$

对于集合中的某一位 (不为末尾因为不能存在 $1$)
存在一种使下面两个成立

前连续几个( $\geq 2$ )都为 $1$, 这样就能满足集合中拥有大于 $1$ 的数
后连续几个( $\geq 2$ )都为 $0$, 由于其他位被证明不可能存在全 $1$, 所以集合中拥有 $0$

2. 实现

特殊处理不在末尾的并查集
因为只有末位为 $0$ 的数可以把末位的 $1$ 消掉
所以然后事先找好哪些边权末位为 $0$ ，将与这些边相邻的点和一个虚点 $0$ 连起来。如果后询问中出发点 $u$ 可以和虚点 $0$ 连通，那么成立

答案为 $\gt 2$
观察到如果有 $2$ , $1$ , $0$ 存在
那么必须存在 $2 \And a = 1$, 而 $a$ 不存在
所以答案只能为 $0, 1, 2$

代码

#include <bits/stdc++.h>
const int MAXN = 1e5 + 20;

int n, m;

/*并查集*/
class Union_Set
{
    private:

    public:
        int fa[MAXN];

        void init() //
        {
            for (int i = 1; i <= 1e5; i++)
            {
                fa[i] = i;
            }
        }

        int find(int x)
        {
            return fa[x] = (x == fa[x]) ? x : find(fa[x]);
        }

        void merge(int u, int v)
        {
            int fa_u = find(u);
            int fa_v = find(v);

            fa[fa_u] = fa_v;
        }

        bool query(int u, int v)
        {
            return find(u) == find(v); //
        }
} US_all[32], US_even[32];

/*并查集判断每一位的情况*/

int main()
{

    for (int i = 0; i <= 30; i++)
    {
        US_all[i].init();
        US_even[i].init();
    }

    scanf("%d %d", &n, &m);

    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        for (int j = 0; j <= 30; j++)
        {
            if ((w >> j) & 1)
            {
                US_all[j].merge(u, v);
                if(j != 0)
                    US_even[j].merge(u, v);
            }
                
        }

        if (!(w & 1))
        {
            for(int j = 0; j <= 30; j++)
            {
                US_even[j].merge(u, 0);
                US_even[j].merge(v, 0);
            }
        }
    }

    int q;
    
    scanf("%d", &q);
    while(q--)
    {
        int s, t;
        scanf("%d %d", &s, &t);

        /*判断答案是否为 0*/
        bool Answer_is_0 = false;
        for (int i = 0; i <= 30; i++)
        {
            if(US_all[i].query(s, t))
            {
                Answer_is_0 = true;
                break;
            }
        }

        if(Answer_is_0)
        {
            printf("0\n");
            continue;
        }

        /*判断答案是否为 1*/
        bool Answer_is_1 = false;
        for(int i = 1; i <= 30; i++) //这里不取到 1 的原因是你至少不能有 1 吧
        {
            if(US_even[i].query(s, 0)) //只需要判断出发点能否使集合中存在 > 1, 之前已经判断了集合中存在 0, 余下不管怎么走都能到达目的地
            {
                Answer_is_1 = true;
                break;
            }
        }

        if (Answer_is_1)
        {
            printf("1\n");
            continue;
        }

        printf("2\n");
    }

    return 0;
}