5030. 核心元素

暴力枚举

暴力枚举所有情况的左右端点 -> 所有子数组 O(n^2)
找单个子数组的核心元素 O(n)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 5010;
int n, a[N], cnt[N], ans[N];//  cnt[i]统计i出现的次数
int main() {
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i];
    for(int i=1; i<=n; i++){//  枚举左端点
        for(int j=i; j<=n; j++){//  枚举右端点
            memset(cnt, 0, sizeof cnt);
            for(int k=i; k<=j; k++)
                cnt[a[k]] ++;
            int mx = 0, t;
            for(int k=1; k<=n; k++){//  找到当前子数组的核心元素
                if(cnt[k] > mx){
                    mx = cnt[k];
                    t = k;
                }
            }
            ans[t] ++;
        }
    }
    for(int i=1; i<=n; i++) cout<<ans[i]<<" ";
    return 0;
}

优化

暴力枚举左右端点 -> 所有子数组 O(n^2)
边枚举边处理子数组计算核心元素
由于用的是哈希查找，可以用O(1)的时间复杂度查找对应元素的出现次数
可以用t来维护当前核心元素

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 5010;
int n, a[N], cnt[N], ans[N];//  cnt[i]统计i出现的次数
int main() {
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i];
    for(int i=1; i<=n; i++){//  枚举左端点
        memset(cnt, 0, sizeof cnt);
        int t = 0;//  当前核心元素
        for(int j=i; j<=n; j++){//  枚举右端点
            cnt[a[j]] ++;
            if(cnt[a[j]] > cnt[t] || (cnt[a[j]] == cnt[t] && a[j] < t)){
                t = a[j];
            }
            ans[t] ++;
        }
    }
    for(int i=1; i<=n; i++) cout<<ans[i]<<" ";
    return 0;
}