集训模拟赛第二轮

nb_jzy · 2024-10-15 18:19:41 · 个人记录

10.15

时间轴

通读全文（今天见识到这一习惯的好处）。发现 A 题怎么又是位运算相关，B 题不是很会，C 题题意很简单，也很 dp，但是在担心会不会算重，看了下 D 题，感觉正解不太好做的样子。

重新开始看 A 题，发现题意可以转换成区间划分的形式，每个区间可以合并为其全部 & 操作起来，题目即求最多可以划分出多少个相同区间。这一看就很 dp。

一开始我一直认为需要枚举一段前缀，确定最终形态下每段区间的值。但这样如何做都不可能突破 \mathcal O(n^2)。于是我便想：是否其最终的数是确定的呢？毕竟这是位运算，而 & 操作最特殊的一点就是：只要有一位上有 0，其这一位的结果就必定为 0。而我们最终的这个数需要满足全局的情况，而如果有个数某个位是 0，那么必定有一段区间这一位上的值也是 0，也就是说最终的那个数字这一位上也是 0。

于是就有一个神奇的发现：最终的数字肯定是所有数 & 起来。

然后就随便 dp （或者是贪心？） 一下就好了，因为要优化成 n\times \log_2 n，于是我写了一棵线段树，打了一个 ST 表，还写了个二分。（好像做麻烦了）

发现过不了样例，原来 ST 表写错了。然后就往后了。

想了一下 B 题，发现不好做，dp 有很大的后效性，然后就只发现了一些自己都觉得神笔的性质。

因为刚刚就觉得 C 题十分好做，原来设的二位状态轻松就优化成了一维，而且这怎么重？这 dp 要是能重我当场就把这个电脑吃掉！然后先打了一个 \mathcal O(n^2)，发现样例过了，再测大样例，多少！算少了！不会吧！

然后就发现一个地方写错了，我就说，怎么可能算重。然后再一测，算多了！继续看代码，发现我写的什么东西，三目运算符里面完全写反了。

然后就过了所有样例，然后赌很多人不会开 T3，认为赢了。

继续回去做 B 题，发现其肯定会有一行或者一列颜色全部相同，然后就跟果果系统差不多，然后发现是 \mathcal O(n^3) 的，就快速写了一个和哈希。一测样例，发现多了。然后意识到这个东西实质上算不了最小，只能判无解。然后盯着 3000B 的哈希，没想出来其他的方式，就去做 D 题了。

看了一下 D 题，一开始觉得不是很好处理，或许还要在树上 dp？但观察了一会儿后就发现题意其实就是求在 l_1\sim r_1,l_2\sim r_2...l_k\sim r_k 这 k 段区间内的点所形成的连通块的个数 -1。然后 \mathcal O(n^2) 就会了，虽然并查集看上去有个 \log，但是无伤大雅。

调了一会儿后就过了样例和第一个大样例，第二个大样例跑了接近 30 秒，本来想把每次询问的复杂度优化成 \sum_{i=1}^{k} r_k-l_k+1，但是感觉没什么前途加上不是很想写（其实也没多写几行）就没写。

在 B 题和 D 题之间来回思考，但都没有过多的突破。于是根据 B 题答案上界不超过 n+m，以及哈希每次更新状态 \mathcal O(n+m)，就打了一个 IDDFS，加了一个小剪枝后第一个大样例就跑得飞快了。

检查低级失误，然后摆了。

直播评测，不是，这极域怎么又爆了，只好围着 hyy 和教师机看，然后就发现 B 题还多拿了 10 分，D 题多拿了 16 分，A,C 稳定通过了，本来已经以为赚到了，但是发现有人 D 题拿了 52 分？然后还跟我想的优化一样？我拿了还能有巧克力？

巧克力？？？？？？我怕长虫牙，不拿了。

总结

失误

1. 不要太懒了，CSP 和 NOIP 基本上都不是子任务，能多拿一个点是一个点，就像今天，如果把 D 题进行一点点小的常数优化其实就可以拿到更不错的分数。
2. 找性质的能力还是有待加强，比如 B 题还有更简单的一个性质：行和列肯定有一个要涂满。可能根据这一点可以想到更多吧。

   优点

3. 通读全文，似乎很多看了我总结的都在学习？记得点赞。

最后，还是希望能拿巧克力？ 上一个立 flag 的人还是上一个。

10.18

以下按通读全文后开题顺序所述。

A

构造，我怕过吗？注意到每个点和异色点的距离最小值肯定是与它直接连边的的点贡献的。所以我们可以考虑答案的形式肯定是每个点都与某一个异色点有一条边，这不就是一棵树吗？

那我们考虑这棵树有什么性质呢？显然，他肯定是原图的最小生成树，这样可以满足最大的边权最小。

然后我们找到最小生成树后就随便染一下色就行了。

