集训阶段反思 · Week1

· · 个人记录

10.5 - 10.7

三天两场模拟赛，六天四场模拟赛。补题的速度要快起来了。

和题目有关的昨天写了很多了。现在写一些缺点吧。

贪心怎么写？

不会贪心。

贪心还是分很多种的，有 K 大这种的贪心（10.5 T2），有猜结论的贪心（10.6 T2）。很巧的是，我都不会。这就导致了模拟赛中严重的失分。所以这样的情况应该怎么避免呢？

要敢于猜结论。猜一个结论发现样例是对的，写就完事了。赛上证明一个贪心结论属实是太难了，10.6 T2 的贪心我到现在还没证明出来。

还有有关第 K 大的东西，貌似都能单独出一篇文章了。如果 K 在 10^5 这个级别，可以尝试用堆。状态的设计是一个难点，不同的状态要用怎样的元组表达取决于状态的复杂程度，还要保证状态能够不重不漏的计算到。

第 K 大子集可以用一个四元组 \left(l,x,r,v\right) 来表示。子集本身可以用一个 01 串表示是否选择某数，为了求 K 大可以将数组本身从大到小排序。那么由一个状态变到另一个更小的状态就可以用一个 1 和它右边的 0 交换来表示。四元组中的 x 就是上一次交换的 1 的位置，l 是它左边的第一个 1，r 是它右边的第一个 1，v 是子集和。每次转移可以尝试移动 x 和 l，这样能保证只有两个分支并且分别是最大子状态与次大子状态。这也分别保证了复杂度正确与不漏。而不重体现在移动的 1 的位置是单调不增的，这点比较显然，就不细说了。

当然 K 在这个级别也可以考虑二分。但是这个二分的 check 不一定是和 n 有关的计数，也可以是和 K 有关的枚举。像这个子集和就可以用神奇的搜索做到每一个状态都有效的 O(K)，感觉和用质因数凑出一个数是差不多的（指状态有效这一方面）。

如果 K 在 10^{12} 这个级别，就二分吧，没什么其它好说的了。这个时候 check 的复杂度一般就和 n 相关了。

计数 DP 怎么写？

我谔谔。

不管是计数 DP 也好组合计数也罢，我真的不会数数啊，，，

复杂度我也不会算，哭了。

先写一个惨痛的教训：若 a_1+a_2+a_3+ \dots +a_k = n，则 \sum\limits_{i=1}^{n-1} a_ia_{i+1} \leq n^2。（见注释 1。）就是这个东西害我昨天把复杂度算错了导致没写正解然后爆了啊啊啊。其实这个东西蛮好证的，昨天已经写过了。

计数 DP 真的是短板啊。计数我感觉也没什么技巧啊，就是一堆乘法原理一堆加法原理一堆容斥原理一堆状态设计叠在一起，只能多做题找找感觉了。

心态！！！

这两场比赛真的有点给我心态整崩了。T2 -> T2 不会 -> T1 不会。不可能是过了个国庆手感就生疏了啊。只能说调整好心态是非常重要的。但是呢心态这个东西又不能靠刷题取得，只能说是尽量地多打一些 CF 啊 AT 啊什么的，搞好一个比赛心态，这个任务确实比较首要。没有好心态做什么题也是白做。

事实上，我在想写大模拟或者说是骨牌那种码量比较大的题对心态有没有帮助。貌似得试一试了。

其它的反思后面再继续补充吧，心态一定要调整好啊。马上又要迎接新的两场模拟赛了。还是同样的，以崭新的面貌面对接下来的每一场崭新的比赛。

我们都有光明的未来。

10.8 - 10.9

本来以为能把 T3 打个 O(n^2q) 的，结果好像有点高估自己了。

还是没有 200pts 啊。

先写点题目总结吧。

T1

还是比较板吧。主要是类似位运算+最短路的题已经做过很多了，有异或的，有与的，总而言之，套路都是改一位。

