星象仪

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门。

输出格式

对于每组测试数据，在单独的一行内输出结果。

样例输入

010101

0 0 0

111111

1 1 1

样例输出

数据范围与约定

对于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.