在 8:50 打起了对拍（SPJ 和暴力写了一会儿），然后发现错了，原来是没把最后一条树边加进去，调出来后发现已经 9:10 了（这都能写这么久！）

D

这个题怎么这么的有趣呢？我发现两个根节点到其他节点的距离构成的多重集相同！然后就写了个哈希，发现全部输出 YES。然后就发现这只是个必要条件。（太蠢了）

然后除了一些显然的东西，就没找到其他比较有突破性的充要条件了。

然后在 9:40 果断放弃思考，输出了 YES。

B

感觉很简单，但是又很难。相当于把区间覆盖问题转换到树上，感觉“删除当前被覆盖次数最多的点”这一做法挺对的，然后就先写了个 \mathcal O(n^2)，发现调试一会儿后能过的数据都过了，然后就开始写了一坨，发现 n\le 10^5 的数据过不了。

然后就一直怀疑自己哪里写错了（毕竟写了很多），但是最终并没有看出来哪里有错误。

然后只能妥协：这是错误的。（现在想起来，当时实在是太蠢了，这个做法转换到区间上显然是一个错误的贪心啊！）

C

看了一会儿后会了 \mathcal O(n\times m\times \log_2 m)，但是要用 set，所以写了很久。

不过这道题实际上很妙啊，我们可以将“选择”转换为判定问题，就直接一股脑把所有可能有贡献的区间放进去，维护一下最大的一个位置使得能够覆盖某个点，查询是最小值，所以线段树可以直接打 lazy。

10.19

当了几次守门员之后还是倒三了。其实开题阅读完全文后就得出了一个结论：每道题都十分可做，但是好像都差一点。于是就陷入了最忌讳的一种策略：每道题来回思考。

时间轴

通读了全文，感觉 A 题可以树形背包，B 题构造但显然可以用二分图，注意到了 kmax 是最大匹配，但是 kmin 没意识到是什么。C 题显然状压，一眼看出来可以记录一下上次删的什么牌，然后每个牌堆的顺序就确定了，直接计算一下代价。D 题又是操作类型的题目，没有细想，而且 dfs 序不连续的修改怎么办呢？

开始想 A 题，想到了用 dp_{i,j,0/1} 表示以 i 为根的子树换了 j 条边后直径/最长链的最小长度。

正当我兴致勃勃地写的时候，突然意识到一个问题：每种直径的情况对应的最长链不同啊！我们并不知道是优先保证直径最小转移最长链还是保证最长链最小转移直径。

而这样的转移显然是个环，那直接 dp 就肯定不行了。

然后就将手离开键盘114514小时很久，想了一些其他做法，类似于贪心、二分之类都未果后，“果断”放弃了这题。

（但实际上还是经常回头看这题，而这些思考多半都是无意义的，只会耽误后面题目的思路）

（中途上了多次厕所，因为第一次 A 题没有明确思路）

开始慌了，看 B 题，虽然知道是二分图，但是还没有一些确定的构造方法，而且我还只知道 K=K_{MAX} 保留的点是哪些，想了一会儿后心烦意乱，又去上了个厕所，准备也跳了。

开始写 C 题，想到可以 \mathcal O(n\times m^3) 预处理，然后又突然想到可以 \mathcal O(2^m\times m^3) 预处理就可以 \mathcal O(2^m\times m^2) 转移（这样的优化没有任何用处！还将空间常数变大了）

然后就编译，发现 CE 了，于是就调调调，发现 2^m\times m^2 的数组开不下，然后又 WA 了，于是又调调调。中途一度慌过头，于是又去上了个厕所。

然后现在终于有 60 分了。

开始补救，打暴力，但是 A 题特殊性质判断错了，少了 10 分，B 题暴搜都没打完，D 题只会最简单的部分分。

反思

然后果不其然，打得是近几场以来最爆炸的一次。

问题有如下几点：

1. 太过于看重前面的题目有没有通过，导致卡一道 A 题后时间也花了，后面的题想起来也心烦意乱。
2. 思路太不集中了，一条思路未果后没办法将其他思路想到更深一步的地方，也不是很擅长将多种思路进行结合。
3. 不是很能接受多种做法假，如果都假了就不太能够正常思考了。
4. 就算自己已经下定决心跳过某道题目，还是会有藕断丝连的感觉，总是往回看，影响自己现在想的题，但是又不会又过多的效果。
5. 太懒了，哪怕知道做法是错的，为什么不写出来乱搞一下呢？知道是二分图为什么不写个匹配呢？构造为什么不写 SPJ 呢？如果我可以减少一些慌的时间和空想的时间，多写一些实际的做法，会不会好一些呢？
6. 暴力没有及时打，导致后面几道题打得很急，没有拿到应有的分数。

总之这次考试对于我来说还是一次很有价值的教训，希望能够在 CSP 之前将状态回暖吧。