Q779’s Blog

几何分布 在概率论和统计学中，几何分布（英语：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\) 为蓝...

洛谷P2766 最长不下降子序列问题 题解 题目链接：P2766 最长不下降子序列问题 题意： 给定正整数序列 \(x_1 \ldots, x_n\)。 计算其最长不下降子序列的长度 \(s\)。 如果每个元素只允许使用一次，计算从给定的序列中最多可取出多少个长度为 \(s\) 的不下降子序列。 如果允许在取出的序列中多次使用 \(x_1\) 和 \(x_n\)（其他元素仍然只允许使用一次），则从给定序列中最多可取出多少个不同的长度为 \(s\) 的不下降子序列。 令 \(a_1, a_2, \ldots, a_s\) 为构造 \(S\) 时所使用的下标，\(b_1, b_2, \ldots, b_s\) 为构造 \(T\) 时所使用的下标。且 \(\forall i \in [1,s-1]\)，都有 \(a_i \lt a_{i+1}\)，\(b_i \lt b_{i+1}\)。则 \(S\) 和 \(T\) 不同，当且仅当 \(\exists i \in [1,s]\)，使得 \(a_i \neq b_i\)。 输入格式： 第一行有一个正整数 \(n\)，表示给定序列的...

洛谷P2763 试题库问题 题解 题目链接：P2763 试题库问题 题意： 假设一个试题库中有 \(n\) 道试题。每道试题都标明了所属类别。 现要从题库中抽取 \(m\) 道题组成试卷。 并要求试卷包含指定类型的试题。试设计一个满足要求的组卷算法。 注意，同一道题可能有多个类别属性，但是每道题在组卷时只能归类于一种类型。 对于给定的组卷要求，计算满足要求的组卷方案。 输入格式： 第一行有两个正整数 \(k\) 和 \(n\)。\(k\) 表示题库中试题类型总数，\(n\) 表示题库中试题总数。 第二行有 \(k\) 个正整数，第 \(i\) 个正整数表示要选出的类型 \(i\) 的题数。这 \(k\) 个数相加就是要选出的总题数 \(m\)。 接下来的 \(n\) 行给出了题库中每个试题的类型信息。每行的第一个正整数 \(p\) 表明该题可以属于 \(p\) 类，接着的 \(p\) 个数是该题所属的类型号。 输出格式: 输出共 \(k\) 行，第 \(i\) 行输出 i: 后接类型 \(i\) 的题号。 如果有多个满足要求的方案，只要输出一个方案。 如果问题无解，则输出No ...

