2048
Special Judge
Time Limit: 1000 ms Memory Limit: 256 MB
Description
2048曾经是一款风靡全球的小游戏。
今天，我们换一种方式来玩这个小游戏。
现在，你有一个双端队列，你只能把元素从左端或从右端放入双端队列中。一旦放入就不得取出。放入后，若队列中有连续两个相同的元素，它们将自动合并变成一个新的元素——原来那两个元素的和。若新的元素与它相邻的元素相同，则继续合并……
如：双端队列中有2, 4, 16三个元素。若将2从左端插入双端队列中，该队列将变成8, 16。若将2从右端插入双端队列中，该队列将变成2, 4, 16, 2。
一开始，双端队列为空。我们将给你一些数，你需要依次插入到双端队列中。问是否存在一种操作方案，使得双端队列最后只剩下一个数。
Input
第一行为一个整数 T，表示数据组数。
对于每组测试数据：
第一行一个整数 n，表示我们给你的数的个数。
接下来一行 n个数，表示我们给你的数 ai 。这些数都是2的非负整数次方，即对于每个 i 都存在一个整数 k 满足 k≥0 且 ai=2^k 。
Output
对于每组数据，若不存在一种操作方案使得双端队列最后只剩一个数，则输出no。否则，输出一个长度为n的字符串，其中若第i个数从左边插入到双端队列，则第i个字符为 l ；若第i个数从右边插入到双端队列，则第i个字符为 r 。
Sample Input
3
9
2 8 4 1 1 4 4 4 4
5
2 16 4 8 2
3
2 2 2
Sample Output
rrrlllrrr
no
noHINT
样例1解释
1、从右边插入2，双端队列变为2
2、从右边插入8，双端队列变为2 8
3、从右边插入4，双端队列变为2 8 4
4、从左边插入1，双端队列变为1 2 8 4
5、从左边插入1，双端队列变为4 8 4
6、从左边插入4，双端队列变为16 4
7、从右边插入4，双端队列变为16 8
8、从右边插入4，双端队列变为16 8 4
9、从右边插入4，双端队列变为32
数据范围与约定
对于20%的数据， n≤19,T≤100
对于所有数据， 1≤n≤1000,a1~an的和不超过2^13,T≤10000，其中 n>20 的数据不超过150组。
Solution
考虑状压+搜索
用一个L表示一下当前状态的左半部分，那么右半部分可以用预处理的前缀和减去L表示出来
如果当前要加入的数比L的lowbit还要小，那么就加入左边
右边部分同理
然后用一个vis表示一下当前状态有没有被搜索过。由于最大只有8192，所以数组是开得下的。
对于某状态的L和R，如果highbit(L)<=highbit(R),那么就把highbit(R)合并到左边，这样左右的合并就完成了
蛮好理解的（虽然我讲得不清不楚）
#include<bits/stdc++.h>
using namespace std;
#define R (sum[x]-L)
#define lowbit(x) x&-x
int n;
int a[10001];
bool flag;
int vis[1010][8195];
bool ans[10001];
int sum[10001];
int highbit[10001];
int sb;
void solve(int x,int L){
//cout<<x<<" "<<L<<endl;
if(highbit[L]<=highbit[R])L+=highbit[R];
if(vis[x][L]==sb)return;
vis[x][L]=sb;
if(x==n){
//cout<<L<<" "<<(lowbit(L))<<endl;
if(L==(lowbit(L)))flag=true;
return;
}
int xx=x+1;
int l=(lowbit(L)),r=(lowbit(R));
if(a[xx]<=l)ans[xx]=0,solve(xx,L+a[xx]);
if(flag)return;
if(!r||a[xx]<=r)ans[xx]=1,solve(xx,L);
}
void init(){
for(int i=2;i<=8192;++i)highbit[i]=highbit[i>>1]+1;
for(int i=1;i<=8192;++i)highbit[i]=1<<highbit[i];
}
void print(){
for(int i=1;i<=n;++i){
putchar((ans[i]?'r':'l'));
}
putchar('\n');
}
int main(){
int T;
scanf("%d",&T);
//T=1;
init();
while(T--){
memset(sum,0,sizeof(sum));
memset(ans,0,sizeof(ans));
flag=false;
sb++;
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
sum[i]=sum[i-1]+a[i];
}
//cout<<sum[n]<<endl;
if(sum[n]!=(lowbit(sum[n]))){
puts("no");
continue;
}
solve(1,a[1]);
if(flag){
print();
}
else puts("no");
}
}