UVA1607-Gates（思维+二分）

Problem UVA1607-Gates

Accept: 111  Submit: 767
Time Limit: 3000 mSec

Problem Description

Input

The first line of the input contains exactly one positive integer d equal to the number of data sets, 1 ≤ d ≤ 20. The data sets follow. Each data set consists of two consecutive lines. The first of those lines contains exactly two positive integers n and m separated by single space, 1 ≤ n ≤ 100000, 1 ≤ m ≤ 200000. Integer n is the number of the net inputs and integer m is the number of the gates in the net. The second of those lines contains exactly 2m nonzero integers, separated by single spaces. The numbers on positions 2j −1 and 2j describe the signal sources for the inputs to gate j. The positive number s means the output of gate s. The negative number s means the (−s)-th input to the net. The gates and the net inputs are numbered starting from one. The input of each gate is connected to an input of the net or to an output of a gate whose description occurred earlier in the sequence. Each net input is connected to at least one gate input. Each gate output is connected to at least one gate input except the output of the last gate that is connected to the output of the net.

 Output

The output should consist of exactly d lines, one line for each data set. The line number i should contain the answer to the i-th data set. The answer to one data set should consist of a sequence of exactly k characters terminated by the end of line (with no spaces in between). Each of those characters should be ‘0’ (the digit ‘zero’) or ‘1’ (the digit ‘one’) or ‘x’ (lower-case letter ‘x’). The i-th symbol of the sequence denotes the assignment to the i-th input of the net. If there are more than one optimal assignment then your program should output any of them (but only one).

 

 Sample Input

1

3 6

-1 -3 -1 -2 1 2 1 2 4 3 5 5

 

 Sample Output

10x

题解：这个题比较难理解的地方我觉得在二分的正确性（orz），前面的推理还是比较好理解的，如果当x为0、1时输出相同那么输出就是常数，随意输出一个01串即可，如果不同，那么输出就是x或!x，，也就是说00……0和11……1输出不同，那么从10……0、110……0一直到11……1中间必有一个状态使得11……100……0的输出和11……1相同，从第一个数开始尝试将其变为1，那么试到的第一个输出和11……1相同的状态就可以构造出一个满足条件的解，把该状态新加的1设置为x即可，然而每次输出的时间复杂度时O(m)，尝试的时间复杂度时O(n)，肯定会超时，这个时候据lrj的分析，可以二分1的个数来找到这个位置，这样就变成O(mlogn)（感觉紫书上写错了），这样就不会超时了。

二分正确性的简单证明：首先要明白一个问题，这个题完全有可能有多解，但是二分不是只能卡出来一个解吗，解不是应该唯一吗，这个想法时错误的，错误的原因可以通过我下面的描述看出。如果现在二分到有mid个1（也就是从左往右显是mid个1，然后全是0）如果这个解不是可行解，也就是说这个状态的输出还是和00……0相同，那么我们就可以忽略前面mid个1，后面一定还有一个状态使得输出改变，所以把解的范围缩小到mid到R是可以找到解的（即便1到L有解），如果这个解是可行解，也就是说这个状态的输出和11……1相同那么我们可以忽略从mid到R的数，从L到mid这个区间里肯定是有解的（不然怎么会输出改变），这就证明了二分的合理性。这个二分难理解就在于虽然是在二分卡一个答案，但是答案完全有可能并不唯一，被你舍弃的搜索范围并不是没有解只是你选择继续搜索的区间里一定有解。

#include <bits/stdc++.h>

using namespace std;

const int maxm = 200000 + 100;

struct Nand {
    int a, b, o;
}nand[maxm];

int n, m;

int output(int k) {
    for (int i = 1; i <= m; i++) {
        int x = nand[i].a, y = nand[i].b;
        int va = x < 0 ? -x > k : nand[x].o;
        int vb = y < 0 ? -y > k : nand[y].o;
        nand[i].o = !(va && vb);
    }
    return nand[m].o;
}

int solve(int vn) {
    int l = 1, r = n;
    int ans;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (output(mid) == vn) {
            ans = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    return ans;
}

int main()
{
    //freopen("input.txt", "r", stdin);
    int iCase;
    scanf("%d", &iCase);
    while (iCase--) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= m; i++) {
            scanf("%d%d", &nand[i].a, &nand[i].b);
        }
        int vn = output(n), v0 = output(0);
        if (vn == v0) {
            for (int i = 1; i <= n; i++) {
                printf("0");
            }
            printf("
");
        }
        else {
            int pos = solve(vn);
            for (int i = 1; i < pos; i++) printf("0");
            printf("x");
            for (int i = pos + 1; i <= n; i++) printf("1");
            printf("
");
        }
    }
    return 0;
}