做题笔记_异或图

原题戳这

题目大意：

有点集V，其中有n个点，第i个点的点权为a[i]。
设置q次询问，每次询#给出k，x，y。如果a[u]^a[v]==k则u、v两点之间有路径连接。
要给出每次询问时，xy间的最短路径条数，不存在则出-1。

我的想法

对于任意两点u和v，有一以下三种情况：

1.有一条边直接连接
2.有多条边间接连接
3.没有边连接。

1.若直接连接则只要满足(a[u]^a[v]==k)即可。

2.a.假设uv之外有p点作为中介点（有两条边间接连接uv）

则有a[u]^k==a[p],a[v]^k==a[p]同时成立，观察两式形式可知a[u]==a[v]。
也就是说，只要a[u]==a[v]，再在剩下的点里找到一个p，使得a[u or v]^k==a[p],就可以说明uv间最短路径为2。

2.b.假设uv之外有p点作为中介点（有两条边间接连接uv）

(这里以两个点举例，更多点和两个点类似)
上图的连接情况可以得到以下式子：

a[u]^k==a[p] —— A
a[v]^k== a[r] —— B

将A，B的左边右边分别异或，得到a[u]^a[v]^k^k==a[p]^a[q],

即a[u]^a[v]==k

这表示uv间有一条路径相连，和情况2的大前提uv间不直接相连矛盾，故排除。

3.不满足以上两种情况即是第三种情况。

代码处理

对于a[x]==a[y]的询问，如果每一次都要从1到n去遍历寻找是否有a[p]==a[x]^k成立，那时间复杂度太高了。
我们可以在开始就用rcd[]数组存下所有a[i]是否出现的状态，在需要寻找a[p]是否存在的时候直接访问rcd[a[x]^k]是否为真即可，用空间换时间，在这里还是很高效的。
下面附上代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
int n,q;
int a[2*N];
int rcd[2*N];
int k,x,y;
int main(){
    scanf("%d %d",&n,&q);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        rcd[a[i]]++;
    }
    while(q--){
        scanf("%d %d %d",&k,&x,&y);
        if((a[x]^a[y])==k){
            printf("1\n");
        }else if(a[x]==a[y]&&rcd[(a[x]^k)]){
            printf("2\n");
        }else printf("-1\n");
    }
}