[比赛补题][2SAT][x] codeforces gym 101987 K TV Show Game

题目链接

题意：

题意：有一排 $n$ 个灯，可以是红色或者蓝色，然后k个人投票，每个人投的票会写上他猜测的某三盏灯的颜色。然后现在问是否有一种红蓝灯的安排方式使得每个人投的票至少有2个猜测是对的。

题解：

$2-SAT$ 板子题，但是比赛时候忘记了（主要这东西在中国真的很少考emm）相当于求让每个人的条件都为真的一组二进制向量。那么现在的问题就是怎么把每个人的约束条件转化为 $2-SAT$ 的子句的形式。

首先用 $x_1$ $x_2$ $x_3$ 表示一个人的三个选择，那么代表这个人的子句用文字表达来说就是 $x_1 x_2 x_3$ 中有2个或者3个为真。用条件的知识可以推出来这个说法等价于 $(x_1\lor x_2 )\land(x_1\lor x_3)\land(x_2\lor x_3)$ ,这样就把每个人的条件写成 $2-SAT$ 的形式了，接下来按板子连通分量+拓扑排序求解就OK了。

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 1e4 + 7;
const int maxm=4e5+10;
const int mod = 1e9 + 7;

struct {
	int to,next;
}edge[maxm];
int head[maxn],tot;
void init(){
	tot=0;
	memset(head,-1,sizeof(head));
}
void addedge(int u,int v){
	edge[tot].to=v;edge[tot].next=head[u];head[u]=tot++;
}
int low[maxn],dfn[maxn],Stack[maxn],belong[maxn];
int index,top;
int scc;
bool instack[maxn];
int num[maxn];
void Tarjan(int u){
	int v;
	low[u]=dfn[u]=++index;
	Stack[top++]=u;
	instack[u]=true;
	for(int i=head[u];i!=-1;i=edge[i].next){
		v=edge[i].to;
		if(!dfn[v]){
			Tarjan(v);
			low[u]=min(low[u],low[v]);
		}else if(instack[v]&&low[u]>dfn[v]){
			low[u]=dfn[v];
		}
	}
	if(low[u]==dfn[u]){
		++scc;
		do{
			v=Stack[--top];
			instack[v]=false;
			belong[v]=scc;
			num[scc]++;
		}while(v!=u);
	}
}
bool solvable(int n){
	memset(dfn,0,sizeof(dfn));
	memset(instack,false,sizeof(instack));
	memset(num,0,sizeof(num));
	index=scc=top=0;
	for(int i=0;i<n;++i) if(!dfn[i]) Tarjan(i);
	for(int i=0;i<n;i+=2) if(belong[i]==belong[i^1]) return false;
	return true;
}
queue<int> q1,q2;
vector<vector<int> >dag;
char color[maxn];
int indeg[maxn];
int cf[maxn];
void solve(int n){
	dag.assign(scc+1,vector<int>());
	memset(indeg,0,sizeof(indeg));
	memset(color,0,sizeof(color));
	for(int u=0;u<n;++u)
		for(int i=head[u];i!=-1;i=edge[i].next){
			int v=edge[i].to;
			if(belong[u]!=belong[v]){
				dag[belong[v]].push_back(belong[u]);
				indeg[belong[u]]++;
			}
		}
	for(int i=0;i<n;i+=2){
		cf[belong[i]]=belong[i^1];
		cf[belong[i^1]]=belong[i];
	}
	while(!q1.empty()) q1.pop();
	while(!q2.empty()) q2.pop();
	for(int i=1;i<=scc;++i) if(indeg[i]==0) q1.push(i);
	while(!q1.empty()){
		int u=q1.front();
		q1.pop();
		if(color[u]==0){
			color[u]='R';
			color[cf[u]]='B';
		}
		int sz=dag[u].size();
		for(int i=0;i<sz;++i){
			indeg[dag[u][i]]--;
			if(indeg[dag[u][i]]==0)
				q1.push(dag[u][i]);
		}
	}
}
int idx(int x,int op){//R 2*x B 2*x+1
	if(op==0) return 2*x;
	return 2*x+1;
}
void addcond(int x1,int op1,int x2,int op2){
	addedge(idx(x1,op1^1),idx(x2,op2));
	addedge(idx(x2,op2^1),idx(x1,op1));
}

int main() {
	int k,n,x1,x2,x3,op1,op2,op3;
	char o1,o2,o3;
	scanf("%d%d",&k,&n);
	init();
	for(int i=1;i<=n;++i){
		scanf(" %d %c %d %c %d %c",&x1,&o1,&x2,&o2,&x3,&o3);
		op1=(o1=='R'?0:1);
		op2=(o2=='R'?0:1);
		op3=(o3=='R'?0:1);
		x1--,x2--,x3--;
		addcond(x1,op1,x2,op2);
		addcond(x1,op1,x3,op3);
		addcond(x2,op2,x3,op3);
	}
	if(solvable(2*k)){
		solve(2*k);
		for(int i=0;i<k;++i){
			if(color[belong[2*i]]=='R')printf("R");
			else printf("B");
		}
	}
	else{
		puts("-1");
	}
	return 0;
}
/*
7 5
3 R 5 R 6 B
1 B 2 B 3 R
4 R 5 B 6 B
5 R 6 B 7 B
1 R 2 R 4 R
*/