题目链接：

题目类型：贪心

第一次bzoj上的暂时的rank1好高兴

题意：

给出n个字符串和一个基础字符串，要求将n个字符串分成两个序列，使得每个序列中前一个字符串是后一个字符串的子序列，同时使得每个序列的最后一个字符串是基础字符串的子序列。

题解：http://www.csc.kth.se/~austrin/icpc/finals2015solutions.pdf

先附上petr的题解

因为一定是长度较短的字符串是长度较长的字符串的子序列，所以考虑将字符串按照长度从大到小排序。

考虑从前往后添加字符串。

可以发现如果已经拥有了最优序列，对后面答案造成影响的只是当前最优的两个序列的各自的最后一个字符串，所以可以用二元组(x,y)表示一个阶段的最优解（之一）。

然后可以知道整个处理的过程中的任何一个时刻至多只有两个不同的最优解。

这个结论可以通过归纳法证明。

然后按照证明过程中的过程直接推就可以了。

需要注意的是记录答案的过程应当是不仅要记录该状态来自于哪一个状态，还要记录相对于全局来说是否翻转过。

程序：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node
{
	char s[4200];
	int le;
}str[4200];
int n,a[4200],hale[4200],path[4220][4220];
bool change[4220][4220];
int cnt1,cnt2,ans1[4200],ans2[4200];
inline bool cmp(int x,int y)
{
	return str[x].le>str[y].le;
}
inline bool judge(int x,int y)
{
	int xp=x;
	int yp=y;
	x=a[x];
	y=a[y];
	int tp=-1;
	for (int i=0;i<str[x].le;i++)
	{
		while (str[y].s[tp+1]!=str[x].s[i]&&tp<str[y].le)tp++;
	//	printf("check:%d %d %d %d\n",xp,yp,i,tp);
		if(tp==str[y].le)return false;
		tp++;
	}
	return true;
}
inline void getans(int x,int y)
{//printf("%d %d %d %d\n",x,y,path[x][y],change[x][y]);
	if(x==0&&y==0)return;
	int x1=path[x][y]/10000;
	int x2=path[x][y]-x1*10000;
	getans(x1,x2);
	if(change[x1][x2]==1)swap(x1,x2);
	if(change[x][y]==1)swap(x,y);
	if(x1!=x)
	{
		cnt1++;
		ans1[cnt1]=x;
	}
	if(x2!=y)
	{
		cnt2++;
		ans2[cnt2]=y;
	}
}
inline void printans()
{
	printf("%d %d\n",cnt1,cnt2);
	for (int i=cnt1;i>=1;i--)
	{
		printf("%s\n",str[a[ans1[i]]].s);
	}
	for (int i=cnt2;i>=1;i--)
	{
		printf("%s\n",str[a[ans2[i]]].s);
	}
}
int p11,p12,p21,p22,num;
int main()
{
	scanf("%d",&n);
	scanf("%s",str[0].s);
	str[0].le=strlen(str[0].s);
	for (int i=1;i<=n;i++)
	{
		scanf("%s",str[i].s);
		str[i].le=strlen(str[i].s);
		hale[str[i].le]++;
		if(hale[str[i].le]>2){printf("impossible\n");return 0;}
		a[i]=i;
	}
	sort(a+1,a+n+1,cmp);
	num=1;
	p11=0;
	p12=0;
	change[0][0]=0;
//	for (int i=1;i<=n;i++)printf("%s\n",str[a[i]].s);
	for (int i=1;i<=n;i++)
	{
		if(num==1)
		{
			int t1=judge(i,p11),t2=judge(i,p12);
			if(t1+t2==2)
			{
				num=2;
				path[i][p12]=p11*10000+p12;
				path[i][p11]=p11*10000+p12;
				change[i][p11]=(1^change[p11][p12]);
				change[i][p12]=change[p11][p12];
				p22=p12;
				p12=p11;
				p11=i;
				p21=i;
				if(p22==p21)num=1;
			}
			else if(t1==1)
			{
				num=1;
				path[i][p12]=p11*10000+p12;
				change[i][p12]=change[p11][p12];
				p11=i;
			}
			else if(t2==1)
			{
				num=1;
				path[i][p11]=p11*10000+p12;
				change[i][p11]=(1^change[p11][p12]);
				p12=p11;
				p11=i;
			}
			else
			{
				printf("impossible\n");
				return 0;
			}
		}
		else
		{
			int t1=judge(i,p11);
			if(t1==1)
			{
				num=2;
				path[i][p12]=p11*10000+p12;
				path[i][p22]=p21*10000+p22;
				change[i][p12]=change[p11][p12];
				change[i][p22]=change[p21][p22];
				p11=i;
				p21=i;
			}
			else
			{
				int t2=judge(i,p12),t3=judge(i,p22);
				if(t2==1||t3==1)
				{
					num=1;
					if(t2==1)
					{
						path[i][p11]=p11*10000+p12;
						change[i][p11]=(1^change[p11][p12]);
					}
					else
					{
						path[i][p11]=p21*10000+p22;
						change[i][p11]=(1^change[p21][p22]);
					}
					p12=p11;
					p11=i;
				}
				else
				{
					printf("impossible\n");
					return 0;
				}
			}
		}//printf("%d %d %d %d %d %d\n",i,num,p11,p12,p21,p22);
	}
	getans(p11,p12);
	printans();
	return 0;
}