题目类型总结最近在阅读《算法竞赛进阶指南》这本书的链表这一节时，学会了链表在一类特定问题中的巧妙用法，遂有此文，也算是自己的一个学习笔记。考虑这样一类问题，一个长度为\(n\)的序列，有\(q\)询问，询问序列前任意个数的一个结果，该结果可通过暴力排序后直接判断，但是这种方法显然很暴力，很容易达到\(O(qn\logn)\)的复杂度。使用链表进行优化，先将序列全部读进来后进行排序，之后通过删除操作达到前任意段排完序后的序列。此时，只需进行一次排序，后面直接进行删除操作即可，效率大幅上升。例题该做法的一个经典应用即动态中位数问题，即一段长度为\(n\)的序列，依次输出前\(i\)个数的中位数，当
A-ContestResult(abc290a)题目大意给定\(n\)道题的分数。现在小\(A\)过了一些题，问他的分数是多少。解题思路模拟即可。神奇的代码#includeusingnamespacestd;usingLL=longlong;intmain(void){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);intn,m;cin>>n>>m;vectors(n);for(auto&i:s)cin>>i;intans=0;while(m--){intx;cin>>x;ans+=s[x-1];}coutB-QualB(abc290b)题
引入在一条链中，二叉查找树的时间复杂度就会退化成\(O(n)\)，这时我们就需要平衡树来解决这个问题。\(Splay\)（伸展树）是平衡树的一种，它的每一步插入、查找和删除的平摊时间都是\(O(log_2n)\)，出于对编程复杂度和算法性能的考虑，这是OI中常用的算法。性质\(Splay\)本质上还是对二叉查找树的优化。所以它也具备二叉查找树的性质，即左子树任意节点的值\(根节点的值\(右子树任意节点的值。操作数组含义roottotfa[i]ch[i][0]ch[i][1]val[i]size[i]cht[i]根节点编号节点数量父节点编号左儿子编号右儿子编号节点权值子树大小节点权值出现次数基本
Posttime:2022-02-1714:11:52本篇文章借鉴于武汉二中吕凯风的2015集训队论文《集合幂级数的性质与应用及其快速算法》。一、声明我们令全集为有限集\(U=\{1,2,...,n\}\)，其中\(n=|U|\)，设所有未标明的\(S\)都是\(U\)的子集。若\(X\)是一个集合，令\(2^{X}\)表示\(X\)的幂集（所有子集构成的集合）。二、定义设\(F\)是一个域，则称函数\(f:2^{U}\toF\)是\(F\)上的一个集合幂级数。对于每个\(S\in2^U\)，记\(f_S\)为\(S\)处的函数值，称\(f_S\)为集合幂级数\(S\)项的系数。集合幂级数之间
1Continuous-TimeDynamicNetworkEmbeddingsAbstract 描述一种将时间信息纳入网络嵌入的通用框架，该框架提出了从CTDG中学习时间相关嵌入Conclusion 描述了一个将时间信息纳入网络嵌入方法的通用框架。该框架为推广现有的基于随机游走的嵌入方法提供了基础，用于从连续时间动态网络学习动态（时间相关）网络嵌入Figureandtable图1：这幅图的边标签为时间，注意v4v1v2不是一个合法的时序游走，因为v1v2的边时序小于v1v4的边图2，可以看到大部分的时序随机游走长度都集中在右侧表1SOTAIntroduction 在这个论文里提出了一种
第三章随机向量3.1随机向量的分布随机向量及其分布函数概念\(X_1,X_2,\cdots,X_n\)是\(n\)个随机向量，则\((X_1,X_2,\cdots,X_n)\)是一个\(n\)维随机向量。\(n\)元函数\(F(x_1,x_2,\cdots,x_n)=P\{X_1\lex_1,X_2\lex_2,\cdots,X_n\lex_n\}\)为随机向量\((X_1,X_2,\cdots,X_n)\)的分布函数。其中\(\{X_1\lex_1,X_2\lex_2,\cdots,X_n\lex_n\}\)表示\(\{X_1\lex_1\},\{X_2\lex_2\},\cdots,\{X
2.5随机变量函数的分布随机变量函数对于一个随机变量\(X\)，其取值是不确定的，如果存在一个函数\(g(x)\)，使得随机变量\(X,Y\)满足：\[Y=g(X),\]则称随机变量\(Y\)是随机变量\(X\)的函数。\(X\)的统计规律决定了\(Y\)的统计规律.离散型随机变量函数的分布离散型随机变量\(X\)的函数\(Y=g(X)\)显然还是离散型随机变量。\(Y\)的概率分布完全由\(X\)的概率分布所确定。连续型随机变量函数的分布设随机变量\(X\)的密度函数为\(f_X(x)\)，分布函数为\(F_X(x)\)。用函数\(g(x)\)构造随机变量\(Y=g(X)\)，记\(Y\)的
2.4常用的连续型分布均匀分布定义如果随机变量\(X\)的密度函数为\[f(x)=\left\{\begin{align*}&\frac{1}{b-a},\quad\quada\lex\leb,\\&0,\quad\quad\quad\quadelse,\end{align*}\right.\]则称\(X\)服从\([a,b]\)上的均匀分布，记作\(X\simU[a,b]\).性质\(\int_{-\infty}^{+\infty}f(x)dx=\int_a^bf(x)dx=1\)矩形面积为1，因此区间\([a,b]\)上的常数必定为\(\frac{1}{b-a}\).分布函数：\[F(x)
2.3常用的离散型分布退化分布若随机变量\(X\)满足\[P\{X=a\}=1\]则称\(X\)服从\(a\)处的退化分布，这种情况下，随机变量退化成了一个确定的常数。两点分布定义若随机变量\(X\)只有两个可能取值，设其分布为\[P\{X=x_1\}=p,\quadP\{X=x_2\}=1-p,\quad0则称\(X\)服从\(x_1,x_2\)处参数为\(p\)的两点分布。如果\(x_1=1,x_2=0\)，则称为0-1分布或伯努利分布，也称\(X\)为伯努利随机变量。性质当\(x_1=1,x_2=0\)时，有\(EX=p,\quadDX=p(1-p)=pq\)，其中\(q=1-p\).两
2.2随机变量的数字特征离散型随机变量的数学期望设离散型随机变量\(X\)的可能值为\(x_i(i=1,2,\cdots)\)，其概率分布为\[P\{X=x_i\}=p_i,\quadi=1,2,\cdots,\]若\(\sum\limits_{i=1}^\inftyx_ip_i\)绝对收敛，则记\(E(X)=\sum\limits_{i=1}^\inftyx_ip_i\)为随机变量\(X\)的数学期望。连续型随机变量的数学期望推导过程设\(X\)是连续型随机变量，密度函数为\(f(x)\).根据密度函数的特点，有：\[P\{x_i其中，\(\Deltax_i=x_{i+1}-x_i\)趋向于
