Codeforces Round #719 (Div. 3) D. Same Differences 动态map维护

梦里梦外; 2024-03-29 15:03 174阅读 0赞

Problem - D - Codeforces

题意：

98d25cd6320e44d143d3cadbc49e4804.png

思路:

这种题，一般跑一个指针，然后推式子用数据结构去维护另一个指针

推一推式子：ai-i=aj-j

那么只需维护前缀满足ai-i的哈希表就好了

Code：

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define db double
  5. const int mxn=2e5+10;
  6. map<int,int> mp;
  7. int n,ans=0;
  8. int a[mxn];
  9. void solve(){
  10.     mp.clear();
  11.     ans=0;
  12.     cin>>n;
  13.     for(int i=1;i<=n;i++) cin>>a[i];
  14.     for(int i=1;i<=n;i++){
  15.         ans+=mp[a[i]-i];
  16.         mp[a[i]-i]++;
  17.     }
  18.     cout<<ans<<'\n';
  19. }
  20. signed main(){
  21.     ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  22.     int __=1;cin>>__;
  23.     while(__--)solve();return 0;
  24. }

发表评论

表情：
评论列表 （有 0 条评论，174人围观）

还没有评论，来说两句吧...

相关阅读