Solution

1 思路

树形 DP。

定义 $dp_{i,0/1}$ 表示在以 $i$ 为根的子树中，$i$ 的值为 $0/1$ 的最小更改数。

可以发现分为以下情况：

• $i$ 是“AND”门，且不能修改：若要求 $0$，则左子节点取 $0$ 时右子节点取 $0/1$，左子节点取 $1$ 时右子节点取 $0$；若要求 $1$，则左子节点取 $1$ 时右子节点取 $1$；
• $i$ 是“OR”门，且不能修改：若要求 $0$，则左子节点取 $0$ 时右子节点取 $0$；若要求 $1$，则左子节点取 $1$ 时右子节点取 $0/1$，左子节点取 $0$ 时右子节点取 $1$；
• $i$ 是“AND”门，且可以修改：在“$i$ 是“OR”门，且不能修改”的情况上加 $1$；
• $i$ 是“OR”门，且可以修改：在“$i$ 是“AND”门，且不能修改”的情况上加 $1$。

特别地，若 $i$ 为叶子节点，则 $dp_{i,val_i} \leftarrow 0,dp_{i,1-val_i} \leftarrow +\infty$。

答案为 $dp_{1,V}$，若该值为 $+ \infty$，则判定无解。

2 实现

梳理了以上的思路，我们就可以愉快地写代码了：

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define pb push_back
#define rep(a, b, c, d) for(int a=b; a<=c; a+=d)
#define inf (INT_MAX >> 1)
const int N = 1e4 + 5;
int ls(int n) {return n << 1;}
int rs(int n) {return (n << 1) + 1;}
struct node {
	bool is_and, changeable, is_leaf, val;
};
bool Min(int &a, int b) {
	return (b < a ? a = b, 0 : 1);
}
void solve(int casenum) {
	int m, v;
	cin >> m >> v;
	vector<node> arr(m + 1);
	rep(i, 1, (m - 1) / 2, 1) {
		bool g, c;
		cin >> g >> c;
		arr[i].is_and = g;
		arr[i].changeable = c;
		arr[i].is_leaf = 0;
	}
	rep(i, (m - 1) / 2 + 1, m, 1) {
		bool n;
		cin >> n;
		arr[i].val = n;
		arr[i].is_leaf = 1;
	}
	vector<vector<int> > dp(m + 1, vector<int>(2, inf));
	for(int i = m; i >= 1; -- i) {
		if(arr[i].is_leaf) {
			dp[i][arr[i].val] = 0;
			dp[i][!arr[i].val] = inf;
		}
		else {
			int ls = (i << 1), rs = (i << 1) + 1;
			rep(tar, 0, 1, 1) {
				int res = inf;
				if(arr[i].is_and) {
					if(tar == 1) {
						if(dp[ls][1] != inf && dp[rs][1] != inf)
							Min(res, dp[ls][1] + dp[rs][1]); 
					}
					else {
						int a = inf, b = inf;
						if(dp[ls][0] != inf)
							a = dp[ls][0] + min(dp[rs][0], dp[rs][1]);
						if(dp[ls][1] != inf && dp[rs][0] != inf)
							b = dp[ls][1] + dp[rs][0];
						Min(res, min(a, b));
					}
				}
				else {
					if(tar == 0) {
						if(dp[ls][0] != inf && dp[rs][0] != inf)
							Min(res, dp[ls][0] + dp[rs][0]);
					}
					else {
						int a = inf, b = inf;
						if(dp[ls][1] != inf)
							a = dp[ls][1] + min(dp[rs][0], dp[rs][1]);
						if(dp[ls][0] != inf && dp[rs][1] != inf)
							b = dp[ls][0] + dp[rs][1];
						Min(res, min(a, b));
					}
				}
				if(arr[i].changeable) {
					if(!arr[i].is_and) {
						if(tar == 1) {
							if(dp[ls][1] != inf && dp[rs][1] != inf)
								Min(res, dp[ls][1] + dp[rs][1] + 1); 
						}
						else {
							int a = inf, b = inf;
							if(dp[ls][0] != inf)
								a = dp[ls][0] + min(dp[rs][0], dp[rs][1]) + 1;
							if(dp[ls][1] != inf && dp[rs][0] != inf)
								b = dp[ls][1] + dp[rs][0] + 1;
							Min(res, min(a, b));
						}
					}
					else {
						if(tar == 0) {
							if(dp[ls][0] != inf && dp[rs][0] != inf)
								Min(res, dp[ls][0] + dp[rs][0] + 1);
						}
						else {
							int a = inf, b = inf;
							if(dp[ls][1] != inf)
								a = dp[ls][1] + min(dp[rs][0], dp[rs][1]) + 1;
							if(dp[ls][0] != inf && dp[rs][1] != inf)
								b = dp[ls][0] + dp[rs][1] + 1;
							Min(res, min(a, b));
						}
					}
				}
				dp[i][tar] = res;
			}
		}
	}
	cout << "Case #" << casenum << ": ";
	if(dp[1][v] != inf)
		cout << dp[1][v] << "\n";
	else
		cout << "IMPOSSIBLE\n";
}
signed main () {
	int n;
	cin >> n;
	rep(i, 1, n, 1)
		solve(i);
	return 0;
}

3 小结

本题作为一道 DP 有一定难度，需要具备分类讨论推导的能力。感谢您能看到这里，也欢迎评论区留言讨论。

也以此纪念我写过最长的代码（$2.68\text{KB}$）。

没有求关的题解不是好题解。