题解：UVA1607 与非门电路 Gates

furina_yyds · 2025-01-13 14:48:29 · 题解

题意

有一个电路，电路中一些个输入 x，求与这个电路功能相同的电路，并使输入的 x 数量尽量少。

思路

乍一看是没思路的，正是因为没思路，所以才要使用一个逆向算法，二分查找。

由于最小的 x 满足单调性，则二分枚举 x。

电路可能有四种情况：

• 恒为一。
• 恒为零。
• 为 x。
• 为非 x。

注意

由于答案可能经历多次改变，输入的内容也不一定会相同，但是无论哪种输入，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 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);
        for (int i = 1; i <= m; i++) {
            int x = q[i].a;
            int y = q[i].b;
            int va = x < 0? -x > 0 : q[x].w;
            int vb = y < 0? -y > 0 : q[y].w;
            q[i].w =!(va && vb);
        }
        int v0 = q[m].w;
        for (int i = 1; i <= m; i++) {
            int x = q[i].a;
            int y = q[i].b;
            int va = x < 0? -x > n : q[x].w;
            int vb = y < 0? -y > n : q[y].w;
            q[i].w =!(va && vb);
        }
        int vx = q[m].w;
        if (v0 == vx) {
            for (int i = 1; i <= n; i++) printf("0");
        }
        else {
            int l = 1, r = n;
            while (l < r) {
                int mid = l + (r - l) / 2;
                for (int i = 1; i <= m; i++) {
                    int x = q[i].a;
                    int y = q[i].b;
                    int va = x < 0? -x > mid : q[x].w;
                    int vb = y < 0? -y > mid : q[y].w;
                    q[i].w =!(va && vb);
                }
                int temp = q[m].w;
                if (temp == vx) r = mid;
                else l = mid + 1;
            }
            int x = l;
            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;
}

由于本人未绑定 UVA 账号，代码仅供参考。