P3825 [NOI2017] 游戏

题目大意

有四种类型的比赛 \(x,a,b,c\),三种赛车(\(A,B,C\))。其中 \(x\) 的数量 为 \(d\)

\(x\) 表示三种赛车都可以选, \(a\) 表示 \(A\)不能选,\(b\) 表示 \(B\)不能选,\(c\) 表示 \(C\)不能选。

现在要比 \(n\) 场,有 \(m\) 个限制形如:

\(p,f,q,t\) 表示如果第 \(p\) 场选了第 \(f\) 种的赛车则第 \(q\)必须选用第 \(t\) 种赛车。

任意一组满足所有要求的赛车选择方案。

\(n,m\leq10^5\)\(d\leq8\)

思路

如果没有 \(x\) 的话可以直接考虑 \(2-SAT\),以每一场比赛作为变量,能选的两种赛车作为布尔变量即可,然后就是找规律。将变量设为 \(i_0\)\(i_1\)

但是现在处理 \(x\),注意到数量很少,所以可以直接枚举 \(x\) 的种类,将它变成 \(a\)\(b\)

为什么我们不需要再变成 \(c\) 呢?因为在发现如果要不选 \(C\) 的话在 \(a,b\) 中都可以直接不选(如果这样是对的话),所以重复了,直接不选。这样我们可以大概猜的最终时间复杂度是 \(O(2^d(m+n))\)

考虑建图。分三种情况,设第 \(i\) 个比赛目前不能选 \(F_i\)

  1. \(f_p=F_p\),则这个情况一定不会成立,可以直接忽略
  2. \(t_q=F_q\),则这个情况的前提一定不能成立,连 \(p_0\rightarrow p_1\)
  3. 除此以外的情况,连命题 \(p_0\rightarrow q_0\) 与它的逆否命题 \(q_1\rightarrow p_1\)

之后跑 \(2-SAT\) 求是否合法与输出方案数即可。对于 \(2-SAT\) 方案数,我们理应按照缩点后图跑拓扑排序后优先输出拓扑序大的,但因为 \(Tarjan\) 缩点就是按拓扑排序的逆序输出的,所以我们只需要输出强连通分量编号小的即可。

代码

#include<bits/stdc++.h>
#define T(u,v) u+turn[rc[u]][v]
#define N(u,v) u+turn2[rc[u]][v]
using namespace std;
typedef long long ll;
const ll MAXN=1e5+5;
ll n,d,m;
vector<ll>adj[MAXN];
ll lyymcl[MAXN],dfn[MAXN],yjr[MAXN],tot;
ll id[MAXN],scc;
bool ins[MAXN];
void add(ll u,ll v){
	adj[u].push_back(v);
}
stack<ll>sta;
ll turn[3][3],turn2[3][3];
ll rc[MAXN];
void lycnpy(ll u){
	dfn[u]=lyymcl[u]=++tot;
	ins[u]=true;
	sta.push(u);
	for(auto lmy:adj[u]){
		if(!dfn[lmy]){
			lycnpy(lmy);
			lyymcl[u]=min(lyymcl[u],lyymcl[lmy]);
		}else if(ins[lmy]){
			lyymcl[u]=min(lyymcl[u],dfn[lmy]);
		}
	}
	if(lyymcl[u]==dfn[u]){
		++scc;
		while(sta.top()!=u){
			id[sta.top()]=scc;
			ins[sta.top()]=false;
			sta.pop();
		}
		id[u]=scc;
		ins[u]=false;
		sta.pop();
	}
}
void lyc(){
	for(int i=1;i<=2*n;++i){
		if(!dfn[i]){
			lycnpy(i);
		}
	}
}
struct Query{
	ll p,q;
	ll t,f;
}ask[MAXN];
void clear(){
	for(int i=0;i<=2*n+3;++i){
		adj[i].clear();
	}
	memset(lyymcl,0,sizeof(lyymcl));
	memset(dfn,0,sizeof(dfn));
	memset(yjr,0,sizeof(yjr));
	tot=scc=0;
	memset(id,0,sizeof(id));
} 
ll tn(char c){
	if(c=='a'||c=='A'){
		return 0;
	} 
	if(c=='b'||c=='B'){
		return 1;
	}
	if(c=='c'||c=='C'){
		return 2;
	}
	return 4;
}
void check(){
		clear();
		for(int i=1;i<=m;++i){
			ll t=ask[i].t,f=ask[i].f,p=ask[i].p,q=ask[i].q;
			if(f==rc[p]){
				continue;
			}
			if(t==rc[q]){
				add(T(p,f),N(p,f));
			}else{
				add(T(p,f),T(q,t));
				add(N(q,t),N(p,f));
			}
		}
		lyc();
		bool good=false;
		for(int i=1;i<=n;++i){
			if(id[i]==id[n+i]){
				good=true;
				break;
			}
		}
		if(!good){
			for(int i=1;i<=n;++i){
				if(id[i]<id[n+i]){
					if(rc[i]==0){
						cout<<"B";
					}else if(rc[i]==1){
						cout<<"A";
					}else{
						cout<<"A";
					}
				}else{
					if(rc[i]==0){
						cout<<"C";
					}else if(rc[i]==1){
						cout<<"C";
					}else{
						cout<<"B";
					}
				}
			}
			exit(0);
		}
}
void dfs(ll x){
	if(x==n+1){
		check();
		return;
	}
	if(rc[x]==4){
		rc[x]=0;
		dfs(x+1);
		rc[x]=1;
		dfs(x+1);
		return;
	}
	dfs(x+1);
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>d;
	for(int i=1;i<=n;++i){
		char c;
		cin>>c;
		rc[i]=tn(c);
	}
	for(int i=0;i<3;++i){
		bool good=false;
		for(int j=0;j<3;++j){
			if(j==i){
				continue;
			}
			if(good){
				turn[i][j]=n;
				turn2[i][j]=0;
			}else{
				good=true;
				turn[i][j]=0;
				turn2[i][j]=n;
			}
		}
	}
	cin>>m;
	for(int i=1;i<=m;++i){
		char f,t;
		cin>>ask[i].p>>f>>ask[i].q>>t;
		ask[i].f=tn(f);
		ask[i].t=tn(t);
	}
	dfs(1);
	cout<<-1<<endl;
	return 0;
}

热门相关:大唐杨国舅   勇闯天涯   帝少宠妻有点甜   极品妖孽归来   美漫之大冬兵