索引（填坑进度：0.1‰）

博客三迁

现在挂在博客园上面，至少比CSDN快一丢丢
http://www.cnblogs.com/P6174/

傻傻分不清楚：XX二叉树

英语里的Full/Complete/Perfect Binary Tree是比较统一的，但是英译中的争论由来已久，最常见的是Full Binary Tree被吃了，Perfect Binary Tree译为满二叉树；有些地方则是Perfect Binary Tree译为完全二叉树，Complete Binary Tree译为满二叉树，并且好像两种译法都不在少数。除此之外，平衡二叉树与AVL树也在很多人甚至很多书里混为一谈。下面这种译法反而罕见（我基本上没见过翻译“完美二叉树”的），但P6174觉得这种译法才是最标准的，所以在此说明，以后的博客涉及这几种树时的译法如下：

833B/834D. The Bakery

题目描述

前段时间甜心公主Slastyona打算自己开一间烘焙坊！她买了所需的配料和一个神奇烤箱。这个神奇烤箱可以烘焙多种蛋糕，并自行给烘焙坊挂上“营业”的牌子。
不久后，烘焙坊开始入不敷出，所以Slastyona打算研究甜点市场。她发现，盒装销售的蛋糕比散装的利润更高，并且盒子里装的蛋糕种类越多（把蛋糕种类的数目称为这盒蛋糕的价值），售价就越高。
她决定革新生产工艺！问题是，Slastyona无法选择烘焙什么类型的蛋糕，而是由神奇烤箱自己决定的。幸好她知道，今天神奇烤箱想烘焙n个蛋糕，还知道每个蛋糕的种类与烘焙的先后顺序。Slastyona要用k个盒子（不能多不能少）包装这n个蛋糕。神奇烤箱会一个接一个的烘焙蛋糕，而她需要往盒子里放上烘焙时连续生产的一些（至少一个）蛋糕。
帮助Slastyona确定包装这k盒蛋糕可能的最大价值。
输入共两行，第一行包括两个整数n和k(1 ≤ n ≤ 35000, 1 ≤ k ≤ min(n, 50))
第二行包括n个整数a₁, a₂, …, a_n (1 ≤ a_i ≤ n)按照烘焙的先后顺序排列的这n个蛋糕的种类。
输出一个整数，表示包装这k盒蛋糕可能的最大价值。

官方题解

定义dp(k,n)为

线段树：基础结构（填坑）

张昆玮大佬的《统计的力量——线段树全接触》实在是看得不明觉厉一脸懵逼，所以线段树这种非常灵活的数据结构我可能会写很多篇，在此预告，不过用线段树做RMQ我就不另外开坑写《线段树：RMQ》了，到时候会写在一篇老长的RMQ讲解里面的（笑）。

一、线段树的结构与结点

（一维）线段树是一棵完美二叉树，且每个结点表示的是一个“线段”，或者说是一个区间。一棵线段树的根节点表示的是整个区间，而它的左右子树也是一棵线段树，分别表示的是这个区间的左半边和右半边。
线段树的结点这样子写：

strcut Tnode {
  int 结点的值, 其它标记;
} tree[maxn];

结点的值是由问题决定的，对于动态RMQ，结点的值便是结点所表示的数组区间内的最小值；对于动态区间和，则是数组区间内的和；而对于第k大数，
那么，对于所有的非叶子结点，

子字符串查找：KMP、Boyer-Moore、Sunday、Rabin-Karp

子字符串查找问题：在一段有N个字符的文本S中找到一段有M个字符的“模型”字符串P，并返回匹配处的下标。当然也可以拓展为找到所有的模型或是统计模型的数量。

一、朴素算法

如果用暴力匹配的思路，并假设现在匹配到S_i，P_j，则有：
如果当前字符匹配成功（即 S_i=P_j），则i++，j++，继续匹配下一个字符；
如果失配（即 S_i≠P_j），令i=i-j+1，j=0。即，i回溯，j清零。

NHOI2015E 黄金矿工

比较基础的分组背包问题。

在那些多色线段上，每个与方格格点的交点都可以埋藏一个物品。显然，在每条线段上，要取距坐标原点远的物品，一定要先取这条线段上距坐标原点近的所有物品。将这条线段上的物品按照到原点的距离从近到远编号为1~x，那么可能的情况有不取、取第1件物品、取前2件物品、取前3件物品……取前x件物品（全取）共(x+1)种情况。因此，按线段分组，每一组里包含了这条线段上的(x+1)种情况即可

一个脑洞

设n∈ℕ，有(2*n)个整数组成一个环形，每个相邻整数之间的差为0或1。
求证：一定有至少一对中心对称（在整数甲与整数乙间顺时针数，无论是从甲数到乙还是从乙数到甲，都相隔n-1个整数）的整数相等。
推广到实数集也可，这里用一个更有趣的例子：假设地球是个完美的球体，但各处的气压不等（当然气压是连续的）。一对CP站在赤道上，求证：这对CP一定可以找到两个对称的点，使得两点的海拔相等。

NHOI2015C 树

按照某老师说的保密要求，题目不放上来，要原题的请在评论区附上证明自己是南海区学生的证明
那这题作为填坑第一弹是因为突然想起那时候眼睁睁看着wyl写了好几个优化版本而我连题目都看不懂，虽然现在看这题目很简单（笑cry）。
说一下做法。标程错了三个点已无力吐槽……
自己的做法是在线做法（在线：读一组处理一组，相对应的是离线，全部读入后再处理）。每读入一条边，这条边连接的俩结点有5种情况：

堆、优先队列、堆排序

可以插入元素和删除最大/小元素的数据类型叫优先队列（以下均为删除最大元素）。
如果用有序数组实现优先队列，易得插入为O(N)（插入排序），删除为O(1)；如果用无序数组实现，插入为O(1)，删除为O(1)（遍历整个数组）。而用堆实现能够保证插入与删除的时间复杂度都为O(logN)。