成都外国语学校集训第一周。

因为做了非常多杂题，所以也自学了一些小知识点。

第一个就是长链剖分，主要的应用就是 $O(1)$ 回答树上 $k$ 级祖先和优化状态中带有深度维的树形 $\text{DP}$，实现要用到指针一类的东西。

其次就是 $\text{slope trick}$，多用于优化 $\text{DP}$ 状态的函数图像为凸函数的 $\text{DP}$，一种是维护拐点，另一种是维护斜率本身，暂时还没有写这类题，因为手上题太多了。

还有很多在比赛和杂题中学到的具体的 $\text{trick}$，记录得比较乱，计划等外培结束后抽时间整理。

这场比赛问题在于被 $\text{T1}$ 卡了快 $2$ 小时，然后切掉 $\text{T2}$ 原题之后，才发现一些性质切了 $\text{T1}$，事实上这道题是 $\text{slope trick}$ 典且板的题。

第二个问题是没对拍，在这场没一个大样例的情况下怒挂 $115$ 分，不仅正解，连暴力都挂没了。

根本原因是能感知到 $\text{DP}$ 的有效状态数较少，但短时间内分析不出其具体分布，导致思考方向的转变，最终浪费时间，没写对拍。

$\text{T3}$ 其实是一个比较水的状压 $\text{DP}$，先考虑链的情况（或者不考虑好像也挺自然？），后面就顺理成章了。

感觉 $\text{T4}$ 就是个实现极复杂的暴力。。。

$\text{T1}$ 简单容斥，$\text{T2}$ 签到题，但全场居然没一个同时过前两题的。

$\text{T3}$ 确实是一个对于现在的我们不太可做的数据结构题，感觉连正解的第一步二分答案都很难想到，还得多积累。

前两题没过完纯属是因为脑子太难受了，赛时基本半死不活，前一个半小时和后一个小时左右基本处于挂机状态。

拼尽全力还是被碾压了。

大家都好强，好像只有我觉得 $\text{T1}$ 特别难。

这种题还是得考虑判无解的充要条件或者构造性地判断无解。

然后在考虑操作方案的时候，因为操作方案是一直加加减减，最后形式也较特殊，应该想一下一类元素之间的差的变化情况。

总体来讲这题有点类似 $\text{CF}$ 风格。

$\text{T3}$ 比较可做，主要思想就是把子串转化成后缀的前缀形式，然后一直套数据结构去维护即可，值得一提的是部分分的分治做法也很常见。

$\text{T4}$ 是利用凸性和一些其它性质的 $\text{DP}$ 优化题，还没补，后面抽时间补。

这场比赛策略啥的倒是没问题，主要问题是没做出来 $\text{T1}$，暴力其实写了但是最后忘交到 $\text{OJ}$ 上了。

到这边来感觉整体效率稍微有点低了，大概是多重因素共同作用的结果，思考的时候没那么集中，接下来要提高效率，珍惜时间。