Link with Bracket Sequence II Link with Bracket Sequence II 思路 区间dp，这个之前没写过，记一下这个题。一般形式就三个循环，从外到里枚举区间长度，区间起点，分割点。这题用f[i] [j]记录，[i,j]是合法序列且i,j是匹配的括号的方案数,g[i] [j]表示[i,j]是合法序列的方案数。 转移：f[i] [j]=k*g[i+1] [j-1]，k为i,j上可匹配的括号数。 g[i] 2022-07-29 算法 题解 区间dp 2022“杭电杯”中国大学生算法设计超级联赛
dijkstra模板 dijkstra最短路 1234567891011121314151617priority_queue<pii,vector<pii>,greater<pii> >q;for(int i=0;i<2*N+10;i++)dis[i]=inf;dis[st]=0;q.push(pii(0,st));//first-路程 second-序号while(!q.e 2022-05-18 算法 模板 模板 dijkstra 最短路
线段树优化建图 线段树优化建图 这是利用线段树优化建图的算法，当出现区间1->n的区间连边操作时，一般的图就需要O(n)的复杂度，但是利用线段树就可以做到O(logn),很好用。 例题 题意 Rick 和他的同事们做出了一种新的带放射性的婴儿食品(???根据图片和原文的确如此...)，与此同时很多坏人正追赶着他们。因此 Rick 想在坏人们捉到他之前把他的遗产留给 Morty。 在宇宙中一共有 2022-05-18 算法 模板 模板 数据结构 最短路 线段树 图论
树链剖分 树链剖分 树链剖分，是将树的结构分解成几条链的线性结构的算法。本以为是很复杂精细的算法，实际上却非常暴力而且码量不小。好处是化树形为线形后可以使用线段树或者树状数组等方便的数据结构，而且算法本身并不复杂而且容易理解，总的来说除了码量大还是优点多多。 例题：P3384 【模板】轻重链剖分/树链剖分 题目描述 如题，已知一棵包含 N 个结点的树（连通且无环），每个节点上包含一个数值，需要支 2022-05-07 算法 模板 模板 数据结构 树链剖分 线段树
cdq分治 cdq分治 cdq分治是cdq创造的一种分治算法，分治的思想就是划分问题，解决子问题，合并答案 cdq分治则是在合并子区间时，考虑左区间对右区间的影响，换言之，cdq分治解决的是前对后（按某种顺序）的单向影响的问题。 例题 P3810 【模板】三维偏序（陌上花开） 题目背景 这是一道模板题，可以使用 bitset，CDQ 分治，KD-Tree 等方式解决。 题目描述 有 n 个元 2022-04-26 算法 笔记 模板 cdq分治 数据结构
绿豆蛙的归宿 绿豆蛙的归宿 题目描述 给出张 n 个点 m 条边的有向无环图，起点为 1，终点为 n，每条边都有一个长度，并且从起点出发能够到达所有的点，所有的点也都能够到达终点。 绿豆蛙从起点出发，走向终点。 到达每一个顶点时，如果该节点有 k 条出边，绿豆蛙可以选择任意一条边离开该点，并且走向每条边的概率为 \(\frac{1}{k}\) 。现在绿豆蛙想知道，从起点走到终点的所经过的路径总长度 2022-04-22 算法 题解 期望dp 拓扑序