近几场考试总结(8.30-9.7)

8.30

第一场，是自己唯一发挥正常的一场。
第一题，在天平上挂秤砣，很简单，一个明显的背包，唯一不同的就是有可能出现背包的值可能为负数，所以我们将背包整体加一个数，平移到正数的范围。计算了可能出现的最大值，算一下内存空间是可行的，直接写就好了。
第二题一看题目范围为\(10^{60}\)，同时要统计满足一些性质的数，所以就自然想到数位\(dp\)。数位\(dp\)记一下有无下降趋势，上一个数是什么，转移时判断是否出现山谷，如果出现就不转，否则就正常转移。
第三题，考场上只想到了前\(30\)分的答案可以直接算出来，得了30分，一直不知道如何处理第二个限制条件，感觉很难做。
看解析发现，因为答案的转移与每行的位置有关系，所以\(dp[k][l1][l2][l3][l4]\)表示用k种颜色第一行涂到l1,第二行涂l2，第三行l3,第四行l4的方案数。
\(dp[k]\)从\(dp[k-1]\)转移，所以滚掉一维。然后转移就正常转，枚举在哪一行涂这个颜色，每次要对不合法的l1,l2,l3,l4的\(dp\)值清零。
第四题，一看\(n\le3\),状压dp的灵魂开始苏醒,\(dp[i][s][t]\)表示第\(i\)行，当前行的状态为\(s\),上一行为\(t\)的方案数，转移即可得70分，因为转移是固定的，所以用矩阵快速幂加速即可。
预估总分300,实际总分300。

8.31

第一题一眼区间\(dp\),手臂不交叉则\(i,j\)内部的只能在内部连，所以\(dp[i][j]\)为i到j最多可以有多少人碰杯，奇数转移一定是不符合条件的会剩一个人无法碰杯，转移就很明显，算一下时间复杂度发现不能过，以为是暴力，就直接写了，只在最外层跳过了奇数，没在里面跳过奇数。结果这道题正解就是这个，只要跳过奇数即可通过，复杂度可能因为跳过奇数而下降明显，但我只判了一次，所以除了第一个点全超时（悲！）。
第二题读完题觉得不是\(dp\),觉得是贪心，所以想了两个情况，如果一个点的两个子树都可以分出n/3或一个点大小为\(\frac{2}{3}*n\)子树为n/3,就可以满足情况，没有严谨证明，但感觉很正确，可以包括所有情况。但写的时候有一个小细节写错了，过了样例后就没管了。结果一分没得。
第三题字符串与\(dp\)的结合题，用\(hash\)判断一下转移即可。但是我统计答案时将dp[i]=(dp[i]+dp[i-len])%mod,写成了dp[i]+=dp[i-len]%mod,所以取模炸了0分。
第四题,就想求\(lis\)一样去枚举转移，但复杂度是\(O(n^3)\),所以加一些数据结构优化过程，如加一个\(map\),\(logn\)的寻找。
所以

9.6

第一题，超级简单二进制转三进制即可。
第二题求最长的对角线，\(dp[i][j]\)表示以(i,j)为终点的最长对角线，取\(min(dp[i-1][j-1],左边最近的1的距离，上面最近的1的距离)\)转移即可。看到这你就会发现，只考虑了，左上到右下的情况没有考虑右上到左下的情况。所以挂分了，需要在做一遍\(dp\)才行。
第三题树型dp板子题，我一直以为是换根\(dp\),所以在正解树型\(dp\)上加了一些稀奇古怪的东西，还没跳出来，其实只需要直接每个点当根统计即可。
第四题很巧妙，用\(dp\)确定上界，然后深搜。但我还没学会，准备先写棋盘分割这道题。

9.7

第一题本来想写一个前缀和然后枚举，结果因为是最后写的，时间不太够，写挂了。正解是需要将前缀和的每一位减去第一位（一个典型的套路），这样只需要两个数相同则他们中间满足条件。可以用\(map\)加速。
第二题字符串题，栈+kmp或栈+hash即可。
第三题\(ACAM\)的典题，只需要将区间覆盖改为区间加，用差分修改即可，但我只输出了以特殊字符结尾的段，没有输出最后一部分，所以又爆0了。
第四题\(SA\)或\(SAM\)的题不会，等noip考完再来。

总结

这几场考试暴露出许多问题，感觉自己在考试上还有许多可以改进的地方，尤其是验题的能力。很多题都思考出了正解，但因为没有验好题而直接爆0，导致分数偏低。同时自己应选择时间复杂度允许下的最简单的实现方法，不要自己为难自己，同时暴力有的比较简单的但可以优化时间的一定要写，让暴力尽可能的优化。同时再做一些\(dp\)题，提升思维，熟悉套路。