【搜索】JZOJ_100047 基因变异

本文主要是介绍【搜索】JZOJ_100047 基因变异，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

给出 $N$ 个数， $Q$ 个询问，每次询问从 $a$ 变换到 $b$ 的最小次数。
有两种变换方法：
$1 .$ 把当前数的二进制下任意一位取反
$2 .$ 把当前数与给出的 $N$ 个数其中一个进行异或操作

思路

对于第一种操作，可以看作是与 $2$ 的幂进行异或操作。
手推一下，可以发现 $a$ 到 $b$ 的异或次数，其实与 $0$ 到 $a$ ^ $b$ 的次数等同，然后我们就可以用广搜求出 $0$ 到每个数的最小次数了。

代码

#include<queue>
#include<cmath> 
#include<cstdio>
#include<cstring>
#include<algorithm>const int MAXN = 2e6 + 1;
int N, Q, a, b;
int gene[41], v[MAXN], d[MAXN];
std::queue<int> q;void bfs() {for (int i = 0; i < 20; i++)gene[++N] = 1 << i;q.push(0);v[0] = 1;d[0] = 0;while (q.size()) {int x = q.front();q.pop();for (int i = 1; i <= N; i++) {int y = x ^ gene[i];if (!v[y]) {v[y] = 1;d[y] = d[x] + 1;q.push(y);}}}
}int main() {scanf("%d %d", &N, &Q);for (int i = 1; i <= N; i++)scanf("%d", &gene[i]);bfs();for (; Q; Q--) {scanf("%d %d", &a, &b);printf("%d\n", d[a ^ b]);}
}

飞天

$a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^{a^a}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}$