2/12考试总结

时间安排

8:30–8:50 读题，T1 不知道是个啥,T2是个dp ，T3可能也是 dp 之类的。
8:50–9:30 T1，读了好几遍才理解了题意，对于部分分有爆搜。考虑正解，想到预处理后O(1) 查询，问题是如何由已知的信息得到所有可能询问的答案，想了几种 子集dp 之类的东西，都不太对。
9:30–10:20 T2，看了一眼发现有 70 分是送的。正解貌似可以前缀和优化一下什么的。仔细分析了一下发现不好维护，暴力前缀和预处理的话时间空间都不允许，尝试着化简式子看看能不能 O(1) 做，貌似做不了。
10:20–11:13 T3,分析题目可以找到一些性质，然后根据这个建图，部分分可以暴力在图上跑。考虑能不能推广，需要快速知道图上的信息，猜了好几个结论都是假的。
11:13–12:00 瞪T1,T3。
12:00–13:00 瞪T1 。

回顾反思

T1:
正解是 dfs 搜索，或者使用状压做类似过程，复杂度是 $n{2}^n$ 的。
比赛时一开始读题理解题意耽误了一点时间。
题目中有 $\exists \forall$ 两种逻辑运算，将 $\exists$ 当做限制，问题是如何预处理出一个限制是否被满足。考场上，我局限于先以某种方式钦定一个限制，然后考虑在限制下的所有可能状态的解，那么这样复杂度就是枚举限制的复杂度与枚举状态复杂度的积，是不能通过的。但是实际上，根本不需要事先钦定某个限制，可以直接将限制的钦定融进状态的枚举中，考虑直接一位一位枚举状态，对于某一位，讨论是采取限制 1 还是限制 2 ,然后得到在此限制下下一位的合法状态，递归进入下一位。这样，递归进入某一位是，之前的所有位的信息都能被有效利用，而非再次搜索产生冗余。
这道题，我在最开始题意的理解上出现了一些偏差，绕了一些弯子;其次，我局限于钦定限制然后找状态，但是实际上可以枚举状态然后讨论限制，边枚举边做；再者，我对 dfs 的复杂度没有信心，没有仔细去计算 dfs的实际复杂度。
要认真分析复杂度，一般的 dfs 会有很多不必要的冗余，若能够做到最大化利用每一段递归公共的部分减少重复冗余操作，其复杂度会极大的降低。
T2:
思路基本和正解相同，考虑组产生的分界，但是角度又略有不同。正解主要考虑是 A 组先满还是 B 组先满，而我则是考虑在给定的 K 的关键点内 B 组是否满了。这两种角度对于部分分计算的复杂度是一样的，但是我涉及的组合数整体的分布不如正解的 “亲近” ，比较难以优化计算；其次，正解的式子几乎只涉及了值域为 n 的 i 以及种数为 $\sqrt{n}$ 的 K，那么枚举 K 对 i 暴力预处理就行了，而我还涉及到另一个值域为 n 的变量 xk ，于是预处理也很困难。于是进行不下去了。
还是要尝试多种角度的思考问题，不仅是这种思路能走多远的问题，更直接的，不同的角度会对式子产生不同的影响。
对于具体的计算方法，
对于每个询问涉及到某种分布或者某段的组合数的计算，直接计算或者预处理都不好做，可以考虑优化暴力，将询问对应的区间离线下来，对相应数值跑莫队，这样可以做到根号。
对于正解，其计算难点在于出现了以 k 为参数的式子，这个 k 值域是 1->n ，若对于每个 1-> n 都预处理是不现实的。但是注意题目条件 $\sum k\le 2\ast n$ ，那么不同的 k 的种数最多只有 $\sqrt{n}$ 级别，于是将 k 离线下来只对这根号个 k 预处理就可以了。
很多题目都涉及了对 $\sum k\le lim$ 这个条件性质的利用，如该题中 k 种类数不超过根号、虚树等。

T3:
想到建图了，建了图，但是对于图的性质没有剖析完全，模型中出现了许多冗余边。具体的，正解的建图是若干条链，相邻的链连边，而我对于一条链与许多不相邻的链也连了边，但实际上这些边即使不加，也存在相应的等价的路径。于是我的图模型不像题解那样简洁，比较乱，也没有规律可循。
这种建模题，连边时要谨慎，考虑到这条边是否有加的必要，是否不需要这条边也能表现出相应的等价关系，精简模型，透露本质。
题目有充要性质：相同的 ai 对应的 pi 递减，且对于一个 pi 大于 i 之前最近的一个满足 aj=ai-1 的 pj 。由此建图，是若干条相连的链。
这个图比较简单，信息可以直接递推处理。

三道题都没有涉及什么比较复杂的算法和数据结构，T1是暴力题，T2是经典套路题，T3难度也不算很高，其实都在个人可控范围内，T1,T2都是应该 AC 的题目，理想分数应该在 250+ 以上。