Q779’s Blog

洛谷P4206 [NOI2005] 聪聪与可可 题解 题目链接：P4206 [NOI2005] 聪聪与可可 题意： 在一个魔法森林里，住着一只聪明的小猫聪聪和一只可爱的小老鼠可可。虽然灰姑娘非常喜欢她们俩，但是，聪聪终究是一只猫，而可可终究是一只老鼠，同样不变的是，聪聪成天想着要吃掉可可。 一天，聪聪意外得到了一台非常有用的机器，据说是叫 GPS，对可可能准确的定位。有了这台机器，聪聪要吃可可就易如反掌了。于是，聪聪准备马上出发，去找可可。而可怜的可可还不知道大难即将临头，仍在森林里无忧无虑的玩耍。小兔子乖乖听到这件事，马上向灰姑娘报告。灰姑娘决定尽快阻止聪聪，拯救可可，可她不知道还有没有足够的时间。 整个森林可以认为是一个无向图，图中有 \(N\) 个美丽的景点，景点从 \(1\) 至 \(N\) 编号。小动物们都只在景点休息、玩耍。在景点之间有一些路连接。 当聪聪得到 GPS 时，可可正在景点 \(M\)（\(M \le N\)）处。以后的每个时间单位，可可都会选择去相邻的景点（可能有多个）中的一个或停留在原景点不动。而去这些地方所发生的概率是相等的。假设有 \(P\) 个...

CF148D Bag of mice 题解 题目链接：CF148D Bag of mice 题意： 龙和公主在争论新年夜应该做什么。龙建议飞到山上观看在月光下跳舞的仙女，而公主认为他们应该早点睡觉。他们急于达成一个友好的协议，所以决定把这交给运气。 他们轮流从一个袋子里抽取老鼠，这个袋子里最初包含 \(w\) 只白鼠和 \(b\) 只黑鼠。第一个抽到白鼠的人获胜。在龙每次抽完老鼠后，袋子里的其余老鼠都会惊慌失措，其中一只会自己跳出袋子（公主抽老鼠时很小心，不会吓到其他老鼠）。公主先抽。公主获胜的概率是多少？ 如果袋子里没有老鼠了，并且没有人抽到白鼠，则龙获胜。自己跳出袋子的老鼠不算作被抽出（不决定胜负）。一旦老鼠离开袋子，它就不会再返回。每只老鼠被抽出的概率是相同的，每只老鼠跳出袋子的概率也是相同的。 输入格式： 唯一一行输入数据包含两个整数 \(w\) 和 \(b\)（\(0 \leq w, b \leq 1000\)）。 输出格式： 输出公主获胜的概率。如果答案的绝对误差或相对误差不超过 \(10^{-9}\)，则认为答案是正确的。 不会翻译可以不翻译，有的人真是连 Ch...

UVA1118 Binary Stirling Numbers 题解 题目链接：Binary Stirling Numbers 或者 SP106 题意： The Stirling number of the second kind \(S(n, m)\) represents the number of ways to partition a set of \(n\) things into \(m\)​ nonempty subsets. For example, there are seven ways to split a four-element set into two parts: \[ \begin{gathered} \{1,2,3\} \cup\{4\},\{1,2,4\} \cup\{3\},\{1,3,4\} \cup\{2\},\{2,3,4\} \cup\{1\} \\ \{1,2\} \cup\{3,4\},\{1,3\} \cup\{2,4\},\{1,4\} \cup\{2,3\} . \end{gathered} \] We can compu...

CF123E Maze 题解 题目链接：Maze 题意： 一棵 \(n\) 个点的树，起点和终点随机选取（概率给定）。 运行如下程序， \(V(x)\) 是与 \(x\) 相邻的顶点列表，最初 \(\mathrm{flag}\) 数组为 \(\verb!false!\)，DFS 的 参数是起点 你要求 \(\mathrm{count}\) 的期望值。 DFS(x) if x == exit vertex then finish search flag[x] <- TRUE random shuffle the vertices' order in V(x) // here all permutations have equal probability to be chosen for i <- 1 to length[V] do if flag[V[i]] = FALSE then count++; ...

【生物】真核生物基因与原核生物基因有何不同？ 与原核生物相比，真核生物基因在结构上的最大特点是： 编码蛋白质的序列（外显子）被编码器中的非编码序列（内含子）间隔成不连续的片段。 而原核生物的基因编码区是连续的。 内含子存在的意义是通过选择性剪接（alternative splicing）实现了由相同的基因控制不同蛋白质的合成 也有助于基因重组，加快进化过程中新基因的形成。

【生物】病毒增殖过程遗传物质、蛋白质如何合成？ 根据病毒所含核酸的性质和状态不同，可将病毒分为以下六类 DNA双链病毒：此类病毒的DNA即可以双链为模板复制出子代病毒DNA；又可以-DNA（-DNA或-RNA表示其核苷酸序列与mRNA互补）链为模板转录成mRNA，进而翻译称病毒蛋白质，如T4噬菌体、乙肝病毒等。 单链+DNA病毒：（+DNA或+RNA是指其核苷酸序列与mRNA序列一致）此类病毒先由+DNA为模板合成-DNA，组成双链±DNA，通过复制合成大量子代±DNA。然后再以新合成的-DNA为模板转录mRNA，翻译蛋白质，如 \(\small \varphi\times174\)​ 病毒等 双链RNA病毒：以双链RNA为模板进行不对称转录，先合成正链RNA（+RNA），再以+RNA为模板合成-RNA，形成双链RNA分子；以+RNA为模板翻译出病毒复制酶及其他蛋白质；蛋白质与子代双链RNA组装成新的病毒颗粒，如呼肠孤病毒。 单链+RNA病毒：该类病毒的+RNA可直接作为mRNA进行翻译，合成蛋白质。复制方式是以该+RNA为模板，复制成-RNA，然后再以-RNA为模板合成...

