Q779’s Blog

【数学】常见几何体的表面积和体积公式 提示：本文全是小学数学。 一、表面积 & 侧面积 公式 直棱柱的侧面积 设直棱柱的底面周长为 \(C\) ，高为 \(h\) ，则 \[ S_\text{侧} = Ch \] 长方体的表面积 设长宽高分别为 \(a,b,c\) ，则 \[ S_\text{表}=2ab+2bc+2ac \] 正方体的表面积 设棱长为 \(a\) ，则 \[ S_\text{表}=6a^2 \] 正棱锥的侧面积 设斜高为 \(h^\prime\) （侧面图形上的高），底面周长为 \(C\) ，则 \[ S_\text{侧} = \dfrac{1}{2} Ch^\prime \] 正棱台的侧面积 设上底面的周长为 \(C_1\) ，下底面的周长为 \(C_2\) ，斜高为 \(h^\prime\) ，则 \[ S_\text{侧}=\dfrac{1}{2}(C_1+C_2)h^\prime \] 圆柱的底面积 设圆柱的底面半径为 \(r\) ，则 \[ S_\text{底}=\pi r^2 \] 圆柱的侧面积 设圆柱的底面半径为 \(r\) ，母线长为...

洛谷P3523 [POI2011] DYN-Dynamite 题解 题目链接：P3523 [POI2011] DYN-Dynamite 题意： 给定一棵 \(n\) 个节点的树，树上有若干个关键点。 现在要你选 \(m\) 个点，使得所有关键点到这 \(m\) 个点距离的最小值的最大值 \(K\) 最小。 输入格式： 第一行给出 \(n,m\) ，第二行给出每个点是否是关键点。 接下来 \(n-1\) 行，每行两个整数 \(u,v\) 表示 \(u,v\) 之间有一条边。 输出格式： 一行，即 \(K\) 的最小值。 数据范围： \(1 \le n,m \le 3\times 10^5\) 。 考虑二分 \(K\) ，问题转化为能否选 \(m\) 个点，使得这 \(m\) 个点与关键点的最小距离均不超过 \(K\) 。 可以发现放的点越多，这个最小距离越不可能超过 \(K\) 。 于是问题就转化为，选 \(k\) 个点，使得这 \(k\) 个点与关键点的最小距离均不超过 \(K\) ，最小化 \(k\) 。 不妨称点 \(u\) 覆盖了关键点 \(v\) ，当且仅当点 \(u...

SRY 基因（Y染色体性别决定区） SRY基因（sex-determining region of Y-chromosome，全称：Y染色体性别决定区）是人体Y染色体上的一段基因片段，该基因是决定男性睾丸发育的主要基因。该基因由 Sinclair 在1990年发现，位于Y染色体短臂上。 SRY基因是一个高度保守的单拷贝基因，它所编码的蛋白质是一种转录因子，它通过与特异的DNA序列结合，实现对其他受控基因的转录和表达的调控。这个过程中SRY基因起着开关作用，与人类性别决定密切相关，有人认为它就是性转换因子。在胚胎发育过程中，第一个月胚胎含有原始的卵巢组织和睾丸组织，以及两种生殖导管，但随着胚胎发育，两种性腺组织和导管中只有一套得到发育，另一套发生凋亡。有了性转换因子，原始性腺就向睾丸组织方向分化，最终发育成睾丸。否则，原始性腺将发育成卵巢。此后的性别及第二性征发育就依赖于雌、雄性激素的作用。 目前认为，SRY基因就是唯一一个性别决定基因。因此可以通过在血液、精液样本中寻找该基因片段，达到判断测试者性别的目的。具体的步骤是，先使用PCR技术扩增基因上某个片段，再利用凝胶电泳判断样本...

CF1098C Construct a tree 题解 题目链接：Construct a tree 题意： Misha 在雪地森林中漫步，他对树木如此着迷，以至于决定自己绘制一棵树！ Misha 想构造一棵有 \(n\) 个顶点的有根树，顶点从 \(1\) 到 \(n\) 编号，其中根的编号为 \(1\)。每个其他顶点都有一个父节点 \(p_i\)，且 \(i\) 是顶点 \(p_i\) 的子节点。顶点 \(u\) 属于顶点 \(v\) 的子树，当且仅当从 \(u\) 开始通过父节点（\(u\), \(p_{u}\), \(p_{p_{u}}\), …）可以到达 \(v\)。显然，\(v\) 属于它自己的子树，子树中的顶点数量称为子树的大小。Misha 只对每个顶点都属于顶点 1 的子树的树感兴趣。 下面是一个有 6 个顶点的树。顶点 2 的子树包含顶点 2、3、4、5。因此其子树的大小是 4。 树的分支系数定义为任意顶点的最大子节点数。例如，上述树的分支系数为 2。你的任务是构造一棵有 \(n\) 个顶点的树，使所有顶点的子树大小之和等于 \(s\)，并且分支系数尽可能小。...

洛谷P5666 [CSP-S2019] 树的重心 题解 题目链接：P5666 [CSP-S2019] 树的重心 题意： 小简单正在学习离散数学，今天的内容是图论基础，在课上他做了如下两条笔记： 一个大小为 \(n\) 的树由 \(n\) 个结点与 \(n - 1\) 条无向边构成，且满足任意两个结点间有且仅有一条简单路径。在树中删去一个结点及与它关联的边，树将分裂为若干个子树；而在树中删去一条边（保留关联结点，下同），树将分裂为恰好两个子树。 对于一个大小为 \(n\) 的树与任意一个树中结点 \(c\)，称 \(c\) 是该树的重心当且仅当在树中删去 \(c\) 及与它关联的边后，分裂出的所有子树的大小均不超过 \(\lfloor \frac{n}{2} \rfloor\)（其中 \(\lfloor x \rfloor\) 是下取整函数）。对于包含至少一个结点的树，它的重心只可能有 1 或 2 个。 课后老师给出了一个大小为 \(n\) 的树 \(S\)，树中结点从 \(1 \sim n\) 编号。小简单的课后作业是求出 \(S\) 单独删去每条边后，分裂出的两个子树的重...

洛谷P3488 [POI2009] LYZ-Ice Skates 题解 题目链接：P3488 [POI2009] LYZ-Ice Skates 题意： 滑冰俱乐部初始有 \([1,n]\) 号码溜冰鞋各 \(k\) 双，已知 \(x\) 号脚的人可以穿 \([x,x+d]\) 号码的鞋子。 现在有 \(m\) 次操作，每次两个数 \(r,x\)，表示来了 \(x\) 个 \(r\) 号脚的人，\(x\) 为负则表示离开。 在每次操作之后，你需要判断溜冰鞋是否足够。 输入格式： 第一行 \(4\) 个整数 \(n,m,k,d\)。 接下来 \(m\) 行，每行两个整数 \(r_i,x_i\)，代表一次操作。 输出格式： \(m\) 行，每行一个字符串，若此次操作后满足题意则输出 TAK，否则输出 NIE。 数据范围： \(n\le 2\times 10^5,m\le 5\times 10^5,k\le 10^9,1\le r_i\le n-d,-10^9\le x_i\le 10^9,0\le d<n\) 考虑将 \(x\) 鞋码的人和 \([x,x+d]\) 的鞋子连边...

洛谷P3599 Koishi Loves Construction 题解 题目链接：P3599 Koishi Loves Construction 题意 Koishi 决定走出幻想乡成为数学大师！ Flandre 听说她数学学的很好，就给 Koishi 出了这样一道构造题： Task1：试判断能否构造并构造一个长度为 \(n\) 的 \(1 \dots n\) 的排列，满足其 \(n\) 个前缀和在模 \(n\) 的意义下互不相同。 Task2：试判断能否构造并构造一个长度为 \(n\) 的 \(1 \dots n\) 的排列，满足其 \(n\) 个前缀积在模 \(n\) 的意义下互不相同。 按照套路，Koishi 假装自己根本不会做，就来找你帮忙辣！ 输入格式： 第一行两个整数 \(X\) 和 \(T\)，分别表示 Task 类型和测试点内的数据组数。 接下来 \(T\) 行，每行一个整数表示每组数据中的 \(n\)。 输出格式： 为了方便 SPJ 的编写，您需要遵从以下格式输出。 对于每组数据仅包含一行输出： 如果您认为当前数据不存在符合题意的构造，只需输出一个整数 \(...

CF1889C2 Doremy’s Drying Plan (Hard Version) 题解 题目链接：Doremy’s Drying Plan (Hard Version) 题意： 多组数据。有 \(n\) 个点和 \(m\) 条线段，你可以选择 \(k\) 条线段删除， 要求最大化未被线段覆盖的点的数量，输出最大值。 数据范围： \(1 \le T \le 10^4,~1 \le \sum n,\sum m \le 2\times 10^5,~2 \le k \le \min(10, m),~1\le l_i \le r_i \le n\) 。 设 \(f(i,x,y)\) 为前 \(i\) 条线段，删除了 \(x\) 条，没有删除的线段的右端点是 \(y\) 时，覆盖位置的最小值。 把线段按左端点升序排序，这样转移考虑枚举当前线段是否被删除即可。 虽然 \(y\) 的值域非常大，但因为只有 \(k+1\) 个极大的右端点是有用的。 于是总状态数为 \(\mathcal{O}(mk^2)\) ，实现的时候可以用 \(i\times 2^{22} + x\times 2^...

CF19E Fairy 题解 题目链接：CF19E Fairy 题意： 给定 \(n\) 个点，\(m\) 条边的无向图，可以从图中删除一条边，问删除哪些边可以使图变成一个二分图。 输入格式： 第一行包含两个正整数 \(n,m~(n,m\le10^6)\)，分别表示点数和边数。 第 \(2\sim m+1\) 行，每行两个正整数 \(x,y~(1 \le x,y \le n,~x\ne y)\)，表示有一条 \((x,y)\) 的边。 输出格式： 第一行输出一个整数，表示能删除的边的个数。 第二行按照从小到大的顺序输出能删除的边的序号。 首先，一个图是二分图当且仅当图中没有奇数长度的环，即没有奇环。 那么我们只需要找到一些边，使得整个图删掉这些边以后没有奇环即可。 考虑建出原图的 DFS 树，则每个奇环对应了一条或多条非树边。 考虑只有一条非树边的奇环，不妨称之为主奇环。 结论1 若 \(e\) 为非树边，则 \(e\) 能被删除的当且仅当它位于（且仅位于）一个主奇环上。 证明 必要性显然，考虑证明充分性。 根据假设，若删除后还有奇环，则一定不是主奇环。 而任何一个非主奇环...

UOJ12 【UER #1】猜数 题解 题目链接：#12. 【UER #1】猜数 题意： 给定一个完全平方数 \(n=a\times b=g \times l\) ，其中 \(a,b,g,l\) 均为正整数。 每次给出 \(g,l\) ，求 \(a + b\) 的最小值和最大值，保证 \(g \mid a\) 且 \(g \mid b\) 。 根据均值不等式，有 \(a + b \ge 2\sqrt{ab} = 2\sqrt{n}\) 。 由于 \(n=gl\) 是完全平方数，我们可以求得 \(\sqrt{n}\) 的值，得到 \(a + b\) 的下界，当 \(a=b=\sqrt{n}\) 时等号成立。 那么当 \(g \mid a,~g\mid b\) 时还能取到等号吗？ 设 \(a = a_0g,~b = b_0g\) ，则 \(n = a_0b_0g^2\) ，则 \(l = a_0b_0g\) ，故 \(g \mid l\) 。 设 \(l = kg\) ，则 \(gl = kg^2\) 为完全平方数，故 \(k\) 也为完全平方数。 设 \(k=t^2\) ，则 ...

UOJ139 【UER #4】被删除的黑白树 题解 题目链接：#139. 【UER #4】被删除的黑白树 题意： 很久很久以前，有一棵树加入了 UOJ 群。 这天，在它讨论“一棵树应该怎么旋转”的时候一不小心被删除了，变成了被删除的树。 突然间，它突然发现它失去了颜色，变成了一棵纯白的树。这让它感觉很焦躁，于是它来拜托你给自己染上一些颜色。 我们可以把它描述为一棵 \(n\) 个节点的有根树（默认树的根为 \(1\) 号节点），所有非根的度数为 \(1\) 的节点被称为叶子节点。最开始所有的节点都是白色的。 现在你需要选出一些节点并把这些节点染成黑色的。为了迎合树的审美，你的染色方案必须要满足所有叶子节点到根路径上的黑色节点个数相同。 你发现黑色节点个数越多，树就会越高兴，所以你想要知道在所有合法的染色方案中，黑色节点总个数最多是多少。 输入格式： 第一行一个正整数 \(n\) 表示树的节点个数。 接下来的 \(n-1\) 行，每行是两个整数 \(u,v\ (1 \leq u,v \leq n,u \neq v)\) 表示树上的一条边。 输出格式： 一个整数，表示在所有合法方案...

洛谷P2473 [SCOI2008] 奖励关 题解 题目链接：P2473 [SCOI2008] 奖励关 题意： 你正在玩你最喜欢的电子游戏，并且刚刚进入一个奖励关。在这个奖励关里，系统将依次随机抛出 \(k\) 次宝物，每次你都可以选择吃或者不吃（必须在抛出下一个宝物之前做出选择，且现在决定不吃的宝物以后也不能再吃）。 宝物一共有 \(n\) 种，系统每次抛出这 \(n\) 种宝物的概率都相同且相互独立。也就是说，即使前 \((k-1)\) 次系统都抛出宝物 \(1\)（这种情况是有可能出现的，尽管概率非常小），第 \(k\) 次抛出各个宝物的概率依然均为 $ n $。 获取第 \(i\) 种宝物将得到 \(p_i\) 分，但并不是每种宝物都是可以随意获取的。第 \(i\) 种宝物有一个前提宝物集合 \(s_i\)。只有当 \(s_i\) 中所有宝物都至少吃过一次，才能吃第 \(i\) 种宝物（如果系统抛出了一个目前不能吃的宝物，相当于白白的损失了一次机会）。注意，\(p_i\) 可以是负数，但如果它是很多高分宝物的前提，损失短期利益而吃掉这个负分宝物将获得更大的长期利益。 假...