原题链接

题目描述

​ Michael 喜欢滑雪。这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael 想知道在一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子：

1
2
3
4
5

1   2   3   4   5
16  17  18  19  6
15  24  25  20  7
14  23  22  21  8
13  12  11  10  9

​ 一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度会减小。在上面的例子中，一条可行的滑坡为 $24－17－16－1$（从 $24$ 开始，在 $1$ 结束）。当然 $25－24－23－\ldots－3－2－1$ 更长。事实上，这是最长的一条。

原题链接

题目描述

​ 呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第 $i$ 层楼$(1 \le i \le N)$ 上有一个数字 $K_i(0 \le K_i \le N)$。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如： $3, 3 ,1 ,2 ,5$ 代表了$K_i(K_1=3,K_2=3,…)$，从 $1$ 楼开始。在 $1$ 楼，按“上”可以到 $4$ 楼，按“下”是不起作用的，因为没有 $-2$ 楼。那么，从 $A$ 楼到 $B$ 楼至少要按几次按钮呢？

题意简述

​ 有 $n$ 个人围坐成环，从 $1$ 开始传递，每次可将球传给相邻的人，问 $m$ 次传递后回到 $1$ 的方案数。

原题链接

题意简述

给出 $n$ 头奶牛，每头可分为三种，对于 $q$ 次询问，给出区间内各种奶牛的数量。

update on 2020.4.5 新增 tarjan 算法。

前言

​ LCA（Lowest Common Ancestor），即最近公共祖先。在一张图中，要找到两个节点的最近公共祖先，最朴素的算法就是分别从两个节点一层一层向上寻找，直到跳到一个相同的点，这个点就是两者的最近公共祖先。这样查找花费的时间代价太大，我们难以承受，于是就有了几种求LCA的算法。

前言

​ 在洛谷上刷题时遇见这么一道题 P1009 阶乘之和 ，题面简单好理解，适合和我一样菜的 OIer。二话不说，我抄起手中一把梭。

​ 提交，Judge，一气呵成。

​ 然而50Pts…

前言

​ 在洛谷上刷题时遇见这么一道题 P1009 阶乘之和 ，题面简单好理解，适合和我一样菜的 OIer。二话不说，我抄起手中一把梭。

​ 提交，Judge，一气呵成。

​ 然而50Pts…

线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。

线段树可以在$\mathcal{O}(log N)$的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。

线段树维护的信息，需要满足可加性，即能以可以接受的速度合并信息和修改信息，包括在使用懒惰标记时，标记也要满足可加性（例如取模就不满足可加性，对 取模然后对 取模，两个操作就不能合并在一起做）。

​ ——OI Wiki

​ update on 2020.2.27 修改了标程，适当的压行

​ update on 2020.8.5 完善了措辞，更改了示例图片

​ 以此题作为树形DP的入门。

树形 DP，即在树上进行的 DP。由于树固有的递归性质，树形 DP 一般都是递归进行的。——OI Wiki