标签：模板

2019-08-03cgazn阅读(365)评论(0)赞(0)

题面 以斐波拉契数列为例, 要从矩阵A $$ \begin{bmatrix} f[n-1] & f[n]  \end{bmatrix} $$ 得到矩阵B $$ \begin{bmatrix} f[n] & f[n+1]  \...

2019-07-27cgazn阅读(112)评论(0)赞(0)

题面 这是一道Trie树模板题. Trie树也叫字典树, 采用类似字典一样的索引方法, 把边看做字符, 把多条字符串建立成树, 达到字符串快速检索, 资瓷插入和查找两个操作. Trie树的思想一句话概括就是相同的前缀共用同一条链, 在不同的...

2019-07-26cgazn阅读(186)评论(0)赞(0)

题面 本题的意义在于告诉你有二维前缀和这个东西, 不能再水了. 定义点(x,y)的二维前缀和S为: $$S[x,y]=\sum_{i=1}^{x}\sum_{j=1}^{y}a[i,j]$$ 我们可以$latex O(N^2)$地递推出S数...

2019-07-26cgazn阅读(355)评论(0)赞(1)

题面 根据题目要求, 求的是两组点之间的最短距离, 在求距离的时候把同一组里面点之间的距离看做inf就变成一个普通的平面最近点对问题. 平面最近点对问题用分治做, 先把点按照横坐标排序, 以中间的点为分界不断分成两个区间, 直到区间内只剩2...

2019-07-24cgazn阅读(332)评论(0)赞(0)

题面 n个人m个电影, 最多涉及$latex n+m\times 2$种语言, 把语言离散化之后可以直接开个大数组统计每门语言会的人数, 然后选出符合要求的电影. 本题的意义在于规范了我离散化的写法.(俗称板子题). 离散化可以理解为一种把...

2019-07-23cgazn阅读(158)评论(0)赞(0)

复习板子. 远古代码概不负责. ST表基于二进制划分思想, 用于求静态RMQ, $latex O(N\log N)$预处理, $latex O(1)$查询. 设$latex max[i][j]$表示区间$latex [i,i+2^j-1]$...

2019-07-23cgazn阅读(122)评论(0)赞(0)

复习板子. 树链剖分可以把树上问题转化为连续线性区间上的问题, 便于使用线段树等区间问题的工具来处理, 也可以把树上进行的操作的效率大大提高如求解LCA等等. 树剖的思路其实不难, 主要是代码长… 考虑如何把一棵树通过编号处理成...

2019-07-23cgazn阅读(165)评论(0)赞(0)

复习下树上常见算法… 本文中都是远古代码, 一切Bug概不负责. lca最暴力的求法就是x,y一次次往上跳, 这样效率显然很低, 考虑优化, 有两种途经: 树上倍增 dfs预处理一个倍增找父亲节点的数组, x,y成倍的往上跳, ...

2019-07-22cgazn阅读(257)评论(0)赞(0)

题面 tarjan缩点模板题 tj的思路: 强连通分量可以相互到达, 必定在一个环上, 一次dfs找出所有尽量大的环即可. sta里面是表示当前所有可能能构成强连通分量的点, 追溯值low[x]表示点x及其子孙节点连的所有点中dfn的最小值...

2019-07-22cgazn阅读(305)评论(0)赞(0)

题面 题目求冒泡排序的最小交换次数.冒泡排序交换一次即减少一个逆序对,所以总交换次数就是逆序对数.用归并排序求出即可. 求逆序对通常用归并排序(树状数组也可以), 统计在两区间合并的过程中产生的逆序对就可以算上所有的逆序对, 因为归并排序实...