[总结] 暑假第四周总结

· · 学习·文化课

暑假第四周总结

前言

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

学习内容

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

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

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

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

比赛情况

7.13

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

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

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

感觉 $\text{T4}$ 就是个实现极复杂的暴力。。。 ### $7.16 $\text{T3}$ 确实是一个对于现在的我们不太可做的数据结构题，感觉连正解的第一步二分答案都很难想到，还得多积累。 前两题没过完纯属是因为脑子太难受了，赛时基本半死不活，前一个半小时和后一个小时左右基本处于挂机状态。 ### $7.19

拼尽全力还是被碾压了。

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

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

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

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

$\text{T4}$ 是利用凸性和一些其它性质的 $\text{DP}$ 优化题，还没补，后面抽时间补。 这场比赛策略啥的倒是没问题，主要问题是没做出来 $\text{T1}$，暴力其实写了但是最后忘交到 $\text{OJ}$ 上了。 ## $\text{Finally}

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