P4171 满汉全席

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

P4171 满汉全席

2023-02-19 15:09:57 来源：博客园

(相关资料图)

题意简述

$\qquad$有几组要求，由二元状态表示 $(ca, cb)$，其中 $a, b$表示的是菜品，$c$表示的是样式，当 $c$ 为 m时是满式，为h时是汉式。问是否有一种方案，使得每组要求至少可以满足其中一个要求。

解题思路

$\qquad$我们将一个点拆为两个，用 $2i$表示满式第 $i$ 种，用 $2i + 1$表示汉式第 $i$ 种。$\qquad$由于每个选手可以做出 $n$ 道菜，而总共的菜数只有 $2n$ 中，那么很容易可以推出每种菜要么做满式，要么做汉式。$\qquad$接下来我们对这个题目进行分类讨论：

$\qquad\large 1.\ \ \large (m_i, m_j)$ 由于至少满足一种情况，那另一种不满足的时候前一种就应该满足，所以可以得到：$$\Large \neg m_i\Rightarrow m_j$$

\[\Large\neg m_j\Rightarrow m_i\]

因为不做满式就只能做汉式，所以整理得到：$$\Large h_i\Rightarrow m_j,\ 2i+1\to 2j$$$$\Large h_j\Rightarrow m_i, \ 2j+1\to2i$$$\qquad\large 2.(m_i,h_j)$同理可得$$\Large h_i\Rightarrow h_j,\ 2i+1\to 2j+1$$$$\Large m_j\Rightarrow m_i,\ 2j\to 2i$$$\qquad\large 3.(h_i,m_j)$同理可得$$\Large m_i\Rightarrow m_j,\ 2i\to 2j$$$$\Large h_j\Rightarrow h_i,\ 2j+1\to 2i+1$$$\qquad\large 4.(h_i,h_j)$同理可得$$\Large m_i\Rightarrow h_j,\ 2i\to 2j+1$$$$\Large m_j\Rightarrow h_i,\ 2j\to 2i+1$$

容易发现上述条件关系有一定的奇偶关系，所以可以用 $xor$ 运算来简化：

u = u * 2 + (t1 == "h");v = v * 2 + (t2 == "h");add(u ^ 1, v), add(v ^ 1, u);

然后跑 Tarjan，如果一个菜满式和汉式在同一个分量里，就无解

代码

#include #include #include #define init(x, y) memset(x, y, sizeof x)using namespace std;const int N = 2010;int e[N], ne[N], h[N], idx;int stmp, dfn[N], low[N];int ins[N], stk[N], tt;int n, m, scc_cnt, id[N];void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;}void dfs(int u) {dfn[u] = low[u] = ++ stmp;stk[ ++ tt] = u, ins[u] = 1;for (int i = h[u]; ~i; i = ne[i]) {int j = e[i];if (!dfn[j]) dfs(j);if (ins[j]) low[u] = min(low[u], low[j]);}if (low[u] == dfn[u]) {int y; ++ scc_cnt;do {y = stk[tt -- ], ins[y] = 0;id[y] = scc_cnt;} while (y != u);}}int main() {int T;scanf("%d", &T);while (T -- ) {init(h, -1), init(dfn, 0);tt = scc_cnt = idx = 0;scanf("%d%d", &n, &m);while (m -- ) {char t1, t2;int u, v;scanf(" %c%d %c%d", &t1, &u, &t2, &v);u --, v --;u = u * 2 + (t1 == "h");v = v * 2 + (t2 == "h");add(u ^ 1, v), add(v ^ 1, u);}for (int i = 0; i < 2 * n; i ++ ) if (!dfn[i]) dfs(i);int flag = 1;for (int i = 0; i < n && flag; i ++ ) if (id[i * 2] == id[i * 2 + 1]) flag = 0;puts(flag ? "GOOD" : "BAD");}return 0;}

关键词：表示的是满汉全席至少可以