2013-09-17 14:20
题目描述
在寂寞的夜里，星象仪是非常浪漫的东西。但是，你作为一个精神稍微有点不太正常的
Geek，把原本正常的星象仪改造得像电报发送器一样。当然，你这个的构造还要更加奇葩
一点。具体来说，你的星象仪是一棵满二叉树，二叉树的节点都是有两个输入端和一个输出
端的AND门或者OR门。它们输入和输出的信号都是只是0 或者1 。它们会接受子节点的
输出信号，然后将这两个信号进行AND运算或者OR运算作为自己的输出。然后，根节点
的输出信号就是整个星象仪的输出信号。叶节点的输入信号是由你来调整的，如果二叉树有
K 层，那么你显然有2^K个输入信号可以调整。调整一次当然只能改变一个输入信号。
由于调整输入信号是一件非常麻烦的事情，现在你希望知道对于一台给定的星象仪，如果想要
得到一串给定的信号，至少需要调整多少次输入。
输入格式
输入文件包含多组测试数据。第一行有一个整数T ，表示测试数据的组数。
测试数据的第一行是一个正整数N，表示输入信号的数目。保证N 是2 的整数次幂。
第二行含有一个由0 和1 组成的字符串 S，表示你想要得到的信号。
第三行包含N – 1个整数，按照层次遍历顺序给出满二叉树的每个节点。整数只会是0
或者1 。0 表示二叉树的这个位置是一个 OR门，1 表示是一个 AND门。
输出格式
对于每组测试数据，在单独的一行内输出结果。
样例输入
2
4
010101
0 0 0
4
111111
1 1 1
样例输出
5
4
数据范围与约定
对于30% 的数据， N≤16，S 的长度在100 之内。
对于100% 的数据，T ≤100，N≤8192 ，S 的长度在10000 之内。
//By BLADEVIL var tt, n :longint; s :ansistring; i :longint; que :array[0..30010] of longint; size :array[0..30010] of longint; k :longint; w :array[0..30010] of longint; sum :longint;function min(a,b:longint):longint;begin if a>b then min:=b else min:=a;end;procedure bfs;var h, t, cur :longint; i :longint;begin h:=0; t:=1; que[1]:=1; for i:=1 to k do begin inc(h); cur:=que[h]; read(size[cur]); inc(t); que[t]:=2*cur; inc(t); que[t]:=2*cur+1; end;end;procedure init;var i :longint;begin readln(n); readln(s); i:=1; k:=1; while i<>n do begin k:=k+i*2; i:=i*2; end; k:=k-n; bfs;end;procedure main;var i, len, j :longint;begin init; for i:=k downto k div 2+1 do if size[i]=0 then w[i]:=1 else w[i]:=2; for i:=k div 2 downto 1 do if size[i]=0 then w[i]:=min(w[i*2],w[i*2+1]) else w[i]:=w[i*2]+w[i*2+1]; len:=length(s); i:=1; while s[i]='0' do inc(i); sum:=1; for j:=i to len-1 do if s[j]<>s[j+1] then inc(sum); writeln(w[1]+sum-1);end;begin assign(input,'pla.in'); reset(input); assign(output,'pla.out'); rewrite(output); readln(tt); for i:=1 to tt do main; close(input); close(output);end.