BZOJ 4945 NOI2017D2T1 游戏

题目大意

给你一堆车属性为"A"/"B"/"C"和一堆赛道，每个赛道都有一个属性表示这个赛道哪种车不能跑（可能所有车都能跑）请输出一种跑车的方案，没有就-1.

这道题因为学了2-SAT就被拐来做……使用$O(n^2)$的2-SAT拿到了75分果断跑路……正确的2-SAT姿势之后再学嘛qwq

注意这道题的连边方法。2-SAT连边需要是完全对称的，所以假设A必须选B那么如果选择B的反点就也必须要选A的反点。

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 50010
#define M 100010
int n,d,m,s[N],ref[N][3],p[N][2],rx[M],ra[M],ry[M],rb[M];
char str[N];
bool choice[10];
int to[M<<1],nxt[M<<1],head[N<<1],tot;
inline void AE(int X,int Y){to[++tot]=Y,nxt[tot]=head[X],head[X]=tot;}
int dfn[N<<1],low[N<<1],bel[N<<1],stk[N<<1],st,cp,cnt;
bool ins[N<<1];
void tarjan(int pos)
{
	dfn[pos]=low[pos]=++cnt,stk[++st]=pos,ins[pos]=true;
	int y;
	for(int i=head[pos];i;i=nxt[i])
	{
		y=to[i];
		if(!dfn[y]) tarjan(y),low[pos]=min(low[pos],low[y]);
		else if(ins[y]) low[pos]=min(low[pos],dfn[y]);
	}
	if(dfn[pos]==low[pos])
	{
		++cp;
		for(int i=0;i!=pos;bel[i=stk[st--]]=cp,ins[i]=false);
	}
}
inline void check()
{
	int tmp=0,i,j;
	for(i=1;i<=n;++i)
		if(s[i]==4)
		{
			memset(ref[i],0,sizeof ref[i]);
			if(choice[++tmp]) ref[i][1]=p[i][0],ref[i][2]=p[i][1];
			else ref[i][0]=p[i][0],ref[i][2]=p[i][1];
		}
	memset(head,0,sizeof head),tot=0;
	for(i=1;i<=m;++i)
		if(ref[rx[i]][ra[i]])
		{
			bool ta=(ref[rx[i]][ra[i]]==p[rx[i]][1]),tb=(ref[ry[i]][rb[i]]==p[ry[i]][1]);
			if(!ref[ry[i]][rb[i]]) AE(p[rx[i]][ta],p[rx[i]][ta^1]);
			else AE(p[rx[i]][ta],p[ry[i]][tb]),AE(p[ry[i]][tb^1],p[rx[i]][ta^1]);
		}
	memset(dfn,0,sizeof dfn);
	for(i=1,j=(n<<1);i<=j;++i) if(!dfn[i]) tarjan(i);
	for(i=1;i<=n;++i) if(bel[p[i][0]]==bel[p[i][1]]) return;
	for(i=1;i<=n;++i)
	{
		if(bel[p[i][0]]<bel[p[i][1]])
		{
			for(int j=0;j<3;++j)
				if(ref[i][j]==p[i][0])
					tmp=j;
		}
		else
		{
			for(int j=0;j<3;++j)
				if(ref[i][j]==p[i][1])
					tmp=j;
		}
		putchar('A'+tmp);
	}
	exit(0);
}
void DFS(int pos)
{
	if(pos>d) {check();return;}
	choice[pos]=true;
	DFS(pos+1);
	choice[pos]=false;
	DFS(pos+1);
}
int main()
{
	int tp=0;
	scanf("%d%d%s",&n,&d,str+1);
	for(int i=1;i<=n;++i)
	{
		switch(str[i])
		{
			case 'a':
			{
				s[i]=1;
				ref[i][1]=p[i][0]=++tp,ref[i][2]=p[i][1]=++tp;
				break;
			}
			case 'b':
			{
				s[i]=2;
				ref[i][0]=p[i][0]=++tp,ref[i][2]=p[i][1]=++tp;
				break;
			}
			case 'c':
			{
				s[i]=3;
				ref[i][0]=p[i][0]=++tp,ref[i][1]=p[i][1]=++tp;
				break;
			}
			case 'x':s[i]=4,p[i][0]=++tp,p[i][1]=++tp;break;
		}
	}
	scanf("%d",&m);
	for(int i=1;i<=m;++i)
	{
		scanf("%d%s",rx+i,str),ra[i]=str[0]-'A',
		scanf("%d%s",ry+i,str),rb[i]=str[0]-'A';
	}
	DFS(1);
	puts("-1");
	return 0;
}