UVa 1607

链接：

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4482

题意：

可以用与非门（NAND）来设计逻辑电路。每个NAND门有两个输入端，输出为两个输入端与非运算的结果。
即输出0当且仅当两个输入都是1。给出一个由m（m≤200000）个NAND组成的无环电路，
电路的所有n个输入（n≤100000）全部连接到一个相同的输入x。
请把其中一些输入设置为常数，用最少的x完成相同功能。输出任意方案即可。

分析：

因为只有一个输入x，所以整个电路的功能不外乎4种：常数0、常数1、x及非x。
先把x设为0，再把x设为1，如果二者的输出相同，整个电路肯定是常数，任意输出一种方案即可。
如果x=0和x=1的输出不同，说明电路的功能是x或者非x。不妨设x=0时输出0，x=1时输出1。
现在把第一个输入改成1，其他仍设为0（记这样的输入为1000…0），如果输出是1，则得到了一个解x000…0。
如果1000…0的输出也是0，再把输入改成1100…0，如果输出是1，则又得到了一个解1x00…0。
如果输出还是0，再尝试1110…0，如此等等。由于输入全1时输出为1，这个算法一定会成功。

但是，有一个问题我想不明白，紫书上说可以用二分法来确定1的个数。如果是这样的话，就必须要有
111...0（1的个数为输出刚好发生变化时的个数，设为p）的输出等于1111...0（1的个数大于p）的输出，
也就是说，当把0改为1改到输出刚好发生变化时，再把后面的0改为1，输出都不会发生变化。
如何证明这一点呢？恳请各位大神指教。

代码：

#include <cstdio>

struct NAND {
    int a, b;
    bool o;
} nand[200000+5];

int n, m;

bool output(int R){
    for(int i = 1; i <= m; i++){
        int a = nand[i].a, b = nand[i].b;
        a = a < 0 ? -a > R : nand[a].o;
        b = b < 0 ? -b > R : nand[b].o;
        nand[i].o = !(a && b);
    }
    return nand[m].o;
}

int solve(bool aim){
    int L = 1, R = n;
    while(L < R){
        int M = L + (R - L) / 2;
        if(output(M) == aim) R = M;
        else L = M + 1;
    }
    return L;
}

int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= m; i++) scanf("%d%d", &nand[i].a, &nand[i].b);
        bool all0 = output(n), all1 = output(0);
        if(all0 == all1){
            for(int i = 0; i < n; i++) printf("0");
            printf("
");
        }
        else{
            int x = solve(all0);
            for(int i = 1; i < x; i++) printf("0");
            printf("x");
            for(int i = x + 1; i <= n; i++) printf("1");
            printf("
");
        }
    }
    return 0;
}