题解：UVA1607 与非门电路 Gates

zhangmuning1016 · 2025-03-13 12:07:02 · 题解

题目传送门

思路

• 输出恒为 1，输出任意常数序列即可。
• 输出恒为 0，输出任意常数序列即可。
• 如果输出是 x 或非 x ，那么这最后一个 1 的位置就是 x 的位置。 这个就是整体的思路，再看题目数据的范围，发现 n \le100000 暴力肯定是过不了的。那么怎么做呢？这里要用到 二分。

  代码

  #include<bits/stdc++.h>
  #define int long long
  using namespace std;
  struct node {
  int u,v,w;
  } a[1000001];
  int n,m;
  int fun(int u) {
  for (int i=n-u; i<n; i++){
      a[i].w=1;
  }
  for (int i=0; i<n-u; i++) a[i].w=0;
  for (int i=n+1; i<=n+m; i++) {
      a[i].w=!(a[a[i].u].w&a[a[i].v].w);
  }
  return a[m+n].w;
  }
  signed main() {
  memset(a,0,sizeof(a));
  int T;
  cin>>T;
  for(t--) {
      cin>>n>>m;
      memset(a,0,sizeof(a));
      for (int i=1; i<=m; i++) {
          int u,v;
          cin>>u>>v;
          a[n+i].u=u+n;//存入 
          a[n+i].v=v+n;
      }
      int x=fun(0);
      int a1=fun(n),ans;
      if (x==y)ans=0;
      else {
          int L=0,R=n;
          while(L<R) {
              int mid=(L+R)/2;
              if (fun(mid)==y){
                  R=mid;//找到了当前的答案 
              }
              else{
                  L=mid+1;//说明答案右边 
              } 
          }
          ans=L;
      }
      for (int i=1; i<ans; i++){//输出答案 
          cout<<1;
      } 
      if (ans>=1){
          cout<<"x";
      }
      for (int i=ans+1; i<=n; i++){
          cout<<0;
      }
      cout<<endl;
  }
  }