7.22——数据结构

上课+做题

首先讲的是树剖。树剖核心就是根据树的一些特征（如深度、最大子树），将一棵树拆分成 \(\log{n}\) 个连续的树链，使得树上问题转化为线性问题，最后再用数据结构维护区间或是直接 dp 之类。由于我之前就比较熟悉树剖、还写过一些题，所以听得非常轻松，但是水平还未达到能随便切紫题的高度。当天下午我也写了几道题，估计是已经完全掌握，做 NOIP 的树剖题感觉没有什么太大问题。

之后还讲了 cdq 分治。这是一种离线算法。当我们遇到不止一个限制求 max、sum 等信息时，我们可以构造加寻找出三种限制，将其转化为三维偏序，然后 cdq 分治。这一算法主要就是分治套树状数组，主要是分治，在分治过程中用树状数组统计答案。代码很简单，能够轻易实现。讲的一些练习题都不是特别难，只是需要你细心观察、发现性质，然后找出三种限制，但是代码实现需要注意许多细节，故我写题较慢。

最后讲了整体二分，就是把多个询问同时进行二分，和普通二分没有太大区别，但题我还一道没写，不清楚对于一道题具体如何实现，之后需要补上。

总结

这天的课程对我来说比较轻松，在课上能紧跟学长思路，还能场切一点题，还算不错。树剖已经基本没有问题，之后 cdq 还可以再自己拓展，整体二分必须写一点题理清代码实现细节。

7.23~7.25——数学、多项式

上课

多项式接着上次 NTT 之后求多项式其他东西继续讲。应用大部分不算难，能够自己推出来，只有多项式除法需要构造没想出来。

之后是生成函数。这个东西就是对于一个数列 \(A\)，构造一个函数 \(F(x)=\sum a_ix^i\)。然后 \(x^i\) 没有实际意义，看成占位符就行。后来讲了两道生成函数的题，但我还是没太搞懂它的应用，感觉就只是对于背包问题求解方案数有奇效，其他应用未知。

后一天讲的是线性代数。学长通过数形结合的思想，从最基础的向量开始讲了线性相关内容、行列式、矩阵最后讲到特征向量与特征值。这一天的学习，我明白了向量在线性代数中的基础性，理清了线性变换与矩阵乘法、行列式等之间的内在关系。之前虽然之前听过一次印象不深，可我还是听得很轻松。学了一上午后就感觉特别神奇，使我对线性代数的兴趣增大。

最后一天讲基础数论。确实很基础！讲了模数有关的大部分内容、筛法、CRT 以及这些东西的推导过程，现在均完全理解且能自行推导。

做题

多项式的题就是以 FFT（或 NTT）为主进行加工。操作是一层套一层，代码看着非常简单，实际写起不难但耗时间，要处理一定的细节。数学题代码量小，只要搞懂题意找到解法就是7 8分钟的事。

总结

之前听数学都没有把东西背后的原理弄懂，所以结论记不住，更别谈应用。这次过完就能够熟练掌握所讲内容，知道了知识的内因，应用也好起来了，只是还需要多见一点不同的题就行。

7.26~7.27——DP

上课

第一天简单。我唯一对状压不算特别熟练，当天也没有写题，准备马上补。

第二天难。计数题的状态设计有时候都是个问题，我感觉到题见太少了、思考量严重不足，总觉得思考时力不从心、有时面对问题会不知所措。就觉得没有找到做题的技巧，思考时总觉得没有太多方向感，而且很死板，总往一个方向使劲想。我觉得我的状态设计能力还有很大提升空间。期望dp 就是根据期望的性质化简式子，写成线性递推方程，如果有初值就直接做，否则就高斯消元。插头dp 听懂了，但是代码实现还是比较困难，之后要写一写。

写题

只写了期望的题，计数题写的少，插头dp还没开动，但是就算写的慢还是坚决自己手推，不去看题解。

总结

这段时间的课程对我来说都还好，除了最后一天的 dp 想不出来几道题，其他时候都算轻松。下午也有认真在做题，就是晚上还可以再稍微写写总结就更好了。那天听了付伟吉的讲话，我也准备开始准备一个本子每天写点东西。并且之后还向他询问了一些东西，个人感觉受益匪浅。中午休息时可以学习其他人看看书，而不是在手机上刷视频。

机房氛围也挺好的，就是有时候不算特别安静，一定程度上会影响我的效率，我也要克制住自己，不要去做过多无意义的事情，最后就是准备换一下座位，坐到教师机前面的那个电脑那里，既是为了督促自己，让自己更加认真地听课，也是方便与学长交流自己的思考，还能避免和yt、wyc或者其他人进行过多讨论。