10.6模拟赛反思

· · 个人记录

约等于干坐了四个小时，不在倒三还是因为别人没写freopen。怎么说也得写一篇总结了，发挥完全不在我能接受的范围内。

UPD:本来这篇反思起稿在重测前，但是重测之后真的倒三了。

T1

起码想了2h，结果什么也没搞出来。挺好笑的，花了0.5h写了一个看得过去的 DP 式，但是只能过四个样例。看第五个样例看了很久，然后搞了一堆一点用的没有的特判，还是过不去。

看样例答案都是什么 3^7，2^4，开始怀疑是不是 DP。万一是什么神奇组合数呢？然后又在错误的道路上想了 0.5h。

其实很早就考虑到了设两个数在状态里的情况，但是没有认真算，以为暴力枚举是 O(n^3) 的，神秘了。实际上，ny_fengzixuan 告诉我如果每次都把枚举的其中一个数看成 n，那么另一个数的和就会刚好为 n，时间复杂度 O(n^2)。所以正常情况下算法运行次数会比 O(n^2) 低。也算是学到了一个算复杂度的小技巧。

状态设对了就很好转移了。设 dp_{i,j} 表示当前这个数为 i，上一个数为 j 时的方案数（哪一个数被滚动掉了），那么就有 dp_{i,j} = dp_{j+cnt_i-i,cnt_i-i}，然后再做一个后缀和。事实上这个转移写出来算对了好像就是 O(n^2) 的，因为我写的转移比较神奇，求后缀和的部分直接成为了转移的一部分。

然后还有卡常小技巧（当然这道题是必备的），先把必须要做的连续三个数的方案提出来，让状态只有 3 的倍数，从而让状态数变成 \frac{1}{9} n^2，才能过掉这个 n \leq 30000 的 n^2。

总而言之，这道题没拿到高分的原因就是复杂度算错了加上抱有 O(n^3) 不想写这种想法。这两个东西都是不该有的，尤其是不想写这个东西只能自己去克服，虽然后面几道题或多或少都有这点想法，这可能是我心态爆了引起的。

T2

一直觉得心态蛮不错的，但是今天才发现 T1 没做出来导致整个人都崩掉了。之前模拟赛的 T2 基本上都是做出来或者说能拿高分的，但是从昨天的 T2 没想出来到今天 T1 崩掉对心态还是有很大影响的。都不是什么难题，主要就是贪心这种偏思维的东西真的不太会。

这都什么东西啊。

这么套路的题怎么都做不出来？

昨天的 T2 就是个用堆实现第 K 大，但是我不会那个三元组存状态就写了个 O(n^2Klogn) 还是什么的只拿了 60pts。明明有更简单的二分做法但是也没有细想怎么 check，一直撞了南墙也不回头地想。今天 T1 也是，就死磕 T1 的 错误做法 磕了两个小时。

怎么戾气这么重呢？

好像扯远了。今天 T2 也比较套路的。区间加转差分这玩意之前接触过不少了，赛上还是没想到这个转化。套上这个差分再猜猜结论对着样例凑一凑这题就做完了。说思维难度真的就高不到哪里去，感觉纯粹是 T1 给多时间了。细节也不难实现，待会补一下吧。

转完差分会发现原操作就是给差分序列中的一个数 -1，后面再选一个数 +1，最后让整个序列变为 0。操作对于最大代价和最小代价不同地贪就可以了。

T3

没看。

大失误。

爆！

都怪 T1。

也不能怪 T1，只能怪我太菜了。

理论上来说多拿 5pts 就能不在倒三虽然对我而言没什么区别，这篇总结还是会有的。想提升只能对自己高标准严要求，不到 200pts/Rank 5 的模拟赛我都接受不了。照这么说得找个时间把昨天的模拟赛也写个总结了。

也确实该写，昨天题挺好的。

比较神奇的题目。k \leq 10 又是分治第一眼是个搜索，但是看到有模数的计数好像又是 DP。就这么喜欢计数 DP 吗。

直接考虑有哪些合法矩阵，发现合法矩阵的数量不会太多，即使最底层也只会有 2^{2k+1} 个合法矩阵而已。再往上就是四个小矩阵能合成一个大矩阵。所以感性理解每一层的矩阵数连起来会呈现一个等比数列，求和约为 4^k。那么就可以直接把这东西设状态里面了。从小矩阵推到大矩阵。最底层的矩阵中，如果一个矩阵刚好包含一块骨牌或是与骨牌没有交，那么它就是合法的，方案数为 1，否则方案数为 0。对于上层矩阵，枚举它的每一种分割方式做乘法原理再做加法原理。但是稍微动动脑子发现会算重。

去重要么重新设计状态，要么容斥。这里的分割方式只有 5 种，所以考虑容斥。看起来有 2^5 种，但是杜老师说只有 11 种。听着常数很大。容斥的方式就是把需要容斥的分割方式叠加在一起，然后产生新的容斥分割方式，计数再乘上容斥系数。有些方式重叠在一起后（好像是很多）会产生 2^k \times 2^k 的矩阵而不是 2^k \times 2^{k+1} 的，这个也要转移，当然也要容斥。

计数 DP 从来都是我的短板，短的不能再短的短板。T1 也是计数 DP T3 也是计数 DP，像个弱点击破仪式一样，只不过把我击破了。

T4

不好题，很难写。

有倒序开题的调出来了，挺有实力。

做法就不讲了，我还是更倾向于建圆方树的。事实上我一直以为 Block-Cut Tree 和圆方树是一种东西。

同样抱着好难写啊的心态，赛上部分分没打全。没什么好评价的，这样的错误一定不能再犯了。

总结

题是好的，心态是坏的。

心态原来真的这么重要啊，果然还是要学着调整心态的。

套路这方面还是见的太少了，本来 T2 应该也做的出来才对的。

明天应该是还有模拟赛的。吸取这次的教训，以崭新的面貌面对每一场比赛就好了。

我们都有光明的未来。