题解 CF1520D 【Same Differences】

oimaster · 2021-05-12 22:25:50 · 题解

我们拿到 a_j-a_i=j-i 后，可以进行整理。

1. a_j-a_i=j-i
2. a_j=j-i+a_i
3. a_j-j=a_i-i

接下来，我们发现只需要计算这个数和下标的差就可以知道匹配个数了。

那么只需要开桶统计即可。这时候我们会发现 a_i 可能会小于 i，所以减出来的可能会是负数。那么我们的传统数组就无法解决这个问题。

那么把凶狠的眼光放在 STL 上，发现 map 可以帮我们解决这个问题。map 的单次修改是 \log n 级别的，也很优秀。

那么一共做 n 次操作，每次是 \log n，复杂度为 \text{O}(n\log n)。

#include<iostream>
#include<map>
#define int long long
using namespace std;
signed main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int a[n+1];
        for(int i=1;i<=n;++i){
            cin>>a[i];
            a[i]-=i;
        }
        int ans=0;
        map<int,int>m;
        for(int i=1;i<=n;++i){
            if(m.count(a[i]))
                ans+=m[a[i]];
            ++m[a[i]];
        }
        cout<<ans<<endl;
    }
}

数组：为什么我不行？

博主：谁说的！

我们注意到，所有减去的下标最多是 n，那么我们只需要把所有的差值统一加上 n 不就进入正数范围了？

不过这时候，因为如果没有减出负数，加完 n 后大小可能会达到 2n。

那么我们开 2n 大小的数组，不就可以了？

#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
signed main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int a[n+1];
        for(int i=1;i<=n;++i){
            cin>>a[i];
            a[i]-=i;
        }
        int ans=0;
        int m[2*n+1];
        fill(m,m+2*n+1,0);
        for(int i=1;i<=n;++i){
            ans+=m[a[i]+n];
            ++m[a[i]+n];
        }
        cout<<ans<<endl;
    }
}

因为查询数组是 \text{O}(1)，时间复杂度就为 \text{O}(n)。

这就是不会 STL 的同学可以走的取巧路线。题解就这么多了。