建议标签：状压 DP、记忆化搜索。
通过机房某几位大佬了解了这题，在一节英语课内想到正解但是不影响我被卡一个晚上（虚
~~所以应该算是水紫吧？应该算吧？~~

分析：

我们尝试从无解条件入手。
显然地，当这些数和不为

2

的整数次幂时肯定无解。
同时，我们容易注意到一件事情：一个数经历合并后只会越来越大。
这条显然的性质有什么用呢？
放到具体情境中，如果一个数两边的数都比他大，那么再怎么消，两边的数都只可能更大，又不会消失，导致中间的数永远无法合并，即该情况无解。
又考虑到相同的数相邻会合并，这意味着，序列的实时状态是单峰的，前半严格递增，后半严格递减。
因为题目保证总和不超过

2^{13}

，我们很容易联想到将序列的状态拆成左右两半，状态压缩为二进制数。
那么，如果我们要从一端插入一个数

a_i

，为避免状态无解，设这一半状态压缩为

x

，则需要满足

a_i\le lowbit(x)

。
手玩一下发现，不考虑两半的最大数合并，我们从一端插入一个数对状态的影响正好满足二进制加法！
那么，如果考虑两半最大数的合并呢？
我们牺牲空间，钦定左半边状态最高位保持更大（右半边也行，事实上由于总能找到左右相反的方案，左与右没有影响），对值域内的所有数预处理下二进制最高位。每次转移状态后，比较两边最高位，如果右边最高位大于等于左边最高位，就把右边的最高位挪到左边去。
因此，我们考虑记忆化搜索实现状压 DP，搜索当前编号

i

和左状态

lft

，因为到第 $i$ 位两半状态总和总是等于第 $i$ 位的前缀和，我们利用前缀和求出右状态

rit

，按照合并规则进行状态转移即可。

实现细节：

$0$ 没有最高位，将其最高位数组值设成 $-1$ 。
$dp$ 初值设为 $-1$ ，可达没搜到解为 $0$ ，可达搜到解为 $1$ 。搜索时更新 $nxt$ 数组储存选择方向，最后搜索打印方案。
如果同时枚举左右状态， $O(2^{26})$ 容易引起常数爆炸。考虑储存前缀和，枚举左状态，前缀和减去左状态得到右状态。两半最高位合并后显然需要更新右状态的值。这样的作法大概 $O(2^{13}n)$ 。

代码：

CPP

#include <bits/stdc++.h>
using namespace std;
int t,n,a[1145],sum[1145],high[(1<<13)+10],dp[1145][(1<<13)+10],nxt[1145][(1<<13)+10];
inline int lowbit(int x){
	return x&(-x);
}
inline bool dfs(int now,int lft){
	int rit=sum[now-1]-lft,h1=-1,h2=-1;
	h1=high[lft];
	h2=high[rit];
	if(h1==h2&&h1>=0) lft+=(1<<h1);
	if(h1<h2) lft+=(1<<h2);
	rit=sum[now-1]-lft;//最高位合并，更新rit 
	if(now==n+1){
		if(!lft||lft==sum[n]||lft==sum[n]>>1) return 1;//3种成功情况
		else return 0;
	}
	if(dp[now][lft]!=-1) return dp[now][lft];//返回已记忆结果 
	int res=0;
	dp[now][lft]=0;
	if(!lft||a[now]<=lowbit(lft)){
		res=dfs(now+1,lft+a[now]);
		if(res){
			dp[now][lft]=1;
			nxt[now][lft]=0;
		}//记录方向 
	}//左侧可插入 
	if(!rit||a[now]<=lowbit(rit)){
		res=dfs(now+1,lft);
		if(res&&!dp[now][lft]){
			dp[now][lft]=1;
			nxt[now][lft]=1;
		}//记录方向，向左能成功就可以不动 
	}//右侧可插入 
	return dp[now][lft];
}
inline void print(int now,int lft){
	int rit=sum[now-1]-lft,h1=-1,h2=-1;
	h1=high[lft];
	h2=high[rit];
	if(h1==h2&&h1>=0) lft+=(1<<h1);
	if(h1<h2) lft+=(1<<h2);//最高位合并，但这里不需要更新rit 
	if(now==n+1) return;
	if(nxt[now][lft]) cout<<'r';
	else cout<<'l';//根据方向打印 
	print(now+1,nxt[now][lft]?lft:lft+a[now]);//沿着记录方向搜索打印 
}
inline void solve(){
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];//前缀和 
	}
	if(sum[n]!=lowbit(sum[n])){
		puts("no");
		return;
	}//无解情况：和不为2的整数幂 
	for(int i=0;i<=n;++i){
		for(int j=0;j<=sum[n];++j) dp[i][j]=-1;
	}//dp置初值 
	if(dfs(1,0)){
		print(1,0);
		puts("");
	} 
	else puts("no");
}
int main(){
	high[0]=-1;//不要漏！！！ 
	for(int i=1;i<=(1<<13);++i){
		for(int j=0;j<=13;++j) high[i]=max(high[i],((i>>j)&1)*j);
	}//预处理最高位 
	cin>>t;
	while(t--) solve();
	return 0;
}

题解：P7093 [CERC2014] Can't stop playing

文章操作

分析：

实现细节：

代码：

相关推荐

评论

题解：P7093 [CERC2014] Can't stop playing