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

题面 这是一道Trie树模板题. Trie树也叫字典树, 采用类似字典一样的索引方法, 把边看做字符, 把多条字符串建立成树, 达到字符串快速检索, 资瓷插入和查找两个操作. Trie树的思想一句话概括就是相同的前缀共用同一条链, 在不同的地方产生分支, 在字符串的结束位置打标记. 每个节点有size个指针指向后继, size为字符集大小, 空间复…

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

题面 根据题目要求, 求的是两组点之间的最短距离, 在求距离的时候把同一组里面点之间的距离看做inf就变成一个普通的平面最近点对问题. 平面最近点对问题用分治做, 先把点按照横坐标排序, 以中间的点为分界不断分成两个区间, 直到区间内只剩2个点, 直接返回答案, 然后再考虑点对横跨区间的情况, $ O(N^2)$枚举可能成为答案的点对. 优化就在这…

题面 n个人m个电影, 最多涉及$ n+m\times 2$种语言, 把语言离散化之后可以直接开个大数组统计每门语言会的人数, 然后选出符合要求的电影. 本题的意义在于规范了我离散化的写法.(俗称板子题). 离散化可以理解为一种把值域缩小却不改变关键性质(相对大小等)的映射, 通过选取代表元素并排序后据代表二分查找原值的方法实现. [collaps…

复习板子. 远古代码概不负责. ST表基于二进制划分思想, 用于求静态RMQ, $ O(N\log N)$预处理, $ O(1)$查询. 设$ max[i][j]$表示区间$ [i,i+2^j-1]$的最大值, 即从$ i$开始长度为$ 2^j$区间的最大值, 类似于树上倍增. 这个数组很容易预处理出来, 有DP方程$ max[i][j]=max(…

复习板子. 树链剖分可以把树上问题转化为连续线性区间上的问题, 便于使用线段树等区间问题的工具来处理, 也可以把树上进行的操作的效率大大提高如求解LCA等等. 树剖的思路其实不难, 主要是代码长... 考虑如何把一棵树通过编号处理成尽量少的链, 同时保证每棵子树/每条链的编号都连续. 容易发现dfs序就满足前者, 这样就保证了每棵子树都在一个连续区…

复习下树上常见算法... 本文中都是远古代码, 一切Bug概不负责. lca最暴力的求法就是x,y一次次往上跳, 这样效率显然很低, 考虑优化, 有两种途经: 树上倍增 dfs预处理一个倍增找父亲节点的数组, x,y成倍的往上跳, 时间复杂度降为log级 通常树上倍增的套路都是设$ F[i][j]$为节点$ i$的第$ 2^j$个父亲, 那么有$ …

题面 tarjan缩点模板题 tj的思路: 强连通分量可以相互到达, 必定在一个环上, 一次dfs找出所有尽量大的环即可. sta里面是表示当前所有可能能构成强连通分量的点, 追溯值low[x]表示点x及其子孙节点连的所有点中dfn的最小值, 如果遇到环就会发现不能再往下搜, 接着会一直回溯至进入环的点x(low[x]=dfn[x], 途中要从后往…

题面 题目求冒泡排序的最小交换次数.冒泡排序交换一次即减少一个逆序对,所以总交换次数就是逆序对数.用归并排序求出即可. 求逆序对通常用归并排序(树状数组也可以), 统计在两区间合并的过程中产生的逆序对就可以算上所有的逆序对, 因为归并排序实际上已经把整个数列的操作完美化为了许多最小子问题, 不会有重复和遗漏. [collapse title="展开…