CF1286F Harry The Potter


一、题目

点此看题

二、解法

答案上界显然是 \(n\),我们考虑怎么样把答案变小,显然我们要考虑怎么合理利用操作二。

我们用图论模型考虑操作的结构,如果对 \(u,v\) 使用了操作二,那么我们把 \((u,v)\) 连边。不难发现最优解的图一定是操作二的一个森林,因为如果操作二成环那么肯定没有直接使用操作一要好。

那么要求这个森林可以用状压 \(dp\) 的技巧解决,关键问题是如果判断集合 \(s\) 是否能成为一棵树。

这个问题比较复杂,可以考虑枚举法,假设我们已经枚举出了树的结构和每个点的点权:

如果我们不考虑那个 \(+1\),发现每个点的贡献只和其深度有关,那么我们最后列出来的方程就是:奇数位置的点权\(-\)偶数位置的点权\(=0\),把 \(+1\) 考虑进去的话那么每个 \(+1\) 可以任意贡献 \(+1/-1\),所以可以列出方程:

\[|\sum_{i=1}^{sz}(-1)^{dep_i}\cdot v_i|

暴力子集枚举是 \(O(3^n)\),可以考虑折半搜索,也就是把两边的所有情况枚举出来,时间复杂度 \(O(2^{\frac{|S|}{2}})\),然后 \(\tt two-pointers\) 合并即可,总时间复杂度 \(O((1+\sqrt 2)^n)\),证明:

\[\sum_{S\in U}2^{\frac{|S|}{2}}=\sum_{S\in U}\sqrt 2^{|S|}=\sum_{i=0}^n\sqrt 2^i\cdot{n\choose i}=(1+\sqrt 2)^n \]

最后考虑怎么状压 \(dp\),好像还是要用子集枚举啊,但是这道题比较特殊可以加点剪枝,考虑刷表法,如果 \(f[s]\) 已经被组合出来过了就那它就不去更新,也就是我们只拿最基本的单位去更新,时间复杂度 \(O(3^n)\) 还是快啊。

三、总结

本题使用了推结论的两大技巧:一是观察操作结构然后转图论模型;而是枚举法确定状态推出真正有关的量。我觉得枚举法是真的神奇,通过枚举我们可以知道所有信息,然后分析枚举后的状态看什么信息才是真正需要的。

子集枚举的优化技巧也值得借鉴,折半搜索那个复杂度是真的牛逼,还可以考虑有效转移来剪枝。

#include 
#include 
using namespace std;
#define int long long
const int M = 1<<20;
int read()
{
	int x=0,flag=1;char c;
	while((c=getchar())<'0' || c>'9') if(c=='-') flag=-1;
	while(c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return x*flag;
}
int n,m,a[25],b[25],f[M],sl[M],sr[M];
int Abs(int x) {return x>0?x:-x;}
void get(int *s,int &k,int l,int r)
{
	s[0]=0;
	static int ad[M],sb[M];
	for(int i=l;i=0;i--)
	{
		while(j

相关