Q779’s Blog

洛谷P1297 [国家集训队]单选错位 题解 题目链接：P1297 [国家集训队]单选错位 题意： gx 和 lc 去参加 noip 初赛，其中有一种题型叫单项选择题，顾名思义，只有一个选项是正确答案。 试卷上共有 \(n\) 道单选题，第 \(i\) 道单选题有 \(a_i\) 个选项，这 \(a_i\) 个选项编号是 \(1,2,3,\ldots,a_i\)，每个选项成为正确答案的概率都是相等的。 lc 采取的策略是每道题目随机写上 \(1 \sim a_i\) 的某个数作为答案选项，他用不了多少时间就能期望做对 \(\sum_{i=1}^n \frac{1}{a_i}\) 道题目。gx 则是认认真真地做完了这 \(n\) 道题目，可是等他做完的时候时间也所剩无几了，于是他匆忙地把答案抄到答题纸上，没想到抄错位了：第 \(i\) 道题目的答案抄到了答题纸上的第 \(i+1\) 道题目的位置上，特别地，第 \(n\) 道题目的答案抄到了第 \(1\) 道题目的位置上。 现在 gx 已经走出考场没法改了，不过他还是想知道自己期望能做对几道题目，这样他就知道会不会被 lc 鄙视了...

洛谷P3802 小魔女帕琪 题解 题目链接：P3802 小魔女帕琪 题意： 从前有一个聪明的小魔女帕琪，兴趣是狩猎吸血鬼。 帕琪能熟练使用七种属性（金、木、水、火、土、日、月）的魔法，除了能使用这么多种属性魔法外，她还能将两种以上属性组合，从而唱出强力的魔法。比如说为了加强攻击力而将火和木组合，为了掩盖弱点而将火和土组合等等，变化非常丰富。 现在帕琪与强大的夜之女王，吸血鬼蕾咪相遇了，夜之女王蕾咪具有非常强大的生命力，普通的魔法难以造成效果，只有终极魔法：帕琪七重奏才能对蕾咪造成伤害。帕琪七重奏的触发条件是：连续施放的 \(7\) 个魔法中，如果魔法的属性各不相同，就能触发一次帕琪七重奏。 请注意，无论前 \(6\) 个魔法是否已经参与施放终极魔法，只要连续 \(7\) 个魔法的属性各不相同，就会再触发一次终极魔法。例如，如果用序号来代表一种魔法，魔法的施放序列为 \(1, 2, 3, 4, 5, 6,7, 1\)，则前 \(7\) 个魔法会触发一次终极魔法，后 \(7\) 个魔法会再触发一次终极魔法。 现在帕琪有 \(7\) 种属性的能量晶体，第 \(i\) 种晶体可以施放出...

洛谷P4438 [HNOI/AHOI2018]道路 题解 题目链接：P4438 [HNOI/AHOI2018]道路 题意： W 国的交通呈一棵树的形状。W 国一共有 \(n-1\) 个城市和 \(n\) 个乡村，其中城市从 \(1\) 到 \(n-1\) 编号，乡村从 \(1\) 到 \(n\) 编号，且 \(1\) 号城市是首都。道路都是单向的，本题中我们只考虑从乡村通往首都的道路网络。 对于每一个城市，恰有一条公路和一条铁路通向这座城市。对于城市 \(i\)， 通向该城市的道路（公路或铁路）的起点，要么是一个乡村，要么是一个编号比 \(i\) 大的城市。没有道路通向任何乡村。除了首都以外，从任何城市或乡村出发只有一条道路；首都没有往外的道路。从任何乡村出发，沿着唯一往外的道路走，总可以到达首都。 W 国的国王小 W 获得了一笔资金，他决定用这笔资金来改善交通。由于资金有限，小 W 只能翻修 \(n-1\) 条道路。小 W 决定对每个城市翻修恰好一条通向它的道路，即从公路和铁路中选择一条并进行翻修。小 W 希望从乡村通向城市可以尽可能地便利，于是根据人口调查的数据，小 W 对...

洛谷P1613 跑路 题解 题目链接：P1613 跑路 题意： cxy 买了一个空间跑路器，每秒钟可以跑 \(2^k\) 千米（\(k\) 是任意自然数）。 当然，这个机器是用 long long 存的，所以总跑路长度不能超过 \(2^{63}-1\) 千米。 cxy 的家到公司的路可以看做一个有向图，cxy 家为点 \(1\)，公司为点 \(n\)，每条边长度均为一千米。 cxy 想每天能醒地尽量晚，所以让你帮他算算，他最少需要几秒才能到学校。 数据保证 \(1\) 到 \(n\) 至少有一条路径。 输入格式： 第一行两个整数 \(n,m\)，表示点的个数和边的个数。 接下来 \(m\) 行每行两个数字 \(u,v\)，表示一条 \(u\) 到 \(v\) 的边。 输出格式： 一行一个数字，表示到公司的最少秒数。 数据范围： \(n \le 50,~m \le 10000\)，最优解路径长度 \(\le 2^{63}-1\)。 倍增好题。注意到贪心不一定是最优的，因此考虑dp。 设 \(g_{i,j,k}\) 表示 \(i,j\) 之间是否存在恰好 \(2^k\) 的路径，...

