NOIP2023模拟12联测33 D. 滈葕
目录题目大意
思路
放一段题解的材料
ABO 血型系统是血型系统的一种,把血液分为 A,B,AB,O 四种血型。血液由红细胞和血清等组成,红细胞表面 有凝集原,血清内有凝集素。根据红细胞表面有无凝集原 A 和 B 来划分血液类型。红细胞上只有凝集原 A 的 为 A 型血,其血清中有抗 B 凝集素;红细胞上只有凝集原 B 的为 B 型血,其血清中有抗 A 凝集素;红细胞上 两种凝集原都有的为 AB 型血,其血清中无凝集素;红细胞上两种凝集原皆无者为 O 型,其血清中两种凝集素 皆有。有凝集原 A 的红细胞可被抗 A 凝集素凝集;有凝集原 B 的红细胞可被抗 B 凝集素凝集。配血试验是两 个人分别提供红细胞和血清并将其混合,观察是否有凝集反应。
可以发现,ABCD 的属性分别表示 A,B,AB,O 型血,一条边表示一次配血试验
设一条边 \((u , v , w)\) ,
若 \(w = 0\) 则:\(\neg(a_u \and a_v) \and \neg (b_u \and \neg b_v) = (\neg a_u \or a_v) \and (\neg b_x \or b_y)\)
若 \(w = 1\) 则:\((a_u \and \neg a_v) \or (b_x \and \neg b_y) = (a_x \or b_x) \and (a_x \or \neg b_y) \and (\neg a_y \or b_x) \and (\neg a_y \or \neg b_y)\)
可以用 \(2-SAT\) 来处理
编号为:
\[a_i , i \newline \neg a_i i +n \newline b_i , i +n *2 \newline \neg b_i , i +n *3 \]数组开大点
code
#include <bits/stdc++.h>
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
using namespace std;
const int N = 1e5 + 5;
int a[N << 2] , a1 , n , m , hd[N << 2] , low[N << 2] , dfn[N << 2] , cnt , p1 , p2 , num[N << 2];
stack<int> stk;
struct E {
int to , nt;
} e[N << 6];
void add (int x , int y) { e[++cnt].to = y , e[cnt].nt = hd[x] , hd[x] = cnt; }
void dfs (int x , int fa) {
stk.push(x);
int y;
dfn[x] = low[x] = ++p1;
for (int i = hd[x] ; i ; i = e[i].nt) {
y = e[i].to;
if (!dfn[y]) {
dfs (y , x);
low[x] = min (low[x] , low[y]);
}
else if (!num[y]) {
low[x] = min (low[x] , dfn[y]);
}
}
if (dfn[x] == low[x]) {
p2 ++;
y = 0;
while (y != x && !stk.empty()) {
y = stk.top();
stk.pop();
num[y] = p2;
}
}
}
int main () {
freopen ("dopetobly.in" , "r" , stdin);
freopen ("dopetobly.out" , "w" , stdout);
int u , v , w;
scanf ("%d%d" , &n , &m);
fu (i , 1 , m) {
scanf ("%d%d%d" , &u , &v , &w);
if (!w) {
add (u , v);
add (v + n , u + n);
add (u + n * 2 , v + n * 2);
add (v + n * 3 , u + n * 3);
}
else {
add (u + n , u + n * 2);
add (u + n , v + n * 3);
add (u + n * 3 , u);
add (u + n * 3 , v + n);
add (v , u + n * 2);
add (v , v + n * 3);
add (v + n * 2 , u);
add (v + n * 2 , v + n);
}
}
fu (i , 1 , n * 4) {
if (!dfn[i]) {
dfs (i , 0);
}
}
fu (i , 1 , n) {
if (num[i] == num[i + n] || num[i + n * 2] == num[i + n * 3]) {
puts ("NO");
exit (0);
}
}
puts ("YES");
fu (i , 1 , n) {
bool x = num[i] < num[i + n] , y = num[i + n * 2] < num[i + n * 3];
if (x && !y) printf ("A");
else if (!x && y) printf ("B");
else if (x && y) printf ("C");
else printf ("D");
}
return 0;
}
标签:12,血清,33,neg,凝集素,凝集,联测,NOIP2023,红细胞
From: https://www.cnblogs.com/2020fengziyang/p/17813871.html