Dream

基本介绍

约瑟夫环问题都很熟悉了，这里也就不多赘述了。

主要是来记录一下，约瑟夫环的一些解法。

题目大意

张老师设计了一个智能调度系统来控制他的遥控车队，今天，他带着他的车队来到黄渡理工大学的一块空地上测试这个系统。
这块空地可以描述为一个 w * h 大小的长方形，广场上有一些障碍物，几个目标点，当然，还有张老师的车队。
每分钟，调度系统会智能地向其中的一辆遥控车发送以下指令的其中一条：

1. ​ 向北走，直到撞到空地的边界、障碍物或其他遥控车；

2. ​ 向南走，直到撞到空地的边界、障碍物或其他遥控车；

3. ​ 向西走，直到撞到空地的边界、障碍物或其他遥控车；

4. ​ 向东走，直到撞到空地的边界、障碍物或其他遥控车；

   ​ 每条指令都会在一分钟之内完成，也就是说，空地上最多只有一辆遥控车在运动。此外，当遥控车无法向相应的方向移动时，它会停在原地。

   你想知道，在第 k 分钟时，有没有可能有任意一辆遥控车处在任意一个目标点上。

基本介绍

树形dp顾名思义就是在“树”上进行动态规划，通过遍历树等一些操作来完成题目要求。

在树形动态规划中是建立在树上的，由树中的父节点和子节点的关系推出来的。

一般有两种。

1、就是由子节点推到父节点，即根的子节点传递有用的信息给父节点，最终有父节点再求出最优解。（此形式较为常用）

2、从父节点推至子节点，这种情况的意思是需要取所有点来求出父节点的值，再减去要除的子节点的dp状态，再将其转移，这样就可由根节点推至叶节点。

通常使用链式前向星来建树。

算法介绍

简单来说，数位DP就是在数的每一位上进行DP，可以说是另类的暴力枚举了。

相比于简单的暴力枚举来说，数位DP具有记忆化的特点。

其实我感觉数位DP和状压DP有一点类似。

也是对每一位来进行DP。

拓欧介绍

简单来说，拓欧就是求关于x，y的方程$ax+by=gcd(a,b)$的所有整数解。

这里就简单的证一下，详细证明点这里

拓展域，个人感觉算是并查集中比较难的部分了。（网上都没什么详细的教学。。。全靠理解代码

简而言之，就是用多个并查集，多个空间，来表示节点之间的一些相互关系，比如x的敌人，x的朋友，我需要找到x的敌人的敌人，就也是我的朋友，x的敌人的朋友，就也是我的敌人。（【NOIP 2010 提高组】关押罪犯）

题目大意

小明有一根长度为a的木棒，现在小明想将木棒分为多段（每段木棒长度必须为整数），
使得分隔后的木棍中，取出的任意三段都不能构成三角形，小明想知道木棒最多被分成几段？

题目大意

给你一些数字，你可以进行一种操作，令一个区间的数字减少1，问令这些数字全为1的最小操作数。

基本介绍

区间dp，简单来说就是以一个子区间为最小元素，一步步递推到根区间的过程。就是通过一个个小区间的最优解来推出大区间的最优解的过程。

二叉搜索树基本介绍

给定一棵二叉树，树上的每一个节点带有一个数值，称为节点的关键值$val$。

对于树上的每一个节点：

1、该节点的关键码不小于它的左子树任意节点的关键码

2、该节点的关键码不大于它的右子树任意节点的关键码

这样的树就叫做二叉查找树（二叉排序树），即BST。