洛谷P6145 [USACO20FEB]Timeline G 题解 题目链接：P6145 [USACO20FEB]Timeline G 题意： Bessie 在过去的 \(M\) 天内参加了 \(N\) 次挤奶。但她已经忘了她每次挤奶是在哪个时候了。 对于第 \(i\) 次挤奶，Bessie 记得它不早于第 \(S_i\) 天进行。另外，她还有 \(C\) 条记忆，每条记忆形如一个三元组 \((a,b,x)\)，含义是第 \(b\) 次挤奶在第 \(a\) 次挤奶结束至少 \(x\) 天后进行。 现在请你帮 Bessie 算出在满足所有条件的前提下，每次挤奶的最早日期。 保证 Bessie 的记忆没有错误，这意味着一定存在一种合法的方案，使得： 第 \(i\) 次挤奶不早于第 \(S_i\) 天进行，且不晚于第 \(M\) 天进行； 所有的记忆都得到满足； 输入格式： 第一行三个整数 \(N,M,C\)。保证 \(1 \leq N,C \leq 10^5\)，\(2 \leq M \leq 10^9\)。 接下来一行包含 \(N\) 个整数 \(S_1, S_2 , \ld...

利用导数求参数 常用步骤： 利用导数的几何意义求参数时，常根据以下关系列方程： 函数在切点处的导数值等于切线的斜率 切点在切线上 切点在曲线上 题目所给的其他条件 最后通过解方程(组)得到参数的值。 例题： 设 \(f(x)=\ln (x+1)+\sqrt{x+1}+a x+b\) （ \(a, b \in \mathbb{R},~ a, b\) 为常数 ） 若曲线 \(y=f(x)\) 与直线 \(y=\frac{3}{2} x\) 在点 \((0,0)\) 处相切，求 \(a,b\) 。 解：由曲线 \(y = f(x)\) 过点 \((0,0)\) 可解出 \(b = -1\) 。 由 \(f(x)=\ln (x+1)+\sqrt{x+1}+a x+b\) 可知 \[ f^{\prime}(x) = \frac{1}{x+1}+\frac{1}{2 \sqrt{x+1}}+a \] 则切线处的斜率为 \(f^{\prime}(0) = 1 + \frac{1}{2} + a = \frac{3}{2} + a = \frac{3}{2}\) ，即 \(a = 0\)...

求曲线的切线方程 利用导数求切线的斜率是一种非常有效的方法，它适用于任何可导函数。 求曲线的切线方程时，一定要注意已知点是否为切点。 若切点没有给出,一般是先把切点坐标设出来，并求出切点坐标，再求切线方程。 常用步骤 求解以曲线上的点 \((x_0,f(x_0))\) 为切点的切线方程的步骤： 求出函数 \(f(x)\) 的导数 \(f^{\prime}(x)\) 求出切线的斜率 \(f^{\prime}(x_0)\) 写出切线方程，并化简 \[ y - f(x_0) = f^{\prime}(x_0)(x - x_0) \] 若已知点 \((x_1,y_1)\) 不在曲线上（一般为切线上一点），则 先设切点为 \((x_0,y_0)\)，再解方程组 \[ \left\{\begin{array}{l} y_0=f\left(x_0\right) \\ \frac{y_1-y_0}{x_1-x_0}=f^{\prime}\left(x_0\right) \end{array}\right. \] 解出切点 \((x_0,y_0)\) ，进而求出切线方程。 注意：...

洛谷P1248 加工生产调度 题解 题目链接：P1248 加工生产调度 题意： 某工厂收到了 \(n\) 个产品的订单，这 \(n\) 个产品分别在 A,B 两个车间加工，并且必须先在 A 车间加工后才可以到 B 车间加工。 某个产品 \(i\) 在 A、B 两车间加工的时间分别为 \(A_i,B_i\)。怎样安排这 \(n\) 个产品的加工顺序，才能使总的加工时间最短。 这里所说的加工时间是指：从开始加工第一个产品到最后所有的产品都已在 A、B 两车间加工完毕的时间。 输入格式： 第一行仅—个整数 \(n\)，表示产品的数量。 接下来一行 \(n\) 个整数是表示这 \(n\) 个产品在 A 车间加工各自所要的时间。 最后的 \(n\) 个整数是表示这 \(n\) 个产品在 B 车间加工各自所要的时间。 输出格式： 第一行一个整数，表示最少的加工时间。 第二行是一种最小加工时间的加工顺序。 数据范围： \(1\leq n\leq 10^5\) 贪心的常见套路似乎就是找到两个存在极小差异的决策，分析哪个更优，以归纳法获得最优决策。 考虑只有两个元素 \((a_1,b_1),(...

离差 数学和统计学中，离差（英语：deviation）是变量的一个观测值与某个特定的参照值（通常是该变量的平均值，此时称为离均差或距平）之间差异的度量。离差的正负表示差异的方向（观测值超过参照值时偏差为正），绝对值的大小表示差异的大小。 离差的分类 观测值与关注量的真值（期望值，例如总体平均值）之间的离差称为误差（error）。 观测值与真值的估计值（例如样本均值；样本期望值可用作总体期望值的估计值）之间的离差称为残差（residual）。这些概念适用于测量区间尺度和比例尺度的数据。 统计学中，数据集中某个元素的绝对离差（absolute deviation）是该元素与给定点之间的绝对差。 绝对离差（无符号离差） 通常，离差是用中心值计算出来的，它被解释为某种类型的平均值，通常是数据集的中位数，也有时是平均值： \[ D_i=\left|x_i-m(X)\right| \] 其中 \(D_i\) 是绝对离差，\(x_i\) 是数据元素。 \(m(X)\) 是所选数据集集中趋势的度量，有时是平均数 \(\overline{x}\) ，但常见的是中位数。 参考文献： [1] 离差...

方差 在概率论和统计学中，方差（英语：variance）描述的是一个随机变量的离散程度 即一组数字与其平均值之间的距离的度量，是随机变量与其总体均值或样本均值的离差的平方的期望值。 方差是标准差的平方、分布的二阶矩，以及随机变量与其自身的协方差。 其常用的符号表示有 \(\sigma^2, s^2 、 \operatorname{Var}(X), V(X)\) 以及 \(\mathbb{V}(X)\) 。 一、定义 设 \(X\) 为服从分布 \(F\) 的随机变量，如果 \(\mathrm{E}[X]\) 是随机变量 \(X\) 的期望值 则随机变量 \(X\) 或分布 \(F\) 的方差为「 \(X\) 的离差平方的期望值」，即 \[ \operatorname{Var}(X)=\mathrm{E}\left[(X-\mu)^2\right] \] 方差的表达式可展开如下 \[ \begin{aligned} \operatorname{Var}(X) &=\mathrm{E}\left[(X-\mathrm{E}[X])^2\right] \\ &=\mat...

二项分布 在概率论和统计学中，二项分布是 \(n\) 个独立的 是/非试验 中成功的次数的离散概率分布，其中每次试验的成功概率为 \(p\)。 这样的 单次成功/失败试验 又称为 伯努利试验 。实际上，当 \(n = 1\) 时，二项分布就是伯努利分布。 数学定义 一般来说，若随机变量 \(X\) 服从参数为 \(n\) 和 \(p\) 的二项分布，我们记作 \(X \sim B(n,p)\) 。\(n\) 次试验中正好得到 \(k\) 次成功的概率由概率质量函数给出: \[ f(k, n, p)=\operatorname{Pr}(X=k)=\binom{n}{k} p^k(1-p)^{n-k} \quad (k \in \mathbb{N}_+) \] 该公式可以用以下方法理解： 我们希望有 \(k\) 次成功和 \(n-k\) 次失败。然而，\(k\) 次成功可以在 \(n\) 次试验的任何地方出现，而把 \(k\) 次成功分布在 \(n\) 次试验中共有 \(\binom{n}{k}\) 个不同的方法。 可以发现 \(\mathrm{Pr}(X = k)\) 就是 \(...

期望值 在概率论和统计学中，一个离散性随机变量的期望值（或数学期望，亦简称期望）是试验中每次可能的结果乘以其结果概率的总和。 期望值更像是随机试验在同样的机会下重复多次，所有那些可能状态平均的结果，便基本上等同“期望值”所期望的数。 期望值可能与每一个结果都不相等，或者说期望值就是该变量输出值的加权平均。期望值并不一定包含于其分布值域，也并不一定等于值域平均值。 例如，掷一枚公平的六面骰子，其每次“点数”的期望值是 \(3.5\) ，计算如下： \[ \begin{aligned} \mathrm{E}(X) &=1 \cdot \frac{1}{6}+2 \cdot \frac{1}{6}+3 \cdot \frac{1}{6}+4 \cdot \frac{1}{6}+5 \cdot \frac{1}{6}+6 \cdot \frac{1}{6} \\ &=\frac{1+2+3+4+5+6}{6}=3.5 \end{aligned} \] 不过如上所说明的，\(3.5\) 虽是“点数”的期望值，但却不属于可能结果中的任一个，没有可能掷出此点数。 高中书上是这...