题解：P13100 [FJCPC 2025] 众数

Deakin · 2025-12-19 21:24:37 · 题解

这题题面有点难懂，~~是我菜了~~。

题意

一个 n 个元素的集合 A，对于每个前缀 ^\text{①}：a_1,a_2,...,a_k，(1 \le k \le n)。对于当前前缀每一个非空下标子集 ^\text{②} S，定义 f(S)=\min\{a_i\}+\max\{a_i\} ^\text{③}，(i \in S)。求当前前缀中所有 2^k-1 ^\text{④} 个子集 S，f(S) 的最大众数 ^\text{⑤}。

:::info[注解]{open} ①〔前缀〕集合 A 的前任意个连续的元素的集合（从第一个元素开始）。

②〔非空子集〕在其中选任意至少一个元素的集和。

③〔\small f(S)〕简单的说就是，下标集合中对应元素的最大值加最小值的和。注意：在后面的示例中，S 不再代表下标，而直接代表元素。

④〔\small 2^k-1〕一共 k 个元素，每个有选和不选两种状态，共 2^k 种，但要求非空，因此去掉一种。

⑤〔众数〕所有数中出现次数最多的数，注意众数可以有多个，但题目要求的是最大众数。 :::

示例

~~样例 1 太臭了~~，所以我们手玩样例 2：

input:
5
1 2 3 4 5
output:
2 4 4 5 6

$\begin{cases} S_1=\{1\} & f(S_1)=2\\ \end{cases}$，最大众数为 $2$。
$\begin{cases} S_1=\{1\} & f(S_1)=2 \\ S_2=\{1,2\} & f(S_2)=3\\ S_3=\{2\} & f(S_3)=4 \\ \end{cases}$，最大众数为 $4$。
$\begin{cases} S_1=\{1\} & f(S_1)=2 \\ S_2=\{1,2\} & f(S_2)=3 \\ S_3=\{1,3\} & f(S_3)=4 \\ S_4=\{1,2,3\} & f(S_4)=4\\ S_5=\{2\} & f(S_5)=4 \\ S_6=\{2,3\} & f(S_6)=5 \\ S_7=\{3\} & f(S_7)=6 \\ \end{cases}$，最大众数为 $4$。

思路

因为 f(S) 只与 S 中的最大值和最小值有关，中间可以放多少个中间数（即大于最小值且小于最大值的数）不影响结果，但影响次数。
可以证明当有中间数存在时，最大众数就是整个前缀的最大值加最小值的和。

:::info[证明：存在中间数时，众数为最大值加最小值] 令当前前缀为：a_1,a_2,...,a_k，最大值为 a_x，最小值为 a_y，中间数为 a_i，(a_x>a_i>a_y)。
当 S 的上下界为 a_x 和 a_y 时，所能容纳的中间数的组合最多，但中间数不影响结果，只影响次数。因此 a_x+a_y 是出现次数最多的值，即众数。 :::

接下来我们分析没有中间数的情况。

令最大值为 a_x，最小值为 a_y，设最小值出现 b 次，最大值出现 k-b 次，此时所有的子集分为三类：

所有数都是最大值，因此所有子集中 \min(S)=\max(S)=a_x，结果为 2 \times a_x。
所有数都是最小值，因此所有子集中 \min(S)=\max(S)=a_y，结果为 2 \times a_y。
既有最大值也有最小值，因此所有子集中 \min(S)=a_y,\max(S)=a_x，结果为 a_x+a_y。

众数是这三种集合数量最多的，于是我们分析三种集合分别的数量。

所有数都是最大值的集合，次数为 2^{k-b}-1。
所有数都是最小值的集合，次数为 2^b-1。
既有最大值也有最小值的集合，次数为 2^k-2^{k-b}-2^b+1（空集被减了两次，需加回一次）。

可以证明，仅当 b=1 时，答案为 2 \times a_x，其余为 a_x+a_y。

:::info[证明：没有中间数，最小值仅出现 1 次，答案为 2 倍最大值，否则为最大值加最小值] 将 b=1 带入之前的三种集合数量公式，仅最大值数量为 2^{k-1}-1，仅最小值数量为 1，既有最大值也有最小值数量为 2^{k-1}-1。
此时，2 \times a_x 和 a_x+a_y 次数相同，最大众数为 2 \times a_x。

当 b>1 时，2 \times a_x 的次数会逐渐减小，a_x+a_y 变为最大众数。 :::

结论

没有中间数且最小值仅出现一次，答案为 2 \times a_x。有中间数存在或最小值次数不为一时，答案为 a_x+a_y。

代码就很好写了。

代码

#include<iostream>
using namespace std;
const int inf=0x7fffffff;
int r(){//快读
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int main(){
    int T=r();
    while(T--){
        int n=r();
        int x=-inf,y=inf;//max和min
        int cntx=0,cnty=0;//max和min分别的次数
        for(int i=1;i<=n;i++){
            int a=r();
            if(x==a)cntx++;
            else if(x<a)x=a,cntx=1;
            if(y==a)cnty++;
            else if(y>a)y=a,cnty=1;
            if(cnty==1&&cntx+cnty==i)printf("%d ",2*x);//最小值仅出现一次，且没有中间数
            else printf("%d ",x+y);//其余情况
        }
        printf("\n");
    }
    return 0;
}