树状数组介绍树状数组，顾名思义，就是树状的一维数组。二叉树同样也可以用一维数组存储。我们以二叉树进行类比。如图所示，图中节点的序号就是存在数组中的下标。记父节点序号为\(p\),子节点序号为\(s\)。则有:\(p\)\(=\)\(s\)\(/\)\(2\)(向下取整)。左子节点\(s_{left}\)\(=\)\(p\)\(*2\)。右子节点\(s_{right}\)\(=\)\(p\)\(*2+1\)。综上可知，二叉树能用一维数组存，是由于其父子节点间存在一定关系，以至于不需要用额外的变量来表示信息。那类比到树状数组中，可以发现：\(c\)数组即为树状数组。\(c_i\)表示区间\(a\)
前言今日偶然打开\(oi-wiki\)，发现树形\(DP\)例题正好是之前在洛谷上鸽着的一道题。所以......\(\color{red}{很高兴以这样的方式认识你，树形DP!}\)这例题造的太好了，简直是无痛入门（感动.jpg）P1352没有上司的舞会题目传送门~思路剖析状态定义\(dp_i\)表示的是以\(i\)为根节点的子树所获得的最大价值。由于每个节点代表着一位人物，有来与不来两种状态，所以再加一维状态变量。\(dp_{i,0}\)表示以\(i\)为根节点的子树所能获得的最大价值，且这位人物没来。\(dp_{i,1}\)则对应来了的状态。状态转移方程现在有个周年庆宴会，宴会每邀请来一个
题目传送门前言今天依旧是不写高精的一天呢！（是的，这位作者又只拿了开\(LL\)的\(\color{yellow}{60}\)分）思路描述看到数据\(n,m\le80(30)\)就知道数组可以任性开，心理有个底后，再来看题目。状态描述首先肯定要来一个\(dp_{i,j}\)来表示第\(i\)次时取第\(j\)行的数。对于每一次放置，我们要考虑到的是之前每一次都取到什么,也就是现在的头和尾分别是哪两个数。想明白这一点，就可以描述状态了。\(dp_{i,j,k,t}\)表示第\(i\)次时取第\(j\)行的数，对于第\(j\)行，它的行首被取了\(k\)个数，他的行尾被取了\(t\)个数。由于$t
1.利用状态方程求传递函数公式状态方程为\(G(s)=\dfrac{Y(s)}{U(s)}=C(sI-A)^{-1}B+D\)例1：\(m-c-k\)系统，求\(m\overset{··}{x}+c\overset{·}{x}+kx=f\)传递函数。解：令\(x_1=x\)，\(x_2=\overset{·}{x}\)则有：\[\begin{cases}\overset{·}{x_1}=x_2\\\overset{·}{x_2}=\dfrac{1}{m}[-cx_2-kx_1]+\dfrac{f}{m}\end{cases}\]根据状态方程的向量表达式和输出方程的向量表达式\[\begin{c
1.利用状态方程求传递函数公式状态方程为\(G(s)=\dfrac{Y(s)}{U(s)}=C(sI-A)^{-1}B+D\)例1：\(m-c-k\)系统，求\(m\overset{··}{x}+c\overset{·}{x}+kx=f\)传递函数。解：令\(x_1=x\)，\(x_2=\overset{·}{x}\)则有：\[\begin{cases}\overset{·}{x_1}=x_2\\\overset{·}{x_2}=\dfrac{1}{m}[-cx_2-kx_1]+\dfrac{f}{m}\end{cases}\]根据状态方程的向量表达式和输出方程的向量表达式\[\begin{c
题目类型总结最近在阅读《算法竞赛进阶指南》这本书的链表这一节时，学会了链表在一类特定问题中的巧妙用法，遂有此文，也算是自己的一个学习笔记。考虑这样一类问题，一个长度为\(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 在这个论文里提出了一种
