这道题真的有点“神”啊。=￣ω￣=
因为输入都是x，所以整个电路的功能一共就四种：0， 1， x，!x
所以就确定了这样一个事实：如果电路的输出是常数，那么所有的输入都可以优化成常数。
否则，只需要将一个输入变为变量即可，其他的全部为常数。
从00...0到11...1，在1的数量增多的过程中一定有一个位置，使得output(k) = output(n), output(k-1) = output(0)。output(k)表示前面有k个1，有n-k个0.
那么将第k为设为变量即可，k前面输出0，k后面输出1即可。
k的位置可以用二分来确定。
1 #include <cstdio> 2 3 const int maxn = 200000 + 10; 4 int a[maxn], b[maxn], o[maxn]; 5 int n, m; 6 7 int output(int k) 8 { 9 for(int i = 1; i <= m; i++) 10 { 11 int va = a[i] < 0 ? -a[i] > k : o[a[i]]; 12 int vb = b[i] < 0 ? -b[i] > k : o[b[i]]; 13 o[i] = !(va && vb); 14 } 15 return o[m]; 16 } 17 18 int main() 19 { 20 //freopen("in.txt", "r", stdin); 21 22 int T; scanf("%d", &T); 23 while(T--) 24 { 25 scanf("%d%d", &n, &m); 26 for(int i = 1; i <= m; i++) scanf("%d%d", &a[i], &b[i]); 27 int v0 = output(0); 28 int vn = output(n); 29 30 if(v0 == vn) 31 for(int i = 0; i < n; i++) putchar('0'); 32 else 33 { 34 int L = 1, R = n; 35 while(L < R) 36 { 37 int M = (L + R) / 2; 38 if(output(M) == vn) R = M; 39 else L = M + 1; 40 } 41 for(int i = 1; i < L; i++) putchar('0'); 42 putchar('x'); 43 for(int i = L + 1; i <= n; i++) putchar('1'); 44 } 45 printf(" "); 46 } 47 48 return 0; 49 }