【題目描述】：21 世紀是生物學的世紀，以遺傳與進化為代表的現代生物理論越來越多的進入了我們的視野。如同大家所熟知的，基因是遺傳因子，它記錄了生命的基本構造和性能。因此生物進化與基因的變異息息相關，考察基因變異的途徑對研究生物學有著至關重要的作用。現在，讓我們來看這樣一個模型：1、所有的基因都可以看作一個整數或該整數對應的二進制碼；2、在 1 單位時間內，基因 x 可能會在其某一個二進制位上發生反轉；3、在 1 單位時間內，基因 x 可能會遭到可感染基因庫內任一基因y的影響而突變為 x XOR y。現在給出可感染基因庫，Q 組詢問，每組給出初始基因與終止基因，請你分別計算出每種變異最少要花費多少個單位時間。 【輸入描述】：第 1 行兩個整數 N, Q；第 2 行 N 個用空格隔開的整數分別表示可感染基因庫內的基因；接下來 Q 行每行兩個整數 S、T，分別表示初始基因與終止基因。 【輸出描述】：輸出 Q 行，依次表示每組初始基因到終止基因間最少所花時間。 【樣例輸入】：3 3 1 2 3 3 4 1 2 3 9【樣例輸出】：2 1 2【時間限制、數據范圍及描述】：時間：1s 空間：256M對于 20%的數據，N=0；額外 40%的數據，1≤Q≤100，所有基因表示為不超過 10^4 的非負整數；對于 100%的數據，0≤N≤20，1≤Q≤10^5，所有基因表示為不超過 10^6 的非負整數。本題可以bfs求出0~所有狀態的解,因為所有狀態的總個數為2^20,然后輸出a^b所對應的解即可. (這里注意:異或的順序改變并不會改變最終答案)Code: #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<ctime> #include<queue> using namespace std; const int N=45,M=1<<20; int n,q,s,t,a[N],ans[M]; void bfs(){queue<int> Q;memset(ans,-1,sizeof(ans));Q.push(0);ans[0]=0;while(!Q.empty()){int now=Q.front();Q.pop();for(int i=1;i<=n+20;i++){int to=now^a[i];if(ans[to]!=-1){continue;}ans[to]=ans[now]+1;Q.push(to);}} } int main(){int s,t;scanf("%d%d",&n,&q);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}a[n+1]=1;for(int i=n+2;i<=n+20;i++){a[i]=2*a[i-1];}bfs();for(int i=1;i<=q;i++){scanf("%d%d",&s,&t);printf("%d\n",ans[s^t]);}return 0; }

轉載于:https://www.cnblogs.com/ukcxrtjr/p/11521791.html

總結

以上是生活随笔為你收集整理的UOJ #577. 基因变异的全部內容，希望文章能夠幫你解決所遇到的問題。

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