题意:n个点 每个点上有边权a[i] q次询问 每次询问给出k x y,只有a[x]⊕a[y]=k时有边,问x到y的最短距离。
思路:首先要知道异或一个知识点 a⊕b=c -> c⊕b=a, c⊕a=b.(证明过程可以自己手写模拟一下) 且交换律在异或运算中也满足,所以可以得出k⊕a[x]=a[y]。所以我们对每次询问的x和y首先先考虑a[x]!=a[y] 那么就直接判断 a[x]⊕a[y]是否等于k,如果是就是输出1,不是输出-1.如果a[x]=a[y]那么就去寻找有没有存在a[p]=a[x]⊕k(因为需要寻找一个中间量 让a[x]先到a[p]再到a[y]),如果有,那么这条路距离就是2,没有就是-1。剩下的情况就是输出-1。ps.标记量建议用数组 2的20次也就1e6多点 我第一次用map t了
#include <bits/stdc++.h> using namespace std; typedef long long ll; int _; int vis[1050000]; int n,q; const int N=1e6+5; int a[N]; int main() { cin>>n>>q; for (int i=1;i<=n;i++) { scanf("%d",a+i); vis[a[i]]=1; } int k,c,b; while (q--){ scanf("%d%d%d",&k,&c,&b); c=a[c]; b=a[b]; if ((c^b)==k) puts("1"); else if (c==b&&vis[k^c]==1) puts("2"); else puts("-1"); } return 0; }