找到
1
篇与
时间复杂度优化
相关的结果
-
![P13100 [FJCPC 2025] 众数 题解](//blog.xiaoeyv.com/usr/themes/joe/assets/images/lazyload.gif)
P13100 [FJCPC 2025] 众数 题解 P13100 [FJCPC 2025] 众数 题解 读题 题目数学公式有点多，先简单复述一下题意： 我们有一串数字，比如说 [4, 1, 5, 3]。 “第一个前缀” 就是前面一个数字：[4]。 “第二个前缀” 就是前面两个数字：[4,1]。 “第三个前缀” 就是前三个数字：[4,1,5]。 以此类推... 对于第 $ k $ 个前缀（长度为 $ k $ ），我们可以从里面任意挑选一些位置，至少要选一个。 比如前缀 [4,1,5]，可以选 {4}，也可以选 {1}，也可以选 {5}，也可以选 {4,1}，甚至可以选 {4,1,5}，总共有 $2^k-1$ 种选法。（子集个数公式，这个高一数学会讲，套公式就是快） 然后在选出来的这堆数里，找到最小和最大的那两个数相加 例如子集 {4,1}，最小是 1，最大是 4，1+4=5； 例如子集 {5}，最小也是最大都是 5，5+5=10； 例如子集 {4,1,5}，最小是 1，最大是 5，1+5=6。 我们把所有子集算出来的值放在一起，看哪个数字出现得最多。（这里就不举例了，一个一个算太累了） 特殊情况： 如果出现最多次数的数有好几个，比如“5”和“7”都出现了三次，就选大的那个数“7”作答案。 开始想算法 刚开始想用map做，但因为子集的数量是指数级的（$2^{k-1}$），所以如果用map记录来做时间复杂度就是O( $ 2^k $)，这里n有 $ 10^6 $ 根本跑不动。（不信可以试一试） 然后就想用数论优化了： 通过样例发现规律：众数的取值仅与当前前缀的最小值、最大值及其出现次数相关。 具体如何推导呢？我们分类讨论吧。这里我们把除了最小值和最大值的其他元素叫做中间元素。 如果存在中间元素，或最小值出现次数不少于 $ 2 $ 包含最小值和最大值的子集，无论是否包含中间元素，其 $ \min $ 必为最小值、$ \max $ 必为最大值，这类子集数量最多。即使存在次数相同的其他和，最小值+最大值也是其中最大的。 所以：众数为最小值+最大值。 若没有中间元素且最小值仅出现 $ 1 $ 次 此时元素只有 $ 1 $ 个最小值和若干最大值，包含最小值和最大值的子集与仅包含最大值的子集数量相同，但 $ 2\times 最大值 $ 更大。 所以：众数为 $ 2\times 最大值 $。 然后我们就可以愉快地写代码啦~ #include <bits/stdc++.h> #define ll long long using namespace std; int main() { ios::sync_with_stdio ( false ); cin.tie ( nullptr ); int T; cin >> T; while ( T-- ) { int n; cin >> n; ll minv = 0, maxv = 0; ll cmin = 0, cmax = 0; for ( int i = 1; i <= n; i++ ) { ll x; cin >> x; if ( i == 1 ) { cout << x * 2 << ' '; minv = maxv = x; cmin = cmax = 1; } else { if ( x == maxv ) { cmax++; } else if ( x > maxv ) { maxv = x; cmax = 1; } else if ( x == minv ) { cmin++; } else if ( x < minv ) { minv = x; cmin = 1; } ll cmid = i - cmin - cmax; if ( cmid > 0 || cmin >= 2 ) { cout << minv + maxv << ' '; } else { cout << maxv * 2 << ' '; } } } cout << endl; } return 0; }
![P13100 [FJCPC 2025] 众数 题解](http://blog.xiaoeyv.com/usr/themes/joe/assets/images/thumb/24.jpg)
