2022.1.17

今日学习：单调栈，单调队列，堆

DS_problem 1 游戏1
单调栈水题，倒序枚举维护一个单调栈即可。

DS_problem 03
枚举以行为底的1最大向上拓展数量，设为 \(h(x)\) ，则 \(l\) 到 \(r\) 的矩阵面积最大值为

\[(r-l+1)× \min^{r}_{i=l} h(i) \]

用单调栈维护即可。

DS_problem 04
用一个 \(l\) 数组和 \(r\) 数组枚举左右，求和使用前缀和即可。

DS_problem 06 滑动窗口
单调队列水题
用ST表水过了

DS_problem 07 游戏6
横纵做2遍单调队列即可。

DS_problem 8 荷马史诗
其实就是 \(k\) 叉哈夫曼树问题。利用贪心求解即可。

2022.1.18

今日学习：单调栈，单调队列，堆

P1901 发射站
单调栈水题，维护一个单调递减的栈，每次输入数据判定高度是否大于栈顶，大于便加上价值。最后入栈。
P1950 长方形
与problem3类似，直接枚举以行为底的全'.'子矩阵即可
P4779 【模板】单源最短路径（标准版）
dijkstra堆优即可
P1776 宝物筛选
可以直接打多重背包板子AC，也可以进行单调队列优化，将数据按 \(\%w_i\) 的余数分组，体积为 \(u,u+w_i,u+2w_i....\) 然后对于每一组考虑状态转移方程：

\[F(1,u+kw_i)=\max^{k}_{j=0} F((0,u+(k-j)w_i)+jv_i) \]

令 \(g(k)=F(0,u+kw_i)-kv_i\) ,则

\[F(1,u+kw_i)=\max_{j=r-k}^r(g(j))+kv_i \]

上面就是一个滑动窗口，直接上单调队列即可。
P2254 NOI2005 瑰丽华尔兹
暴力dp可以直接水过？
状态转移方程：

\[f[t][x][y]=max(f[t-1][x][y],f[t-1][x-dx[d[i]]][y-dy[d[i]]]) \]

2022.1.19

今日学习：并查集，带权并查集，种类并查集
abs讲课！
P3367 【模板】并查集
直接套并查集模板即可
P5937 [CEOI1999]Parity Game
很有思维的一题。可以用种类并查集或者带权并查集做。带权并查集就是将区间转换为一棵树，边权表示奇偶，将节点到根节点所经过的所有的节点异或即可判断奇偶
UVA11987 Almost Union-Find
操作1和操作3很好想，直接最基础的并查集操作，而操作二则会影响到自己的子节点，所以我们可以建立一个虚节点，作为每个集合的父节点，这样操作的时候不会影响到子节点，剩余就很好想了
P2024 [NOI2001] 食物链
像P5953一样，可以用2中方法做。本人用的带权并查集，吃与被吃的关系可以用%3的关系式来推出。当然种类并查集就是分成三组然后判断每组中有没有谎话。
P3420 [POI2005]SKA-Piggy Banks
将每个存钱罐向此存钱罐里的钥匙可打开的存钱罐连边，最后判断联通块的个数即可。判断操作可用并查集判断
P3465 [POI2008]CLO-Toll
题意就是构造一个的基环树，保证只有一个环，直接魔改kruskra构造一棵基环树，用并查集维护即可
P3631 [APIO2011]方格染色
写出来会写题解的