集训总结1
第一次考试
这次考试考得很差，本来以为可以考 \(100 + 10 + 80 + 0 =190\) 分，结果爆了很多分，最后只考了 \(30 + 10 + 60 + 0 = 100\) 分，属实很炸裂。
A
自认为自己的位运算学的还可以（？），所以第一眼就知道这个题直接对 \(2^k\) 手动取模就可以了。但是敲完之后只测了样例，没有测其他的数据，导致忘记了特判 \(k=64\) 的情况，而且有些不该取模的地方区勒莫，导致只有 \(30\) 分。
B
刚看完题就觉得是 \(\operatorname{dp}\)，也把状态设出来了，但是推了半天也没把转移方程推出来，所以就写了一个线段树优化暴力（但是和普通暴力有什么本质区别吗？）听了讲之后才知道了一个结论：当走到一个陷阱时，在它之前的陷阱都一定处于激活状态。所以依据这个性质就可以推出状态转移，再用一个__二分+前缀和优化__就可以过了。
C
我很不擅长构造题，所以瞪了半天的题也没看出来什么眉目，所以我就写了一个暴力，想要通过小数据的所有可行解寻找一些普遍规律。很巧，我还真找出来了一个规律：
对于任意一个 \(n\)，都一定存在一个排列 \(p\) 使得 \(p_i + p_{i+1} = P (P \in \{ 奇质数 \},2 \not\mid P)\)。
所以根据这个性质，我打出了一个保证正确性的代码，但是打完测了一些大数据后发现会 \(\operatorname{TLE}\)，不过总比暴力好多了。
这里提供三种正解：
公差为5的等差数列
分别以 \(1,2,3,4,5\) 为首项，构造公差为 \(5\) 的等差数列，再根据条件把这 \(5\) 个等差数列首尾相接。
长度为8的循环节
构造一个排列 \(p=\{ x,x + 3,x + 6,x + 1,x + 4,x + 7,x + 2,x + 5 \}\)，然后根据不同的 \(x\) 这个排列构造多个循环节，最后把这些循环节首尾相接即可。
哥德巴赫猜想
引理1
哥德巴赫猜想：\(\forall n~(n \geq 4,2 \mid n)\)，一定存在 \(p1,p2 \in \{ primes \}\)，使得 \(p1 + p2 = n\)。
虽然未被证实，但是在一定范围内是绝对成立的。
引理2
\(\forall n~(n \geq 6,2 \mid n)\)，一定存在 \(p1,p2 \in \{ 奇质数 \}\)，使得 \(p1 + p2 = n\)。
论证：
由于 \(n\) 的取值范围较小，所以 \(n\) 满足哥德巴赫猜想。
但是当 \(p1 = 2\) 时，\(2 \mid p2\) 且 \(p2 \geq 4\)，则 \(p2\) 为合数。
而 \(n\) 满足哥德巴赫猜想，所以一定存在 \(p1,p2 \in \{ 奇质数 \}\)，使得 \(p1 + p2 = n\)。
引理3
对于任意的 \(n\)，一定存在一种排列 \(p\) 使得 \(\mid p_i - p_{i+1} \mid \in \{ 奇质数 \}\)。
引理4
对于 \(n~(2 \mid n)\)，只需找出一对 \((p1,p2)\)，使得 \(p1,p2 \in \{ 奇质数 \},p1 + p2 = n\)，
则对于每一个 \(i\)，答案即为 \((i \times p1) \bmod n + 1\)。
此时对于每一对 \((p_i,p_{i+1})\)，\(\mid p_i - p_{i+1} \mid = p1 ~ or ~ n-p1(即p2)\)。
而由于 \((p1,n)=1\)，所以此时的排列 \(p\) 是关于 \(n\) 的完全剩余系，即 \(p_i\) 两两不同，满足条件。
对于 \(n ~ (2 \not\mid n)\)，只需先求出一种满足条件的 \(n-1\) 的排列，然后再把 \(n\) 插进 \(p\) 即可。
D
做到这个题的时候已经没有太多时间了，所以准备打个暴力就走人。然而暴力都写错了，最后一分没得。
对于每一个单词 \(i\)，我们都预处理：
\(1.\) 以它为开头放置一个空行，下一行的第一个单词是第 \(f1_i\)；
\(2.\) 以它为开头放在图片所在行且放在图片左边，图片右边的第一个单词是 \(f2_i\)；
\(3.\) 以它为开头放在图片所在行且放在图片右边，下一行的第一个单词为 \(f3_i\)。
然后用倍增优化一下，在询问时就能跳多少行就跳多少行，即可求出答案。
总结
估分估得还是不太准，总是会估的比较高。而且 \(\operatorname{dp}\) 还是比较弱，总是知道某一道题要用 \(\operatorname{dp}\) ，但是就是不会设状态或写状态转移方程，以后要通过练题来提高自己的水平。构造题还做的不够好，以后要加以练习。
第二次考试
这次考试还是考得很差，以为自己能考 \(80 + 10 + 100 + 10 = 200\) 分，结果只得了 \(70 + 0 + 35 + 15 = 120\) 分。
A
考试的时候只想到了 \(O(n^3)\) 的暴力做法，死活想不出来怎么优化。最后用 \(\operatorname{bitset}\) 优化了一下，时间复杂度为 \(O(\frac{n^3}{w})\) ，虽然只得了 \(70\)，但是总归比纯暴力好。
正难则反，考虑先求出总的三角形个数，即为 \(\tbinom{n}{3}\)。
然后再求出非纯色三角形的个数，最后相减就可以了。
对于非纯色三角形，统计点 \(i\) 所连的红边数量 \(x\)，蓝边数量为 \(y\)，那以 \(i\) 为顶点的非纯色三角形的数量为 \(x \times y\)。
但是这样每个非纯色三角形会算两遍，所以把数量除以 \(2\) 即可。
B
在考试的时候觉得是个 \(\operatorname{dp}\)，但是我连状态都没想出来怎么设，直接爆零。
正解是带有贪心思想的 \(\operatorname{dp}\)。问题可以转化为，从右上角走到左下角01交替的最大次数。
则状态转移方程即为：
C
大模拟，没什么好说的，但是我考场上没拿到全分。考后改了很多遍，最后发现条件判多了。这道题的细节很多，是练习缜密性的好题。
D
可以把式子转化为：\(a_i - a_{i-1} \leq a_{i+1} - a_{i}\)，就是一个 差分递增。
把点丢到平面直角坐标系上，可以得到一个开口朝上的抛物线，而且两点的纵坐标之差递增。
讲原数组升序排序，则在谷底的一定是值最小的元素，且每一个点要么放在抛物线的左边，要么放在抛物线的右边，所以可以用 \(\operatorname{dp}\) 来进行方案转移。
设 \(f_{l_1,l_2,r_1,r_2}\) 表示 当前抛物线的左右端点分别为 \(l_1,r_1\)，上一次的抛物线左右端点分别为 \(l_2,r_2\)。
每一次，新加入的点都等于 \(\max(l_1,r_1) + 1\)，然后分情况讨论新加入的点在抛物线左端或右端，分别转移即可。
总结
这次考试说明以前学过的东西很多都忘了，之前做过很多正难则反的题目，现在居然还是一点都想不到，以后要经常温习之前做过的题。\(\operatorname{dp}\) 的题还是没做出来，以后要多加练习。代码力还是太差，需要总结经验，勤加练习。
DP1学习总结
最近学的内容都是 \(\operatorname{LIS}\)，\(\operatorname{LCS}\) 模型及其变种题目。以前觉得，这种模板类的题目并不是很难，而且也深挖不了。做了题之后才发现这种题居然可以挖得这么深。而且还学到了很多 \(\operatorname{dp}\) 技巧，比如求字典序最小（大）的可行方案、方案数等。
字典序最小
正着做比较麻烦，因为在同为最优解并且结尾一样的情况下，可能要往前比很多位，一定会 \(\operatorname{TLE}\)。
正着做麻烦就考虑倒着做。先将原序列翻转，然后 \(\operatorname{dp}\) 的时候，在保证最优解的情况下，越往后的位置，放置的数的字典序越小，最后从后往前倒推即可。带有一点贪心的思想。
\(O(n \log n)\) 求 \(\operatorname{LIS}\)
依旧设 \(dp_i\) 表示以 \(a_i\) 结尾的 \(\operatorname{LIS}\) 长度，不过转移有所不同。
二分
主要思想是贪心。
对于每一个长度 \(i\)，都记录一个 \(g_i\) 表示长度为 \(i\) 的上升子序列的末尾元素的最小值。
在求 \(dp_i\) 的时候，我们每次都找一个 \(g_j < a_i\) 的最大位置 \(j\)，此时 \(dp_i\) 即为 \(j+1\)，再用 \(a_i\) 更新 \(g_{j+1}\) 即可。
由于 \(g\) 中的元素单调递增，所以每次查找最大位置的时候可以使用二分。
树状数组
朴素的转移方程为：
考虑到这是一个 二位偏序，第一维已经满足有序，所以第二维可以用树状数组进行优化。
树状数组的转移方程为：
修改操作为：
每次询问、修改，都对树状数组中的元素取 \(\max\)。
当 \(a_i\) 的数据范围较大时，需要对其离散化。
方案数
对于 \(\operatorname{LIS}\)，只需要在转移时同时记录方案，如果比当前更优就把当前的方案数改为上一步的方案数，如果和当前长度一样就把上一步的方案数加上。
对于数据范围更大的，有两种做法：
二分
在 \(g\) 数组的基础上，在对每个长度记录一下它的历史修改，并记录方案数的前缀和，每一次二分的时候，都统计一下从当前位置往后的后缀和，再在插入的时候更新一下前缀和就可以了。
树状数组
再开一个记录方案数的树状数组 \(count\)，在询问时先把最大值 \(maxn\) 求出来，然后再在树状数组中将值域满足条件且那一位上的最大值等于 \(maxn\) 的 \(count\) 加上。
更新的时候，如果当前位的最大值小于更新的 \(v\)，则把更新的 \(w\) 设为当前位的方案数，如果当前位的最大值等于更新的 \(v\)，则把当前位的方案数加上 \(w\)。
总结
最近做了很多 \(\operatorname{dp}\) 的题，感觉自己的 \(\operatorname{dp}\) 水平又上了一个层次。但是考试考的还不是很好，以后需要继续总结提高。