CF453A Little Pony and Expected Maximum 题解 题目链接：Little Pony and Expected Maximum 题意： 暮暮刚刚在和她的朋友——AJ（苹果杰克）、FS（小蝶）、RD（云宝黛西）玩Ludo游戏。但是她马品没攒够总是输。回到城堡过后，她对游戏用的骰子产生了兴趣。 这个骰子有 \(m\) 面：骰子的第一面有一个点，第二面有两个点，以此类推，第 \(m\) 面含有 \(m\) 点。暮暮确信的是，当掷骰子时，每一面都有 \(\frac{1}{m}\) 的可能性出现，并且每次投掷的概率都是都是独立的。请你帮助她计算掷N次骰子后每次得到的点数中最大值的期望。 输入格式： 一行两个整数 \(m\) 和 \(n (1 \le m, n \le 10^5)\) 。 输出格式： 输出一行一个实数，与答案误差不大于\(10^{-4}\) 扔 \(n\) 次，最大值是 \(k\) 的方案数有 \(k^n - (k-1)^n\) 种，每种方案对答案的贡献是 \(k\) 。 因此 \[ \begin{aligned} \mathrm{Ans...

洛谷P3412 仓鼠找sugar II 题解 题目链接：P3412 仓鼠找sugar II 题意： 小仓鼠和他的基（mei）友（zi）sugar 住在地下洞穴中，每个节点的编号为 \(1\sim n\) 间的一个整数。地下洞穴是一个树形结构（两个洞穴间距离为 \(1\)）。这一天小仓鼠打算从从他的卧室 \(a\)（是任意的）走到他的基友卧室 \(b\)（还是任意的）（注意，\(a\) 有可能等于 \(b\)）。然而小仓鼠学 OI 学傻了，不知道怎么怎么样才能用最短的路程走到目的地，于是他只能随便乱走。当他在一个节点时，会等概率走到这个点的母亲或者所有孩子节点（例如这个节点有一个母亲节点和两个子节点，那么下一步走到这 \(3\) 个节点的概率都是 \(\dfrac{1}{3}\)），一旦走到了他基友的卧室，就会停下。 现在小仓鼠希望知道，他走到目的地时，走的步数的期望。这个期望本来是一个有理数，但是为了避免误差，我们要求输出这个有理数对 \(998,422,353\) 取模的结果。 形式化地说，可以证明答案可以被表示为既约分数 \(\dfrac{y}{x}\)，其中 \(x\no...

洛谷P6057 [加油武汉] 七步洗手法 题解 题目链接：P6057 [加油武汉] 七步洗手法 题意： 给定一张含有 \(n\) 个点的无向完全图，其中 \(m\) 条边是白边，其余是黑边。 现在需要你求出同色的三元环（或者说，三角形）的个数。 输入格式： 第一行整数 \(n,m\)，意义如题。 剩下的 \(m\) 行每行两个整数 \(u,v\)，代表白边的两个端点。保证给出的白边没有重边和自环。 输出格式： 一行一个整数，为答案。 数据范围： 满足 \(1 \leq n \leq 10^5,1 \leq m \leq 3\times 10^5\)。 正难则反，用三角形的总个数减去异色的个数。 因为一条边只会影响两个点，所以我们可以统计所有异色角的个数，除以 \(2\) 就是异色三角形的个数 时间复杂度 \(\mathcal{O}(n+m)\) 代码： #include <bits/stdc++.h> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f void up(int...

【化学】同分异构体 总结 同分异构物（英语：Isomer）是拥有相同分子式，但结构式却不相同的多种分子。 其彼此间的化学性质并不相同，除非它们拥有相同的官能团（functional groups）。 化学中常见的两种主要的种类为结构异构以及立体异构。 思维导图：

【生物】为何S型菌的DNA经高温处理后仍然具有遗传效应？ 众所周知，蛋白质经高温处理后空间结构会被破坏而变性失活，该过程不可逆。 高温能断裂DNA双链间的氢键使其解旋为单链，但不破坏DNA的一级结构，且这一过程是可逆过程。 当温度降低时，碱基可以互补配对形成氢键，回复原有的双链结构。

【生物】S型菌的多糖类荚膜是否能直接致病？ 答案：不能。 荚膜是某些细菌的特殊结构，是位于细胞壁外一层厚度不定的透明胶状物质，主要由水、多糖或多肽组成。 荚膜主要有以下作用：防止细菌变干、吸附阳离子，防止噬菌体的侵袭，防止吞噬细胞的吞噬和消化。 S型菌的多糖类荚膜能够使S型菌抵抗吞噬细胞的吞噬和体液中杀菌物质的作用， 从而在小鼠体内存活并迅速繁殖而导致小鼠患病死亡。 R型菌没有多糖类荚膜，易被吞噬细胞和体液中的杀菌物质清楚，不会导致小鼠患病。 故S型菌的致病性并非直接由多糖类荚膜引起，而是由于其保护作用使S型菌在体内大量繁殖所致。