UVALive 6931 Can't stop playing (Regionals 2014 >> Europe

题目

一开始有一个双头队列，每次添加一个数（这是数是二的幂，所有数的和不大于(2^13)），由你来决定添加到队头还是队尾。如果队列里面相邻的两个数相同，设它们都是(x)，那么这两个数会合并为(2x)。问所有数添加完后队列里能否只剩下一个数。

算法

搜索题，但是需要巧妙地记录状态！这种题不可多。

一个显然的是，队列里不会存在相邻的三个数(a,b,c)，满足(a>b,c>b)。这样的话，队列肯定是一个倒V字。

记状态((i,j))为添加完前(i)个数，(j)是倒V左半边的上升序列状态，(j)最大是(2^{13})。通过这两个，我们可以算出倒V右半边的序列状态！

这样的话，时间复杂度就是(O(n 2^{13}))。

代码

官方的标程有点点小错误。UVALive上的数据也错了。但当时比赛的数据是正确的！

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#include <assert.h>
using namespace std;

template <class T>
void tension(T &a, const T &b) {
	if (b < a) a = b;
}

template <class T>
void relax(T &a, const T &b) {
	if (b > a) a = b;
}

typedef long long i64;

#ifndef ONLINE_JUDGE
#define ep(...) fprintf(stderr, __VA_ARGS__)
#else
#define ep(...) assert(true)
#endif

int n;
int sum[1003], A[1003];
bool vis[1003][(1 << 13) + 1];
char ans[1003];
int highBit[1 << 14];

int place(int a, int b, int x) {
	if (highBit[a] > highBit[b]) {
		int tmp = highBit[a];
		a -= tmp;
		b += tmp;
	}
	if (a && (a & -a) < x) return -1;
	a += x;
	while (highBit[a] == highBit[b]) {
		int tmp = highBit[a];
		a += tmp;
		b -= tmp;
	}
	return a;
}

bool dfs(int k, int s1) {
	int s2 = (k ? sum[k - 1] : 0) - s1;
	
	if (k == n) {
		if (highBit[s1] > highBit[s2]) {
			int tmp = highBit[s1];
			s1 -= tmp;
			s2 += tmp;
		}
		if (highBit[s2] > highBit[s1]) {
			int tmp = highBit[s2];
			s2 -= tmp;
			s1 += tmp;
		}
		if (s1 == (s1 & -s1) && s2 == 0) return true;
		if (s2 == (s2 & -s2) && s1 == 0) return true;
		return false;
	}
	
	if (vis[k][s1]) return false;
	vis[k][s1] = true;
	
	int x = A[k];
	int tmp = place(s1, s2, x);
	if (tmp != -1 && dfs(k + 1, tmp)) {
		//ep("l (%d, %d) %d ->
", s1, s2, x);
		ans[k] = 'l';
		return true;
	}
	tmp = place(s2, s1, x);
	if (tmp != -1 && dfs(k + 1, sum[k] - tmp)) {
		//ep("r (%d, %d) %d ->
", s1, s2, x);
		ans[k] = 'r';
		return true;
	}
	return false;
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	//freopen("all.in", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	for (int i = 1; i < 1 << 14; i ++) 
		if ((i & -i) == i) highBit[i] = i;
		else highBit[i] = highBit[i - 1];

	scanf("%*d");
	for (int cases = 1; scanf("%d", &n) == 1; cases ++) {
		//ep("Case %d: ", cases);
		for (int i = 0; i < n; i ++) {
			scanf("%d", A + i);
			sum[i] = A[i];
			if (i) sum[i] += sum[i - 1];
		}
		
		//memset(vis, 0, sizeof vis);
		for (int i = 0; i < n; i ++)
			memset(vis[i], 0, sizeof vis[i]);
		if (dfs(0, 0)) {
			ans[n] = '';
			printf("%s
", ans);
		}
		else printf("no
");
	}

	return 0;
}