算法题

    技术2022-07-10  131

    题目:

    思路: 如上面的式子所示,我们可以维护每个数组与其第一个位置元素的差构成的数组,若两个数组的差数组互为相反数则构成对子。

    接下来我们用C++进行编程:

    #include<bits/stdc++.> using namespace std; typedef long long ll; map<vector<int>, int> mp; int main(){ int n, k; while(cin >> n >> k) { for(int i = 0; i < n; i++) { vector<int> vec(k - 1, 0); int fv, v; cin >> fv; for(int j = 1; j < k; j++) { cin >> v; vec[j - 1] = v - fv; } mp[vec]++; } ll result = 0; vector<int> neg(k - 1, 0); if(mp.find(neg) != mp.end()) { ll cnt = mp[neg]; result += cnt * (cnt - 1) / 2; mp.erase(neg); } ll pcnt = 0; for(auto it = mp.begin(); it != mp.end(); it++) { for(size_t i = 0; i < it -> first.size(); i++) { neg[i] = -it -> first[i]; } if(mp.find(neg) != mp.end()) { ll cnt = mp[neg]; pcnt += cnt * it -> second; } } result += pcnt / 2; cout << result << endl; } return 0; }
    Processed: 0.015, SQL: 9