嗯哼，接下来如果没有意外以及我不咕咕咕的话，每周都有一篇这样的集训队笔记和解题报告（停了大半年又要回归啦）。写这个东西一来是巩固一下上课学到的知识，二来是存下一点代码和思路以后做题想不起来就翻一下；三是丰富一下博客的内容。如果没有意外的话，更新会隔一周。
本期主要内容：基础数据结构，卡特兰数，表达式处理，单调队列和单调栈，优先队列和堆，二分法。
栈与括号序列匹配 —— 卡特兰数
进出栈序列：n 个元素按照 $1, 2, …, n$ 的顺序进栈，问有多少种可能的出栈序列？
显然，对于 $n = 1$ 的情况下，只可能有一种出栈序列；对 $n = 2$ 的情况，可能是：1进1出，2进2出 或 1进2进，2出1出，有两种不同的序列。那么对于更多的 $n$ 呢？
括号序列匹配：有 $n$ 对左右括号，请求出合法的排列有多少个？
它基于这样的一个原则：每出现一个左括号，必定有一个右括号与它匹配。并且，一定先出现左括号，再出现对应的右括号。例如，当括号序列数目 $n=1$ 的时候，合法的匹配序列：$()$, 不合法的匹配序列：$)($.
可以看出，这两个问题属于同一个模型，这个问题模型与组合数学的一个经典概念——卡特兰数有关。首先是卡特兰数的结论：递推公式 $f(n)=\Sigma_{k=0}^{n-1}f(k)\cdot f(n-k-1), f(0) = 1$;
展开递推公式得到 $f(n)=C_{2n}^{n}x-C_{2n}^{n+1}=\frac{1}{n+1}C_{2n}^{n}$.
以进出栈序列的问题为例，设 $f(n)$ 为序列个数为 $n$ 的出栈序列数，假定这 $n$ 个元素的其中一个元素 $k$ 为最后出栈的元素，那么：首先进栈了 $k-1$ 个元素 $1, 2, …, k-1$，然后全部弹出，弹出栈的顺序序列记为 $s_1$；然后让 $k$ 入栈；再由剩下的 $n-k$ 个元素 $k+1, …, n$ 进栈，再全部弹出，最后 $k$ 出栈。这部分弹出的顺序序列记为 $s_2 + k$。
在这种情况下，因为 $s_1$ 和 $s_2$ 互不影响，它们各自独立，因此这种情况下总的出栈序列 $s_k = s_1 + s_2 + k$，$s_k$ 可能的出栈序列数目便是 $s_1, s_2$ 两个序列数量的相乘，即 $f_{s_k}(n) = f(k-1) \cdot f(n-k)$（注意卡特兰数的递推公式是从 $x=0$ 开始定义的）. 那么，让最后一个出栈的序列为第 $0, 1, …, n-1$ 个；
令 k 取 $0, …, n-1$，我们就能得到卡特兰数的递归定义，从而可以直接套公式解决该问题。
括号序列匹配数量的问题事实上是相同的，区别就在于将进栈、出栈分别视为左右括号；括号数目视为元素 $1, 2, …, n$，问题就转化为了上面的模型。
例题链接：Vijos P1122 出栈序列统计
#include <cstdio>
double getCatalan(int x)
{
double res = 1.0;
for (int i = x + 1; i <= 2 * x; i++)
res *= ((double)i / (double)(i-x));
return (res / (x + 1));
}
int main()
{
int n;
scanf("%d", &n);
printf("%.0lf", getCatalan(n));
return 0;
}
栈与表达式处理
表达式处理与解析这个问题在讲栈的时候已经老生常谈了，这里就直接复述一遍大概思路就好了。
首先是集训的时候讲的，处理简单表达式(没有括号，加法和乘法)的思路：从左到右扫描表达式，遇到操作数先加入栈中；如果遇到加法运算符，则先不做任何操作；如果遇到乘号，则将栈顶的元素取出、并取乘号后的一个数，相乘后丢进栈中。最后再将栈中的所有元素相加。
对于大部分表达式都适用的解析处理操作如下：
首先将中缀表达式转化为后缀表达式：
- 从左到右扫描表达式，每遇到一个操作数，就直接添加到后缀表达式中。
- 栈为空的时候，若遇到运算符，直接入栈。
- 遇到左括号将其入栈；遇到右括号，弹出栈顶的运算符添加到表达式中，直到弹出栈的是左括号为止。
- 栈不为空时，遇到加减乘除运算符，弹出栈顶所有优先级大于等于该运算符的运算符加入表达式，直到栈为空或遇到左括号为止，再将该运算符入栈。
- 表达式扫描完成后将栈顶元素全部弹出，加入后缀表达式中。
那么，计算后缀表达式呢？这就很简单啦：
- 从左到右扫描表达式，遇到操作数就将其加入栈中
- 遇到操作符，则弹出栈顶的两个数 $s_2, s_1$（注意先后顺序），进行运算后将新的结果加入栈中
最后栈中的数即为结果。
#include <iostream> #include <string> #include <stack> using std::string; using std::cout; using std::endl; using std::stack; bool shouldPopFromStack(char current, char fromStack) { int p1 = (current == '*' || current == '/') ? 1 : 0; int p2 = (fromStack == '*' || fromStack == '/') ? 1 : 0; return p1 <= p2; } string convert(string raw) { int length = raw.length(); stack<char> s; string res = ""; for (int i = 0; i < length; i++) { // 遇到数字，直接加入后缀表达式中 if (raw[i] >= '0' && raw[i] <= '9') { res += raw[i]; continue; } else { res += ' '; } // 遇到左括号，入栈 if (raw[i] == '(') { s.push('('); } // 遇到右括号，本身不加入表达式， 让栈中元素出栈，直至遇到左括号 else if (raw[i] == ')') { while (true) { char now = s.top(); s.pop(); if (now == '(') { break; } else { res += now; } } } // 运算符 else { // 分为栈为空与不为空两种情况讨论 if (s.empty()) { s.push(raw[i]); // 栈为空，直接加入 } else { // 否则，弹出栈顶元素加入表达式，直到遇见左括号，然后自己入栈 while (!s.empty()) { char now = s.top(); if (now == '(' || !shouldPopFromStack(raw[i], now)) { break; } else { s.pop(); res += now; } } s.push(raw[i]); // 最后别忘了把自己加进去 } } } res += ' '; // 完成后把栈中剩余符号加入表达式 while (!s.empty()) { char now = s.top(); s.pop(); res += now; } return res; } int main() { string raw; std::cin >> raw; std::cout << "Original expression: " << raw << endl; string res = convert(raw); std::cout << "Parsed expression: " << res << endl; stack<long long> s; int length = res.length(); long long cur = 0; for (int i = 0; i < length; i++) { // 遇到数字就入栈 if (res[i] >= '0' && res[i] <= '9') { cur = cur * 10 + res[i] - '0'; } else if (res[i] == ' ') { s.push(cur); cur = 0; } // 否则，弹出栈顶的两个数计算，注意先后顺序 else { long long s2 = s.top(); s.pop(); long long s1 = s.top(); s.pop(); switch (res[i]) { case '+': s.push(s1 + s2); break; case '-': s.push(s1 - s2); break; case '*': s.push(s1 * s2); break; case '/': s.push(s1 / s2); // 可能会有小数 break; } } } long long ans = s.top(); std::cout << ans; return 0; }
例题链接：Vijos 1849 表达式求值
这道题没有括号，只有加乘没有减除，所以属于我们刚刚提到的最简单的一类情况：
#include <iostream>
#include <string>
#include <stack>
using std::string;
using std::stack;
using std::cin;
using std::cout;
stack<long long> s;
int main()
{
string exp;
cin >> exp;
int len = exp.length();
bool flag = 0;
long long cur = 0;
for (int i = 0; i < len; i++) {
if (exp[i] >= '0' && exp[i] <= '9') {
cur = cur * 10 + exp[i] - '0';
} else {
if (flag) {
long long next = s.top();
s.pop();
cur = (next * cur) % 10000;
flag = 0;
}
s.push(cur);
cur = 0;
}
if (exp[i] == '+') {
flag = 0;
continue;
} else if (exp[i] == '*') {
flag = 1;
continue;
}
}
if (flag) {
cur = (cur * s.top()) % 10000;
s.pop();
}
s.push(cur);
long long ans = s.top();
s.pop();
while (!s.empty()) {
ans = (ans + s.top()) % 10000;
s.pop();
}
cout << ans % 10000;
return 0;
}
二叉树的先、中、后序遍历
有关先序、中序、后序遍历的概念这里就不细讲了，总之先序是根-左-右，中序是左-根-右，后序是左-右-根。给定中序和后序遍历可以确定先序，给定中序和先序遍历可以确定后序。
例题链接：Vijos 1132 求二叉树的先序序列
根据中序遍历和后序遍历的结果把二叉树建出来就行了，建树的思路是这样的：考虑一颗子树序列 $s_c$，后序遍历的最后一个字母一定是根节点；再到中序遍历中找这个字母，设其在位置 $k$ 处，那么 0~k-1 就是左子树，k+1~n-1 就是右子树。设左子树的节点数为 $k-1$，右子树的节点数为 $n-k$, 则又可以得到这两棵子树在后序遍历中的对应位置。最后递归建树即可。
#include <cstdio>
#include <cstring>
char post[10], mid[10];
/**
* l1: 中序起点; l2: 后序起点
* r1: 中序终点; r2: 后序终点
*/
void build(int l1, int r1, int l2, int r2)
{
if (l1 > r1)
return;
// print root
printf("%c", post[r2]);
// find root
int i = l1;
while (mid[i] != post[r2])
i++;
int cnt = i - l1;
// build left child
build(l1, i - 1, l2, l2 + cnt - 1);
// build right child
build(i + 1, r1, l2 + cnt, r2 - 1);
}
int main()
{
scanf("%s%s", mid, post);
build(0, strlen(mid) - 1, 0, strlen(mid) - 1);
return 0;
}
单调队列与单调栈——滑动窗口最小值问题
问题背景：输入正整数 $k$ 和一个长度为 $n$ 的整数序列 $A_1, A_2, …, A_n$, 定义 **$f(i)$ 表示从元素 $i$ 开始的连续 $k$ 个元素的最小值，即 $f(i)=min{A_i, A_{i+1}, …, A_{i+k-1}}$. 要求计算 $f(1), f(2)…f(n-k+1)$. （参见紫书 P241）
例题链接：洛谷 P1886 滑动窗口
显然，这道题如果用定义计算，对于每个 $i$ 用 $O(n)$ 枚举一次序列的最小值，是很耗时的。因此我们可以考虑用数据结构来解决这个问题。我们发现每次窗口滑动都有一个元素“滑出”窗口，有一个新的元素“滑入”窗口，并且我们要维护的是窗口中元素的最小值——听起来是不是很像优先队列？但是，优先队列好像也不太符合题意，因为被滑出去的元素不一定是最小的，所以删除元素的操作是比较难实现的。那么有没有什么数据结构可以方便地做到呢？
此时我们引入一个叫做单调队列的东西——它是在普通队列基础上的改进，具有：队列中的元素从头到尾单调递增/递减的性质。这个单调性显然要我们自己去维护，以维护一个单调增加的队列为例，从队头到队尾元素单调递增。当我们向队尾插入元素的时候，如果该元素比队尾元素大，我们可以直接插入，此时因为先前队列已经有了单调性，我们再插入一个更大的元素，队列仍然是单调递增的；但如果新元素比队友元素小，那么就不断地从队尾删除比它大的元素，直到队尾元素比它小或队列为空后再将新元素插入。使用双端队列可以让我们很方便地完成这个操作。
具体到滑动窗口这道题上，思路就很清晰了——维护一个单调递增列，当 $i$ 等于 1 的时候，将 $1$ ~ $k$ 个元素按照单调性加入队列。如果新加入的的元素比前面的元素更小，说明前面更大的元素已经不可能是答案了——后面有比它更小且比它更晚出队的，那么它还有什么存在队列中的必要吗（大嘘）；接下来每滑动一次就按照相同的规则处理一次。同时，我们需要一个标记数组，来标记元素是否在队列中。如果元素在队列中，且此时需要删除该元素（该元素已从窗口左端滑出），那么很显然它一定在队首；如果元素不在队列中而需要删除它，那就不做任何操作。或者，我们也可以直接往队列里塞对应数组的下标，这样只需要判断 $q.front() + k \gt i$ 时移除队首元素即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <deque>
#include <utility>
using std::deque;
using std::pair;
using std::make_pair;
const int MAXN = 1000005;
int n, k;
int a[MAXN];
bool inq[MAXN], inq2[MAXN];
deque<pair<int, int> > q;
deque<pair<int, int> > q1;
void push(int i, int cmp)
{
if (i == 0) {
if (cmp == 0) {
q.push_back(make_pair(a[i], i));
inq[i] = 1;
} else {
q1.push_back(make_pair(a[i], i));
inq2[i] = 1;
}
} else {
if (cmp == 0) {
while ((!q.empty() && q.back().first >= a[i]) || q.size() >= k) {
inq[q.back().second] = 0;
q.pop_back();
}
inq[i] = 1;
q.push_back(make_pair(a[i], i));
} else {
while ((!q1.empty() && q1.back().first <= a[i]) || q1.size() >= k) {
inq2[q1.back().second] = 0;
q1.pop_back();
}
inq2[i] = 1;
q1.push_back(make_pair(a[i], i));
}
}
}
int main()
{
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
for (int i = 0; i < k; i++) {
push(i, 0);
push(i, 1);
}
printf("%d ", q.front().first);
for (int i = k; i < n; i++) {
if (inq[i-k]) {
q.pop_front();
inq[i-k] = 0;
}
push(i, 0);
printf("%d ", q.front().first);
}
printf("\n%d ", q1.front().first);
for (int i = k; i < n; i++) {
if (inq2[i-k]) {
q1.pop_front();
inq2[i-k] = 0;
}
push(i, 1);
printf("%d ", q1.front().first);
}
return 0;
}
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <deque>
using std::deque;
const int MAXN = 1000005;
int n, k;
int a[MAXN];
deque<int> q1, q2;
void push(int i, int cmp)
{
if (i == 0) {
if (cmp == 0) {
q1.push_back(i);
} else {
q2.push_back(i);
}
} else {
if (cmp == 0) {
while ((!q1.empty() && a[q1.back()] >= a[i]) || q1.size() >= k) {
q1.pop_back();
}
q1.push_back(i);
} else {
while ((!q2.empty() && a[q2.back()] <= a[i]) || q2.size() >= k) {
q2.pop_back();
}
q2.push_back(i);
}
}
}
int main()
{
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
for (int i = 0; i < n; i++) {
while (!q1.empty() && q1.front() + k <= i) {
q1.pop_front();
}
push(i, 0);
if (i >= k - 1)
printf("%d ", a[q1.front()]);
}
printf("\n");
for (int i = 0; i < n; i++) {
while (!q2.empty() && q2.front() + k <= i) {
q2.pop_front();
}
push(i, 1);
if (i >= k - 1)
printf("%d ", a[q2.front()]);
}
return 0;
}
单调性与二分法
“说到二分我就想到二分答案，就想到单调性，今年下半年……”
二分我好像还真的没什么好说的……大概就像下面这样：
int x, y, flag, m, ans = -1;
int a[MAXN];
while (x < y) {
m = x + (y - x) / 2; // 找中点，向下取整
if (a[m] == flag) { // 恰好中点就是结果
ans = m;
break;
} else if (a[m] > flag) {
y = m; // 往左边找
} else {
x = m + 1; // 往右边找，注意起点 +1
}
}
二分答案的话，就是修改一下上面二分的条件：上面的条件是 a[m] == flag 就停，二分答案一般在这里用一个函数判断答案的合法性。至于例题……疫情控制了解下。
题目给了好多个特殊约束，比如根之间绝对值差 >= 1, 而且根属于 $[-100, 100]$，那么我们就在区间 $[-100, 100]$ 以步长 1 枚举，然后二分这个区间就行了。
#include <cstdio>
#include <cmath>
double a, b, c, d;
double eps = 1e-6;
double func(double x)
{
return a * x * x * x + b * x * x + c * x + d;
}
void find(double left, double right)
{
if (fabs(right - left) <= eps) {
printf("%.2lf ", left);
return;
}
double mid = (left + right) / 2;
if (fabs(func(mid)) <= eps) {
printf("%.2lf ", mid);
return;
} else {
if (func(left) * func(mid) < 0) {
find(left, mid);
} else if (func(mid) * func(right) < 0) {
find(mid, right);
}
}
}
int main()
{
scanf("%lf%lf%lf%lf", &a, &b, &c, &d);
for (double x = -100.0; x < 100.0; x++) {
if (func(x) == 0) {
printf("%.2lf ", x);
}
if (func(x) * func(x + 1) < 0) {
find(x, x + 1);
}
}
return 0;
}
既然二分法没啥好说的，我们来说说三分法。所谓三分查找就是在二分查找分出了两个区间（左区间，右区间）的情况下，再对左区间或右区间进行一次二分。通常三分法可以用来快速确定最值。
二分法要求二分的序列要具有单调性，而三分法不同，三分法要求序列是一个有凹凸性的函数（空间想象能力告诉我们有凹凸性的函数就是图形上上凸一块或下凹一块的函数；高等数学告诉我们凹凸函数就是 $f”(x) >(<) 0$ 的函数）。这样的函数拥有一个最大值（或最小值）。
三分法的算法步骤是这样的：
- 首先取得整个区间的中间值 $mid=\lfloor(left + right) / 2\rfloor$
- 先取右区间的中间值 $mid2 = \lfloor(mid + right) / 2 \rfloor$，将区间分成三个部分
判断 $a[mid2]$ 与 $a[mid]$ 的关系。若 $a[mid]$ 比 $a[mid2]$ 更接近最值，则我们舍弃右区间，转而搜索左区间；否则就搜索左区间。以求区间最大值为例：
if (check(mid) > check(mid2)) { right = mid2; } else { left = mid2 }重复 1~3, 边界为 $left == right$ 或两者的差距达到某个控制值，如 $eps$.
堆和优先队列
堆是基于完全二叉树衍生出来的数据结构（啥叫完全二叉树？：）
定义：对一棵具有 n 个结点的二叉树按层序从左到右排号，如果编号为 i 的结点与同样深度的满二叉树编号为 i 结点在二叉树中位置完全相同，称为完全二叉树。若结点起始序号为 1，完全二叉树及其子树满足 $left\_child = (root * 2)$，$right\_child = (root * 2) + 1$。
(图源网络，找不到出处了，侵删)
堆就是拥有如下性质的二叉树：
- 所有节点中的最大值/最小值一定位于根节点。这样的堆分别称作大根堆和小根堆。
- 子树也是相应性质的大根堆/小根堆。
堆的效率是很高的，无论是排序也好，还是什么都好。堆结构的平均操作复杂度是 $O(log n)$, 不知道高效到哪里去了。
那么这么牛逼的数据结构怎么写呢？什么？堆？using std::priority_queue; 众所周知 STL 的 priority_queue 优先队列就是我们需要用这类数据结构时的最佳选择，但是今天我们不要当搬运工了，我们要来手写堆，顺便来理一下堆是怎么实现的。好了，前方灵魂画手上线。以小根堆为例：
首先，完全二叉树的表示与顺序存储：我们刚刚说到完全二叉树及其子树的性质，那么我们可以开一个从 1 开始编号的节点数组 node[i], 这样满足 node[2*i] 是其左子树的根节点，node[2*i+1] 是其右子树的根节点。
其次，数据的查询。因为我们要查询的最值就在根节点，因此返回 node[1] 即为所求。
再来，数据的插入。数据的插入分两步，第一步是追加树叶结点存储新元素，第二步是将新元素与其他元素交换到它应该在的位置：
- 用
cnt记录当前最大的结点编号，初始时cnt = 0 - 将新元素
x插入到cnt之后：node[++cnt] = x - 令
tmp表示x的位置（tmp = cnt），接下来循环找到x应该在的位置： - 令
par表示x的父节点，如果node[par] > x，说明x应该顶替其父节点的位置，将两者交换，可以发现这样做并不破坏堆的性质； - 直到
node[par] <= x或x成为根节点时，退出循环。
最后，数据的删除。数据的删除分几步：
- 把当前编号最大的结点提到根节点处，这样根节点的值就被覆盖掉了：
node[1] = node[cnt] - 处理其它结点的关系，令
tmp = 1 - 若
node[tmp]没有右儿子或右儿子比左儿子小的时候，判断node[tmp]与node[tmp * 2]（就是他的左儿子）的关系，如果node[tmp] > node[tmp * 2]，则交换两个结点并令tmp = tmp * 2，否则退出循环 - 如果
node[tmp]的左儿子比右儿子小，判断node[tmp]与node[tmp * 2 + 1]（右儿子） 的关系，如果node[tmp] > node[tmp * 2 + 1]，则交换两个结点并令tmp = tmp * 2 + 1，否则退出循环 - 最后令
cnt减一：cnt--;
所以说……写这玩意还是很麻烦的……除非题目特别，否则为啥放着好好的 priority_queue 不用来写这么长一串东西……
OK, 来最后一道例题吧，经典的 Vijos P1097 合并果子, 理论上这道题用单调队列解题应该是更优的，优先队列也是可以的。但是这里可以测试一下我们手撸的最小堆：
#include <cstdio>
#include <cstring>
#include <algorithm>
const int MAXN = 10010;
struct Heap {
long long val[MAXN];
int cnt;
void init()
{
memset(val, 0, sizeof val);
cnt = 0;
}
void insert(int x)
{
val[++cnt] = x;
int tmp = cnt;
while (tmp != 0) {
int par = tmp / 2;
if (val[par] > x) {
std::swap(val[par], val[tmp]);
} else
break;
tmp = par;
}
}
int top()
{
return val[1];
}
void pop()
{
if (cnt == 0) // empty
return;
int rt = 1;
val[rt] = val[cnt];
while (2 * rt < cnt)
{
int lc = rt << 1, rc = (rt << 1) + 1;
if (rc >= cnt || val[lc] < val[rc]) {
if (val[rt] > val[lc]) {
std::swap(val[rt], val[lc]);
rt = lc;
} else
break;
} else {
if (val[rt] > val[rc]) {
std::swap(val[rt], val[rc]);
rt = rc;
} else {
break;
}
}
}
cnt--;
}
bool empty()
{
return cnt == 0;
}
};
Heap hp;
int main()
{
int n, tmp;
long long ans = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &tmp);
hp.insert((long long)tmp);
}
while (!hp.empty()) {
int c1 = hp.top();
hp.pop();
int c2 = hp.top();
hp.pop();
ans += (c1 + c2);
if (hp.empty()) {
printf("%lld", ans);
return 0;
} else {
hp.insert(c1 + c2);
}
}
return 0;
}
最后一些比较高深的内容和作业的部分，后面补上。