精集训日记集训日记

wcqk

9天前更新

595

### D1
今天学到了/回忆起了什么知识, 有什么收获
STL map、set 以及 multiset 。multiset 不去重但排序。

auto 遍历 STL 容器。指针相关只能++或–。eg：不做评价

思考问题“从特殊到一般”关注题目特殊性质。eg：D1 T4 的 -1 情况判断

追忆到了部分与 find 相关的内容（？）eg：不做评价

03.
没有合理的分配想正解与暴力的时间。eg：快速浏览题目，小半时间想正解，一半时间写正解，小半时间暴力（T3/4，部分T2）

前期没有对构造题没有任何接触。扩充刷题类型（？）eg：不做评价

—
### D3

复习了一下树状数组。
树状数组可以单开一个 $tree$ 数组，`tree[i] = a[i-lowbit(i)+1,i]` 的和。

树状数组本质上仅支持单点修改与区间查询。单点修改可以一直进行找父亲的操作，给每个父亲全部加上 $y$, $i$ 的父亲是 `i+lowbit(i)`，即让刻意 $i$ 进位，以让 $i$ 的管理范围更大。

计算 $[1,x]$ 区间的和，从后到前计算 `for(;x;x-=lowbit(x))sum+=tree[x];` 会更加方便思考一些。

树状数组本质上仅支持单点修改与区间查询，但也可以通过维护不同的 $tree$ 数组（$a$ 数组），来实现不同的功能。[树状数组2](https://www.acgo.cn/problemset/info/22467) 可以通过维护差分 `add(i,a[i]-a[i-1]);` 实现。

回忆起了一部分离散化相关的内容。

部分问题如果无法通过下标思考，可以从值域的角度出发。类似于 [LIS 加强版](https://www.acgo.cn/problemset/info/137279。)

回忆起了快速幂相关内容。

了解了交互题。[例子](https://www.acgo.cn/problemset/info/113974)

—

在复习模版时，没有回忆到树状数组2 的解法。

对树状数组模板记忆仍然不够熟练，只拿到了暴力部分分，还可以反复记忆巩固印象。

没有详细的了解交互题？

—

### D4

在定义 $dp$ 数组时，我们通常会考虑以 $i$ 结尾能获得的最优解或者是到了 $i$，能获得的最优解。

当某一维度的 $dp$ 存不下当前的几种状态时，如果维度不够，当前定义的状态十分诡异，考虑多开几维。

当维度很大，且后面的每一维都是 $2$ 时（`dp[n][2][2][2]…`）时，我们可以考虑二进制，例如 `dp[n][mask]`，将 $mask$ 转为二进制后，$1$ 表示取，$0$ 表示不取。

当某一维度的 dp 存不下当前的几种状态时，如果维度不够，当前定义的状态十分诡异，考虑多开几维。

在 ${dp}$ 时，设 ${dp}$ 数组有 $k$ 维，那么通常会用 $k$ 层循环枚举维度。在这 $k$ 层循环下，再用 $1$ 层或多层循环枚举可以到达 ${dp}_i$ （${dp}_{{i,j}}$）的所有状态

—

模拟赛在 [T1](https://www.acgo.cn/problemset/info/117885) 的部分分浪费时间太多了。其实题目可以转化为将这个序列用两个下标分为 $3$ 个部分，因为必须除了两个单人单座的，必须要两两坐在一起，于是易得第 $1$ 个单身的人的座位必须是奇数，第 $2$ 个单身的人的座位必须是偶数，且必须在第 $1$ 个人的右侧。

于是可以想到预处理一个数组 $brr$，$brr_i$ 表示第 $i$ 个座位（$i$ 为奇数）右侧最大的偶数座位的值。预处理 $brr$ 时更方便的做法是从右往左处理。

我们再从左向右遍历每一个奇数下标座位，找到一个最大的 $arr_i+brr_i$ 即可。

—
### D4小课堂

正常情况下，题目问什么，dp 就定义成什么

– 题目问什么，就定义什么
– 状态转移方程（公式）
– 分段转移

### D5

学习了单调栈，以及如何用双端队列 `deque` 实现单调队列。

单调栈常用于处理如下类型的问题：
给定数列 $a_1, a_2, \dots, a_n$，定义 $f(i)$ 为第 $i$ 个元素之后**第一个大于**

$a_i$ 的元素的下标，$f(i) = \min_{i < j \leq n,\ a_j > a_i} \{j\}$

对应的模板题可参考：[题目](https://www.acgo.cn/problemset/info/49360?homeworkId=23691&teamCode=2042058713337094144)。

悬线法。我们可以定义数组 $high$ 表示每个位置向上能扩展的最大行数，于是转化为模版题。

对于单调队列，用了 `deque`来维护。在维护窗口最值等场景中，通过弹出队尾来维护队列的单调性，同时弹出队头来移除太古早范围的元素，解决滑动窗口问题。