唯一想说的是本来以为早上写的做法均摊下来是 O(V) 的（值域），结果还是 O(V \log V) 的，复杂度又算错了啊可恶。（见注释 2。）

T2

构造题我也不会啊。

最开始看了一会连严格 n 次操作的做法都不太会。那个把切牌操作转化成区间翻转再整体翻转的想法真的是非常神奇，也没有想到，这就使思维难度增大了很多。

在赛上只知道怎么把一个数放在另一个数后面，所以就想到了以此为基础的一个做法。找一串连续的数，把其最开始的一个数 a_1 换到 a_1-1 后面，然后发现很多放置操作可以在一次操作里面进行，而且普通的放置操作可能会影响后面的放置操作，有时，一个不那么普通的操作可能会让整体更优。

所以把 a_1 放在 a_1-1 后面的操作称作平凡操作，然后写了一个 DP。

这个神秘做法拿了 50pts，不细讲了。

正解是类似于快排的神奇东西，通过和快排相同的分治来让多个操作可以同时进行，非常有趣的想法，恍然大悟后感觉很不错。

T3

原来不是计数 DP 我也不会做啊可恶。

赛上 15pts 有点一眼了。写完 T2 的神秘做法后就在看能不能写个 O(n^2q) 拿个 55pts。看着很好拿，然而设了两个状态都不行后才发现好像有点离谱了。

最后 55pts 没拿到就连 15pts 也没拿到，芝麻也没捡到还丢了西瓜（好像也不算西瓜）啊。

正解一点也不套路。可以（但是很难）发现在每一轮操作时抽到的牌可以被划分为两类。一种是垃圾牌（雌雄双股剑，方天画戟），一种是好牌（贯石斧，诸葛连弩），抽到垃圾牌就丢掉然后抽下一轮，抽到好牌就收入囊中然后结束游戏。

这东西可以稍微理性一点地感性理解，如果 a_i 是好牌，那么比 a_i 大的牌也是好牌。因为 a_i 是好牌就代表抽到它再继续抽不会得到正收益。而抽到比 a_i 大的牌会让牌堆变得比抽到 a_i 后的牌堆更差，那么就肯定也不会得到正收益。

这也就是在说，好牌的定义是有一个阈值的，而这个阈值会随着剩余牌数的增大而减小（意思是剩的牌越少阈值越大）。这个也可以稍微理性一点地感性理解。在抽 i 次牌时的阈值是 k，那么抽 i+1 次牌时会比第 i 次多付出 C 的代价，那么我就需要更好的牌来弥补这个代价才能获得正收益，所以阈值就会变大。

那么就可以设 dp_{i,j} 表示剩余 i 张牌且阈值为 a_j 时的期望最大收益。但是呢这个二维 dp 比较抽象没搞懂，一维 dp 倒是搞懂了。直接设 dp_i 表示剩余 i 张牌的期望最大收益。因为能到达这一步说明前面抽到的都是垃圾牌，全部都扔掉了，所以前面的操作和现在的状态没有什么关系。（这里需要更加感性的感性理解。）那么我们可以直接枚举阈值为 k（第 k 张牌），就有转移式：

不写转移式了，因为如果想到这里就已经比较简单了。（想到这里本身就是难点了啊。）

转移式看起来是 O(n^2) 的，但是因为 a_k 有单调性，所以可以优化到 O(n \log n)。又因为阈值本身就有单调性，所以可以指针维护决策点优化到 O(n)。

这题多少带一点神奇贪心思想，但是我还是不会贪心啊可恶。而且写这题总结时是不是用了太多感性理解了啊。

T4

好题，性质给我听的一愣一愣的，但是不太会。赛上只知道可以根据边的值域来建生成树，没想到还可以用一个前缀值域然后做差分。

