集训模拟赛第一轮

nb_jzy · 2024-10-05 18:57:55 · 个人记录

10.5

时间轴

国庆放假回来第一天，竟然没开门？？？延迟 10 分钟。

通读全文，A 很可做的样子。B 求前 k 大的和，这不我原创题套路，但是子集还限定元素个数，就不太会了。C 一看就是背包，但是还可以交换价值，有点意思。D 题什么大数据结构题。

发现还好假的不多，刚刚只保证了单调栈弹完后只含当前被删元素的位置个数。但是被删的那个元素可能弹掉了前面的一些元素，于是再加一个限制，让这些数还要满足能够弹完前面的所有元素，于是形式化就是还要满足 a_j>\max_{k=1}^{i-1}a_k。这个随便搞一下就行了。

继续对拍，最后一共拍了 20000 多组。

开始搞 B 题，想了很多做法，但是二分不会统计数量，搜索没办法保证每次都搜当前次大，用堆不会扩展和记录状态。想了很久后作出决定：跳了！

想 C 题，观察后发现被选的那些数之间不会互相交换，于是想考虑是不是可以把交换的和选的分成两段区间，发现好像不行。又考虑是不是选的数量越多越好（即把所有权值赋成 1），发现好像可以 HACK。于是又跳了。

只有看看 D 题了，\mathcal{O(n^3)} 是简单的，考虑是否能够继承答案，于是就有了 \mathcal{O(n^2\times \log_2n)}。觉得已经能拿不错的分了，但是其实傻了，\mathcal{O}(n^2) 换个枚举顺序就可以了。关键是最后还因为使用了 set，直接又 T 掉 10 分。

回头看 B，打了个搜索加剪枝（针对 a_i>0 的剪枝），测了一下 n=200，跑的飞快（因为写错了一个小地方）。

发现 C 题第一种思路是正确的，只需要按照体积排序就可以把它分成两段然后背包了，但是当时脑抽了，循环顺序写错变成完全背包加上时间复杂度莫名其妙多了个 n（其实可以边背包边统计答案），来不及调了，然后发现有 60 分，悲。

反思

1.别被一道题搞太久了，如果把 C 题 60 分搞出来这场比赛也是赢的。

2.少用类似 set 之类的快速STL。

PS.本来要写检讨，结果B题重测，0\rightarrow 30，刚好守门，不需要写了，但写都写了这么多，干脆写完。（毕竟考的也不好）。

D

很好啊，忘记可以在单调栈上做合并，于是写了依托。

10.6

咕咕咕。

策略依然是先通读全文，这个 A 题很好啊，虽然题意很简单，但是感觉不是很好做，数据范围也很迷惑，n\le 30000，应该是个小常数的 n^2。B 题看了一下，发现最大值是比较简单的，单调栈随便搞一下就行了，但是最小值就不会了。C 题题没读懂。D 题发现是超纲知识，感觉代码应该很长。

A

于是开始做 A 题，显然是可以 dp 的，并且我们显然可以将同一种数字同一处理，于是设了一个状态 f_{i,j,k} 表示前 i 种数字，第 i 种还剩 j 个，第 i-1 种还有 k 个。

这看起来是 \mathcal O(n^3) 的，但是我们没有其他思路，只能试一下。发现跑样例很快，n=30000,m=500 也飞快，但是 m=3 很慢，于是将 m\le 3 特判了。然后分析了一下，发现复杂度是接近 \mathcal O(n^2) 的（当时是伪证的，严谨证明见补充）。虽然 n=30000 ，但是我盲猜一波跑不满，就用了一个 unordered_map。

于是最后就爆了，m\le 3 还错了一个点！？

实际上我们只需要在进行一步观察，发现只要某个数的个数不是 3 的倍数，我们一定会将它和相邻几个凑成一对。而若每个数都是 3 的倍数，那么每种相同的分组数量也一定是 3 的倍数。于是我们可以先将所有数的个数通过操作变成 3 的倍数，然后就考虑 3 个数捆在一起，发现刚好是 30000/3=10000 ，就稳过了。

B

最大的方案是平凡的，最小简直就是****。

一个经典的转换是将一段区间的 -1 操作用差分表示后改成一个位置上 -1，另一个位置上 +1，我们首先在序列开头和末尾添加一个 0，得到差分数组后不难发现总和为 0，即在一些正数位置 -1，在一些负数位置 +1，使得每个位置都是 0。

而使得操作代价最小即可使用一种贪心策略：我们从后往前进行操作，考虑对于每个负数，找到最近的一个还未变成 0 的正数，和他进行抵消。

不严谨的证明如下：

