Trie树又称字典树，前缀树。是一种可以高效查询前缀字符串的树，典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。

它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。`做题看到大量字符串或者大量字符就往Trie树或者哈希这边想，因为速度很快.

image.png

全民制作人ikun大约 10 分钟

[NOIP2016 提高组] 换教室

链接：https://www.luogu.com.cn/problem/P1850

题目描述

对于刚上大学的牛牛来说，他面临的第一个问题是如何根据实际情况申请合适的课程。

在可以选择的课程中，有 $2n$ 节课程安排在 $n$ 个时间段上。在第 $i$ （ $1 \leq i \leq n$ ）个时间段上，两节内容相同的课程同时在不同的地点进行，其中，牛牛预先被安排在教室 $c_i$ 上课，而另一节课程在教室 $d_i$ 进行。

全民制作人ikun大约 9 分钟

概率DP

Bag of mice

题面翻译

https://www.luogu.com.cn/problem/CF148D

袋子里有 $w$ 只白鼠和 $b$ 只黑鼠，A和B轮流从袋子里抓，谁先抓到白色谁就赢。A每次随机抓一只，B每次随机抓完一只之后会有另一只随机老鼠跑出来。如果两个人都没有抓到白色则B赢。A先抓，问A赢的概率。

全民制作人ikun大约 9 分钟

数位DP

数字游戏

题目

链接：https://www.acwing.com/problem/content/1084/

科协里最近很流行数字游戏。

某人命名了一种不降数，这种数字必须满足从左到右各位数字呈非下降关系，如 $ 123 $，$ 446 $。

全民制作人ikun大约 6 分钟

树形DP

树的重心

题目

链接：https://www.acwing.com/problem/content/848/

给定一颗树，树中包含 $ n $ 个结点（编号 $ 1 \sim n $）和 $ n-1 $ 条无向边。

请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。

重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。

全民制作人ikun大约 6 分钟

区间DP

石子合并（弱化版）

题目描述

https://www.luogu.com.cn/problem/P1775

设有 $N(N \le 300)$ 堆石子排成一排，其编号为 $1,2,3,\cdots,N$ 。每堆石子有一定的质量 $m_i(m_i \le 1000)$ 。现在要将这 $N$ 堆石子合并成为一堆。每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻。合并时由于选择的顺序不同，合并的总代价也不相同。试找出一种合理的方法，使总的代价最小，并输出最小代价。