[USACO22DEC] Reverse Engineering B：USACO铜组例题讲解——逻辑推理

这一题的逻辑真的是非常神奇，可以列入铜组史上史题前三。

题目太长，这里不放了。

题目链接：

洛谷：P8899 [USACO22DEC] Reverse Engineering B - 洛谷 | 计算机科学教育新生态

官网：USACO

说实话，洛谷的题解我是一点也看不懂，大家写的都非常复杂，难以理解。

我们的目的是：用模拟的方法始终找到目前优先级最高的那一组代码，我们同时假设返回值为0和1，分别判断。以下以1为例。
我们按照结果把式子分为两组：结果为1的和结果为0的。
找到的数据不能自相矛盾，也就是这一位可以是1，其他的结果也是1但是与这位不同的，说明其得到这个结果的原因和这里不同，可能是一些优先级比较低的导致结果是1，也有可能根本就是因为0倒推的。
为了不自相矛盾，我们还得确定目前所有可能是这一位导致结果的与0的结果不矛盾，也就是，这一位结果和所有0这一位都不一样！否则就没有办法解释为什么那一位和你一样结果却不一样了。
我们的目的是要找到是哪一位的数据导致返回值为1，以及那一位是1还是0。我们已经所有数据分为两类，
对于返回值为1的，我们找到所有可能的位，哪一位可能是0，哪一位可能是1，我们都列到一个变量里面，我这里的做法是自己实现位运算，
把所有数据取and和or，那么and之后就能知道哪些是0，or之后就能知道哪一位是1。
这些位的数据得到了之后，我们把其分别和0的每一位求异或，然后再求and，这样就能确定哪一位或哪几位符合这个条件
如果一位都没有，就说明撒谎了，构建不出if条件。输出“LIE”，直接goto到结尾，进行下一轮循环。
排掉之后的哪一个条件用vis标记，剩下的结果是由优先级较低的if体现的，在第一轮里面体现不出来。
当所有都给排掉之后，剩下的语句用else一波带走。输出“OK”，程序结束。

这题需要把逻辑捋清楚，思维难度不低，代码也很不好写。

我本来打算用位运算做，但是因为M的大小超过了100，只能自己实现位运算，如果使用long long（c++）/long（java），只能存储64位数，达不到题目要求。

以下是AC代码：

#include<bits/stdc++.h>
using namespace std;

class bitcollection {
private:
	vector<bool> bits;
public:
	bitcollection(){}
	bitcollection(int length, int defaultNum = 0) {
		bits = vector<bool>(length);
		for (int i = 0; i < bits.size(); i++)
			bits[i] = defaultNum;
	}
	bitcollection(string s) {
		for (int i = 0; i < s.size(); i++)
			bits.push_back(s[i] - '0');
	}

	~bitcollection() {
		vector<bool>().swap(bits);
	}

	const int sum() const{
		int num = 0;
		for (int j = 0; j < bits.size(); j++)
			num += bits[j] * pow(2, bits.size() - j - 1);
		return num;
	}

	const bool& operator[](int i) const {
		return bits[i];
	}

	const bitcollection operator&(const bitcollection& number) {
		bitcollection newNum(number.size());
		for (int i = 0; i < number.size(); i++)
			newNum.bits[i] = bits[i] && number.bits[i];
		return newNum;
	}

	void operator&=(const bitcollection& number) {
		for (int i = 0; i < number.size(); i++)
			bits[i] = bits[i] && number.bits[i];
	}

	void operator|=(const bitcollection& number) {
		for (int i = 0; i < number.size(); i++)
			bits[i] = bits[i] || number.bits[i];
	}

	const bitcollection operator|(const bitcollection& number) {
		bitcollection newNum(number.size());
		for (int i = 0; i < number.size(); i++)
			newNum.bits[i] = bits[i] || number.bits[i];
		return newNum;
	}

	const bitcollection operator^(const bitcollection& number) {
		bitcollection newNum(number.size());
		for (int i = 0; i < number.size(); i++)
			newNum.bits[i] = bits[i] ^ number.bits[i];
		return newNum;
	}

	const bitcollection operator!() const{
		bitcollection newNum(bits.size());
		for (int i = 0; i < bits.size(); i++)
			newNum.bits[i] = !bits[i];
		return newNum;
	}

	void setNumber(int number) {
		do {
			bits.insert(bits.begin(), number % 2);
			number /= 2;
		} while (number);
	}

	const int find(bool bit) const {
		for (int i = 0; i < bits.size(); i++)
			if (bits[i] == bit)
				return i;
		return -1;
	}

	const int size() const{
		return bits.size();
	}

	const string toString() const {
		string s;
		for (int i = 0; i < bits.size(); i++)
			s.push_back(bits[i]+'0');
		return s;
	}
};

vector<bitcollection> nums;
bool* bit = new bool[105]();
bool* vis = new bool[105]();
unique_ptr<bool> rec;
int n, m;
bool canForm(bool b) {
	rec.reset(new bool[m]);
	copy(vis, vis + m, rec.get());
	bitcollection gand(n,1), gor(n,0);
	for (int i = 0; i < m; i++)
		if (bit[i] == b and !vis[i]) {
			gand &= nums[i], gor |= nums[i];
		}
	//cout << gand.toString() << ' ' << gor.toString() << endl;;
	bitcollection xorand(n,1), xoror(n,1);
	for (int i = 0; i < m; i++)
		if (bit[i] == !b and !vis[i])
			xorand &= gand ^ nums[i], xoror &= gor ^ nums[i];

	for (int i = 0; i < m; i++)
		if (bit[i] == b and !vis[i]) {
			auto f = !nums[i];
			if ((f & xorand).find(1)!=-1 or (nums[i]& xoror).find(1)!=-1) {
				vis[i] = true;
			}
		}
	return !equal(vis, vis + m, rec.get());
}
bool check(bool b) {
	for (int i = 0; i < m; i++)
		if (vis[i] != b)
			return false;
	return true;
}
int main() {
	int T;
	cin >> T;
	while (T--) {
		memset(vis, 0, 100);
		cin >> n >> m;
		nums = vector<bitcollection>();
		for (int i = 0; i < m; i++)
		{
			string s;
			cin >> s >> bit[i];
			nums.push_back(bitcollection(s));
		}
		while (!check(1)) {
			if (!canForm(1) and !canForm(0)) {
				cout << "LIE\n";
				goto end;
			}
		}
		cout << "OK" << endl;
	end:;
	}
}