JZOJ100047.基因变异 (Standard IO)

\[Description\]

21 世纪是生物学的世纪，以遗传与进化为代表的现代生物理论越来越多的 进入了我们的视野。 如同大家所熟知的，基因是遗传因子，它记录了生命的基本构造和性能。 因此生物进化与基因的变异息息相关，考察基因变异的途径对研究生物学有着 至关重要的作用。现在，让我们来看这样一个模型：
1、所有的基因都可以看作一个整数或该整数对应的二进制码；
2、在 1 单位时间内，基因 x 可能会在其某一个二进制位上发生反转；
3、在 1 单位时间内，基因 x 可能会遭到可感染基因库内任一基因 y 的影响 而突变为 x XOR y。
现在给出可感染基因库，Q 组询问，每组给出初始基因与终止基因，请你 分别计算出每种变异最少要花费多少个单位时间。

\[Input/Output\]

第 1 行两个整数 N, Q； 第 2 行 N 个用空格隔开的整数分别表示可感染基因库内的基因； 接下来 Q 行每行两个整数 S、T，分别表示初始基因与终止基因。

输出 Q 行，依次表示每组初始基因到终止基因间最少所花时间。

\[Sample\]

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

\[Data\ Constraint\]

对于 \(100\)% 的数据，\(0 ≤ N ≤ 20\)，\(1 ≤ Q ≤ 10^5\)，所有基因表示为不超过 \(10^6\) 的 非负整数。

\(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\) 作为队头继续 \(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.

转载于:https://www.cnblogs.com/FibonacciHeap/articles/10123355.html

总结

以上是生活随笔为你收集整理的JZOJ100047.基因变异 (Standard IO)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。