Reverse Engineering (USACO Bronze 2022 December)

这个题整体是一个贪心的思路。有一定思维难度，要在逻辑运算中找到规律，但仔细找就可以找到，不要放弃。

假设有一系列连续if b[0] == 0/1 return 0/1 else if b[1] == 0/1 ...的表达式，给定一系列b[i]的输入（ $0..N-1$ , $N \lt 100$ ），和最后的布尔输出，问是否能构造出一个这样的if..else序列，能的话输出YES，不可能的话则输出LIE。

我们称每一行输入为一个“表达式”。首先可以看到，if..else这个结构，对数据有一个要求，就是每次可以找到一个输入位（就是第一个if对应的b），它是0或者1时（两者取一个即可），所有对应表达式行的输出结果是一样的。

有了这个判断条件之后，我们就可以根据这个来依次构造出一个if..else的序列出来。办法就是找到这样一位，然后删除所有对应的输出一样的表达式，再重复这个过程。整体是一个贪心的做法。复杂度是 $\mathcal{O}(NM)$ 。

如果要证明这个贪心的正确性，可以这么想：如果一开始就找不到这样的一位，那么肯定是个LIE。如果只有一个位满足这个条件，那也只有这样一条路可走。所以剩下的问题是要考虑有多个位都满足的情况，是否随意贪心选择一个位能保证正确性？这里可以看，如果有多个位满足，假设a和b，那么去掉a之后，剩下的表达式中，b的输出依然也是一致的，所以还是可以删除b，因为先后顺序是不重要的，贪心算法是正确的。

#include <cstdio>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstring>
using namespace std;
 
int T, n, m;
 
struct E {
    int in[105];
    int out;
};
 
vector<E> en;
vector<E> en2;
 
void del(int i, int v) {
    en2.clear();
    for (E e: en) {
        if (e.in[i] != v)
            en2.push_back(e);
    }
    swap(en, en2);
}
 
int main() {
    scanf("%d", &T);
    for (int t = 0; t < T; t++) {
        scanf("%d %d", &n, &m);
        en.clear();
        for (int i = 0; i < m; i++) {
            E e;
            char s[105];
            scanf("%s %d", s, &e.out);
            for (int j = 0; j < n; j++)
                e.in[j] = s[j]-'0';
            en.push_back(e);
        }
 
        bool found = false;
        while (true) {
            found = false;
            for (int i = 0; i < n; i++) {
                // look at b[.][i]
                int cnt[2] = {0};
                int total[2] = {0};
                for (int j = 0; j < en.size(); j++) {
                    cnt[en[j].in[i]] += en[j].out;
                    total[en[j].in[i]]++;
                }
                if (total[0] > 0 && (cnt[0] == 0 || cnt[0] == total[0])) {
                    del(i, 0);
                    found = true;
                    break;
                }
                if (total[1] > 0 && (cnt[1] == 0 || cnt[1] == total[1])) {
                    del(i, 1);
                    found = true;
                    break;
                }
            }
            if (!found || en.empty()) break;
        }
 
        if (found) printf("OK\n"); else printf("LIE\n");
    }
 
    return 0;
}