设 i<j<j'<i',a_i,a_j<0,a_{i'},a_{j'}>0,|a_i|=|a_j|=|a_{i'}|=|a_{j'}|，因为我们要满足 a_j 先被消完，所以可能交换消的顺序的情况即如上，那么当前操作的代价即为 a_{i'} \times (i'-i)^2+a_{j'}\times (j'-j)^2，而若我们考虑将 i 和 j' 消，j 和 i' 消，就变成了 a_{i'}\times (i'-j)^2+a_{j'}\times (j'-i)^2，即证 (i'-j)^2+(j'-i)^2\le(i'-i)^2+(j'-j)^2，这显然是对的啊，因为呢将两式都加上 2\times (i'j'+ij-ij'-i'j)，就都变成了 (i'+j'-i-j)^2，肯定不会更劣。

这个转换差分的套路还是挺常见的，不要太局限了。

C

这个图困扰了我 5 分钟。

没什么思路，还是说这题实在是很妙啊。

这种将牌面划分成若干个区域的题目实际上就是在提醒我们两个字：地皮。但是我们会发现不同的划分方案之间会有重复，于是就是 dp 的经典套路，去重。

而去重主要有几种方式：要么使得状态不重不漏，要么再设一个状态记录重的个数，要么就是某二字词语：容斥（特指 2^n 的容斥）。而这题显然用容斥看起来是比较方便的，因为只有五种划分状态的方式，但是怎么算几种方案里面的交集呢？（可能只有我不会吧）

如图就十分明了了：

这是其中的一种情况，其他几种划分方式的交也类似。其实我们发现算重的部分就是这若干个划分方法会将矩形分为若干个正方形。

所以这提示我们还需要再算一下正方形的方案数，而正方形本身是简单的，就直接将横着放加竖着放再减去四个正方形。

但是代码是比较长的，因为不同的交集情况有 13 种（有两种系数为 0），封装后都有2000多B。

D

超纲题，仙人掌，我不会啊，但是思路是比较简单的，只需要对于每个环求出最短的一条经过它的路径，其他就和树差不多，就是很难写。

10.8

通读全文后发现 A 题是经典建图题，B 题怎么是构造！C 题是期望！D 题什么东西！预感会爆了。然后确实爆了。感觉就做了个 A 题。

A

比较套路，我将它命名为优化子集，感谢 Just_int_mian 大佬给我推荐了这道题目，使得我对这种建图思想有了更深刻的理解。

然后就用 Dijkstra？发现边权只有 0 和 1，于是 01BFS 即可，但是我地杰斯特拉过了，NKOJ 被卡了。

再次赞颂某二字词语：对拍。这使我发现没给 0 的 dis 数组赋值。

B

这就难起来了。相当于是通过洗牌的操作将序列排序。

发现洗牌操作的位置一直在变化，于是我们考虑用一种等价的方式洗牌，发现可以将其变化为（但是我没有发现）：

选择若干段连续的区间 (l_1,r_1),(l_2,r_2)...(l_{i-1},r_{i-1}),(l_i,r_i) l_1=1,r_i=n，将这些区间内的数字翻转，然后在整体翻转一次。

考虑是否有一种排序的过程可以转换为若干次这样的操作。想到快速排序。

我们把每一层大于 mid 的数记为 0，小于等于 mid 的数记为 1，我们的目标即把整段区间变为前面若干连续的 0，后面若干连续的 1，我们可以考虑用翻转操作合并若干段分开的 1。可以 3 个为一组，翻转第一个和第三个肯定是步数最少的。

而我们又发现每一层被划分成了若干不相交的区间，于是操作可以并行，理论的操作步数即为 \log_2 n\times \log_3 n，时间复杂度表示为 T(n)=2\times T(\frac{n}{2})+n\times \log_3 n（谁能告诉我主定理分析的结果，但是主不在乎）。

还有一个小细节是，因为每次整段区间被翻转了，所以答案有的要翻转，如果序列是倒着的，最后可能还要再将其全部翻转一遍。

C

不是很会啊，考试的时候甚至没算出来 \frac{7}{6}（发现是把几种方案当成等概率了）。参考 Aaron_Romeo 大佬的题解。

D

不会。

10.10

好啊好啊，说好的比上场简单，还真就比上场简单。

时间轴

取用以往的策略，首先通读全文，发现：咦？这 A 题好像有点难啊，多次修改怎么处理啊! B 题十分可做，但是好像有点细节。 C 题怎么又是计数！还是排列！ D 题没认真看，感觉和栈的操作差不多，或许考虑区间 dp，不过 n\le 3\times 10^5，没什么思路。

现在差不多会了 T2，把 A 题冲出来应该就赢了（但是好像并不是，200分基本上都有。）

于是盯着题面看了两分钟，咦？他原来说的是“可以”啊，只能进行一次操作的话，\mathcal O(n^3) 就是简单的。

