2021/7/1

今天没有刷题，只参加了一场网络赛。

T1 没想到直接设区间作为状态，于是只打了暴力。

T2 没想到是个费用流模型，于是只写了随机化迭代，然而有 85。

T3 想到了决策单调性，但是没理清楚，于是只写了个暴力。

字符串的最长公共子序列的 dp 状态是可以通过决策单调性拼起来的。

Lis 值相同的位置上的值必然递减，求 lis 可以树状数组，线段树，也可以维护每个答案结尾的最小值。

决策单调性等优化还需加强，思路要灵活。

2021/6/30

题数：4，码量：11.8kb

• 区间本质不同子串个数

  SAM + LCT + 线段树 + 离线

• CF1037H Security

  SAM + 线段树 + 按位贪心

• CF700E Cool Slogans

  SAM + 线段树 + 后缀树 + dp + 结论

• 「PKUWC2018」Minimax

  概率 + dp + 线段树

其实早上还打了场网络赛，发现 F 题是个字符串题不会。于是今天主要做了点字符串题。

SAM 要争取一遍写对，关于子串问题可以考虑用 SAM/后缀树 这一结构来转化问题。

2021/6/29

题数：4，码量：8.82kb

• CF578F Mirror Box

  结论 + 图论 + 矩阵树定理 + 并查集

• 「NOI2011」智能车比赛

  计算几何 + dp / 最短路

• 「NOI2011」兔兔与蛋蛋的游戏

  二分图博弈 + 最大匹配

• 「NOI2011」兔农

  循环节 + 数论 + 矩阵乘法

fib 数列模意义下存在纯循环，以 0 1 1 开头，并且在递推过程中可以定义 -1 项为 1 方便计算。

对于网格图，以及黑白棋这种带有二分图色彩的问题上可以考虑在二分图上分析问题。

然后比赛时要有信仰，复杂度不对也可能碾过去！

最后写题前想好整体流程，理清思路，提高效率。

2021/6/28

题数：4，码量：9.98kb

• 「HAOI2017」八纵八横

  biset + 离线 + 线段树分治 + 线性基 + 回退

• [HNOI2010]城市建设

  LCT 维护 MST + 离线 + 线段树分治 + 回退

• 「TJOI / HEOI2016」排序

  二分答案 + 线段树 / 权值线段树分裂与合并

• CF626G Raffles

  贪心 + 线段树 + 数学分析 + 单调性

学习了线段树分治，是个离线算法。

对询问建立线段树，然后把每个操作影响的询问在线段树上记录，然后从根开始 dfs 线段树，进入子树时进行操作，然后回溯时回退。

跟 「NOI2014」购票 实现上差不多。