7.7~7.17、7.20 NOI模拟+好题分享

考试

五六次的模拟考试，让我深刻了解到 \(\text{NOI}\) 的难度，明白自己和真正高手之间的差距，也懂了我自己需要努力的方向。

我的代码能力有待提升，可以通过多做不同类型的题让我掌握一些写代码的技巧，规范我的码风，在同时了解自己容易出错、需要特别注意的地方。我的解题能力不足，做题思维不太清晰，常常跟着感觉做。我应该强化自己的数学基础，学习一些解题的方法，还需要知道每个算法对应的套路和算法核心是什么。

在考试时，我应该考虑正解后想暴力，以最大化我的得分，不能死磕一道题，而是通读题面，再根据自己的情况选择开题顺序。在写完题后，要根据算法出 \(\text{hack}\) 数据，适当时可以写拍。

之后的学习中，我应该有计划尽可能多刷一点题、见见题型，对于每个题还要想想如果不是正解应该怎么去得多分。

7.18~7.19 DP专题

讲课

学长讲了一天课，从最基础到后面复杂的 \(\text{DP}\) 甚至是几种优化都讲完了。由于有基础，我听得很轻松。上午简单就相当于复习，下午有一些难题就跟着想。

刷题

之后一天多，我把几类 \(\text{DP}\) 题目基本都刷完了，有成就感。

收获

这几天对于 \(\text{DP}\) 专题的强化练习，我对其的运用更加熟练、同时也加深对它的理解，找到了做题的套路。

总结

动态规划就是把一个问题转化成许多小问题，它更注重思维的优化，但各种类型又有一定的格式。动态规划主要在设计状态和转移状态，在转移中可能又需要用数据结构、差分、前缀和等进行优化。对于确定状态，可以思考我们最需要什么，而什么又可以不省掉，怎么定义最好转移？对于转移，我是否需要再记录其他东西，怎么去优化转移的时间复杂度？但如果题的确太难，可以考虑暴力加优化拿部分分。

7.21~7.24 计算几何专题

讲课

讲了两次课，从最基本的点、线、面之间位置关系判定到求凸包、半平面交、面积并等，学长讲了许多高中几何知识。虽然是第一次学计算几何，但我认为我的听课效果还行，大部分都能完全掌握，只有面积并有关部分有点没太懂，之后要回过头去再理解+写题。

刷题

计算几何的题除了板子都比较有难度，它会结合好几种与几何有关的东西一起考你，所以只掌握一点知识肯定没法做题。它通常结合数据结构等进行考察，但以几何为主，码量有一点大。我把所有板子敲了后只做了几道题，感觉对我来说比较难，写题有些困难，之后自己要去多整整。

收获

掌握了一些高中几何知识，明白该类题型的考法，对板子不太熟，还需要多练。

总结

计算几何的题目在 \(\text{CSP-S}\) 中基本不考，但在水平更高的比赛中常会出现。计算几何我认为最重要是需要理解和背板，再是在题中的运用。只要能把板子敲熟，运用就会比较简单，但在真正的写代码中却要复杂得多，所以还需要精确的理解。

7.26 后缀数组、后缀自动机专题

讲课+收获

学长讲课仔细，课件图文并茂，还有代码辅助，让基本不会的我听懂了后缀数组，但后缀自动机我觉得太难不会。再后来我翻了一些博客后好了许多，但是到现在也没完全懂、只懂个大概，有的地方不太能理解。

刷题+总结

后缀数组和后缀自动机的板子都全部写了好几遍，能背熟。后缀数组刷了好几道，套路都是先求每个 i 的 sa[i] 和 height[i]，再转化题就可以过了。但是复杂的运用还没做，之后得补上，但好像变化不是太离谱，只要能懂原理会敲板子就能做。

后缀自动机不同于 \(\text{AC}\) 自动机，它存在一个 \(\text{DAG}\) 上，通过记录每个点最长字符串长度和集合大小、维护父亲儿子关系维护整个串。由于我还没太理解，所以有关其运用我完全不会，需要放假时补。

7.25、7.28~7.29 数论、多项式

讲题+刷题

每天上午讲题，下午消化。

第一次课讲的莫反和筛法比较简单，只有 \(\text{Min_25}\) 筛难理解。当天下午把全部内容消化并敲完板子顺便还做了几道题。

第二次课讲 \(\text{FFT}\) \(\text{NTT}\) 之类的东西，有难度，涉及高中甚至以上的数学。但我有基础，再加上预习过，所以听课比较轻松。后面难度突增，有关多项式的运用听得有些晕没太懂，后来理解部分。多项式加运用共十道板子只写了一半。

第三次学长太巨，课讲得很抽象。公式、定理都基本没听懂，后面直接上题没法做。最后听不下去就回去朴前面的了。

收获

让我对数论、多项式的运用更熟练，掌握了一些快速求多项式的方法并熟练背板。

总结

这块知识需要扎实的数学功底，许多推导与数学关系密切。在做题推式子时需要掌握一些技巧，根据时间复杂度分析。

最后

这段时间我的收获颇丰，在与 \(\text{NOI}\) 选手集训中明白了许多方向性的东西，学会了一些好的策略，后面在听课中也学到许多新知识会背板子并能进行一些运用。所以不管是意识层面还是知识层面我都有许多进步，自己的志向更坚定，无教练在机房时也能认真学习，不需要人管理。希望这种学习的动力我能够一直保持，也感谢所有指出我错和所有帮助我变得更好的人！