前缀和做法

CashCollectFactory · 2023-12-03 11:24:57 · 题解

这一套 ICPC 的问题全是关于原神的诶，可莉好可爱，所以必须交一份题解来宠爱可莉呢~

思路简述

1. 统计各个数在不同位置上出现次数的前缀和。对于 x 来说，它可由 x 和 x-k 得到，而一个区间内的众数可通过枚举不同的区间得到。

2. 用 sum[i][0] 表示该数字 x 在下标 i 处出现了几次。

3. 用 sum[i][1] 表示该数字 x-k 在下标 i 处出现了几次。

容易得到递推公式：ans = sum[n][0]+sum[r][1]-sum[l-1][1]-(sum[r][0]-sum[l-1][0])。

化简得到：ans = sum[n][0]+sum[r][1]-sum[r][0]+sum[l-1][0]-sum[l-1][1]。

依照此式进行前缀和（类似动态规划）即可，最终时间复杂度为 O(n)。

代码实现

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,k,a[N],sum[N*4][2],mx,g,ans;
vector<int>e[N*4]; 
int main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];a[i]+=2e6;
        e[a[i]].push_back(a[i]);
        e[a[i]+k].push_back(a[i]);
        g=max(g,a[i]+k);
        mx=max({mx,(int)e[a[i]].size(),(int)e[a[i]+k].size()});
    }
    if(!k){
        cout<<mx/2<<endl;
         return 0;
    }
    for(int i=0;i<=g;i++){
        if(e[i].size()==0) continue;
        for(int j=0;j<e[i].size();j++){
            sum[j+1][0]=sum[j][0]+(e[i][j]==i);
            sum[j+1][1]=sum[j][1]+(e[i][j]!=i);
        }
        int tmp=sum[1][0]-sum[1][1];
        for(int j=1;j<=e[i].size();j++){
            tmp=max(tmp,sum[j-1][0]-sum[j-1][1]);
            ans=max(ans,sum[e[i].size()][0]+sum[j][1]-sum[j][0]+tmp);
        }
    }
    cout<<ans;
    return 0;
}