每日一题：完美对物品

题目

$n$ 个物体，每个物品都有 $k$ 个属性，实际上就是 $a[n][k]$ 的数组，满足 $a[i][0]+a[j][0]=a[i][1]+a[j][1]=…=a[i][k−1]+a[j][k−1]$ 的物体 $i$ 和物体 $j$ 称为一对完美对，求完美对对数。

Solution

公式变形：$x1 + y1 = x2 + y2 -> x1-x2 = -(y1-y2)$，用一个 $map(vector, int)$ 来记录每件物品的差值即可，然后去 $map$ 里面查找有几个正好是相反数 $vector$，累加答案即可。

Code

#include <bits/stdc++.h>
using namespace std;
map<vector<int>, int> mp;
int a[15];
signed main() {
  int n, k, res = 0;
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    vector<int> g;
    for (int j = 1; j <= k; j++) 
      cin >> a[j];
    for (int j = 2; j <= k; j++) {
      g.push_back(a[j] - a[j - 1]);
    }
    res += mp[g];
    for (int j = 0; j < g.size(); j++) {
      g[j] = -g[j];
    }
    mp[g]++;
  }
  cout << res << endl;
  return 0;
}