wxyww

分类

未归档(12) 精品(28) 题解(65)

/ 注册

全部文章（共395篇）

LCA

LCA LCA（Lowest CommonAncestors），即最近公共祖先，是指在有根树中，找出某两个结点u和v最近的公共祖先一般采用倍增的方法来求最近公共祖先。还可以用树链剖分。dfs序似乎也可以思路用数组fa[i][j]表示从i往上跳2j步所得到的祖先。用dep[i]表示i的深...

最近公共祖先

2018-08-13

0 378

斜率优化dp

dp的状态和转移方程就足够让人头疼，却还有一些普通dp复杂度不够优秀的题目要用优化。。。 dp的解题方法似乎只能通过讲解题目来完成。一道例题：洛谷3195 题目描述 P教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩，其可以将任意物品变成一堆，...

动态规划dp

2018-08-07

0 397

斜率优化dp

dp的状态和转移方程就足够让人头疼，却还有一些普通dp复杂度不够优秀的题目要用优化。。。 dp的解题方法似乎只能通过讲解题目来完成。一道例题：洛谷3195 题目描述 P教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩，其可以将任意物品变成一堆，...

动态规划dp

2018-08-07

0 546

树链剖分&dfs序

树上问题　　很多处理区间的问题（像是RMQ，区间修改）。可以用线段树，树状数组，ST表这些数据结构来维护。但是如果将这些问题挪到了树上，就不能直接用这些数据结构来处理了。这时就用到了dfs序和树链剖分。 DFS序　　dfs序就是按照dfs的顺序对一棵树上的结点进行编号。这样完成编号的优点是...

数据结构

2018-08-06

0 407

树链剖分&dfs序

树上问题　　很多处理区间的问题（像是RMQ，区间修改）。可以用线段树，树状数组，ST表这些数据结构来维护。但是如果将这些问题挪到了树上，就不能直接用这些数据结构来处理了。这时就用到了dfs序和树链剖分。 DFS序　　dfs序就是按照dfs的顺序对一棵树上的结点进行编号。这样完成编号的优点是...

数据结构

2018-08-06

0 540

trie树

trie树？？？　　trie树是一种树形结构，可以用来找前缀固定的字符串。思想　　其实思想很简单，就是将每个字符串都挂到树上去，如果当前节点在之前已经有了就不用新建节点，可以继续前面的向下找。否则就新建一个节点，这样就节省了时间和空间。具体实现　　代码一看就懂了，不多bb 板子...

字符串

2018-08-05

0 471

trie树

trie树？？？　　trie树是一种树形结构，可以用来找前缀固定的字符串。思想　　其实思想很简单，就是将每个字符串都挂到树上去，如果当前节点在之前已经有了就不用新建节点，可以继续前面的向下找。否则就新建一个节点，这样就节省了时间和空间。具体实现　　代码一看就懂了，不多bb 板子...

字符串

2018-08-05

0 459

单调队列

　单调队列就是维护一个队列，使得该队列从队首到队尾成单调递增或是单调递减。　做法就是每向队列里加入一个元素就判断该元素是不是比队尾元素大（以递减序列为例），是的话就将队尾元素出列，直到该元素比队尾元素小，然后将该元素放置队尾。　　这么久了一直不明白单调队列的实现，现在看来，原来这么简单。。。...

数据结构

2018-08-04

0 471

单调队列

　单调队列就是维护一个队列，使得该队列从队首到队尾成单调递增或是单调递减。　做法就是每向队列里加入一个元素就判断该元素是不是比队尾元素大（以递减序列为例），是的话就将队尾元素出列，直到该元素比队尾元素小，然后将该元素放置队尾。　　这么久了一直不明白单调队列的实现，现在看来，原来这么简单。。。...

数据结构

2018-08-04

0 394

网络流24题——试题库问题

题目链接：luogu2763 题目描述 «问题描述：假设一个试题库中有n道试题。每道试题都标明了所属类别。同一道题可能有多个类别属性。现要从题库中抽取m 道题组成试卷。并要求试卷包含指定类型的试题。试设计一个满足要求的组卷算法。 «编程任务：对于给定的组卷要求，计算满足要求的组卷方案。...

2018-07-23

0 445