标签:模板

OI

[POJ3630][HDU1671]Phone List[Trie]

cgazn阅读(59)评论(0)赞(0)

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

OI

[POJ3714]Raid[分治,平面最近点对]

cgazn阅读(140)评论(0)赞(0)

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

OI

[CF670C]Cinema[离散化]

cgazn阅读(140)评论(0)赞(0)

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

OI

[洛谷P3865]【模板】ST表

cgazn阅读(72)评论(0)赞(0)

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

OI

[洛谷P3384]【模板】树链剖分

cgazn阅读(57)评论(0)赞(0)

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

OI

[洛谷P1262]间谍网络[tarjan缩点]

cgazn阅读(118)评论(0)赞(0)

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

OI

[POJ2299]Ultra-QuickSort[逆序对,归并排序]

cgazn阅读(163)评论(0)赞(0)

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