14322: 【原4322】完美对

题目

题目描述

author: smallling 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4322

Description

有$n$个物品，每个物品有$k$个属性，第$i$件物品的第$j$个属性用一个正整数表示记为$a_{i,j}$，两个不同的物品$i,j$被称为是完美对的当且仅当$a_{i,1}+a_{j,1} = a_{i,2}+a_{j,2}=\dots=a_{i,k}+a_{j,k}$，求完美对的个数。

Input Format

第一行两个数字$n,k$。

接下来$n$行，第$i$行$k$个数字表示$a_{i,1}, a_{i,2},\dots,a_{i,k}$。

$1 \leq n \leq 10^5, 2 \leq k \leq 10, 1 \leq a_i \leq 100$

Output Format

一行一个数字表示答案

Sample Input

5 3
2 11 21
19 10 1
20 11 1
6 15 24
18 27 36

Sample Output

3

ligongzzz's solution

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
using ull = unsigned long long;
constexpr auto mod = 203ull;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, k;
    cin >> n >> k;

    unordered_map<ull, int> rdata, ldata;
    int zero_num = 0;

    for (int i = 0; i < n; ++i) {
        ull rcode = 0ull, lcode = 0ull;
        int fnum;
        cin >> fnum;
        for (int j = 1; j < k; ++j) {
            int tmp;
            cin >> tmp;
            rcode = rcode * mod + ull(100 + tmp - fnum);
            lcode = lcode * mod + ull(100 + fnum - tmp);
        }
        if (rcode == lcode) {
            zero_num++;
            continue;
        }

        if (rdata.find(rcode) == rdata.end()) {
            rdata[rcode] = 1;
        }
        else
        {
            rdata[rcode]++;
        }

        if (ldata.find(lcode) == ldata.end()) {
            ldata[lcode] = 1;
        }
        else
        {
            ldata[lcode]++;
        }
    }

    int ans = 0;
    for (auto p : rdata) {
        if (ldata.find(p.first) != ldata.end()) {
            ans += p.second * ldata[p.first];
        }
    }
    ans /= 2;
    ans += zero_num * (zero_num - 1) / 2;

    cout << ans;

    return 0;
}

zqy2018's solution

#include <bits/stdc++.h>
#define REP(temp, init_val, end_val) for (int temp = init_val; temp <= end_val; ++temp)
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while (c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while (c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, k, a[100005][11];
map<vector<int>, int> mp;
void init(){
    n = read(), k = read();
    REP(i, 1, n)
        REP(j, 1, k)
            a[i][j] = read();
}
void solve(){
    ll ans = 0;
    vector<int> tmp(11, 0);
    REP(i, 1, n){
        REP(j, 1, k - 1)
            tmp[j] = a[i][j + 1] - a[i][1];
        if (mp.count(tmp))
            ans += mp[tmp];
        REP(j, 1, k - 1)
            tmp[j] = a[i][1] - a[i][j + 1];
        if (!mp.count(tmp))
            mp[tmp] = 0;
        ++mp[tmp];
    }
    printf("%lld\n", ans);
}
int main(){
    init();
    solve();
    return 0;
}