记录编号	37065	评测结果	AAAAAAAA
题目名称	分球	最终得分	100
用户昵称	Czb。	是否通过	通过
代码语言	C++	运行时间	0.550 s
提交时间	2012-03-23 11:47:30	内存使用	41.26 MiB

#include<stdio.h>
#include<string.h>

struct orz
{
	int k,s,x,y;
	char c[15];
	orz()
	{
		k=s=x=y=0;
		memset(c,0,sizeof(c));
	}
}qu[500001];

int q,n,l,t,ans,aa[500001],last[5000001];

char *c;

bool flag[5000001];

int val(orz a)
{
	int k=1,s=0;
	for(int i=n-1;i>0;i--)
	{
		if(a.c[i]=='a')
		{
			s+=k;
		}
		else if(a.c[i]=='b')
		{
			s+=k*2;
		}
		k*=3;
	}
	return s;
}

bool solve(orz a)
{
	int i,x,y;
	x=0;
	y=n>>1;
	y--;
	for(i=0;i<n;i++)
	{
		if(a.c[i]=='a')
			x++;
		else if(a.c[i]=='b'&&x<y)
			return false;
	}
	return true;
}

int main(int argc,char *argv[])
{
	freopen("balls.in","r",stdin);
	freopen("balls.out","w",stdout);
	int i,l,r;
	orz tmp;
	c=new char[15];
	scanf("%d",&q);
	while(q--)
	{
		memset(flag,1,sizeof(flag));
		memset(last,0,sizeof(last));
		scanf("%d\n",&n);
		n<<=1;
		scanf("%[ ab]",c);
		l=strlen(c);
		if(l<n)
		{
			c[-1]=c[-2]=' ';
			c=c-2;
		}
		strcpy(tmp.c,c);
		for(i=0;i<n;i++)
		{
			if(c[i]==' ')
			{
				tmp.x=i;
				tmp.y=++i;
			}
		}
		tmp.k=val(tmp);
		flag[tmp.k]=false;
		l=r=1;
		qu[1]=tmp;
		while(l<=r)
		{
			tmp=qu[l];
			if(solve(tmp))
			{
				ans=l;
				break;
			}
			for(i=0;i<n-1;i++)
			{
				if(tmp.c[i]!=' '&&tmp.c[i+1]!=' ')
				{
					orz temp=tmp;
					temp.c[temp.x]=temp.c[i];
					temp.c[temp.y]=temp.c[i+1];
					temp.c[i]=' ';
					temp.c[i+1]=' ';
					temp.x=i;
					temp.y=i+1;
					temp.k=val(temp);
					temp.s=tmp.s+1;
					if(flag[temp.k])
					{
						flag[temp.k]=false;
						qu[++r]=temp;
						last[r]=l;
					}
				}
			}
			l++;
		}
		if(ans)
		{
			t=0;
			while(ans)
			{
				t++;
				aa[t]=ans;
				ans=last[ans];
			}
			for(i=t;i>0;i--)
			{
				printf("%d %s\n",t-i,qu[aa[i]].c);
			}
		}
		else
			printf("NO SOLUTION\n");
		printf("\n");
	}
	return 0;
}