统计学基础
统计学基础 Varianece 方差 运算法则 \[ Var(aX+bY)=a^2Var(X)+b^2Var(Y)+2abCov(X,Y) \] \[ \operatorname{Var}(Y)=\operatorname{Var}(a X+b)=a^{2} \operatorname{Var}(X) \] Corvariance 协方差 对于两个随机变量 \(X_1,X_2\) \[ \operatorname{Cov}\left(X_{1}, X_{2}\right)=E\left(\left(X_{1}-\mu_{1}\right)\left(X_{2}-\mu_{2}\right)\right) \] 另一个等价的公式 \[ \operatorname{Cov}\left(X_{1}, X_{2}\right)=E\left(X_{1} X_{2}\right)-\mu_{1} \mu_{2} \] 若两个随机变量 \(X_1, X_2\) 是独立的 \[ \operatorname{Cov}\left(X_{1}, X_{2}\right)=0 \] 有一个数据集的两个...
刷题总结DIV1C
知识点 枚举 cnt枚举2个量 在一个数组中, \(cnt[x]\) 代表 \(x\) 出现的次数 \[ \sum_x cnt[x] \le n \] 于是可以枚举所有 \(x\) 在枚举所有小于 \(cnt[x]\) 的数，总复杂度不超过 \(O(n)\) CF1637E(2100) 枚举 \(2^k\) 长度是 \(2^k\) 那么直接枚举 \(k\) 即可 CF1626D(2100) 二分 同时检查多个参数: 用二进制表示，0表示不符合，1表示符合，放到一个集合里，再枚举集合 zone2021_c 对 $x_i \(找下一个不超过\)L$ 的点，可以用lowerbound查询 倍增dp arc060_c 整体二分 CF1601C 并查集 对于两者选1的问题，用边建图，然后分析。 arc111_b 数据结构，小的向大的合成可以降低复杂度 abc183_f 神奇构造 分式 \[ \frac{1}{x(x+1)} = \frac{1}{x} - \frac{1}{x+1} \] arc163c 拆分再组合 agc055_a 构造部分解，然后组合...
非线性优化
问题设置 一般的非线性优化问题 \[ \min _{x \in \mathbb{R}^{n}} f(x) \quad \text { s.t. } \quad g(x) \leq 0, \quad h(x)=0 \] \(f\) 是目标函数，连续可导 \(g\) 是\(m\) 个不等号约束条件 \(h\) 是 \(p\) 个等号约束条件 定义1 feasible set 集合 \[ X=\left\{x \in \mathbb{R}^{n} ; g(x) \leq 0, h(x)=0\right\} \] 是feasible set (可行的集合), \(x\) 是 feasible 若它在这个集合中。index set of active inequality constraints \(\mathcal{A}(x)\) 是在不等式中使得等号成立的集合。\(\mathcal{I}(x)\) 是不等号严格成立的集合 \[ \begin{aligned} &\mathcal{A}(x)=\left\{i ; 1 \leq i \leq m, g_{i}(x)=0\right...
线性规划
线性规划问题 我们要优化一个目标函数 \[ F(x_1,x_2,...x_p)=c_1x_1 + c_2x_2+...+c_px_p \] 也就是求它的最大值或者最小值。同时还有很多约束条件 \[ a_{i1}x_1+...+a_{ip}x_p \le b_i \\ a_{i1}x_1+...+a_{ip}x_p \ge b_i \\ a_{i1}x_1+...+a_{ip}x_p = b_i \] 以及非负的限制条件 \[ x_j \ge 0 \] 解集的定义 \(\textbf{x}=(x_1,x_2,...,x_p)\) 满足线性约束条件的是一个解 如果 \(\textbf{x}\) 还满足非负限制条件，那么是一个可行解 \[x^{*}\] 是最优解 \[X^*\] 是所有最优解的集合 转化问题 每个线性规划问题可以转化成最大值的线性规划问题： 最大化目标函数 \[ F(x_1,x_2,...x_p)=c_1x_1 + c_2x_2+...+c_px_p \] 约束条件： \[ \sum_{j=1}^{p} a_{ij} x_j \le b_i \\ x_j ...
二进制与位运算
二进制与位运算 数的表示有很多种，我们最常用的是 \(10\) 进制。也就是缝 \(10\) 进位。在计算机中，数都是由二进制的形式存储的。而二进制的意思就是缝 \(2\) 进位。因此二进制的数中，只有 \(0\) 和 \(1\) 二进制 下面这个是一个二进制数 \(101011\) , 我们把它转化成 \(10\) 进制 \[ (101011)_2 \] 怎么转化, 我们从右往左看 \[ \begin{aligned} (101011)_2&= 1*2^5 +0*2^{4}+1*2^{3}+0*2^{2}+1*2^{1}+ 1*2^{0}\\ &=1+2+8+32 \\ &=43 \end{aligned} \] 把一个十进制数转化成二进制 \[ \begin{aligned} 43 /2 = 21 ...& 1 \\ 21/2= 10 ... & 1 \\ 10/2=5 ... & 0 \\ 5/2 = 2 ... & 1 \\ 2/2 = 1 ... & 0 \\ 1/2 = 0 ... & 1 \e...
数字化编程
第1章 定义2.1 机器数字Maschinenzahlen 有限集合 \(M\) 计算机可以表示的数字 定义2.2 取整Rundung 映射 \(\mathbb{R} \rightarrow M\) 是一个Rundung \[ |x-r d(x)|=\min _{m \in M}|x-m| \] 于是产生absolute Rundungsfehler \[ f_{r d}(x):=x-r d(x) \] 定义2.3 Festkommazahlen \[ \begin{aligned} &n_{1} n_{2} \cdots n_{k}, m_{1} \cdots m_{j} \quad \text { mit } \\ &n_{1}, n_{2}, \ldots, n_{k}, m_{1}, \ldots, m_{j} \in\{0,1, \ldots, 9\}, \quad k, j \in I N \end{aligned} \] 补码 取反后+1 最高位符号为负数 浮点数 \(x\in \mathbb{R}\) 可以如下表示， \(m\) 是Mantis...
统计学
统计学 概述 什么是统计学 研究量化数据的方法的科学 Statisticsis the study of methods for dealing with quantitative information (data). 从数据中获得信息和知识 分为 Descriptive Statistics 制作图表 Explorative Data Analysis 分析数据得出结论 Inductive Statistics(inferential statistics) 研究数据间的关系 预测未来趋势 统计学基本概念 Statistical units统计单元 Objects on which data is observed 被研究数据的对象 Population 所有需要的统计单元的集合 可以有限(finite)，无限(infinite)，假设的(hypothetical) Subpopulations sub set of the population Sample Actual subset of the population surveyed Character...
建模和仿真
Focus Analysis 基础部分 多变量函数 定义 \[ f: D \rightarrow W, D \subseteq \mathbb{R}^{n}, W \subseteq \mathbb{R}^{m} \] 对于自然数 \(n\) 和 \(m\) 这个函数可以这样表示： \[ f: D \subseteq \mathbb{R}^{n} \rightarrow \mathbb{R}^{m}, x=\left(\begin{array}{c} x_{1} \\ \vdots \\ x_{n} \end{array}\right) \mapsto f(x)=\left(\begin{array}{c} f_{1}\left(x_{1}, \ldots, x_{n}\right) \\ \vdots \\ f_{m}\left(x_{1}, \ldots, x_{n}\right) \end{array}\right) \] 高维度拓扑学 定义域Domain \(D\subseteq \mathbb{R} ^n\) 定义补集complement 为 \(D^c=\mathbb...
概率论习题
概率论 习题1 例1 A,B,C 三匹马比赛跑步，构造一个离散概率空间，使得事件“A比B快”，“B比C快”，“C比A快”出现的概率都大于 \(1/2\) 例2 已知带偶数条纹的斑马出现的概率是带奇数条纹斑马的2倍。设事件 \(E_n\) 为随机选取一个斑马，发现它有数量为 \(n\) 的条纹。构造一个离散概率空间，使得 \(E_n\) 所有正整数的概率都大于0，且符合题意。 例3 现在要做 \(m\) 个蓝莓蛋糕，一共有 \(n\) 个蓝莓。现在把这 \(n\) 个蓝莓等可能随机放到 \(m\) 个蛋糕上。 求第 \(i\) 个蛋糕没有蓝莓的概率 求所有蛋糕至少有 \(1\) 个蓝莓的概率 例4 有一个幸运轮盘，上面写有 \(1\) 至 \(125\) 的数字（包含1和125），每一个数字等可能出现 求转出的数字是4的倍数或者是平方数的概率 转出的数，每位上数字的和大于3的概率 例5 A，B，C轮流扔硬币（从A开始），硬币是正面的概率是 \(0<p<1\) ，第1次扔到反面的人赢。求A，B，C各自赢的概率 例6 有 \(n\) 份没有名字的作业。把这 \(n\...
图论习题
拓扑排序 Directing Edges 此题很巧妙，先用拓扑排序排出来，再利用拓扑序构造解