而这种在树上选取一条简单路径的题目，不就是很经典的 dp 做法，考虑换根后枚举子树内的两条链做拼接。而这个代价很好算啊，只需要看其他的子树有多少 siz_u \ge K 就行了。

于是几分钟后写完，感觉大样例挺强的，本来想对拍，但是不想造树，于是就没有然后了。

好了，最煎熬的时刻到了。

发现 B 题比较简单，第一步就求出每个 a_i 作为最小值的区间，发现是笛卡尔树，但是为了保证常数，可以直接用单调栈维护 l 和 r。第二步就是经典的求第 k 大的做法，可以用堆，考虑扩展状态，再小小 \mathcal O(1) 计个数就可以了。

开始写 B 题，发现细节真的很多（因为希望实现一个 \mathcal O(n) 的 check），于是就先把统计排名的部分写了。测了一下第一个样例，没什么问题之后就把后面的堆给写了。然后就发现第二个样例过不了，多输出了一个 18。

看了一会儿没有结果之后就打了一个暴力，发现暴力也过不了样例。于是发现暴力跑出来的个数不止 \frac{n\times (n+1)}{2}，然后想了想，发现单调栈中相同的元素覆盖的区间会有交集。于是看了看建出来的笛卡尔树根本不是笛卡尔树。正在想怎么调时，发现 IMSB，直接任意一边跑单调栈的时候取等不就行了，这样肯定是笛卡尔树。

然后过了第二个样例，发现大样例过不了一点，然后我急了啊，一直怀疑是计数的时候细节方面写错了，于是这修修那补补，还是没什么进展。看了看排名算没算对，发现好像没对。

然后就是然后

但是看了很久之后还是没什么进展，于是又用暴力跑了一遍，发现好像细节没写错！？

然后我直接崩了啊，已经 10:40 了，我发现堆有两个地方写错了！？然后还又调了很久！？

看来抠细节的能力还是有待提高的。紧接着就打了个对拍，一直怕写错了。

赶紧开最后两道题，没多少时间细想了，于是 C 题打了个状压，还卡了一会儿常，D 题就写了个暴搜走人了。

反思

这场比赛其实并不是特别难（虽然 C 和 D 我还是做不出来），但是其实是比较极限的，试想，如果我 11:59 才调出来 B 题，那这场实际上就输了。

所以说，有以下几点值得注意：

1. 注意读题的准确性，这样可以为一些难调的题目节约时间。
2. 题目的细节要思考清楚，最好是在纸上写下一些关键点，防止写错浪费大量时间。

   10.12

   时间轴

   8:00\sim 8:10

通读了全文，发现 A 题是求每一位上 1 的总数小于等于 1 的序列的个数。B 题感觉不是很好做。C 题被构造劝退，还是在图上，更加劝退。 D 题看起来很数据结构，很快会了 40 分，不过预估代码长度爆炸。

于是选择回来想 A 题。

看到 n\le 16 之后就想到两类大方向，一种是最近才练的容斥，另一种是状压。

然后感觉状压可以做啊，设 f_{i,s} 表示当前考虑到第 i 为，用了的数的状态为 s。于是就推了一下对于 x\le r_i 且第 j 位为 1 的数有多少。然后发现过不了样例。

然后发现我在算什么东西，这样做其实是有后效性的，因为不能保证前面一些位上的情况，肯定是错的。

那怎么让它没有后效性呢？首先应该是从高到低考虑，这样可以保证大小关系，然后呢？看了看我刚刚推的东西，不就是分了两种情况吗？一种是前缀等于 r_i 的前缀，那么后面的数肯定是和 r_i 放一样的；一种是前缀小于 r_i 的前缀，那么就可以随便放。于是就把状态换成了 s 表示有多少数第 60\sim i+1 位与 r 相同。然后发现这不就是数位 dp 吗？（看来还是有进步）

于是优化了一些常数后就往后做了。

开始想 B 题，想到了最终结果的形式肯定是 x\times K +a_i+a_{i+1}+...-a_{n-1}-a_{n},a_1\sim a_n 为原序列的排列，但是无法证明每一种情况都能通过合并操作合法的构造出来，K 的系数 x 也不知道怎么求。（其实就是因为没想到可以将合并操作转换成一颗操作树）

然后就去体检了。

去体检了，但回来还是没什么思路。

准备先放一下 B 题，看 C 题，观察部分分，不知道 n 的奇偶性有什么用，n,m\le 20 状压就行了。

然后想到了一种构造方法：将两个偶点之间的一条边删去，然后马上被 HACK 了（我太弱了）。

