有个物品,每个物品有个属性,第件物品的第个属性用一个正整数表示记为,两个不同的物品被称为是完美对的当且仅当,求完美对的个数。
进阶:时间复杂度,空间复杂度
class Solution { private: int n, k; int allSameNum = 0; //<code:形如+1-2+3,code对应的物品个数> unordered_map<string, int> memo; string getAntiCode(const string &s) { string r; for (char c : s) { if (c == '+') r += '-'; else if (c == '-') r += '+'; else r += c; } return r; } public: Solution() { cin >> n >> k; int temp, last; for (int i = 0; i < n; i++) { string code; bool allSame = true; for (int j = 0; j < k; j++) { cin >> temp; if (j == 0) last = temp; else { if (temp != last) allSame = false; if (temp - last > 0) code += '+'; code += to_string(temp - last); last = temp; } } if (allSame) allSameNum += 1; else if (memo.count(code)) ++memo[code]; else memo[code] = 1; } } void solve() { int r = 0; for (const auto &m : memo) { string antiCode = getAntiCode(m.first); if (memo.count(antiCode)) r += m.second * memo[antiCode]; } r /= 2; r += allSameNum * (allSameNum - 1) / 2; cout << r << endl; } }; int main() { ios::sync_with_stdio(false); Solution s; s.solve(); return 0; }
如果a, b互为完美对, 则需要满足
有 , 等价于
由于任意 有 , 故可推导得 :
a, b互为完美对, 等价于其差分序列相等
我们可以用其差分序列作为键, 序列数量作为值建立Hash表,以达到快速查找某个物品的完美对的目的
#include <iostream> #include <vector> #include <map> using namespace std; #define int long long signed main() { int n, k; cin >> n >> k; int ans = 0; map<vector<int>, int> mvii; for(int i = 0; i < n; ++ i) { vector<int> a(k); for(int &t: a) cin >> t; vector<int> b(k-1); for(int j = 1; j < k; ++ j) b[j-1] = a[j] - a[j-1]; ans += mvii[b]; for(int &t: b) t = -t; mvii[b] ++; } cout << ans << endl; }
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.ArrayList; import java.util.HashMap; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] params = br.readLine().trim().split(" "); int n = Integer.parseInt(params[0]), k = Integer.parseInt(params[1]); int[][] fields = new int[n][k]; HashMap<Integer, ArrayList<Integer>> counter = new HashMap<>(); int count = 0; for(int i = 0; i < n; i++){ String[] row = br.readLine().trim().split(" "); for(int j = 0; j < k; j++) fields[i][j] = Integer.parseInt(row[j]); // 计算出差分之和 int diffSum = fields[i][k - 1] - fields[i][0]; // 检查相反数是否在里面,并检查是否是完美对 if(counter.containsKey(-diffSum)){ for(int j = 0; j < counter.get(-diffSum).size(); j++) if(isValid(i, counter.get(-diffSum).get(j), fields)) count ++; } if(counter.containsKey(diffSum)) counter.get(diffSum).add(i); else{ ArrayList<Integer> path = new ArrayList<>(); path.add(i); counter.put(diffSum, path); } } System.out.println(count); } private static boolean isValid(int i, int j, int[][] fields) { int val = fields[i][0] + fields[j][0]; for(int fi = 1; fi < fields[0].length; fi++) if(fields[i][fi] + fields[j][fi] != val) return false; return true; } }
#include <iostream> #include <queue> #include <vector> #include <string> #include <stack> #include <utility> #include <cstdio> #include <algorithm> #include <map> #include <limits.h> #include <math.h> #include <unordered_map> #include <set> #include <list> using namespace std; int main() { int n, k; cin >> n >> k; vector<vector<int>> num_list(n, vector<int>(k)); for (int i = 0; i < n; i++) { for (int j = 0; j < k; j++) { cin >> num_list[i][j]; } } int ans = 0; unordered_map<string, int> hash_z; for (int i = 0; i < n; i++) { string z = ""; string d = ""; for (int j = 0; j < k - 1; j++) { int zi = num_list[i][j] - num_list[i][j + 1]; int di = num_list[i][j + 1] - num_list[i][j]; z += zi >= 0 ? "+" + to_string(zi) : to_string(zi); d += di >= 0 ? "+" + to_string(di) : to_string(di); } //cout << z << " "; if (hash_z.find(d) != hash_z.end()) ans += hash_z[d]; hash_z[z]++; } cout << ans; return 0; }
def count(n, k, a_list): cnt = 0 delta_map = dict() for i in range(n): delta_list = [] for m in range(k-1): delta_list.append(a_list[i][m+1] - a_list[i][0]) p_str = ' '.join([str(j) for j in delta_list]) n_str = ' '.join([str(-j) for j in delta_list]) if delta_map.get(n_str): cnt += delta_map.get(n_str) if delta_map.get(p_str): delta_map[p_str] += 1 else: delta_map[p_str] = 1 return cnt
def judge(a, b): n = a[0] + b[0] for i in range(1, len(a)): if a[i] + b[i] != n: return False return True n, k = map(int, input().split()) a = [[] for i in range(n)] for i in range(n): a[i] = input().split() for i in range(n): for j in range(len(a[i])): a[i][j] = int(a[i][j]) cnt = 0 for i in range(n-1): for j in range(i+1, n): if judge(a[i], a[j]) == True: cnt += 1 print(cnt)
#include <bits/stdc++.h> typedef long long ll; using namespace std; int a[100005][11]; int n,k; vector<int>head[2005]; bool check(int x,int y) { int sum=a[x][1]+a[y][1]; for(int i=2;i<=k;i++) if(a[x][i]+a[y][i]!=sum) return false; return true; } int main() { ios::sync_with_stdio(0),cin.tie(0); int i,j,ans=0; cin>>n>>k; for(i=1;i<=n;i++) for(j=1;j<=k;j++) cin>>a[i][j]; for(i=1;i<=n;i++) { int sum=0; for(j=2;j<=k;j++) sum+=a[i][j]-a[i][j-1]; for(j=0;j<head[-sum+1000].size();j++) if(check(i,head[-sum+1000][j])) ans++; head[sum+1000].push_back(i); } cout<<ans; return 0; }
n, k = [int(i) for i in input().split()] A = [0] * n Diff = [0] * n for i in range(n): A[i] = [int(j) for j in input().split()] Diff[i] = [A[i][j+1] - A[i][j] for j in range(k-1)] hashh = {} res = 0 for i in range(len(Diff)): h0 = str(Diff[i]) # 原差分数列字符串 h1 = str([-Diff[i][v] for v in range(len(Diff[i]))]) # 取反差分数列字符串 if h1 in hashh.keys(): res += hashh[h1] if h0 in hashh.keys(): hashh[h0] += 1 else: hashh[h0] = 1 print(res)
import javax.swing.plaf.IconUIResource; import java.util.HashMap; import java.util.HashSet; import java.util.Scanner; public class Solution2_1 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); // n 个物品 int n = sc.nextInt(); // k 个属性 int k = sc.nextInt(); int[][] items = new int[n][k]; // 输入 items for(int i = 0; i < n; i++){ for(int j = 0; j < k; j++){ items[i][j] = sc.nextInt(); } } int res = 0; // 形成查分数组,并且将其形成字符串,放入map // key: 字符串 value: 字符串出现次数 HashMap<String, Integer> map = new HashMap<>(); for(int i = 0; i < n; i++){ StringBuilder s = new StringBuilder(); StringBuilder s_opp = new StringBuilder(); for(int j = 1; j < k; j++) { int diff = items[i][j] - items[i][j - 1]; s.append(String.valueOf(diff)).append(","); s_opp.append(String.valueOf(-diff)).append(","); } // 查看有没有相反的完美对 if(map.containsKey(s_opp.toString())) res += map.get(s_opp.toString()); // 计数 map.put(s.toString(),map.getOrDefault(s.toString(),0)+1); } System.out.println(res); } }
import collections def ans(data): res = 0 hash_map = collections.defaultdict(int) for i in range(len(data)): diff = [] for j in range(1,len(data[0])): diff.append(data[i][j] - data[i][0]) str_1 = " ".join(str(id) for id in diff) str_2 = " ".join(str(-id) for id in diff) res += hash_map[str_2] hash_map[str_1] += 1 return res if __name__ == "__main__": num = list(map(int,input().split())) m = num[0] data = [] for i in range(m): data.append(list(map(int,input().split()))) print(ans(data))
/** * 两个序列 * 我们将数组a所有相邻两数的差值求出来,求和即为属性差分和 * 完美对的属性差分和互为相反数 * 我们可以用其差分序列作为键, 序列数量作为值建立Hash表,以达到快速查找某个物品的完美对的目的 */ public class Main { public static void main(String[] args) throws IOException { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int k = scanner.nextInt(); HashMap<List<Integer>, Integer> hashMap = new HashMap<List<Integer>, Integer>(); int ans = 0; for (int i = 0; i < n; i++) { int[] a = new int[k]; ArrayList<Integer> b = new ArrayList<>(); for (int j = 0; j < k; j++) { a[j] = scanner.nextInt(); } //得到差分序列b for (int j = 1; j < k; j++) { b.add(a[j] - a[j - 1]); } //先加上之前的相反数和自己相同的 ans += hashMap.getOrDefault(b, 0); for (int h = 0; h < b.size(); h++) { b.set(h, -b.get(h)); } //然后转换为相反数存储,供后面使用,为了后面找相同 hashMap.put(b, hashMap.getOrDefault(b, 0) + 1); } System.out.println(ans); } }
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Comparator; import java.util.Scanner; public class Main { public static void main(String[] args) { int ans = 0; BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String s = null; try { s = br.readLine(); } catch (IOException e) { e.printStackTrace(); } String[] s1 = s.split(" "); int n = Integer.parseInt(s1[0]); int k = Integer.parseInt(s1[1]); int[][] el = new int[n][k]; for (int i = 0; i < n; i++) { String[] s2 = new String[k]; try { s2 = br.readLine().trim().split(" "); } catch (IOException e) { e.printStackTrace(); } for (int j = 0; j < k; j++) { el[i][j] = Integer.parseInt(s2[j]); } } Arrays.sort(el, new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) { return (o1[0] - o1[1]) - (o2[0] - o2[1]); } }); int mid = 0; for (int i = 0; i < n; i++) { if (el[i][0]-el[i][1]>0){ mid = i; break; } } for (int i = 0; i < mid; i++) { for (int j = n-1; j >=mid ; j--) { if ((el[i][0] - el[i][1]) + (el[j][0] - el[j][1]) == 0) { for (int l = 1; l < k; l++) { int num = el[i][0] + el[j][0]; if (el[i][l] + el[j][l] != num) { break; } if (l == k - 1) { ans++; } } }else if((el[i][0] - el[i][1]) + (el[j][0] + el[j][1]) < 0){ break; } } } System.out.println(ans); } }
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main{ public static void main(String[] args)throws IOException{ BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); String[] str=br.readLine().trim().split(" ");; int thingNum=Integer.parseInt(str[0]); int propertyNum=Integer.parseInt(str[1]); int[][] ans=new int[thingNum][propertyNum]; for(int i=0;i<thingNum;i++){ str=br.readLine().trim().split(" "); for(int j=0;j<propertyNum;j++){ ans[i][j]=Integer.parseInt(str[j]); } } Map<String,Integer> map=new HashMap<>(); int count=0; for(int i=0;i<thingNum;i++){ StringBuilder pro1=new StringBuilder(); StringBuilder pro2=new StringBuilder(); for(int j=0;j<propertyNum-1;j++){ int num=ans[i][j]-ans[i][j+1]; pro1.append(num); pro2.append(-num); } count+=map.getOrDefault(pro2.toString(),0); map.put(pro1.toString(),map.getOrDefault(pro1.toString(),0)+1); } System.out.println(count); } }
#include<bits/stdc++.h> using namespace std; string change(string s){ for(int i = 0; i < s.size(); i++){ if(s[i]=='+') s[i] = '-'; else if(s[i] == '-') s[i] = '+'; } return s; } int helper(int n, int k, vector<vector<int>>& arr){ unordered_map<string, int> mp; int ans = 0; //根据差分属性 for(int i = 0; i < n; i++){ string temp; for(int j = 1; j < k; j++){ int num = arr[i][j] - arr[i][j - 1]; if(num > 0){ temp += "+"; } temp += to_string(num); } string anti_temp = change(temp); if(mp.find(anti_temp) != mp.end()){ ans += mp[anti_temp]; } mp[temp]++; } return ans; } int main(){ int n, k; while(cin >> n >> k){ vector<vector<int>> arr(n, vector<int>(k)); for(int i = 0; i < n; i++){ for(int j = 0; j < k; j++){ cin >> arr[i][j]; } } cout << helper(n, k, arr) << endl; } }
import java.util.*; public class Main{ public static void main(String[] args) { Scanner scan = new Scanner(System.in); int n = scan.nextInt(); int k = scan.nextInt(); int[][] input = new int[n][k]; for(int i=0; i<n; i++){ for(int j=0; j<k; j++){ input[i][j] = scan.nextInt(); } } int res = getAns(input, n, k); System.out.println(res); } public static int getAns(int[][] input, int n, int k){ int count = 0; Map<String, Integer> map = new HashMap<>(); for(int i=0; i<n; i++){ String s = transferToString(input[i]); String reverse = reverseString(input[i]); if(map.containsKey(s)){ count += map.get(s); } map.put(reverse, map.getOrDefault(reverse, 0)+1); } return count; } public static String transferToString(int[] arr){ StringBuilder sb = new StringBuilder("0"); for(int i=1; i<arr.length; i++){ if(arr[i]-arr[0] > 0){ sb.append("+"); sb.append(arr[i]-arr[0]); }else if(arr[i]-arr[0] < 0) { sb.append(arr[i]-arr[0]); }else { sb.append(0); } } return sb.toString(); } public static String reverseString(int[] arr){ StringBuilder sb = new StringBuilder("0"); for(int i=1; i<arr.length; i++){ if(arr[i]-arr[0] > 0){ sb.append("-"); sb.append(arr[i]-arr[0]); }else if(arr[i]-arr[0] < 0) { sb.append("+"); sb.append(arr[0]-arr[i]); }else { sb.append(0); } } return sb.toString(); } }
import java.util.*; public class Main{ public static void main(String[] args){ Scanner scan = new Scanner(System.in); int n = scan.nextInt(),k = scan.nextInt(),res = 0; int[][] num = new int[n][k]; HashMap<String,Integer> table = new HashMap<>(); for(int i = 0; i<n; i++){ if(!scan.hasNextInt()){ break; } int min = scan.nextInt(); for(int j = 1; j<k; j++){ if(scan.hasNextInt()){ num[i][j] = scan.nextInt() - min; } } } for(int i = 0; i<n; i++){ String[] key = inttostr(num[i]); if(table.containsKey(key[1])){ res += table.get(key[1]); } if(table.containsKey(key[0])){ table.replace(key[0],table.get(key[0])+1); }else{ table.put(key[0],1); } } System.out.println(res); } public static String[] inttostr(int[] a){ String[] buffer = new String[2]; buffer[0] = Arrays.toString(a); for(int i = 0; i<a.length; i++){ a[i] = -a[i]; } buffer[1] = Arrays.toString(a); return buffer; } }