夏晓光(loveJY)的博客

NOI2017D2T1

早就压在我的任务清单里了...

另外打算开完十年(左右)NOI系列的坑就去开集训队作业和Ynoi吧

为什么呢?因为PKWUC2020数据结构大赛,做过Ynoi和没做过的肯定不一样

小 L 计划进行$n$场游戏，每场游戏使用一张地图，小 L 会选择一辆车在该地图上完成游戏。

小 L 的赛车有三辆，分别用大写字母A、B、C表示。地图一共有四种，分别用小写字母x、a、b、c表示。其中，赛车A不适合在地图a上使用，赛车B不适合在地图b上使用，赛车C不适合在地图c上使用，而地图x则适合所有赛车参加。适合所有赛车参加的地图并不多见，最多只会有d张。

$n$场游戏的地图可以用一个小写字母组成的字符串描述。例如：S=xaabxcbc表示小 L 计划进行$8$场游戏，其中第$1$场和第$5$场的地图类型是x，适合所有赛车，第$2$场和第$3$场的地图是a，不适合赛车A，第$4$场和第$7$场的地图是b，不适合赛车B，第$6$场和第$8$场的地图是c，不适合赛车C。

小 L 对游戏有一些特殊的要求，这些要求可以用四元组 $(i, h_i, j, h_j)$来描述，表示若在第$i$场使用型号为$h_i$​的车子，则第$j$场游戏要使用型号为$h_j$的车子。

你能帮小 L 选择每场游戏使用的赛车吗？如果有多种方案，输出任意一种方案。如果无解，输出$-1$（不含双引号）。

首先其实不难发现这是一个2-SAT题,因为他要求构造方案,而且有一些很像2-SAT的限制条件,另外赛车只有三种,一个地图限制了1种,所以只有两种可用的赛车这样子

所以我们想去掉x地图是不是就是个2-SAT裸题了啊,怎么解决x的限制呢,3-SAT好像是没有确定性多项式算法的.....而n又这么大

看一眼x的数量,小于等于8.....这个不是明摆着让你枚举吗?????

好吧,我承认,难度在于写代码,所以仔细看看代码,里面有很不错的trick,比如利用tran函数找到相关的点

code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

namespace fastIO {
#define BUF_SIZE (1<<19)
	static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;

	inline char nc() {
		if(p1==pend) {
			p1=buf;
			pend=buf+fread(buf,1,BUF_SIZE,stdin);
		}
		return *p1++;
	}

	inline int read() {
		int x=0,f=1;
		char s=nc();
		for(; !isdigit(s); s=nc())if(s=='-')f=-1;
		for(; isdigit(s); s=nc())x=(x<<1)+(x<<3)+s-'0';
		//	printf("%d??\n",x);
		return x*f;
	}
	inline char get() {
		char c=nc();
		for(; !isalpha(c); c=nc());
		return c;
	}
	inline void _gets(char *s) {
		int tot=1;
		s[tot]=nc();
		for(; !isalpha(s[tot]); s[tot]=nc());
		for(; isalpha(s[tot]); s[tot]=nc())++tot;
		return ;
	}
}
using namespace fastIO;
const int MAXN=2e5+7;
int n,d,m,a1[MAXN],b1[MAXN],ccnt,nxt[MAXN],home[MAXN],to[MAXN],dfn[MAXN],low[MAXN],
    times,num,bel[MAXN],top,stk[MAXN],cyx[MAXN];
char s[MAXN],a2[MAXN],b2[MAXN],orz[MAXN];
bool ins[MAXN],flag;

inline void add(int u,int v) {
	nxt[++ccnt]=home[u];
	home[u]=ccnt;
	to[ccnt]=v;
}

inline int neg(int x) {
	return x>n?x-n:x+n;
}

inline int tran(int x,char c) {
	if(s[x]=='a')return c=='B'?x:x+n;
	if(s[x]=='b'||s[x]=='c')return c=='A'?x:x+n;
	if(c=='C')return x+n;

	//说实话,这个tran就是
	//如果搬掉A,那么就用B为真,C为假
	//搬掉b,同理A真C假
	//啥都没搬,硬点x搬掉A或者B
	//为C一定false,否则可能为A或者B
	return x;
}

