【JZOJ100047】基因变异【BFS】

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

题目大意：

题目链接：https://jzoj.net/senior/#main/show/100047
题目图片：
http://wx1.sinaimg.cn/mw690/0060lm7Tly1fy7gss4ijmj30j50cujrv.jpg
http://wx4.sinaimg.cn/mw690/0060lm7Tly1fy7gss4gyaj30j20asdfx.jpg
已知数组$a$，两种操作：

• 将$x$变成$xxor{a}_i$
• 将$x$二进制下任意一位取反。

求从$x$变成$y$的最少步数。

---

思路：

如果我们有一个数$z$使得$xxorz=y$，那么很明显的$z$就是我们要求的答案。
反过来得$xxory=z$。
所以，其实$x$到$y$的最少步数就是$0$到$z$的最少步数！
那么就从$0$开始$BFS$，求出不超过 z = m a x { 1111111 } z=max\{1111111\} z=max{1111111}的答案（因为$xor$最大就是$1111111$了）。然后就可以$O(1)$输出了。
思维好题。

---

代码：

#include <cstdio>
#include <queue>
#define ri register
using namespace std;const int N=1200000;
int n,u,v,Q,a[N],s,t,ans[N];
bool vis[N];
char c;int read()
{u=0;c=getchar();while (c<'0'||c>'9') c=getchar();while (c>='0'&&c<='9')u=(u<<3)+(u<<1)+c-48,c=getchar();return u;
}int write(int x)
{if (x>9) write(x/10);putchar(x%10+48);
}void bfs()
{queue<int> q;q.push(0);vis[0]=1;while (q.size()){u=q.front();q.pop();for (ri int i=1;i<=n;i++)  //选择每一个数xorif (!vis[u^a[i]]){vis[u^a[i]]=1;ans[u^a[i]]=ans[u]+1;q.push(u^a[i]);}for (ri int i=0;i<=19;i++)  //选择每一位取反{if ((u&(1<<i))==(1<<i)) v=u-(1<<i);else v=u+(1<<i);if (!vis[v]){vis[v]=1;ans[v]=ans[u]+1;q.push(v);}}}
}int main()
{n=read();Q=read();for (ri int i=1;i<=n;i++)a[i]=read();bfs();while (Q--){s=read();t=read();write(ans[s^t]);putchar(10);}return 0;
}

这篇关于【JZOJ100047】基因变异【BFS】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---