3523: [Poi2014]Bricks

题意：

有n种颜色的砖块，第i种颜色的砖块有a[i]个，你需要把他们放成一排，使得相邻两个砖块的颜色不相同，限定第一个砖块的颜色是start，最后一个砖块的颜色是end，请构造出一种合法的方案或判断无解。

题解：

先考虑没有头尾限制怎么构造。
首先取出个数最多的那种颜色，放成一排，然后其他的插进去，显然是可行的。
而有了头尾限制，那么就先将头尾颜色插入即可，其他不变。
链表维护当前颜色序列。
细节略多。
code：

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
int a[1000010];
int n,st,ed;
int l[1000010],r[1000010],c[1000010],s,cnt=2,p[1000010];
void add(int x,int C)
{
	c[++cnt]=C;
	l[cnt]=x;r[cnt]=r[x];
	r[l[cnt]]=cnt;l[r[cnt]]=cnt;
}
int Next(int x) {x=r[r[x]];if(x==2) x=1;return x;}
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int main()
{
	n=read();st=read();ed=read();
	for(int i=1;i<=n;i++) a[i]=read();
	if(n==1)
	{
		if(a[1]==1) puts("1");
		else puts("0");
		return 0;
	}
	a[st]--;a[ed]--;
	if(a[st]<0) return puts("0"),0;
	for(int i=1;i<=n;i++)
		if(a[s]<a[i]) s=i;
	c[1]=st;c[2]=ed;r[1]=2;l[2]=1;
	int x=1;
	for(int i=1;i<=a[s];i++) add(x,s),x=r[x];
	if(ed!=s)
	{
		x=l[l[2]];
		for(int i=1;i<=a[ed];i++) add(x,ed),x=l[x];
	}
	if(st!=s&&a[st]&&st!=ed)
	{
		x=r[1];
		for(int i=1;i<=a[st];i++) add(x,st),x=Next(x);
	}
	else x=r[1];
	for(int i=1;i<=n;i++)
	{
		if(i==st||i==s||i==ed) continue;
		for(int j=1;j<=a[i];j++) add(x,i),x=Next(x);
	}
	x=1;cnt=0;
	while(x) p[++cnt]=c[x],x=r[x];
	for(int i=1;i<cnt;i++)
		if(p[i]==p[i+1]) return puts("0"),0;
	for(int i=1;i<=cnt;i++)
	{
		if(i!=1) printf(" ");
		printf("%d",p[i]);
	}
}