Q779’s Blog

洛谷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] 狼抓兔子 题意： 现在小朋友们最喜欢的”喜羊羊与灰太狼”。话说灰太狼抓羊不到，但抓兔子还是比较在行的，而且现在的兔子还比较笨，它们只有两个窝，现在你做为狼王，面对下面这样一个网格的地形： 左上角点为 \((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] 氪金手游 题意： 小刘同学是一个喜欢氪金手游的男孩子。 他最近迷上了一个新游戏，游戏的内容就是不断地抽卡。现在已知： - 卡池里总共有 \(N\) 种卡，第 \(i\) 种卡有一个权值 \(W_i\)，小刘同学不知道 \(W_i\) 具体的值是什么。但是他通过和网友交流，他了解到 \(W_i\) 服从一个分布。 - 具体地，对每个 \(i\)，小刘了解到三个参数 \(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\)。 小刘开始玩游戏了，他每次会氪一元钱来抽一张卡，其中抽到卡 \(i\) 的概率为：\(\frac{W_i}{\sum_j W_j}\) 小刘会不停地抽卡，直到他手里集齐了全部 \(N\)​ 种卡。 抽卡结束之后，服务器记录下来了小刘第一次得到每张卡的时间 \(T_i\)。游戏公司在这里设置了一个彩蛋：公司准备了 \(N-1\) 个二元...

【生物】多倍体是否均可育？ 答案：不一定，但大多数偶倍数异源多倍体是可育的。 显然，奇倍数多倍体联会紊乱，高度不育。而偶倍数多倍体可不一定正常。 以同源四倍体为例，减数分裂时4条同源染色体可能结合成一个四价体 也可能是一个三价体+一个单价体、或者两个二价体+一个二价体和两个单价体 总之上面这几种都会导致最后的生殖细胞有异常的染色体数，导致不育。 因此偶倍数同源多倍体也有不同程度的不育性 相反，大多数偶倍数异源多倍体是可育的。 例如，六倍体小麦细胞中含拟斯卑尔脱山羊草、一粒小麦和方穗山羊草的各两个染色体组 减数分裂时同源染色体两两联会、分离，表现出与二倍体相同的性状遗传规律。

【生物】基因突变是原核生物唯一的变异来源吗？ 答案：不准确，原核生物也可以基因重组。 对于原核生物来说，目前高中教材只提到有拟核，并无染色体，似乎只有基因突变能导致变异。 事实上显然不是。参考 R型菌是如何转化为S型菌的？可以反向转化吗？ ，这就是一种基因重组。 此外，“接合”和“转导”也可以通过实现细菌DNA序列的转移而产生基因重组。

【生物】紫外线诱发基因突变的机理是什么？ 紫外线（UV）是太阳光中可以使人晒黑和灼伤的成分 其能量比电离辐射小得多，它不能引起原子激发出电子，因此不会产生自由基。 能够吸收紫外线的分子是那些有机环状化合物，当它们吸收紫外线后，外层电子变得活跃起来。 DNA的嘧啶碱基（胞嘧啶C和胸腺嘧啶T）对紫外线有很强的吸收作用。 如果相邻的两个碱基恰好都是嘧啶碱基的话，当他们吸收紫外线能量后， 彼此之间会形成共价键，形成嘧啶二聚体（pyrimidine dimer，简称PD） 大多数情况下，细胞内的紫外线辐射修复系统可以将链接嘧啶二聚体的共价键打断， 或者将嘧啶二聚体从 DNA 分子链上整个切除，再利用另一条完整的互补单链把缺口补上。 偶尔也会发生嘧啶二聚体切除处未被处理的情况。 这时 DNA 聚合酶无法复制形成二聚体的部分，就跳过该部分继续前行，把填补缺口的任务留下 不过，以后的填补经常发生错误，因此可能在缺口处产生基因突变。 一些未被修补的嘧啶二聚体由于本身是单链结构，可能阻碍整个 DNA 分子的复制进程，这对细胞来说是致命的。

【生物】杂合子（Aa）中隐性基因是否表达？ 在部分教辅中，认为是 A 基因的存在抑制了 a 基因的表达，这是不准确的。 一般情况下，a 基因在 aa 个体和 Aa 个体中的表达情况是是一致的。 那么为什么隐性性状没有表现出来呢？ 因为 A 基因一般是控制合成有功能的蛋白质，而 a 基因合成的蛋白质不正常，或者完全不能合成。 于是，在杂合子中，如果 A 基因的产物足以维持生命活动的需要，则 a 基因的效应就被掩盖了。 例如，豌豆种子中的圆粒（A）对皱粒（a）是显性的。 A 是正常的淀粉分支酶同工酶 I 基因，a 则是在 A 基因中插入了一个 0.8kb 的片段， 导致淀粉分支酶同工酶 I 失活，继而引起淀粉合成量下降，游离蔗糖的积累增加，种子成熟时失水而皱缩。 而 Aa 种子不皱缩，是因为 Aa 个体中正常的酶足以催化足够的淀粉合成，是种子有效的保留水分，维持圆粒。 其他的例子都差不多，懒得写了。

洛谷P2634 [国家集训队] 聪聪可可 题解 题目链接：P2634 [国家集训队] 聪聪可可 题意： 聪聪和可可是兄弟俩，他们俩经常为了一些琐事打起来，例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑（可是他们家只有一台电脑）……遇到这种问题，一般情况下石头剪刀布就好了，可是他们已经玩儿腻了这种低智商的游戏。 他们的爸爸快被他们的争吵烦死了，所以他发明了一个新游戏：由爸爸在纸上画 \(n\) 个“点”，并用 \(n-1\) 条“边”把这 \(n\) 个“点”恰好连通（其实这就是一棵树）。并且每条“边”上都有一个数。接下来由聪聪和可可分别随机选一个点（当然他们选点时是看不到这棵树的），如果两个点之间所有边上数的和加起来恰好是 \(3\) 的倍数，则判聪聪赢，否则可可赢。 聪聪非常爱思考问题，在每次游戏后都会仔细研究这棵树，希望知道对于这张图自己的获胜概率是多少。现请你帮忙求出这个值以验证聪聪的答案是否正确。 输入格式： 输入的第 \(1\) 行包含 \(1\) 个正整数 \(n\)。后面 \(n-1\) 行，每行 \(3\) 个整数 \(x,y,w\)，表示 \(x\...

【生物】减数分裂 流程图 下图的从左上角开始，按着箭头方向看。 标题：减数分裂 流程图。 下图用于做题时判断题目所给的细胞处于哪个阶段。

【生物】基因互作 & 致死效应 总结 最为常见和令人熟知的就是 AaBb 自交，后代产生 \(9:3:3:1\) 表现型 下图总结了其他可能的结果，包括隐形纯合致死、显性纯合致死等情况。

洛谷P4178 Tree 题解 题目链接：P4178 Tree 题意： 给定一棵 \(n\) 个节点的树，每条边有边权，求出树上两点距离小于等于 \(k\) 的点对数量。 输入格式： 第一行输入一个整数 \(n\)，表示节点个数。 第二行到第 \(n\) 行每行输入三个整数 \(u,v,w\) ，表示 \(u\) 与 \(v\) 有一条边，边权是 \(w\)。 第 \(n+1\) 行一个整数 \(k\) 。 输出格式： 一行一个整数，表示答案。 数据范围： \(1\leq n\leq 4\times 10^4,~1\leq u,v\leq n,~0\leq w\leq 10^3,~0\leq k\leq 2\times 10^4\)。 这个题和 P3806 【模板】点分治 1 的差别是，询问只有一个，且问的是小于等于 \(k\) 的。 是不是直接把已经知道的距离的值排个序，然后用两个指针跑一遍，就能得到答案了呢？ 并不是，因为我们会统计到一些不合法的路径，比如下图 那么解决办法其实很简单，我们在枚举重心的儿子时，把重复的那一段，即 \(2\times w(u,v)\) 加上...

洛谷P3806 【模板】点分治 1 题解 题目链接：P3806 【模板】点分治 1 题意： 给定一棵有 \(n\) 个点的树，询问树上距离为 \(k\) 的点对是否存在。 输入格式： 第一行两个数 \(n,m\)。 第 \(2\) 到第 \(n\) 行，每行三个整数 \(u, v, w\)，代表树上存在一条连接 \(u\) 和 \(v\) 边权为 \(w\) 的路径。 接下来 \(m\) 行，每行一个整数 \(k\)，代表一次询问。 输出格式： 对于每次询问输出一行一个字符串代表答案，存在输出 AYE，否则输出 NAY。 数据范围： 保证 \(1 \leq n\leq 10^4\)，\(1 \leq m\leq 100\)，\(1 \leq k \leq 10^7\)，\(1 \leq u, v \leq n\)，\(1 \leq w \leq 10^4\)。 本题是点分治的模板题。点分治的算法思想很简单。 考虑点 \(u\) 作为根节点时，任意两个点产生的路径可以被分为：经过 \(u\) 的、不经过 \(u\) 的。 前者有 \(d(i,j) =d(i,u) + d(u,j...