hihoCoder 1505-小Hi和小Ho的礼物
#1505 : 小Hi和小Ho的礼物
时间限制:10000ms
单点时限: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 q 1 3 2 4 1 3 2 5 1 4 2 3 1 4 2 5 1 5 2 3 1 5 2 4 2 3 1 4 2 3 1 5 2 4 1 3 2 4 1 5 2 5 1 3 2 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
简化一下题意就是：给定一个数组，从中取出四个数a,b,c,d，使得a+b=c+d，问一共有多少种取法。 首先尝试了一下$$O(n^4)$$的暴力方法，过了70%的数据。后面想想先把所有数存hash表，然后固定a,b,c三个数，如果a+b-c也在hash表中，则找到一种合法的取法，想来复杂度能降到$$O(n^3)$$，提交之后居然WA，没理解。 后来参考大神的解法。首先把数及其频率hash到hash1中，然后把任意两数之和的频率hash到hash2中。最后遍历a和b，则hash2[a+b]是所有和为a+b的两数取法数，hash2[a+b]-hash1[a]*hash1[b]则是所有不是a和b但两数之和也是a+b的取法数，如果a,b本身有多次重复的话，还需要加上(hash1[a]-1)*(hash1[b]-1)。 比如有三个1和两个2，a=1,b=2，则还剩两个1和一个2，此时，如果从1,2中选两个数等于3，则有2*1=2种取法，即(hash1[a]-1)*(hash1[b]-1)。但是还有可能有0+3=3的情况，这就是hash2[a+b]-hash1[a]*hash1[b]。 当然还需要分a和b是否相等两种情况，因为a==b的情况有点特殊。 代码如下： [cpp] #include<iostream> #include<cstdlib> #include<algorithm> #include<vector> #include<string> #include<map> #include<unordered_map> using namespace std; int main() { //freopen("input.txt", "r", stdin); int n; scanf("%d", &n); vector<long long> nums(n, 0); unordered_map<long long, int> hash1, hash2; for (int i = 0; i < n; ++i) { scanf("%lld", &nums[i]); ++hash1[nums[i]]; } for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { ++hash2[nums[i] + nums[j]]; } } long long ans = 0; for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { if (nums[i] != nums[j])ans += hash2[nums[i] + nums[j]] – hash1[nums[i]] * hash1[nums[j]] + (hash1[nums[i]] – 1)*(hash1[nums[j]] – 1); else { int cnt = hash1[nums[i]]; int left = cnt – 2; ans += hash2[nums[i] + nums[j]] – cnt*(cnt – 1) / 2 + left*(left – 1) / 2; } } } printf("%lld\n", ans); return 0; } [/cpp] 本代码提交AC，用时444MS。]]>