CF1608D Dominoes 题解
CF1608D Dominoes 题解 题目链接:Dominoes 题意: 有 \(n(1 \le n \le 10^5)\) 个多米诺骨牌,每个骨牌由左右两个方格组成。有的方格已经被涂上了白色(W)或者黑色(B),剩下的方格(?)还没有被涂色。你需要给所有未涂色的方格涂上黑色或者白色。 一种涂色方案被认为是合法的,当且仅当存在一种排列骨牌方案使得任意一块牌的右面不同于下一块的左面。特殊地,最后一个骨牌的下一块是第一个骨牌。值得注意的是不能旋转它们,也就是不能交换左右方格的颜色。 两种涂色方案被认为是不同的,当且仅当存在一个方格在一个方案中被涂白在另一个方案中被涂黑。形如 BW WB 和 WB BW 的两个方案被认为是不同的方案。(同时他们都是非法的)。 求方案数对 \(998244353\) 取模的结果。 输入:\(n\) 行字符串。输出:答案 搬一张图 一般情况: 至少「一个 \(\mathtt{BB}\) 和一个 \(\mathtt{WW}\) 」,剩下的保证「 \(\mathtt{W}\) 个数等于 \(\mathtt{B}\) 个数」即可。 设有 \(a...
CF1540B Tree Array 题解
CF1540B Tree Array 题解 题目链接:Tree Array 题意: 给定一棵 \(n\) 个节点的树。 对于这棵树,我们通过下列方法来生成一个序列: 等概率选择这 \(n\) 个节点中的一个节点,并对这个节点打上标记(初始时没有节点被打上标记) 在所有没被打上标记且与至少一个打上标记的节点相连的节点中等概率选择一个节点并对这个节点打上标记 重复步骤 2 直到所有节点都被打上标记,此时生成的序列就是所有节点编号按照节点被打上标记的时间排序后的形成的序列。 求生成序列的期望逆序对数对 \(10^9+7\) 取模后的值。 输入:树;输出:答案 数据范围: \(2\leq n\leq200\) ,保证给出的是棵树 首先可以发现,这个标记的过程和第一个点息息相关 考虑枚举第一个被标记的点,然后把它提成根节点。 那么现在所有的点对 是祖先关系的,一定会产生贡献 \(0/1\) 的贡献。 不是祖先关系的,当他们的 LCA 被加入后,接下来的任何标记都可以解释为: 两个栈, \(p\) 概率弹第一个栈栈顶,\(p\) 概率弹第二个栈栈顶,\(1-2p\) 概率啥...
洛谷P5921 [POI1999] 原始生物 题解
洛谷P5921 [POI1999] 原始生物 题解 题目链接:P5921 [POI1999] 原始生物 题意: 原始生物的遗传密码是一个自然数的序列 \(K=(a_1,...,a_n)\)。 原始生物的特征是指在遗传密码中连续出现的数对 \((l,r)\),即存在自然数 \(i\) 使得 \(l=a_i\) 且 \(r=a_{i+1}\)。 在原始生物的遗传密码中不存在 \((p,p)\) 形式的特征。 请设计一个程序: 读入一系列的特征。 计算包含这些特征的最短的遗传密码。 将结果输出. 输入格式: 第一行是一个整数 \(n\) ,表示特征的总数。 在接下来的 \(n\) 行里,每行都是一对由空格分隔的自然数 \(l\) 和 \(r\)。 数对 \((l,r)\) 是原始生物的特征之一。 输入文件中的特征可能会有重复,请过滤掉。 输出格式: 唯一一行应该包含一个整数,为包含了所有特征的遗传密码的最小长度。 数据范围: \(1\le n\le 10^6,~1\le l,r\le1000\) 。 题目要求一个序列,使得每条边都在序列中出现过。 考虑将现在图中所有的弱连通分...
洛谷P4001 [ICPC-Beijing 2006] 狼抓兔子 题解
洛谷P4001 [ICPC-Beijing 2006] 狼抓兔子 题解 题目链接:P4001 [ICPC-Beijing 2006] 狼抓兔子 题意: 现在小朋友们最喜欢的”喜羊羊与灰太狼”。话说灰太狼抓羊不到,但抓兔子还是比较在行的,而且现在的兔子还比较笨,它们只有两个窝,现在你做为狼王,面对下面这样一个网格的地形: 左上角点为 \((1,1)\),右下角点为 \((N,M)\)(上图中 \(N=3\),\(M=4\))。有以下三种类型的道路: \((x,y)\rightleftharpoons(x+1,y)\) \((x,y)\rightleftharpoons(x,y+1)\) \((x,y)\rightleftharpoons(x+1,y+1)\) 道路上的权值表示这条路上最多能够通过的兔子数,道路是无向的。左上角和右下角为兔子的两个窝,开始时所有的兔子都聚集在左上角 \((1,1)\) 的窝里,现在它们要跑到右下角 \((N,M)\) 的窝中去,狼王开始伏击这些兔子。当然为了保险起见,如果一条道路上最多通过的兔子数为 \(K\),狼王需要安排同样数量的 \(K\...
洛谷P5405 [CTS2019] 氪金手游 题解
洛谷P5405 [CTS2019] 氪金手游 题解 题目链接:P5405 [CTS2019] 氪金手游 题目描述 qry 同学是一个喜欢氪金手游的男孩子。 他最近迷上了一个新游戏,游戏的内容就是不断地抽卡。现在已知: 卡池里总共有 \(N\) 种卡,第 \(i\) 种卡有一个权值 \(W_i\),qry同学不知道 \(W_i\) 具体的值是什么。但是他通过和网友交流,他了解到 \(W_i\) 服从一个分布。 具体地,对每个 \(i\),qry了解到三个参数 \(p_{i,1},p_{i,2},p_{i,3}\),\(W_i\) 将会以 \(p_{i,j}\) 的概率取值为 \(j\),保证 \(p_{i,1}+p_{i,2}+p_{i,3}=1\)。 qry 开始玩游戏了,他每次会氪一元钱来抽一张卡,其中抽到卡 \(i\) 的概率为:\(\frac{W_i}{\sum_j W_j}\) qry 会不停地抽卡,直到他手里集齐了全部 \(N\) 种卡。 抽卡结束之后,服务器记录下来了 qry 第一次得到每张卡的时间 \(T_i\)。游戏公司在这里设置了一个彩蛋:公司准备了 \...
【生物】多倍体是否均可育?
【生物】多倍体是否均可育? 答案:不一定,但大多数偶倍数异源多倍体是可育的。 显然,奇倍数多倍体联会紊乱,高度不育。而偶倍数多倍体可不一定正常。 以同源四倍体为例,减数分裂时4条同源染色体可能结合成一个四价体 也可能是一个三价体+一个单价体、或者两个二价体+一个二价体和两个单价体 总之上面这几种都会导致最后的生殖细胞有异常的染色体数,导致不育。 因此偶倍数同源多倍体也有不同程度的不育性 相反,大多数偶倍数异源多倍体是可育的。 例如,六倍体小麦细胞中含拟斯卑尔脱山羊草、一粒小麦和方穗山羊草的各两个染色体组 减数分裂时同源染色体两两联会、分离,表现出与二倍体相同的性状遗传规律。
【生物】基因突变是原核生物唯一的变异来源吗?
【生物】基因突变是原核生物唯一的变异来源吗? 答案:不准确,原核生物也可以基因重组。 对于原核生物来说,目前高中教材只提到有拟核,并无染色体,似乎只有基因突变能导致变异。 事实上显然不是。参考 R型菌是如何转化为S型菌的?可以反向转化吗? ,这就是一种基因重组。 此外,“接合”和“转导”也可以通过实现细菌DNA序列的转移而产生基因重组。
【生物】紫外线诱发基因突变的机理是什么?
【生物】紫外线诱发基因突变的机理是什么? 紫外线(UV)是太阳光中可以使人晒黑和灼伤的成分 其能量比电离辐射小得多,它不能引起原子激发出电子,因此不会产生自由基。 能够吸收紫外线的分子是那些有机环状化合物,当它们吸收紫外线后,外层电子变得活跃起来。 DNA的嘧啶碱基(胞嘧啶C和胸腺嘧啶T)对紫外线有很强的吸收作用。 如果相邻的两个碱基恰好都是嘧啶碱基的话,当他们吸收紫外线能量后, 彼此之间会形成共价键,形成嘧啶二聚体(pyrimidine dimer,简称PD) 大多数情况下,细胞内的紫外线辐射修复系统可以将链接嘧啶二聚体的共价键打断, 或者将嘧啶二聚体从 DNA 分子链上整个切除,再利用另一条完整的互补单链把缺口补上。 偶尔也会发生嘧啶二聚体切除处未被处理的情况。 这时 DNA 聚合酶无法复制形成二聚体的部分,就跳过该部分继续前行,把填补缺口的任务留下 不过,以后的填补经常发生错误,因此可能在缺口处产生基因突变。 一些未被修补的嘧啶二聚体由于本身是单链结构,可能阻碍整个 DNA 分子的复制进程,这对细胞来说是致命的。
【生物】杂合子(Aa)中隐性基因是否表达?
【生物】杂合子(Aa)中隐性基因是否表达? 在部分教辅中,认为是 A 基因的存在抑制了 a 基因的表达,这是不准确的。 一般情况下,a 基因在 aa 个体和 Aa 个体中的表达情况是是一致的。 那么为什么隐性性状没有表现出来呢? 因为 A 基因一般是控制合成有功能的蛋白质,而 a 基因合成的蛋白质不正常,或者完全不能合成。 于是,在杂合子中,如果 A 基因的产物足以维持生命活动的需要,则 a 基因的效应就被掩盖了。 例如,豌豆种子中的圆粒(A)对皱粒(a)是显性的。 A 是正常的淀粉分支酶同工酶 I 基因,a 则是在 A 基因中插入了一个 0.8kb 的片段, 导致淀粉分支酶同工酶 I 失活,继而引起淀粉合成量下降,游离蔗糖的积累增加,种子成熟时失水而皱缩。 而 Aa 种子不皱缩,是因为 Aa 个体中正常的酶足以催化足够的淀粉合成,是种子有效的保留水分,维持圆粒。 其他的例子都差不多,懒得写了。
洛谷P2634 [国家集训队] 聪聪可可 题解
洛谷P2634 [国家集训队] 聪聪可可 题解 题目链接:P2634 [国家集训队] 聪聪可可 题意: 聪聪和可可是兄弟俩,他们俩经常为了一些琐事打起来,例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑(可是他们家只有一台电脑)……遇到这种问题,一般情况下石头剪刀布就好了,可是他们已经玩儿腻了这种低智商的游戏。 他们的爸爸快被他们的争吵烦死了,所以他发明了一个新游戏:由爸爸在纸上画 \(n\) 个“点”,并用 \(n-1\) 条“边”把这 \(n\) 个“点”恰好连通(其实这就是一棵树)。并且每条“边”上都有一个数。接下来由聪聪和可可分别随机选一个点(当然他们选点时是看不到这棵树的),如果两个点之间所有边上数的和加起来恰好是 \(3\) 的倍数,则判聪聪赢,否则可可赢。 聪聪非常爱思考问题,在每次游戏后都会仔细研究这棵树,希望知道对于这张图自己的获胜概率是多少。现请你帮忙求出这个值以验证聪聪的答案是否正确。 输入格式: 输入的第 \(1\) 行包含 \(1\) 个正整数 \(n\)。后面 \(n-1\) 行,每行 \(3\) 个整数 \(x,y,w\),表示 \(x\...
【生物】减数分裂 流程图
【生物】减数分裂 流程图 下图的从左上角开始,按着箭头方向看。 标题:减数分裂 流程图。 下图用于做题时判断题目所给的细胞处于哪个阶段。
【生物】基因互作 & 致死效应 总结
【生物】基因互作 & 致死效应 总结 最为常见和令人熟知的就是 AaBb 自交,后代产生 \(9:3:3:1\) 表现型 下图总结了其他可能的结果,包括隐形纯合致死、显性纯合致死等情况。


![洛谷P5921 [POI1999] 原始生物 题解](/qwq/img/p168.webp)
![洛谷P4001 [ICPC-Beijing 2006] 狼抓兔子 题解](/qwq/img/p26.webp)
![洛谷P5405 [CTS2019] 氪金手游 题解](/qwq/img/p19.webp)




![洛谷P2634 [国家集训队] 聪聪可可 题解](/qwq/img/p57.webp)


![洛谷B3869 [GESP202309 四级] 进制转换 题解](/qwq/img/p184.webp)

![洛谷B3883 [信息与未来 2015] 求回文数(加强版) & B3882 题解](/qwq/img/p214.webp)
![洛谷B3879 [信息与未来 2015] 连续数的和(加强版) & B3878 题解](/qwq/img/p230.webp)