洛谷P5358 [SDOI2019]快速查询 题解 题目链接：洛谷P5358 [SDOI2019]快速查询 题意： 给定一个长度为 \(n\) 的整数数列，里面的元素依次编号为 \(a_1,~a_2,~a_3,~\dots,~a_n\)。初始的时候，所有元素都为零。现在按照时间顺序提供了若干次关于这个数列的修改或询问，每一次修改或询问一定为以下六种情况之一： 1 i x ：将 \(a_i\) 赋值为给定整数 \(x\)； 2 x ：将所有元素同时加上 \(x\)； 3 x ：将所有元素同时乘上 \(x\)； 4 x ：将所有元素同时赋值为 \(x\)； 5 i ：询问第 \(i\) 个元素 \(a_i\) 现在的值是多少； 6 ：询问现在所有元素的和。 输入格式： 为了避免读入太大，输入文件采取如下的形式。 第一行给定整数 \(n\)，表示给定数列长度为 \(n\)。 第二行给定整数 \(q\)，并且之后的 \(q\) 行，每一行提供一个修改或询问，输入的格式与题目所述一致，请参见样例。 我们称上述给定的修改或询问为标准操作。 之后给定一个整数 \(t\)，并且之后的 \(...

SP1557 GSS2 - Can you answer these queries II 题解 题目链接：SP1557 GSS2 - Can you answer these queries II 题意： 给定一个长度为 \(n\) 的序列 \(a_i\) 。 \(q\) 次询问，查询区间最大子段和，相同的数只算一次。选出的子段可以为空 数据范围： \(1\le n,q \le 10^5,~ |a_i| \le 10^5\) 。 真就加了一句话就比 GSS1 难了 \(+\infty\) 倍（悲） 感觉这题是 GSS 系列第二难的题。 因为相同的数只能算一次，所以直接维护那 \(4\) 个信息就不太行了。 想起来一道题叫 HH 的项链，这题的思想和那道题有一些相似。 考虑从左往右依次加入每个元素，记 \(\mathtt{pre}(a_i)\) 表示 \(a_i\) 上次出现的位置。 对于第 \(i\) 个元素 \(a_i\) ，它能产生贡献的范围为 \([\,\mathtt{pre}(a_i) + 1, i-1\,]\) 任意 \(l~(\mathtt{pre}(a_i) ...

洛谷P5568 [SDOI2008] 校门外的区间 题解 题目链接：P5568 [SDOI2008] 校门外的区间 题意： 受校门外的树这道经典问题的启发，cxy 根据基本的离散数学的知识，抽象出 \(5\) 种运算维护集合 \(S\) （\(S\) 初始为空）并最终输出 \(S\)。现在，请你完成这道校门外的树之难度增强版——校门外的区间。 五种运算如下： U T：\(S = S \cup T\) I T：\(S = S \cap T\) D T：\(S = S - T\) C T：\(S = T - S\) S T：\(S = S \oplus T\) 集合的基本运算操作定义如下： \(A \cup B\)：\(\{x | x \in A \vee x \in B\}\) \(A \cap B\)：\(\{x | x \in A \wedge x \in B\}\) \(A - B\)：\(\{x | x \in A \wedge x \notin B\}\) \(A \oplus B\)：\((A-B)\cup (B-A)\) 输入格式： 输入 \(M\) 行。 ...

洛谷P4137 Rmq Problem / mex 题解 题目链接：P4137 Rmq Problem / mex 题意： 有一个长度为 \(n\) 的数组 \(\{a_1,a_2,\ldots,a_n\}\)。 \(m\) 次询问，每次询问一个区间内最小没有出现过的自然数。 输入格式： 第一行，两个正整数 \(n,m\)。 第二行，\(n\) 个非负整数 \(a_1, a_2, \ldots , a_n\)。 接下来 \(m\) 行，每行两个正整数 \(l,r\)，表示一次询问。 输出格式： 输出 \(m\) 行，每行一个数，依次表示每个询问的答案。 数据范围： \(1\leq n,m\leq 2\times {10}^5,~1\leq l\leq r\leq n,~0\leq a_i\leq 2\times 10^5\) 线段树上二分经典题，维护区间 \(\mathrm{mex}\) 。 建一棵可持久化权值线段树，然后从左往右扫一遍 每次修改当前权值对应的「最后一次出现的位置」为「当前位置」 查询区间 \([l,r]\) 时，答案就是第 \(r\) 棵线段树上，第一个「最...

UOJ340 【清华集训2017】小 Y 和恐怖的奴隶主 题解 题目链接：#340. 【清华集训2017】小 Y 和恐怖的奴隶主 题意： 小 Y 是一个喜欢玩游戏的 OIer。一天，她正在玩一款游戏，要打一个 Boss。 虽然这个 Boss 有 \(10^{100}\) 点生命值，但它只带了一个随从——一个只有 \(m\) 点生命值的 “恐怖的奴隶主”。 这个 “恐怖的奴隶主” 有一个特殊的技能：每当它被扣减生命值但没有死亡（死亡即生命值 \(\leq 0\)），且 Boss 的随从数量小于上限 \(k\)，便会召唤一个新的具有 \(m\) 点生命值的 “恐怖的奴隶主”。 现在小 Y 可以进行 \(n\) 次攻击，每次攻击时，会从 Boss 以及 Boss 的所有随从中的等概率随机选择一个，并扣减 \(1\) 点生命值，她想知道进行 \(n\) 次攻击后扣减 Boss 的生命值点数的期望。为了避免精度误差，你的答案需要对 \(998244353\) 取模。 输入格式： 从标准输入读入数据。 输入第一行包含三个正整数 \(T, m, k\)，\(T\) 表示询问组数，\(m, k...

SP1043 GSS1 - Can you answer these queries I 题解 题目链接：SP1043 GSS1 - Can you answer these queries I 题意： 给定一个长度为 \(n\) 的序列 \(a_i\) 。 \(q\) 次询问，查询区间最大子段和 数据范围： \(1\le n,q \le 5\times 10^4,~ |a_i| \le 2\times10^4\) 。 纯粹是为了凑齐才写的，详见 GSS3 线段树经典题。我们需要维护总和、最大前缀、最大后缀、最大子段和。 \[ \mathtt{sum[u]} = \mathtt{sum[l]} + \mathtt{sum[r]} \\\mathtt{pre[u]} = \max\{\mathtt{pre[l]},~\mathtt{sum[l]}+\mathtt{pre[r]}\} \\\mathtt{suf[u]} = \max\{\mathtt{suf[r]},~\mathtt{sum[r]}+\mathtt{suf[l]}\} \\\mathtt{res[u]} = \m...