CF1462E1 Close Tuples (easy version) 题解

紊莫 · 2024-01-05 18:53:54 · 题解

简单版解法。

开一个桶记录前缀和后缀中数字出现次数，可以枚举时顺便递推。

因为差值很小，可以暴力枚举中间项，排列组合左右，这里直接全部写出来方便观察。

cin>>n;int ans=0;
map<int,int> t1,t2;
F(i,1,n) cin>>a[i];
F(i,1,n) t2[a[i]]++;
F(i,1,n){
    t2[a[i]]--;
    ans+=t1[a[i]]*(t2[a[i]]+t2[a[i]+1]+t2[a[i]+2]+t2[a[i]-1]+t2[a[i]-2])+
         t1[a[i]+1]*(t2[a[i]]+t2[a[i]+1]+t2[a[i]+2]+t2[a[i]-1])+
         t1[a[i]+2]*(t2[a[i]]+t2[a[i]+1]+t2[a[i]+2])+
         t1[a[i]-1]*(t2[a[i]]+t2[a[i]+1]+t2[a[i]-2]+t2[a[i]-1])+
         t1[a[i]-2]*(t2[a[i]]+t2[a[i]-1]+t2[a[i]-2]);
    t1[a[i]]++;
}
cout<<ans<<'\n';

虽然内容有点多，但是思维量较少。

完整示例代码。