滕州手机网站建设,响应式网站开发原则,购物网站建设思路,交通银行网站开发NOIP2023模拟12联测33 D. 滈葕 文章目录 NOIP2023模拟12联测33 D. 滈葕题目大意思路code 题目大意 思路
放一段题解的材料 ABO 血型系统是血型系统的一种#xff0c;把血液分为 A,B,AB,O 四种血型。血液由红细胞和血清等组成#xff0c;红细胞表面 有凝集原#xff0c;血清…NOIP2023模拟12联测33 D. 滈葕 文章目录 NOIP2023模拟12联测33 D. 滈葕题目大意思路code 题目大意 思路
放一段题解的材料 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 ) (u , v , w) (u,v,w)
若 w 0 w 0 w0 则KaTeX parse error: Undefined control sequence: \and at position 10: \neg(a_u \̲a̲n̲d̲ ̲a_v) \and \neg …
若 w 1 w 1 w1 则KaTeX parse error: Undefined control sequence: \and at position 6: (a_u \̲a̲n̲d̲ ̲\neg a_v) \or (…
可以用 2 − S A T 2-SAT 2−SAT 来处理
编号为 a i , i ¬ a i i n b i , i n ∗ 2 ¬ b i , i n ∗ 3 a_i , i \newline \neg a_i i n \newline b_i , i n *2 \newline \neg b_i , i n *3 ai,i¬aiinbi,in∗2¬bi,in∗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];
stackint 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;
}