想到这个前缀值域过后就只需要维护连通性了，又因为子图和全图的 MST 的性质，可以把部分分做法优化到 O(nl)，再发现 l \geq n 时方案就不会变化了，那么部分分做法就可以优化到 O(n^2)。后面的就有些不会了，应该是根据当前的图去推一个增量，再用这个增量去推另一个增量，比较神奇，但是赛上没什么时间想。

10.10

打得还行，但是这个还行只是因为没有挂分并且多打了一些部分分然后排名就比较高，整体的提升空间还是很大的。

T1

啧。想了 10 min 贪心感觉好像不行就在想 DP 了。然后发现可以做，还是树上 DP，于是理所当然的想到了线段树合并。

到底哪里理所当然了啊！真的是蠢到离谱了才会把简单的树形 DP 复杂化成线段树合并的吧！

然后突然灵光一现了，发现这个东西不需要合并，因为它合并的一定是存储不相交区间信息的线段树，也就是每个点就只有一个状态，所以可以直接用普通线段树。

所以都想到这里了为什么不能直接用树形 DP 呢？啧，太傻了。

题目本身很简单，但是因为这个东西直到比赛开始 1h 才调完。在想，如果把这部分写线段树的时间让给 T4 而 T1 就写简单的树形 DP，能不能在赛上把 T4 想出来或者多拿点分呢？

所以说啊，又多了一条新的心得体会。想到做法时不要立刻去写，因为不仅可能正确性有问题，用一种更简单的解法代替可能会节约更多时间。

T2

简单笛卡尔树题，确实比较一眼，但是和 T3 的杜老师说的一眼不是同一个一眼，是数据结构特有的一眼。唯一可以说的就是卡常，但是我不想提这个让我有点伤心的事情。

T3

我不会容斥计数啊。

计数题真的都好难啊。这个 T3 看起来就像一道加强版的错排问题，感觉会比较难。赛上明明有两个小时去想后面的题，但是什么也没有想出来。

具体做法也很神奇，就是把 a_i 和对应的 b_i 分别连一条边，整张图就会是若干个环。然后会发现一个数不合法就意味着它的值是它对应的边的两端选一个点所对应的值。然后做一个环上 DP 再用总方案数减去不合法方案数就可以了。

挺难的，我还是不会数数题。

T4

哇，思维题。赛上打了一个记忆化搜索+区间 DP。

感觉正解就是猜结论+大分讨啊，练点计数题就去补一下吧。

10.12

爆完了。先把总结给写了吧。

T1

计数题练了和没练一样，虽然本来也没练多少。

一直在往容斥的方向考虑，状压则是想一想就弃掉了。但是这也并不能怪谁，只能怪我两种都学艺不精。本来最多 10 min 就可以看出来那题不能用容斥，因为对于一个不合法的集合，它的子集不一定同样不合法，这就导致 O(2^n) 容斥完全不可行。

正解是数位 DP。不是学了很久的知识点，果然放在非专题里就做不出来了。之前学数位 DP 的时候感觉这东西应该很好辨别，T1 的限制也特别像数位 DP，甚至正常人应该是一眼就想到数位 DP 的，然而我大抵是精神不太正常了。

正解就是简单数位 DP 加状压 limit，赛上没想出来，不知道为什么，可能还是因为学艺不精吧。希望这段时间能把计数题给补起来啊，还记得上一次强制总结也是因为 T1 是计数题。

T2

为什么呢？

不知道在哪里多出了一段做过类似的题的记忆，也不知道是不是错觉。赛上想到了拆贡献，每个数的正负贡献取决于其被合并的次数以及要对每一种正贡献数量算一个 K 的数量这些东西。但是因为没有建树所以不知道具体怎么算。把树建出来了过后就会发现这个东西是定值并且很好算。如果赛上做到这一步感觉就可以做出来了。

然而实际上好像打表也是可以猜到结论的，但是我并没有想到去找规律，其实有时候这也可以说是一种有效的做法。

