欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

3523: [Poi2014]Bricks

程序员文章站 2022-07-13 12:42:51
...

题意:

有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]);
	}
}

上一篇: TF笔记 - 正则化

下一篇: Java正则化