题目传送门

题意：

　　有n个人，k盏灯，灯有红蓝两种颜色，每个人都猜了三种灯的颜色，问如何安排灯的颜色，使得每个人猜的灯至少有两个是对的。

思路：

　　很容易想到2-sat，但是显然枚举每个人猜对的情况是不显示的，因为猜对两个和猜对三个两种情况就很难搞了。所以我们枚举每一个人猜的灯错的是哪一盏，如果某一盏错了，那么另外两盏就必须是对的，这样才符合条件。

　　我们用一个light的二维vector，保存：$灯的某种颜色，选这个颜色是属于选错的人$，再用一个二维vector名字叫people保存每个人的三种错误情况。

　　然后在twosat的函数里枚举每种灯的颜色，如果说某一种颜色对于所有选错的人来说都满足条件（满足dfs），那对于这个灯的颜色选对的人肯定已经是更优的，所以可以这样枚举。

　　在dfs中check合法性的时候，就枚举所有选错的人，这个人的其他颜色都必须选对才可以。

　　结合文字看代码吧，光靠文字有点难表述清楚。

#pragma GCC optimize (2)
#pragma G++ optimize (2)
#pragma comment(linker, "/STACK:102400000,102400000")
#include
#include
#include
#define rep(i,a,b) for(int i=a;i<=b;i++) #define dep(i,b,a) for(int i=b;i>=a;i--)
#define clr(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define pii pair
using namespace std;
typedef long long ll;
const int maxn=;
const int inf=0x3f3f3f3f;
ll rd()
{
ll x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();} return x*f; } int vis[maxn],sta[maxn],top; struct node{ int p1,p2,p3,c1,c2,c3; }a[maxn]; vectorlight\[maxn\],peo\[maxn\];
int n,k;
bool dfs(int u){
if(vis\[u^\])return false;
if(vis\[u\])return true;
vis\[u\]=;
sta\[++top\]=u;
for(auto &x:light\[u\]){
for(auto &v:peo\[x\]){
if(v==u)continue;
if(!dfs(v^))return false;
}
}
return true;
}
int two\_sat(int n){
for(int i=;i<=n;i+=){ if(vis\[i\]||vis\[i^\])continue; top=; if(!dfs(i)){ while(top){vis\[sta\[top--\]\]=;} if(!dfs(i^))return false; } } return true; } int main(){ cin>>k>>n;
rep(i,,n){
char xx,yy,zz;
scanf("%d %c %d %c %d %c",&a[i].p1,&xx,&a[i].p2,&yy,&a[i].p3,&zz);
a[i].c1=a[i].p1*+(xx=='B');
a[i].c2=a[i].p2*+(yy=='B');
a[i].c3=a[i].p3*+(zz=='B');

    light\[a\[i\].c1^\].push\_back(i);  
    peo\[i\].push\_back(a\[i\].c1^);

    light\[a\[i\].c2^\].push\_back(i);  
    peo\[i\].push\_back(a\[i\].c2^);

    light\[a\[i\].c3^\].push\_back(i);  
    peo\[i\].push\_back(a\[i\].c3^);  
}  
int f=two\_sat(\*k);  
if(f==){  
    puts("-1");  
}else{  
    for(int i=;i<=k;i++){  
        if(vis\[i\*\])putchar('R');  
        else putchar('B');  
    }  
    puts("");  
}  

}
/*
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

5 6
1 B 3 R 4 B
2 B 3 R 4 R
1 B 2 R 3 R
3 R 4 B 5 B
3 B 4 B 5 B
1 R 2 R 4 R
*/