UVA1607 Gates
题意不难理解：描述一个电路结构，电路中若干个输入点都输入x，求此电路的等效电路，并使输入的x数量尽量少
对于一组电路，在输入x的值确定时，输出的值可能与x无关，也可能与x有关，而因为输入输出只可能是0或1，一组电路可能有以下输出情况：
- 永远输出0，与x的值无关
- 永远输出1，与x的
- 输出x
- 输出非x（输出与x相反）
显然对于前两种情况，无论输入x是多少，输出都是不变的，那么此时输入的x就没有任何实际意义，题目要求输入尽可能少的x，那么在这两种情况下可以不输入x。我们可以通过全输入0，在全输入1，比较两次输入的结果：若相同，则说明输出的值与输入的x无关；若不同，则说明输出的值与输入的x有关，即后两种情况
在几个输入接口中，不一定所有的输入都会对输出结果造成影响，那么我们就需要想一种方式来找出对输出无关的位置，替换成定值减少x的输入。那么如何寻找与输出无关的位置呢？
不妨设某组电路有5个输入位置，输入00000时，输出的结果是0。这里我们默认已经通过上文提到的方法确定了这组电路的输出与x有关，那么可以确定，当输入11111的时候，输出的值一定是1（因为每一个输入接口都被取反了，所以答案一定会被取反）
那么我们可以将00000不断改变，使其变为11111，每次改变都记录一个输出的值，尽管我们无法确定输出结果在哪一次改变后发生了改变，我们仍然可以确定的是：一定有一次改变，使得输出结果发生了改变，我们可以用二分法找到这个位置
值得注意的一点是：从整体来看输出的答案并不具有单调性，也就是说随着一次次改变，答案有可能经历被多次在0和1之间来回改变的情况（事实证明很可能会出现这种情况），但这并不会影响我们使用二分法，应为既然00000和11111的输出结果不同，就说明中间一定经历了至少一次从0到1的改变，此次改变前后的这一段答案一定是满足单调性的
而由于答案可能经历多次改变，输入的内容也不一定会相同，但是无论哪种输入，x输入的次数都是相同的
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200000+5;
int n,m;
struct node{
int a,b,w;
}q[maxn];
int work(int k){
for(int i=1;i<=m;i++){
int x=q[i].a;
int y=q[i].b;
int va=x<0?-x>k:q[x].w;
int vb=y<0?-y>k:q[y].w;
q[i].w=!(va&&vb);
}
return q[m].w;
}
int solve(int vx){
int l=1,r=n;
while(l<r){
int mid=l+(r-l)/2;
if(work(mid)==vx)r=mid;
else l=mid+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",&q[i].a,&q[i].b);
int v0=work(0);
int vx=work(n);
if(v0==vx){
for(int i=1;i<=n;i++)printf("0");
}
else{
int x=solve(vx);
for(int i=1;i<x;i++)printf("0");
printf("x");
for(int i=x+1;i<=n;i++)printf("1");
}
printf("\n");
}
return 0;
}