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

· · 题解

原题目资料连接：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} 表示二进制最低位）：

对于右侧序列 (\sum_{j=1}^i a_i) - s 同理。

通过上述方式转移完之后，我们还需要判断一些情况。

首先对于“峰”即上文所说 a_K 其可以属于左或右两边，需要处理。

同时两边序列的最高点有可能相同，我们需要判断然后合并。

答案 f(n,\sum a)。

对于”峰“，实现中我们可以预处理一个数的二进制最高位来解决。

同时还需要记录转移点和插入在左还是右两个信息，方便最后用递归找答案。

记得判断 \sum a_i 是否是 2 的幂。

时间复杂度 O(n \sum a_i)。

#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;
}