然后可以分别把与前 cnt 大值和与 K 相关的函数写出来，答案就是相加后取个最大值。因为是一次相关所以可以李超线段树，但是推式子能发现这个东西是单峰的，所以可以直接二分。

然后这个题就做完了。

其实本来想看能不能做到单组询问 O(n) 然后多拿点部分分，但是最后连 5 分暴力都没拿到。虽然已经考成这样了暴力打不打挂已经没多大关系了。其实比之前那次 T1 没做出来已经好很多了，至少心态没那么炸了，然后 T1 也只看了 1 h 30 min，所以看起来有很多时间留给了后面的题，虽然没拿多少分就是了。主要还是套路见少了，没有建树。诶。

T3

看着就是比较恶心的题。怎么说呢，就是那种不会考很复杂算法但是很难想的题。哦，想起来了，叫思维题。

赛上没想多久就去看 T4 了，看完 T4 又看了看这题的数据，感觉树的部分分还是很好拿的，就开写了。

结果写了 5KB...原因是并没有想到树的最大方案是在 n 为偶数时是唯一的，所以就直接开写了，写了一个很复杂的记录方案的东西，而且还没有过样例。后面一怒之下把 5KB 全删了，打了个 20pts 的暴力，但是挂了。虽然挂不挂都没有区别就是了。

正解说难想也不难想，也是比较套路的。只要发现树的最大方案在 n 为偶数时是唯一的这个性质后面的思路就会比较自然了。其实，光想到这里好像就已经有一些部分分了，然后再加上 n 为奇数时枚举偶度点的 O(n^2) 应该就有 50pts 了。既然是枚举偶度点进行 dfs，那么换根也顺理成章了。就是那个反转路径上的边以达到答案最大的目的确实有点难想，然后从高位到低位贪心也要一定思考。

树上做法出来过后图上做法也很显然了，就是贪心地从后缀找一棵最大生成树然后跑上面的树上做法。

虽然这一整段都感觉透露着这道题不难想的感觉，但是赛上还是没有思路。不好评价了。

T4

哇，还有黑科技数据结构。

本来想过 bfs 序拿点部分分，结果发现要做一堆容斥啥的就没有写。没想到正解还真的跟这玩意有点关系。

看着 0 \leq k \leq 9 就很神奇，突破口肯定就在这里。然后是非常神奇的 bdfs 序，然后就做完了。

小数据结构题，看起来没什么意义，好像实际上也没什么意义。会神奇 bdfs 序的就会做，不会的就不会做，但是好歹也算学了点新东西吧。

总结

四道题都分析了一遍了，那就罗列一下问题吧。

计数

还是不会。练了也不会，因为计数是很多变的，有可能是容斥，可能是状压，可能是数位 DP，但是肯定都和 DP 脱不了关系，所以归根结底还是 DP 练少了。

套路

这一次记住了合并操作可以建树，那下一次呢？很有可能有什么新的套路，但是我也不会，然后又拿不到什么高分。这样看来，不仅是 DP 练少了，什么东西都练少了。

心态

写过很多遍的问题了。这次心态要比上次好一点了，但还是出现了无能狂怒的情况，删了写的 5KB 的没用代码类似的。但是时间安排还是比较合理的，所以问题主要就是上面两点。

总感觉这模拟赛是越来越难了。就昨天的模拟赛简单了一会。感觉自己的发挥不是特别稳定，还记得上次 NOIP 模拟赛 T2 的数数题都能 A，现在 T1 的数数都不行了。总之还是要加练了。平时休整日就多写点题吧，希望以后不会再被 T1 数数卡了，然后多见一点套路就更好了。

我们都有光明的未来。

Week 1 总结的总结

这周怎么不止七天啊。

总算是进入了停课集训的阶段，可能要辛苦很久了。这周最大的收获就是真正找到了自己最最最薄弱的点：数数。两次考炸都是因为 T1 放了数数题。套路也见了一些了，回过头来看有以下这些：

