这道题真的有点“神”啊。=￣ω￣=
因为输入都是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的位置可以用二分来确定。
#include <cstdio> const int maxn = + ;
int a[maxn], b[maxn], o[maxn];
int n, m; int output(int k)
{
for(int i = ; i <= m; i++)
{
int va = a[i] < ? -a[i] > k : o[a[i]];
int vb = b[i] < ? -b[i] > k : o[b[i]];
o[i] = !(va && vb);
}
return o[m];
} int main()
{
//freopen("in.txt", "r", stdin); int T; scanf("%d", &T);
while(T--)
{
scanf("%d%d", &n, &m);
for(int i = ; i <= m; i++) scanf("%d%d", &a[i], &b[i]);
int v0 = output();
int vn = output(n); if(v0 == vn)
for(int i = ; i < n; i++) putchar('');
else
{
int L = , R = n;
while(L < R)
{
int M = (L + R) / ;
if(output(M) == vn) R = M;
else L = M + ;
}
for(int i = ; i < L; i++) putchar('');
putchar('x');
for(int i = L + ; i <= n; i++) putchar('');
}
printf("\n");
} return ;
}
代码君