首页 > 其他分享 >NOIP2023模拟12联测33

NOIP2023模拟12联测33

时间:2023-11-06 22:14:59浏览次数:35  
标签:12 血清 33 neg 凝集素 凝集 联测 NOIP2023 红细胞

NOIP2023模拟12联测33 D. 滈葕

目录

题目大意

231101_5PtkSBXNaX.png (654×896) (hszxoj.com)

思路

放一段题解的材料

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

相关文章

  • 【题解】HNOI2012 - 集合选数
    HNOI2012-集合选数https://www.luogu.com.cn/problem/P3226不算难的非显然状压dp。首先根据限制条件建图,\((x,2x),(x,3x)\)连边,表示边上相邻两个点不能同时选,然后一组独立集就是一个可行的集合。发现画出来的图是若干个部分网格图,每个连通块最小的点都是与\(6\)互质的数......
  • NOIP2023模拟12联测33 B. 游戏
    NOIP2023模拟12联测33B.游戏目录NOIP2023模拟12联测33B.游戏题目大意思路code题目大意期望题思路二分答案\(mid\),我们只关注学生是否能够使得被抓的人数\(\lemid\)那我们就只关心\(a>mid\)的房间就行了。设学生有\(p\)的概率进入第\(i\)个房间,那么老是去......
  • NOIP2023模拟12联测33 A. 构造
    NOIP2023模拟12联测33A.构造题目大意构造题思路想一种构造方法,使得\(y\)能够凑成尽可能多的答案第一行\(xyry\cdotsr\)第二行\(ryxy\cdotsx\)第三行\(xyry\cdotsr\)把最后一列空出来。此时有\(2202\)个答案如果\(n<2202\)贪心从后往前把\(y\)变成......
  • 【多校联考NOIP#12】比赛复盘
    A.星穹铁道读完题面就想到了\(O(n^2)\)的暴力。很好想,但是只有40分。观察到\(z_i=\pm1\),然而即便如此,我也没有得到有用的性质。(正解是用到这个性质的)然后我就暴力写了。正解的性质“最终在一个区间L,R内,初始也一定在一个连续段内”赛事没有想到。同时题解用了逆向思维,对......
  • Linux p12 查找指令
    搜索查找指令find指令find指令将从指定目录向下递归的遍历其各个子目录,将满足条件的文件或者目录显示在终端。基本语法find[搜索范围(指定目录)][选项]选项说明选项功能-name<查询方式>按照指定的文件名查找模式查找文件-user<用户名>查找属于指定用户名......
  • 文心一言 VS 讯飞星火 VS chatgpt (129)-- 算法导论11.1 4题
    四、用go语言,我们希望在一个非常大的数组上,通过利用直接寻址的方式来实现一个字典。开始时该数组中可能包含一些无用信息,但要对整个数组进行初始化是不太实际的,因为该数组的规模太大。请给出在大数组上实现直接寻址字典的方案。每个存储对象占用O(1)空间;SEARCH、INSERT和DELETE操......
  • NOIP 模拟12(NOIP A层联测25)
    100+100+30+100,T4自己写了Check最后一分钟发现Check锅了,赌了一发替换了部分分,赢!A.构造默认\(n\geq3,n\in\{2x+1,x\inN\},m\geq4\)。考虑构造rrrrr---yyyyy---xxxxx---yyyyy---rrrrr---yyyyy---xxxxx-----------这样有\(\dfrac{n-1}{2}\times(3m-4)\)个......
  • 文心一言 VS 讯飞星火 VS chatgpt (129)-- 算法导论11.1 4题
    四、用go语言,我们希望在一个非常大的数组上,通过利用直接寻址的方式来实现一个字典。开始时该数组中可能包含一些无用信息,但要对整个数组进行初始化是不太实际的,因为该数组的规模太大。请给出在大数组上实现直接寻址字典的方案。每个存储对象占用O(1)空间;SEARCH、INSERT和DELETE操......
  • SFTP无法连接 Connection closed by server with exitcode 127
    命令:Pass:************状态:Connectedto66.77.88.99错误:Connectionclosedbyserverwithexitcode127错误:无法连接到服务器 解决方法:vi/etc/ssh/sshd_config    其中:“Subsystemsftp/usr/libexec/sftp-server” 将其修改为正确的sftp-server路径Subsystem......
  • Oracle imp 导入数据出现 ORA-12560
    错误如下:D:\software\xfwebdb2015-05-11\autobackup>impImport:Release10.2.0.1.0-Productionon星期三5月1319:36:102015Copyright(c)1982,2005,Oracle. Allrightsreserved.用户名:zfzb口令:IMP-00058:遇到ORACLE错误12560ORA-12560:TNS:协议适配器错误IM......