发现树有很多分，然后想到可以用树形 dp，正准备开始写，发现记录字典序最大的方案就变成了 \mathcal O(n^2\times \log_2n)，想了一下能不能优化，发现好像空间怎么都有问题，因为只有 20 分，就先把 n,m\le 20 快速打了（埋坑了），准备实现 D 题“ 40 分的高分”

开始写 D 题，前两个子任务就是线段树板子，但是毕竟还是要写一会儿。（结果还是有个细节写错了）

然后做子任务 4，跟之前某场比赛的 D 题很想，就是一个先统计子树内再统计子树外的思想，想了一会儿后开写。然后发现过不了这一档的大样例，于是就开始调。结果是统计子树外部时忘记继续 dfs 了。

然后写着写着发现就 4000 B 了。（关键是这依托还只有 20 分）

垂死挣扎 B 题，但是没想到操作树真的很难做出来啊，我也不是很觉得有什么规律。 然后就打了一个爆搜，n\le 10 还过不了，于是花了这么久只有 5 分。

准备去实现 C 题 \mathcal O(n^2\times \log_2 n) 的做法，然后写着写着就崩溃了，因为没时间了。

打开时钟，开始倒计时。

结果

这场挂分严重，（这几场都没什么分拿来挂）C 题 20 分将 0,1 的状态含义搞反了（关键还能过样例！？），-20，D 题线段树 res=-1e14，但实际上下界可以到 -1e15 左右，关键是写子任务 4 意识到了这一点，然后又 -20。（为什么前后不统一！！！）

反思

1. 虽说这场打得很炸裂，但是这些小分平常也应该重视，他们可以给高分锦上添花，有时还可以拯救中档分于水深火热之中。
2. 结论一定要勇敢猜，比如说 B 题 K 的系数，其实感觉可能在每种本质相同的情况下是定值，但是就是被操作顺序困扰了，而如果想到树就一目了然了。以后这种合并的题目可以想一想是否是树的结构。
3. 细节一定要仔细抠好，像上下界开小这个问题已经是老生常谈，但这次又犯了。
4. 构造题多想想部分分的提示，比如 n 的奇偶性，其实是很有用的，因为当 n 为偶数时，实际上每个点都能变成奇点，所以说在树上的构造方式就是唯一的。奇数还是有点技巧，赛场上自己应该是不会的，但要多积累。
5. 不要把那些带有修改查询的操作固化的认为是数据结构，D 题技巧性还是很强，这种把儿子连续访问，子树也是一段区间的“ BDFS 序”还是比较又技巧性的。

   整体总结

   优点

6. 延续了自从前几次总结以来总结的方法，比如说每次都通读全文，一些简单但是有些细节的题目打对拍，这些策略都让自己每场比赛没有那么凌乱。
7. 一些时间点做出的策略还是比较的正确，基本上没有在一道题上花费超过两个小时的时间。
8. 对于一些题目条件的转换能力有所提升，一些比较难的问题虽然不能做出整道题目，但是大部分情况下能有客观的部分分。
9. 基本上每道题都在尽力拿分，没有哪道题目没留时间思考。（因为感觉这几天的题都挺难的）
10. 不会在因为某种思路错误而被其干扰，可以重新开辟一条道路进行思考，也不会因为一些题目没有做出来而被过度耽误其他题目。

    缺点

11. 想到一些自认为正确的做法时过于激动，导致可能浪费时间去实现一些很容易 HACK 的做法。
12. 一些有比较难写的细节的题目有时会写错然后调试很久。
13. 对于很多题目性质的挖掘还不够深入，导致一些题目无法推出正解或者是拿到一些理应获得的部分分。
14. 上次比赛犯了一个很久没犯过的错误了，就是上下界开小还有读题产生错误，希望下不为例（为什么这两个错误都出现在这周最后一次啊......）
15. 思维，思维要打开！！！多想一想与题目相关的模型，多敢于猜点结论。

总之，优点继续保持，缺点尽力改正。

CSP 前最后2周了，冲冲冲！！！

补充

好像有人不会10.6日的 A 题时间复杂度分析。（刚刚 IMSB 了）

我们的状态是 f_{i,j,k} 表示前 i 个数，第 i 个数还有 j 个，第 i-1 个数还有 k 个。那么有 \sum_{i=1}^m cnt_i\le n，我们的复杂度即为 \sum_{i=1}^{m-1} cnt_i\times cnt_{i+1}，因为 n^2=(\sum_{i=1}^m cnt_i)^2=\sum_{i=1}^m cnt_i^2+2\times \sum_{i=1}^{m} \sum_{j=i+1}^m cnt_i\times cnt_j > \sum_{i=1}^{m-1} cnt_i\times cnt_{i+1} ，故时间复杂度可缩放为 \mathcal O(n^2)。