NOIP2020考前瞎扯

突然想到马上联赛了，把这么多场模拟赛用到的一些 $\text{tricks}$ 都写下来。

关于 $\text{dp}$

• 计数类 $\text{dp}$ 可能会由于前面的决策而使当前位置的决策方案数不同，例如前面选择了多少数字会影响该点可以选择多少种数字。当在某一个状态下可以更新的数字有限制的时候，可以考虑通过排序等方法，先将某一个状态可选择的点转化为连续一段的形式（例如一个前缀），然后在 $\text{dp}$ 数组中记录一维：当前已经选择多少个点，由于这些点在前面的状态中合法，则在当前点依然合法，则我们实际上没有关心前面的状态中具体选择了谁，也不去关心当前状态选择了谁，而只是得到一个方案数，因为无论选择了谁，在接下来的状态中他们都是等价的。

• 在计算所有状态的贡献和的时候，可以考虑转化为计算每一个单点的贡献，这一点在计数类 $\text{dp}$ 中尤其常见。具体地，我们在考虑一个点的贡献时，仅考虑所有会对当前点的贡献产生影响的位置，剩下的都可以随意，从而试图得到更优的解法。实际上，提前计算贡献也可以算作这一种方法。

• 当写出转移方程之后，若没有可行的优化方案，不妨考虑一下 $\text{dp}$ 柿子的一些关系。例如$\text{Emiya}$ 家今天的饭 中，只关心两种食物的个数差，从而直接降低了复杂度。再例如某一些题目，一个状态可以看做另外一个状态的超集，若这个超集与其子集的前驱状态个数差很小，不妨直接从其子集转移，再加上多出来的一部分前驱状态的贡献。

• 树形 $\text{dp}$ 中若考虑与根联通的联通块的情形，直接树形背包可能无法直接获得优秀的复杂度，这时候可以考虑使用 远古 较为常见的优化形式：将该点的 $\text{dp}$ 值直接继承给儿子，在递归遍历完子树之后，再将 $\text{dp}$ 值合并上来。

• $\text{dp}$ 状态的设置很大程度影响复杂度。考虑若转化 $\text{dp}$ 的状态，是否可以获得更好的复杂度。例如对于区间 $\text{dp}$，是否可以将状态设置为与区间长度相关，而不是区间左右端点。状压 $\text{dp}$ 是否可以通过删除压缩状态中的无用部分，来进行时空优化。

• 考虑循环顺序对答案的影响。例如背包类 $\text{dp}$ 中，循环顺序会很大程度地影响答案的正确性。再例如一些关于前缀/后缀 $\max,\min,\text{sum}$ 的题目，是否可以通过调整循环顺序从而直接获取已经得到的状态。

• 对于一些转移有限制的，可以通过单调队列/斜率优化来进行优化的 $\text{dp}$，可以考虑是否能通过将状态按照模意义分组等方式进行划分，当转移时就直接去对应的地方寻找转移。

• 对于包含"恰好"等字眼的 $\text{dp}$，考虑是否能够转化为求钦定，然后二项式反演回来。

关于数据结构

首先一点，有一些题一眼上去很像数据结构或某一个特定算法，但是一定要仔细斟酌，考虑是否真的是可以通过数据结构来维护的东西。如果没有想到数据结构的做法，应该跳出这个思想去思考 $\text{dp}$ 等方法，或者考虑是否有转化模型的方法。

• 联赛几乎不会考主席树、莫队、线段树合并、树链剖分及以上难度的任何数据结构 虽然他们都不难，但是如果有足够的部分分算法，也应该去写一写。

• 对于纯粹的数据结构题，首先应该考虑使用常数小、码量小的算法，例如能用树状数组就不用线段树，平衡树能不打就不打......

• 对于一些较为难以维护的信息，可以考虑使用另外的数据结构进行该信息的求解，然后再挂在主要的数据结构上，从而至少保证 $\mathcal{O}(n\log^2n)$ 的复杂度。例如可以使用主席树维护静态的区间信息，然后当对线段树某一个点进行查询的时候，碰到叶子就去主席树上查询等。

• 部分题目可能难以在线维护，例如扫描线或一些奇怪的区间问题。这类问题的一般规律是维度可能较高，或限制较紧。这时候应该考虑离线下来，通过排序等方法消除一些限制，然后再进行求解。这类问题不一定是莫队等算法，但是离线排序求解的思想需要牢记。

• 离线可以莫队但是强制在线的题，可以考虑分块。分块的时候，有很多看似十分暴力的思想实际上复杂度是正确的，所以要敢于往这方面想。

• 对于维护方案数总和一类的区间问题，可以考虑在右端点右移的过程中，左端点的变化情况。

关于线段树的一些想法：

线段树具有十分强的拓展性，可以维护很多类型的信息。序列的值、值域、时间等都可以用线段树维护。

当维护的信息关心序列中区间的限制，则只能维护序列下标上的值，若除了关心区间，还关心值域，则需要主席树。

若在进行一些转化之后，发现只关心权值的关系了，则可以考虑权值线段树，权值线段树可以考虑离散化，或者直接动态开点。

时间线段树一般用于线段树分治，用于处理在某一个时间区间内，一些操作有作用的题目。当然这个时间不一定真的是维护时间戳，而是一类类似在某区间可以使得某操作合法的信息。例如一次考试的 $\text{minmax}$ 一题可以认为是把边权值看做时间，然后线段树分治。

维护前缀 $\max$ 之类的一些更为复杂的内容，若是见过确实可以通过线段树维护的，则可以写。否则优先思考一些其他的方向，毕竟线段树的妙用还是比较难想的。在这一类问题中，是否可以使用线段树维护，关键在于信息是否有可加性，还有在两个区间合并的时候应该如何维护两个区间之间的信息对答案的影响，同时保证正确的复杂度。

关于贪心

这东西太神了......能写多少写多少吧。

• 对于制定排序方案的贪心，可以考虑邻项交换，推推柿子看怎样可以使排序更优。
• 树上的贪心 随缘吧，较为套路的一种是考虑将一条路径的贡献丢在其 $\text{lca}$ 上，然后尽量考虑使得 $\text{lca}$ 满足一些限制。
• 很多题目中第一步就是一些比较贪心的想法，不见得一定是一整道题都考贪心，而只是说很多都运用贪心思想。

关于数学

联赛考数学应该不会难，最多是个小学数学题或者什么 $\text{ExGcd}$（$\text{flag}\times 1$）。