题解 CF1446D1 【Frequency Problem (Easy Version)】

· · 题解

CF1446D1 Frequency Problem (Easy Version)&CF1446D2 Frequency Problem (Hard Version)解题报告：

更好的阅读体验

题意

分析

首先有一个结论：最长的众数不唯一的子序列一定包含整个序列的众数。

反证法：设整个序列的众数为x，如果这个子序列中众数不含有x，那么我们尝试每次给这个子序列扩展一个位置（如果扩展不了那么众数一定含有这个x），因为x为整个序列的众数，每一次扩展会最多让x增加1，所以总有一个时间x的数量会等于当前序列众数的数量，此时这个序列满足条件，且它一定优于原来的序列。

有了这个结论，我们先求得整个序列的众数x，如果众数不唯一，那么答案就是n，否则我们继续分析：

先考虑Easy Version，因为a_i的值域为[1,100]，所以我们直接枚举这个众数（设为y），然后重构一个新序列b：

对于一个满足条件的序列，它的x出现次数与y的出现次数一定相等，因此我们可以统计所有b之和为0的序列进答案。

但是这里有一个疑问：如果在某一个区间中存在一个数z，出现次数比x和y均多，那这样的序列是否合法？

还是可以用上面的那种扩展的方法，发现一定存在一个更长的序列众数为x,z，且比刚才的序列更优，因此刚刚的序列被统计了也不会对最终答案造成影响。

这样我们就用O(maxa\times n)的复杂度解决了Easy Version。

对于Hard Version，观察数据范围，我们可以考虑进行根号分治。

设定一个阈值S，对于出现次数大于S的数字，它的个数一定不会超过\frac{n}{S}，因此我们可以用一个\text{vector}存下所有出现次数大于S的数字，然后用Easy Version的方法暴力统计答案，时间复杂度O(n\sqrt{n})。

然后，对于出现次数小于等于S的数字，我们很显然可以枚举这个出现次数（设为i），然后对于整个序列做一遍\text{two pointer}，里面维护所有数的出现次数和出现次数的出现次数，只要出现次数i的出现次数大于等于2，我们就统计这个答案。这样我们可以用O(n\sqrt{n})的复杂度解决问题。

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

代码

Easy Version:

#include<stdio.h>
#define inf 1000000000
const int maxn=200005,maxk=105;
int n,maxx,cnt,ans;
int a[maxn],tot[maxk],sum[maxn],t[maxn*2];
inline int min(int a,int b){
    return a<b? a:b;
}
inline int max(int a,int b){
    return a>b? a:b;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        tot[a[i]]++;
    }
    for(int i=1;i<=100;i++){
        if(tot[i]==maxx)
            cnt++;
        if(tot[i]>maxx)
            cnt=1,maxx=tot[i];
    }
    if(cnt>1){
        printf("%d\n",n);
        return 0;
    }
    for(int i=1;i<=100;i++)
        if(tot[i]==maxx){
            maxx=i;
            break;
        }
    for(int i=1;i<=100;i++){
        for(int j=1;j<=n;j++)
            sum[j]=sum[j-1]+(a[j]==i? -1:(a[j]==maxx? 1:0));
        for(int j=-n;j<=n;j++)
            t[n+j]=inf;
        for(int j=1;j<=n;j++){
            ans=max(ans,j-t[n+sum[j]]+1);
            t[n+sum[j-1]]=min(t[n+sum[j-1]],j);
        }
    }
    printf("%d\n",ans);
    return 0;
}

Hard Version

#include<stdio.h>
#include<math.h>
#include<vector>
#define inf 1000000000
using namespace std;
const int maxn=200005,maxt=505;
int n,maxx,cnt,ans,S,val;
int a[maxn],tot[maxn],sum[maxn],t[maxn*2],cnt1[maxn],cnt2[maxn];
vector<int>v;
inline void modify(int x,int v){
    cnt2[cnt1[x]]--;
    cnt1[x]+=v;
    cnt2[cnt1[x]]++;
}
int main(){
    scanf("%d",&n),S=sqrt(n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        tot[a[i]]++;
    }
    for(int i=1;i<=n;i++){
        if(tot[i]==maxx)
            cnt++;
        if(tot[i]>maxx)
            cnt=1,maxx=tot[i];
    }
    if(cnt>1){
        printf("%d\n",n);
        return 0;
    }
    for(int i=1;i<=n;i++){
        if(tot[i]==maxx)
            val=i;
        else if(tot[i]>S)       
            v.push_back(i);
    }
    for(int i=0;i<v.size();i++){
        int k=v[i];
        for(int j=1;j<=n;j++)
            sum[j]=sum[j-1]+(a[j]==k? -1:(a[j]==val? 1:0));
        for(int j=-n;j<=n;j++)
            t[n+j]=inf;
        for(int j=1;j<=n;j++){
            ans=max(ans,j-t[n+sum[j]]+1);
            t[n+sum[j-1]]=min(t[n+sum[j-1]],j);
        }
    }
    for(int i=1;i<=S;i++){
        for(int j=1;j<=n;j++)
            cnt1[j]=cnt2[j]=0;
        int l=1,r=0;
        while(r<n){
            r++,modify(a[r],1);
            while(cnt1[a[r]]>i)
                modify(a[l],-1),l++;
            if(cnt2[i]>=2)
                ans=max(ans,r-l+1);
        }
    }
    printf("%d\n",ans);
    return 0;
}