# 小白月赛96出题人题解

写在前面

感谢 贡献的 ，以及各位验题、内测、讲题的大佬~

出题人： _

对于内测时题数据的争议：当时,但是发现卡不掉 的写法，说改部分题意，但是我懒了就没改，若影响体验，在此说声抱歉。

A.最少胜利题数

预期难度：400

当胜利方达到 题时，失败方无法反超。

否则失败方反超胜利方只需要解出差值题数 即可。

时间复杂度：

B.最少操作次数

预期难度：800

当整个串为全 或者全 时，操作次数为 .

当整个字符串的 数量不等时，可以直接选取索引 和索引 直接操作，此时只需要 次。

当整个字符串的 数量相等时，必定存在索引 使得 的 数量不等，然后先操作这个区间，使得整个串的 数量不等，再操作一次即可达到要求。

特判字符串为 和 的无解情况。

时间复杂度：

C.最多数组数量

预期难度：1200

我们首先考虑双 暴力搜索，必然超时，故考虑枚举每个索引， 级别查询另一个满足条件的索引。

由于要满足 且前缀和单调，所以可以二分查询最左端满足 的索引 。

然后再找满足 的最左端索引 故当前索引的答案即为 ，累加所有索引的答案即可，需要注意的是只有当 和 都存在时才可进行计算。

时间复杂度：

也可双指针做法，时间复杂度 。

D.最小连通代价

预期难度：1500

首先抓住最小值和连通两个要求入手。

首先我们把所有可加的负边权全部加上，然后再考虑连通性。

在上一步的基础上，考虑不同奇偶数是否连通，如果已经连通，就输出答案，因为后边的正边权可以不加。

此时只有两种情况导致不连通。

.全是奇数或者全是偶数:如果相同奇偶性质的已经连通则输出答案，否则，只需要加上 条的 即可。

.：分类讨论相同性质的是否连通。

如果连通，只需要加上一个即可。

如果不连通，由于不同奇偶性质必须连接一个 ，剩下的 个点就选择选择 较小代价连接即可。

时间复杂度：

E.最大稳定数值

预期难度：1700

首先先考虑不使用删除的机会，算出此时的答案 。

然后枚举每条边删除的可能，记录每种答案。

由于删除一棵子树对上层结点已经是目标结点并不会产生影响。

所以枚举删除每条边，我们可以记录对于当前结点中，有多少个上层结点是满足条件 不满足条件 的，然后在树状数组上记录这种点需要扣掉多少值才能满足条件，此时的答案即为。

( 表示结点 为根的子树存在多少个目标结点， 表示结点 为根的子树的权值总和, 表示删除 会新增的目标结点个数。)

此表达式的值意思为整棵树中目标结点总数减去删除此子树目标结点总数，加上删除此子树会让上层结点中非目标结点成为目标结点的数量。

由于需要在树状数组上维护权值，其权值很大,但不同的个数不会超过 个，提前离散化即可。

答案在所有情况中取最大值。

时间复杂度：

F.最少逆序对数

预期难度：1900

我们考虑把第 个数加进去时对每个数的贡献。

用 表示数字 如果做为首元素进行后移操作时贡献的逆序对对数，那么新增一个数字 时，贡献应为

解释：这个元素由于处在 的前面，所以只有小于 的元素后移才可以新增逆序对数量，大于 的则会由原本的正贡献变为负贡献。

那么我们计算区间 时的最少逆序对数量则先计算出此时的不操作时的逆序对总数 。

然后枚举 中的所有点进行操作时的前缀贡献对数 ，取最小的 再加上 即可。

时间复杂度：