1010: 四个年级
时间限制: 3 Sec 内存限制: 128 MB
题目描述
为了加强全体软件学院的同学的较量，学院想让ACM协会设计一次活动让所以软件学院的同学都加入，并且要实现高年级和低年级互动的效果。会长想了这样一个活动（可能有点无聊），他写了一个小程序，让每个年级的同学都来随机生成一个数字，如果有来着四个年级的四个同学他们手上的数字相加等于零，就称这是一组超强组合。例如一年级的同学的数字为{-45，-41，-36,26,32，1}，二年级的同学数字为{22，-27,53,30，-38，-54}，三年级的同学数字为{42,56，-37，-75，-10，-6}，四年级同学数字为{-16,30,77，-46,62，45}。则有6组超强组合（-45，-27,42,30），（26,30，-10，-46），（-32,22,56，-46），（-32,30，-75,77），（-32，-54,56,30）（1 -27 42 -16）。你的任务是给你所有年级人的数字，让你计算有多少组超强组合。为了方便出来我们假设每个年级的人一样多。
输入
输入包含多组数据，第一行为测试数据T组（1<=T<=10）;以下每组数据第一行包含一个数字N（1<=N<=2000）表示每个年级人数。接下来数N行，每行有4个数A1,A2,A3,A4(-1000<Ai<1000)，分别表示一二三四年级同学的数字。
输出
输出超强组合的组数，没有就输出0。
样例输入
1
6
-45 22 42 -16
-41 -27 56 30
-36 53 -37 77
26 30 -75 -46
-32 -38 -10 62
1 -54 -6 45
样例输出
Case 1: 6 题目链接：https://acm.xju.edu.cn/JudgeOnline/problem.php?id=1010 这题就是要在每列找一个数，使4个数的和为0，问有几组这样的4个数。 直观的想法要4层循环，即4种数，所有情况都遍历一遍，这样肯定会超时。
因为时间复杂度是O（n^4）,n = 2000。 所以我们优化一下，
map<int,int> m1,m2;
m1存前两种数的所有组合的和，m2存后两种数的所有组合的和。 然后遍历一遍就可以了。 代码：
#include <iostream>
#include <map>
using namespace std;
typedef long long ll; int a[][]; int main() {
int t,n;
cin >> t;
int k = ;
while(t--){
cin >> n;
for(int i = ;i < n; i++){
for(int j = ;j < ; j++){
cin >> a[i][j];
}
}
map <int,int> m1,m2;
for(int i = ;i < n; i++){
for(int j = ;j < n; j++){
m1[a[i][]+a[j][]]++;
m2[a[i][]+a[j][]]++;
}
}
int ans = ;
map <int,int>::iterator it;
for(it = m1.begin();it != m1.end(); it++){
ans += it->second*m2[-it->first];
}
cout << "Case " << ++k << ": ";
cout << ans << endl;
}
return ;
}
// writen by zhangjiuding