首页 > 代码库 > HiHo1505:小Hi和小Ho的礼物(Meet-In-The-Middle + 组合数学)
HiHo1505:小Hi和小Ho的礼物(Meet-In-The-Middle + 组合数学)
单点时限:1000ms
内存限制:256MB
描述
某人有N袋金币，其中第i袋内金币的数量是Ai。现在他决定选出2袋金币送给小Hi，再选2袋金币送给小Ho，同时使得小Hi和小Ho得到的金币总数相等。他想知道一共有多少种不同的选择方法。
具体来说，有多少种下标四元组(i, j, p, q)满足i, j, p, q两两不同，并且i < j, p < q, Ai + Aj = Ap + Aq。
例如对于数组A=[1, 1, 2, 2, 2]，一共有12种选法：
i j p q1 3 2 41 3 2 51 4 2 31 4 2 51 5 2 31 5 2 42 3 1 42 3 1 52 4 1 32 4 1 52 5 1 32 5 1 4
输入
第一行包含一个整数N。
第二行包含N个整数，A1, A2, A3 ... AN。
对于70%的数据，1 <= N <= 100
对于100%的数据，1 <= N <= 1000, 1 <= Ai <= 1000000
输出
不同选择的数目。
样例输入
5 1 1 2 2 2
样例输出
12
Code:
1 #include <bits/stdc++.h> 2 using namespace std; 3 static const int MAXN = 1e3 + 10; 4 static const int HS = 2000000 + 10; 5 typedef long long LL; 6 struct Node 7 { 8 int x , y , num; 9 Node()10 {11 num = 0;12 }13 };14 LL vis[HS];15 LL dvis[HS];16 LL data[MAXN];17 LL ans;18 int n;19 int main()20 {21 scanf("%d" , &n);22 for(int i = 1 ; i <= n ; ++i)23 scanf("%lld" , &data[i]) , ++dvis[data[i]];24 for(int i = 1 ; i <= n ; ++i)25 {26 for(int j = i + 1 ; j <= n ; ++j)27 {28 ++vis[data[i] + data[j]];29 }30 }31 32 for(int i = 1 ; i <= n ; ++i)33 {34 for(int j = i + 1 ; j <= n ; ++j)35 {36 if(data[i] != data[j])37 {38 LL a = dvis[data[i]] , b = dvis[data[j]];39 LL sum = data[i] + data[j];40 ans += vis[sum] - (a * b - (a - 1) * (b - 1));41 }42 else43 {44 LL sum = data[i] + data[j];45 LL pre = dvis[data[i]];46 LL last = pre - 2;47 ans += vis[sum] - (pre * (pre - 1) - last * (last - 1)) / 2;48 }49 }50 }51 printf("%lld" , ans);52 }
HiHo1505:小Hi和小Ho的礼物(Meet-In-The-Middle + 组合数学)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。