2025/08/23 模拟赛总结

模拟赛排名：\(90+100+100+30,1/30\)。

其实本来是 \(90+100+70+30\) 的，然而某题出锅了，把数据修改后就 \(100\) 分了。

\(T1\)

求最短区间满足区间和 \(\ge L\)。

这题真的太水了，一眼双指针。不过看我没拿到满分就说明我挂了。

原来题目还有个限制：

如果不存在，输出0。

眼瞎了没看到。（这里引用 3k 的下次一定）

\(T2\)

给你一个数组，分别求：

一段最长的，严格递增的，右端点最小的子区间，输出该子区间的右端点。

去掉一个区间后，一段最长的，严格递增的，右端点最小的子区间，输出该子区间的右端点和长度。

首先考虑第一问，非常的水，几乎等于纯凑数的，设 \(dp_i\) 表示子区间右端点为 \(i\) 时最长区间，不难有一个转移：

\(\begin{cases}dp_{i - 1} + 1,&a_i>a_{i - 1}\\1,&a_i\leqslant a_{i - 1}\end{cases}\)

很容易得证，因为必须得是连续的区间，所以必须从 \(dp_{i - 1}\) 转移。

然后思考第二问，有意识反映出第二问肯定和第一问有很大关系。所以我们设 \(dp2_i\) 表示表示子区间右端点为 \(i\) 时最长的去掉一个区间后的区间长度，这样 \(dp2_i\) 可以从 \(dp2_{i - 1}\) 转移（已选择区间）和最大的 \(dp_j\;(a_j < a_i)\) 转移（未选择区间）。这里可以用树状数组维护，每当求出一个答案后把 \(dp_i\) 插入树状数组。

\(T3\)

给定一个 \(n\) 点 \(m\) 边的无向图，从中选出两个没有公共边的生成树，使得被选择的边权值和最小。有 \(T\) 组数据。

\(n \le 10,m \le 25,T \le 5000\)

\(n\) 竟然只有十，这可不可以暴力过？然后发现暴力比较难写，枚举边就会爆了，只能枚举点。

回想一下最小生成树的做法：对边权排序，如果边的两端不在同一个并查集内则进行合并。那么到了两棵树内也是如此：

这条边连在第一棵树上枚举，或者连在第二棵树上枚举。由于最多只要合并 \(2n\) 次，所以复杂度就是 \(\mathcal{O}\)\((2^{2n}m\,T)\) 了，但复杂度显然偏高。

但有些边只可能连在一棵树上，当两棵树都需要合并这条边时才需要分开枚举。都没有被合并的情况显然最多 \(n - 1\) 次，所以复杂度降到 \(\mathcal{O}\)\((2^{n}m\,T)\)。不过因为要支持并查集回溯，所以需要使用可撤销并查集，这正是前几天我在博客上强调的。

不过听别人说这种做法是暴力，因为有人用别的做法耗时很短过了，而且还支持更多棵生成树。不过我还是别想这么高端的写法了。

\(T4\)

太难了，直接躺平写暴力算了

不过现在题解也没看懂。

总之，10min切T1,40min切T2,2h30min切T3应该还算快吧。