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 $ 根本跑不动。（不信可以试一试）

然后就想用数论优化了：

通过样例发现规律：众数的取值仅与当前前缀的最小值、最大值及其出现次数相关。

具体如何推导呢？我们分类讨论吧。这里我们把除了最小值和最大值的其他元素叫做中间元素。

1. 如果存在中间元素，或最小值出现次数不少于 $ 2 $

包含最小值和最大值的子集，无论是否包含中间元素，其 $ \min $ 必为最小值、$ \max $ 必为最大值，这类子集数量最多。即使存在次数相同的其他和，最小值+最大值也是其中最大的。

所以：众数为最小值+最大值。

2. 若没有中间元素且最小值仅出现 $ 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;
}