有关题目和知识点本身的已经写了很多了，无非都是数数、贪心、套路什么的。但是跳出逻辑之外的，比赛时的一些问题好像还没有写。

这周应该是犯过低级错误的。比如某次考试的 T4，本来以为所有题都是 1 GB 就没有看到它特殊的数据范围是 32 MB，然后导致暴力挂了 5pts。再者，上次考试排名不高，也是因为暴力打挂了 20pts 多一点，虽然打对了排名也好不到哪里去，而且对我而言 100pts 和我这个分差不多，都是最最最基础的暴力而已，打对打挂都会暴露出我知识点掌握不牢固的事实。但是还好这周应该拿高分的题都没有挂掉，打对拍还是有用的。虽然我有一次 T1 T2 都打了对拍但是没有错。

即使如此，比赛策略却完善了不少。例如可以根据 T1 估计本场难度然后进行合理时间分配（当然其它题也是要看的），如果是数数题这场可能就有点难了，或者 1h 都没做出来那么可能也有点难了。部分分方面能拿多少就拿多少。事实上我好几次都朝着拿高点的部分分想，但是那些简单的性质我却总是想不到，所以需要性质的部分分要认真推性质，可能推着推着就想到正解了。实在没有性质可发现时，打打表找找规律或是猜结论再去验证都是还行的手段。如果这些都不行，那就出去转转，说不定就想到了呢，而且还可以散散心，防止心态爆炸。

另外，说到心态，心态一定要稳定，只有心态稳定了，发挥才能稳定，太过消极的心态和过分骄傲的心态都是不可取的。（当然我现在只可能太过消极，没有过分骄傲的资本啊。）在每一场比赛中都只记住得到的知识、学会的套路和掌握的策略就好了，没必要老是去想上一次的成绩，每次打完模拟赛再和之前作对比来进行复盘总结，吸取教训。

找到弱点了就要努力去击破，现在正在造一张计数题题单，相信计数能力一定会有提升的。如果再有哪次还是这种名次，一次加练五道计数题，这也算是一种激励和警示吧，期待着可以完全拿下一场模拟赛，先暂时朝着这个目标前进吧，都已经把暂时停停whk作为代价了，不拿出点成绩可说不过去呢。计数，贪心，结论，DS，图论，现在就来迎接你们。

我们都有光明的未来。

注释

1.“实际上，ny_fengzixuan 告诉我如果每次都把枚举的其中一个数看成 n，那么另一个数的和就会刚好为 n，时间复杂度 O(n^2)。”——摘自 10.6模拟赛反思 By Just_int_mian。

感谢 nk_fzx_sd 提供证明。感谢 nk_fzx_sd 教了我怎么打出 \sum。

2.又是喜闻乐见的复杂度证明环节。所有二进制下长度为 20 的数的 1 的个数的和就是我最坏情况下的复杂度。这个东西等于 \sum\limits_{i=1}^{20}C_{n}^{i}i。拆柿子得到

\sum\limits_{i=1}^{20}C_{n}^{i}i = \sum\limits_{i=1}^{20}\frac{n!}{i!\left(n-i\right)!} i = \sum\limits_{i=1}^{20}\frac{n!}{\left(i-1\right)!\left(n-i\right)!} = n\sum\limits_{i=1}^{20}\frac{\left(n-1\right)!}{\left(i-1\right)!\left(n-i\right)!}=n\sum\limits_{i=1}^{20}C_{n-1}^{i-1}

这个东西就等于 \frac{V \log V}{2} 即 O(V \log V)。

不是特别感谢 nk_fzx_sd 提供证明，因为这个证明把问题复杂化了。感谢 nk_fzx_sd 教了我怎么打出 \sum。

感谢 wxr_ 提供另一个证明：每一位上的 1 只会在一半的数上面出现，所以答案为 \frac{V \log V}{2} 即 O(V \log V)。