Q779’s Blog

洛谷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\) 虽是“点数”的期望值，但却不属于可能结果中的任一个，没有可能掷出此点数。 高中书上是这...

几何分布 在概率论和统计学中，几何分布（英语：Geometric distribution）指的是以下两种离散型概率分布中的一种： 在伯努利试验中，得到一次成功所需要的试验次数 \(X\) 。 \(X\) 的值域是 \(\{ 1, 2, 3, \cdots \}\) 在得到第一次成功之前所经历的失败次数 \(Y = X − 1\) 。\(Y\) 的值域是 \(\{ 0, 1, 2, 3, \cdots \}\) 实际使用中指的是哪一个取决于惯例和使用方便。 这两种分布不应该混淆。 前一种形式（ \(X\) 的分布）经常被称作 shifted geometric distribution 但是，为了避免歧义，最好明确地说明取值范围。因此本文优先采用前者。 数学定义 如果每次试验的成功概率是 \(p\) ，那么 \(k\) 次试验中，第 \(k\) 次才得到成功的概率是 \[ \operatorname{Pr}(X=k)=(1-p)^{k-1} p,\quad k = 1,2,3,\cdots \] 而另一种形式，也就是第一次成功之前所失败的次数，可以写为 \[ \ope...

概率质量函数 在概率论和统计学中，概率质量函数是离散随机变量在各特定取值上的概率。有时它也被称为离散密度函数。 概率质量函数通常是定义离散概率分布的主要方法，并且此类函数存在于其定义域是离散的标量变量或多元随机变量。 具有最大概率质量的随机变量的值称为众数。 概率质量函数可以定义在任何离散随机变量上，包括常数分布， 二项分布（包括伯努利分布）， 负二项分布， 泊松分布， 几何分布以及超几何分布随机变量上。 数学定义 假设 \(X\) 是一个定义在可数样本空间 \(S\) 上的离散随机变量 \((S \subseteq \mathbb{R})\) ，则其概率质量函数 \(f_X(x)\) 为 \[ f_X(x)= \begin{cases}\operatorname{Pr}(X=x), & x \in S \\ 0, & x \in \mathbb{R} \backslash S .\end{cases} \] 注意这在所有实数上，包括那些 \(X\) 不可能等于的实数值上，都定义了 \(f_X(x)\) 。 在那些 \(X\) 不可能等于的实数值上，\(f_X(...

两点分布（伯努利分布） 两点分布的应用非常广泛，如抽取的彩票是否中奖，买回的一件产品是否为正品，新生婴儿的性别，投篮是否命中等，都可以用两点分布来研究。 基本概念 伯努利分布，又名 两点分布 或者 0-1分布 ，是一个离散型概率分布，为纪念瑞士科学家雅各布·伯努利而命名。 若伯努利试验成功，则伯努利随机变量取值为 \(1\) 若伯努利试验失败，则伯努利随机变量取值为 \(0\) 。 记其成功概率为 \(p(0\le p\le 1)\) ，失败概率为 \(q = 1 - p\) ，则 其概率质量函数为 \[ f_X(x) = p^x(1-p)^{1-x} = \begin{cases}p & \text { if } x=1 \\ q & \text { if } x=0\end{cases} \] 其期望值为 \[ \operatorname{E}[X] = \sum_{i=0}^{1} x_i f_X(x) = 0 + p = p \] 其方差为 \[ \begin{aligned} \operatorname{Var}[X] &=\sum_{i=...

洛谷P2065 [TJOI2011] 卡片 题解 题目链接：P2065 [TJOI2011] 卡片 题意： 桌子上现在有 \(n\) 张蓝色卡片和 \(m\) 张红色卡片，每张卡片上有一个大于 \(1\) 的整数 \(x\) 。 现在你要从桌子上拿走一些卡片，分若干次拿。 每次只能拿走一组卡片：这组卡片颜色不同，并且两张卡片上面的数字的最大公约数大于 \(1\)。 问最多可以从桌上拿走多少组卡片。 输入格式： 文件的第一行读入一个整数 \(T\) ，为数据组数。 对于每组数据，第一行给出 \(n,m\) 。 第二行给出每张蓝色卡片上面的数字，第三行给出每张红色卡片上的数字。 输出格式： 对每组测试数据，输出最多可以拿走多少组卡片。 数据范围： \(1\le T\le 100,~1\le m,n\le 500\) ，卡片上的数字 \(x\) 满足 \(1 \le x \le 10^7\) 。 虽说网络流复杂度很宽松，但是直接 \(\mathcal{O}(n^2)\) 暴力建边是不行滴。 考虑对卡片上的每个数质因数分解，称这些质因数的并为点集 \(P\) 。 称 \(A\) 为蓝...