正題

---

題目大意

一個長度為$n$的序列$a$。
對于一個數每秒可以將一個二進制位取反或異或$a$中的一個數。
$q$個詢問，詢問從$x$變化到$y$最少要多少秒。

---

解題思路

對于一個$x和y$，設
$$xxorw=y$$
$$?x=yxorw$$
$$xxory=w$$
所以我們對于每個詢問，我們只需要求$0$變成$w$的距離就好了。
由于起點只有一個，我們可以用$bfs$預處理$0$到$w$距離。
時間復雜度:$O(2^{20}(n+20)+q)$

---

$code$

#include<cstdio> #include<queue> #include<cctype> #define MS 2097151 using namespace std; int n,Q,a[25],v[MS+10]; queue<int> q; inline char Getchar() {static char buf[100000],*p1=buf+100000,*pend=buf+100000;if(p1==pend){p1=buf; pend=buf+fread(buf,1,100000,stdin);if (pend==p1) return -1;}return *p1++; } inline long long read() {char c;int d=1;long long f=0;while(c=Getchar(),!isdigit(c))if(c==45)d=-1;f=(f<<3)+(f<<1)+c-48;while(c=Getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48;return d*f; } inline void write(register long long x) {if(x<0)write(45),x=-x;if(x>9)write(x/10);putchar(x%10+48);return; } void bfs()//預處理 {v[0]=1;q.push(0);int y,i;while(!q.empty()){int x=q.front();q.pop();for(i=1;i<=n;i++)//異或a中的數{y=x^a[i];if(!v[y]){v[y]=v[x]+1;q.push(y);}}for(i=0;i<=20;i++)//位數取反{y=x^(1<<i);if(!v[y]){v[y]=v[x]+1;q.push(y);}}} } int main() {freopen("data.in","r",stdin);freopen("data.out","w",stdout);n=read();Q=read();for(int i=1;i<=n;i++)a[i]=read();bfs();for(int i=1;i<=Q;i++) {int x,y,z;x=read();y=read();write(v[x^y]-1);putchar('\n');} }

總結

以上是生活随笔為你收集整理的jzoj100047-基因变异【位运算,bfs】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。