inline void tarjan(int u) {
	dfn[u]=low[u]=++times;
	ins[stk[++top]=u]=1;
	for(int i=home[u]; i; i=nxt[i]) {
		int v=to[i];
		if(!dfn[v]) {
			tarjan(v);
			low[u]=min(low[u],low[v]);
		} else if(ins[v]) {
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(dfn[u]==low[u]) {
		int v;
		bel[u]=++num;
		ins[u]=0;
		while (v = stk[top--], v != u) bel[v] = num, ins[v] = 0;
	}
}

bool solve() {
	int i;
	ccnt=times=num=0;
	for(int i=1; i<=(n<<1); ++i)bel[i]=home[i]=dfn[i]=0;
	for(int i=1; i<=m; ++i) if(s[a1[i]]!='x'&&s[b1[i]]!='x') {
			if(a2[i]==s[a1[i]]-32)continue;//厉害的是,这场比赛根本不让用
			int u=tran(a1[i],a2[i]),v;
			if(b2[i]==s[b1[i]]-32) {
				add(u,neg(u));//厉害的是,另一边的比赛根本不让用
				//所以你也不让用
				continue;
			}
			v=tran(b1[i],b2[i]);
			add(u,v);
			add(neg(v),neg(u));
			//相当于如果这场比赛a1你用a2,可推出b1用b2
			//否则b1不用b2,可推出a1不用a2
		} else {
			char o=s[a1[i]],p=s[b1[i]];
			int u,v,x=cyx[a1[i]],y=cyx[b1[i]];
			if(o=='x'&&p=='x') {
				if(a2[i]==orz[x])continue;//orzx是不能用的之前dfs的
				u=tran(a1[i],a2[i]),v;
				if(b2[i]==orz[y]) {
					add(u,neg(u));
					continue;
				}
				v=tran(b1[i],b2[i]);
				add(u,v);
				add(neg(v),neg(u));
			} else if(o=='x'&&p!='x') {
				if(a2[i]==orz[x])continue;
				u=tran(a1[i],a2[i]),v;
				if(b2[i]==s[b1[i]]-32) {
					add(u,neg(u));
					continue;
				}
				v=tran(b1[i],b2[i]);
				add(u,v);
				add(neg(v),neg(u));
			} else {
				if(a2[i]==s[a1[i]]-32)continue;
				u=tran(a1[i],a2[i]),v;
				if(b2[i]==orz[y]) {
					add(u,neg(u));
					continue;
				}
				v=tran(b1[i],b2[i]);
				add(u,v);
				add(neg(v),neg(u));
			}
		}
	for(int i=1; i<=(n<<1); ++i)if(!dfn[i])tarjan(i);
	for(int i=1; i<=n; ++i)if(bel[i]==bel[i+n])return 0;//判合法?
	for(int i=1; i<=n; ++i) {
		if(bel[i]<bel[i+n]) {
			if(s[i]=='a')putchar('B');
			else if(s[i]=='b'||s[i]=='C')putchar('A');
			else if(orz[cyx[i]]=='A')putchar('B');
			else putchar('A');
		} else {
			if(s[i]=='a'||s[i]=='b')putchar('C');
			else if(s[i]=='c')putchar('B');
			else if(orz[cyx[i]]=='A')putchar('C');
			else putchar('B');
		}
	}
	return 1;
}

void dfs(int dep) {
	if(dep>d) {
		if(!flag)flag=solve();
		if(flag)exit(0);
		return;
	}
	orz[dep]='A';
	dfs(dep+1);
	orz[dep]='B';
	dfs(dep+1);
	//原来这只是个dfs
}

int main() {
//	freopen("test.in","r",stdin);
//	scanf("%d",&n);
	n=read();
	int ___;
	___=read();
	_gets(s);
	m=read();
	register int i;
	for(i=1; i<=n; ++i)if(s[i]=='x')cyx[i]=++d;
	for(i=1; i<=m; ++i)a1[i]=read(),a2[i]=get(),b1[i]=read(),b2[i]=get();
    //printf("%c %c\n",a2[i],b2[i]);
	dfs(1);
	if(!flag)puts("-1");
	return 0;
}