题解：P11822 [湖北省选模拟 2025] 团队分组 / divide

· · 题解

测试点 1\sim 3

直接搜索所有可能的解，由于 n 很小可以直接通过。

测试点 4\sim 10

题目相当于对于每一个前缀，要将其分成若干个区间，要求区间和单调递减。同时字典序最小的限制要求后面的区间尽可能短，这个过程可以之间贪心。

直接 O(n) 模拟这一个过程，总时间复杂度 O(n^2)。

测试点 11\sim 17

考虑记 f_{i,j} 表示当前这一段是 [i,j)，处理 [0,j) 一共要分多少组，同时用 g_{i,j} 维护需要维护的求和。

因此有转移 f_{i,j}=f_{k,i}+1，g_{i,j}=g_{k,i}+f_{i,j}i，其中 k 为最大的满足 \sum\limits_{g=k}^{i-1}v_g>\sum\limits_{g=i}^{j-1}v_g 的数。

记 sum_i=\sum\limits_{j=i}^nv_i，对于 f_{i,j} 而言的转移点就是最大的 k，满足 sum_k-sum_i>sum_i-sum_j，也就是 sum_k>2sum_i-sum_j。

最终就是要求所有 f_{i,i+1} 和 g_{i,i+1}。但由于每一个点仅由一个点转移而来，所以考虑所有有用的状态数量。发现任何有用的状态都对应一个区间 [i,j)，其在某一个前缀的划分方案中出现。

对于 i-j\le \sqrt{n} 区间，这样的区间一共只有 O(n\sqrt{n}) 个；对于 i-j>\sqrt{n} 的区间，一个前缀中最多只有 O(\sqrt{n}) 个长度 >\sqrt{n} 的组，所以最多只有 O(n\sqrt{n}) 个有用的区间。因此，有用的状态最多只有 O(n\sqrt{n}) 个。

直接使用记忆化搜索，这样会访问到的状态数就是 O(n\sqrt{n}) 的。现在的问题就变成如何找到转移的 k，对于每一个状态使用二分可以做到 O(\log n)。

总复杂度 O(n\sqrt{n}\log n)。

常数较大的可能只能通过前一部分。

满分做法

优化找到每一个状态转移的 k。

按照 i 从大到小扫描，找到所有我们需要转移的 j。假设对于 i 的所有 j 已经按照从小到大排序了。

对序列进行分块，对于一个点 i，可以直接暴力 O(\sqrt{n}+cnt) 扫描出所有 k 和 i 在同一个块内的 j 对应的转移点，其中 cnt 为满足这样条件的 j 的数量。

对于 k 与 i 不在同一个块的转移，可以将当前块内的所有这样的状态 (i,j) 按照 2sum_i-sum_j 进行排序，然后 O(n) 扫描一遍所有的 k，即可同时扫描所有的 (i,j) 即可得到转移。由于 sum_i 的值有上界 n^2，排序可以做到 O(n)。

对于一个点 i，如果所有的 j 是从大到小加入的，就可以保证在处理 i 时所有的 j 已经排序完成，因此在对于每一个点加入需要转移的状态时，需要按照 i 的大小从大到小加入。

最后直接按照 i 从小到大依次求解 f 和 g 即可。

总时间复杂度 O(n\sqrt{n})。