原题目资料连接：Link。
首先合并肯定是越合越大的，又我们在两头加数，所以一个可行的队列总是单峰的。
形式话的说：
$a_1 < a_2 < \dots < a_K$
$a_K > a_{K-1} > \dots > a_n$
那么我们考虑如何表示它。
对于序列的左边，注意到它是递增的，再根据相同项合并的规则，以及 $a_i = 2^p$，我们会发现它是序列总和的二进制拆分。
更具体的，其类似于 2 8 16 32 的形式。
对于序列的右边也是这样的。
而总和是我们知道的，所以我们只需要左边序列的和即可表示这样一个单峰的合法序列。
故可以动态规划，设 $f(i,s)$ 表示考虑到第 $i$ 位，左侧序列为 $s$ 是否可以被操作构造出来。
那么我们每次加入一个数 $a_i$，其能加入左侧序列 $s$ 当且仅当满足下列两个条件之一（$\operatorname{lowbit}$ 表示二进制最低位）：
- $s = 0$
- $a_i \leq \operatorname{lowbit}(s)$
对于右侧序列 $(\sum_{j=1}^i a_i) - s$ 同理。
通过上述方式转移完之后，我们还需要判断一些情况。
首先对于“峰”即上文所说 $a_K$ 其可以属于左或右两边，需要处理。
同时两边序列的最高点有可能相同，我们需要判断然后合并。
答案 $f(n,\sum a)$。
对于”峰“，实现中我们可以预处理一个数的二进制最高位来解决。
同时还需要记录转移点和插入在左还是右两个信息，方便最后用递归找答案。
记得判断 $\sum a_i$ 是否是 $2$ 的幂。
时间复杂度 $O(n \sum a_i)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
| #include<bits/stdc++.h>
using namespace std;
const int maxn=1e3;
const int maxs=1<<13;
int n;
int a[maxn+5],sum;
bool f[maxn+5][maxs+5];
char g[maxn+5][maxs+5];
int to[maxn+5][maxs+5];
int h[maxs+5];
char str[maxn+5];
inline int Lowbit(int x){return x&(-x);}
inline bool Check(int x,int s){
return (s==0)||(x<=Lowbit(s));
}
void Print(int i,int s){
if(i){
if(g[i][s]) str[i]=g[i][s],Print(i-1,to[i][s]);
else str[i]=g[i][s],Print(i-1,to[i][s]);
}
}
inline void Solve(){
scanf("%d",&n);
sum=0;
f[0][0]=1;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
sum+=a[i];
for(int s=0;s<=sum;s++) f[i][s]=0;
}
sum=0;
for(int i=1;i<=n;i++){
for(int s=0;s<=sum;s++){
if(!f[i-1][s]) continue;
if(Check(a[i],s)){
f[i][s+a[i]]=1;
g[i][s+a[i]]='l';
to[i][s+a[i]]=s;
}
if(Check(a[i],sum-s)){
f[i][s]=1;
g[i][s]='r';
to[i][s]=s;
}
}
sum+=a[i];
for(int s=0;s<=sum;s++){
if(!f[i][s]) continue;
if(h[s]<h[sum-s]){
f[i][s+h[sum-s]]=1;
g[i][s+h[sum-s]]=g[i][s];
to[i][s+h[sum-s]]=to[i][s];
}
if(h[s]>h[sum-s]){
f[i][s-h[s]]=1;
g[i][s-h[s]]=g[i][s];
to[i][s-h[s]]=to[i][s];
}
if(h[s]==h[sum-s]){
f[i][s]=0;
f[i][s+h[s]]=1;
f[i][s-h[s]]=1;
g[i][s+h[s]]=g[i][s];
g[i][s-h[s]]=g[i][s];
to[i][s+h[s]]=to[i][s];
to[i][s-h[s]]=to[i][s];
}
}
}
int tmp;for(tmp=sum;!(tmp&1);tmp>>=1);
if(tmp==1&&f[n][sum]){
Print(n,sum);
for(int i=1;i<=n;i++) putchar(str[i]);
putchar('\n');
}
else puts("no");
}
inline void Init(){
for(int s=0;s<=maxs;s++){
if(Lowbit(s)==s) h[s]=s;
else h[s]=h[s>>1]<<1;
}
}
signed main(){
Init();
int T;scanf("%d",&T);
while(T--) Solve();
return 0;
}
|