自动搬运

查看原文

来自洛谷，原作者为

	Nights_watcher 转阴阳，定乾坤，镇天地

搬运于2025-08-24 22:32:34，当前版本为作者最后更新于2025-04-05 08:51:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一眼看到 $n\le20$，便可以想到状压 DP。

很显然，$dp_{i,j}$ 表示第 $i$ 秒，状态是否可以为 $j$。但是如果按照常规方法转移，时间复杂度为 $O(Qn^32^n)$，直接爆炸。

于是我们想一下优化。我们可以将现有的所有操作都延迟一秒去做，这样它们影响的总时间不变，这时再在第一秒插入一个新的操作，这样影响的时间就为现在枚举到的时间。

我们可以预处理出一个数组表示在每个点使用魔法后每秒影响到的状态。转移时异或即可。

代码如下

#include <bits/stdc++.h>
using namespace std;
int q , n , fa[21] , s[21][21];
bool dp[21][1 << 20];
string S;
vector <int> ve[21];
void dfs (int u , int f)
{
	fa[u] = f;
	for (int v : ve[u])
		if (v != f) dfs (v , u);
}
int main ()
{
	ios :: sync_with_stdio (false);
	cin.tie (0);
	cout.tie (0);
	cin >> q;
	while (q --)
	{
		cin >> n >> S;
		for (int i = 1;i <= n;i ++) ve[i].clear ();
		for (int i = 1;i < n;i ++)
		{
			int u , v;
			cin >> u >> v;
			ve[u].push_back (v);
			ve[v].push_back (u);
		}
		dfs (1 , 0);
		for (int i = 1;i <= n;i ++)
			for (int j = 1 , k = i;j <= n;j ++ , k = fa[k])
				if (k) s[i][j] = s[i][j - 1] ^ (1 << k - 1);
				else s[i][j] = s[i][j - 1];
		int ed = 0;
		for (int i = 1;i <= n;i ++)
		{
			char c;
			cin >> c;
			if (c != S[i - 1]) ed ^= (1 << (i - 1));
		}
		dp[0][0] = 1;
		for (int i = 0;i <= n;i ++)
		{
			if (dp[i][ed])
			{
				cout << i << "\n";
				memset (dp[i] , 0 , sizeof (dp[i]));
				break;
			}
			for (int j = 0;j < (1 << n);j ++)
				if (dp[i][j])
				{
					dp[i][j] = 0;
					dp[i + 1][j] = 1;
					for (int k = 1;k <= n;k ++) dp[i + 1][j ^ s[k][i + 1]] = 1;
				}
		}
	}
	return 0;
}