\[Description\]

21 世紀是生物學的世紀，以遺傳與進化為代表的現(xiàn)代生物理論越來越多的 進入了我們的視野。 如同大家所熟知的，基因是遺傳因子，它記錄了生命的基本構造和性能。 因此生物進化與基因的變異息息相關，考察基因變異的途徑對研究生物學有著 至關重要的作用。現(xiàn)在，讓我們來看這樣一個模型：
1、所有的基因都可以看作一個整數(shù)或該整數(shù)對應的二進制碼；
2、在 1 單位時間內(nèi)，基因 x 可能會在其某一個二進制位上發(fā)生反轉(zhuǎn)；
3、在 1 單位時間內(nèi)，基因 x 可能會遭到可感染基因庫內(nèi)任一基因 y 的影響 而突變?yōu)?x XOR y。
現(xiàn)在給出可感染基因庫，Q 組詢問，每組給出初始基因與終止基因，請你 分別計算出每種變異最少要花費多少個單位時間。

\[Input/Output\]

第 1 行兩個整數(shù) N, Q； 第 2 行 N 個用空格隔開的整數(shù)分別表示可感染基因庫內(nèi)的基因； 接下來 Q 行每行兩個整數(shù) S、T，分別表示初始基因與終止基因。

輸出 Q 行，依次表示每組初始基因到終止基因間最少所花時間。

\[Sample\]

3 3 1 2 3 3 4 1 2 3 9 2 1 2

\[Data\ Constraint\]

對于 \(100\)% 的數(shù)據(jù)，\(0 ≤ N ≤ 20\)，\(1 ≤ Q ≤ 10^5\)，所有基因表示為不超過 \(10^6\) 的 非負整數(shù)。

\(x\ xor\ a_1\ xor\ a_2....=y\)

\(a_1\ xor\ a_2....=x\ xor\ y\)

所以我們可以預處理所有的 \(a_i\),然后得出所有的 \(dis_{x\ xor\ y}\)。

預處理 \(a_i\) 的時候我們將 \(num_i\) 和 \(2^k (2^k \leq 10^6)\) 丟到隊列里面去。然后用 \(0\) 作為隊頭繼續(xù) \(xor\) 即可。

// T2Uses math;varbucket:array[-1..5100000] of boolean;queue:array[-1..5100000] of longint;dis:array[-1..2100000] of longint;num:array[-1..100] of longint;u,n,m,i,tmp,maxn,head,tail:longint; beginread(n,m);for i:=1 to n do read(num[i]);for i:=0 to 19 do begin inc(n); num[n]:=1 << i; end;head:=0; tail:=1; queue[1]:=0; dis[0]:=0; bucket[0]:=True;while(head<tail) dobegininc(head);u:=queue[head];for i:=1 to n dobegintmp:=u xor num[i];if (bucket[tmp]=False) thenbegininc(tail); queue[tail]:=tmp;dis[tmp]:=dis[u]+1;bucket[tmp]:=True;end;end;end;for i:=1 to m dobeginread(head,tail);writeln(dis[head xor tail]);end; end.

轉(zhuǎn)載于:https://www.cnblogs.com/FibonacciHeap/articles/10123355.html

總結

以上是生活随笔為你收集整理的JZOJ100047.基因变异 (Standard IO)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。