写在前面
不会吧不会吧，这么裸的2-SAT都看不出来？ 经验题
Solution
2-SAT处理
关于什么是2-SAT，详见Oiwiki
简单来说，2-SAT问题的形式是给一堆条件，每个条件中有两个小条件，不过只需要满足其中一种
题目中说评委的两个条件只需要满足一个即可，然后每种材料又有满式和汉式两种选择
这不显然让我们打2-SAT？可能也有其他神仙做法
而2-SAT主要考察建图这一块，我们用 \(0 \sim n\) 表示满式，用 \(n+1 \sim 2n\) 表示汉式，用 \(x^{-1}\) 表示 \(x\) 的另一种菜式
那么对于任意一个条件 \((a_i,b_i)\)，
-
首先让我们满足 \(a_i\) 而不满足 \(b_i\) ，那就从 \(a_i\) 向 \(b_i^{-1}\) 连一条边
-
然后让我们满足 \(b_i\) 而不满足 \(a_i\) ，那就从 \(b_i\) 向 \(a_i^{-1}\) 连一条边
（别搞混了调半天）
字符串处理
暴力处理即可，判断第一个字符确定满式还是汉式
扫一遍字符串取出是第几号菜，然后按上面的方式加边
答案判断
用强连通分量缩点
缩点后，如果存在同一菜品出现在同一强联通分量里，那就不能满足
否则就可以满足
大体思路就这些，看代码吧
Code
/*
Work by: Suzt_ilymics
Knowledge: ??
Time: O(??)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define orz cout<<"lkp AK IOI!"<<endl
using namespace std;
const int MAXN = 1e5+5;
const int INF = 1e9+7;
const int mod = 1e9+7;
struct edge{
int to, nxt;
}e[MAXN << 1];
int head[MAXN], num_edge = 0;
int T, n, m;
int dfn[MAXN], low[MAXN], cnt = 0, stc[MAXN], sc = 0;
int num[MAXN], t = 0;
bool vis[MAXN];
int read(){
int s = 0, f = 0;
char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
return f ? -s : s;
}
void add_edge(int from, int to){ e[++num_edge] = (edge){to, head[from]}, head[from] = num_edge; }
void tarjan(int u){
stc[++sc] = u, dfn[u] = low[u] = ++cnt, vis[u] = true;
for(int i = head[u]; i; i = e[i].nxt){
int v = e[i].to;
if(!dfn[v]){
tarjan(v), low[u] = min(low[u], low[v]);
}
else if(vis[v]) low[u] = min(low[u], dfn[v]);
}
if(low[u] == dfn[u]){
int pre; ++t;
do{
pre = stc[sc--];
vis[pre] = false;
num[pre] = t;
}while(pre != u);
}
}
int main()
{
T = read();
while(T--){
memset(head, 0, sizeof head);
memset(vis, false, sizeof vis);
memset(dfn, 0, sizeof dfn);
num_edge = t = sc = cnt = 0;
n = read(), m = read();
char u[9], v[9];
for(int i = 1; i <= m; ++i){
// top = 0;
// while(true){
// ch = getchar();
//// cout<<ch<<endl;
// if(ch == ' ') break;
// else u[++top] = ch;
// }
// top = 0;
// while(true){
// ch = getchar();
// if(ch == '\n') break;
// else v[++top] = ch;
// cout<<ch<<" ";
// }
cin >>(u + 1)>>(v + 1);
// cout<<(u + 1)<<" "<<(v + 1)<<endl;;
int u_ = 0, v_ = 0;
for(int j = 2; j <= (int)strlen(u + 1); ++j) u_ = (u_ << 1) + (u_ << 3) + (int)(u[j] ^ 48);
for(int j = 2; j <= (int)strlen(v + 1); ++j) v_ = (v_ << 1) + (v_ << 3) + (int)(v[j] ^ 48);
if(u[1] == 'm' && v[1] == 'm') add_edge(u_, v_ + n), add_edge(v_, u_ + n);
if(u[1] == 'h' && v[1] == 'm') add_edge(u_ + n, v_ + n), add_edge(v_, u_);
if(u[1] == 'm' && v[1] == 'h') add_edge(u_, v_), add_edge(v_ + n, u_ + n);
if(u[1] == 'h' && v[1] == 'h') add_edge(u_ + n, v_), add_edge(v_ + n, u_);
}
for(int i = 1; i <= 2 * n; ++i){
if(!dfn[i]) tarjan(i);
}
int flag = false;
for(int i = 1; i <= n; ++i){
if(num[i] == num[i + n]){
flag = true;
}
}
if(flag) printf("BAD\n");
else printf("GOOD\n");
}
return 0;
}
如果有什么问题，请在评论区指正