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[2010][4]; int main() { int t,n; cin >> t; int k = 0; while(t--){ cin >> n; for(int i = 0;i < n; i++){ for(int j = 0;j < 4; j++){ cin >> a[i][j]; } } map <int,int> m1,m2; for(int i = 0;i < n; i++){ for(int j = 0;j < n; j++){ m1[a[i][0]+a[j][1]]++; m2[a[i][2]+a[j][3]]++; } } int ans = 0; 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 0; } // writen by zhangjiuding