前言

先说明我前两天没有写随笔的原因。第一天（8.21）是因为我当时写完一篇题解后没有来得及写总结，然后我妈就说要带我去九眼桥那片去转转，最后我们十点半才回到家。昨天是因为我想复习一下当日内容，先去写了主席树，然后做了一道题单里的 dp 加贪心题，然后特判的时候没有 return 0 交上去一直 RE，调了快一个小时，遂自闭。然后这三天其实有非常多值得写的，但是前面没有写，所以这一篇博客就长话短说了。

8.21考试

当时想的是顺序开题，因为看上去一二三都比较可做。第一题我发现了一个很好的性质，然后去考虑 dp，可是如果暴力转移那么状态和时间都不够，于是就根据性质只维护了一部分我认为有用的状态，然后好像数据水没法检查，然后就跳过了，最后得了65pts，全场最高。赛后才知道还有一个性质可以优化转移，然后状态数其实是够的，只不过范围太大可以用 STL （比如 set、map）存一下，太可惜了，不过也知道了 dp 的灵活，以后还要优化思路。目前我总结出来的思路是：先观察性质，然后去对应算法，再选取数据结构，最后考虑细节；还有就是写代码前检查正确性。

第二题可以先转化问题，然后贪心。但是难点在于如何处理多组询问。我最开始想了一个单源最短路的做法，然后发现因为网格图所以假了，就想到了一个维护障碍物的做法，但是不知道怎么预处理，最后也没有想出其他可替代的方法于是就乱搞做法最后25pts 成功坠机。之后知道 yt 暴力 \(n^2\) 过十万，难受！

第三题一眼是生成函数，但感觉数据范围太大不行。然后想背包做，然后再随便乱搞一下的，但是看测试点的时候看到 \(n\le20\) 的有40就爆搜走了。然后考试后初中生基本都100，方才反应过来是一个折半搜索。由此观之，我对折半搜索一点也不熟悉，之后要注意一下。

第四题来不及多想了。首先先把题意转化，正难则反，统计不满足条件的区间然后用总的去减。看上去就是用 hash 加上前缀异或和去做，更多思路没有了就去打特殊性质，最后写挂了，0pts。

真要说总结的话我觉得考试的时候我的思路还不是特别清晰，逻辑有时有点混乱。总之就是找不到去年的感觉了。我认为我最近做题有点死板，应该真正设身处地的去想一道题。为了解决问题而解决问题。然后 hfu 今天早上也恰巧说到这个，也算是与我的想法不谋而合吧。

我还有就是不够自信（个人感觉），害怕失去。但如果过于保守反而会失去的更多，所以我要勇敢去尝试，相信自己能够做出题。

那天也没什么好说的了，就是觉得第一题出的很好就写了一篇题解。

8.22多维数据结构

讲了树套树、kd-tree 以及 STL 的 bitset，感觉就是题目思维难度不是特别高，但代码实现较为困难。题目也没什么好说的，大多是二维数点、平衡树的操作套上区间的限制等类型的题。 kd-tree 只听懂了思路不会写；bitset 讲了好像有没讲，但我觉得 STL 的容器真的没有什么好讲的，就是知道每个容器有什么函数就行，然后就是我想听一下迭代器的用法结果学长做课件的时候漏了（悲。

下午复习了一下线段树、fhq treap 和主席树，感觉良好！写了两道板子，用的都是树状数组套权值线段树。然后有关数据结构我想说的就只有一点，能用树状数组代替线段树就用前者！只有被卡常才会深有体会！

8.23分块莫队

先讲了基础内容，然后基础题都能暴切。后面上了主菜：Ynoi 的大分块。自己一道都想不出来。然后听讲也大概只听懂不到 60%。我谔谔。

下午在死磕一道大分块，最后没有写出来，后来感觉不如去自己找一点蓝题紫题做熟悉算法。

其他

感觉这段时间有些疲惫了，之前从没有过。明天下午后就又是周天了，可以休息一下，然后把上周鸽掉的字符串补上。