题目链接:Click here~~
比赛时的一道题,当时没有好的思路,听学长讲了讲才知道可以用Hash做,之前用Hash只写过那个找球号的题。
题意:
有5组数,每组有n个,问能否在每组中找到一个数,令这5个数之和为0。
解题思路:
先用O(n^2)的时间求出前两组数的所有组合情况,将它们存入一个Hash表。
然后用O(n^3)的时间求出后三组数的所有组合情况,每求出一种就看下它的相反数是否在Hash表中出现。
之所以可以这样做,是因为Hash可以在大约常数时间内判断出一个数是否在Hash表中出现。Orz。
PS:
Hash函数用的是取模,性价比还行,用别的貌似更慢。
注意负数的处理,我开始是转成绝对值,1500+MS,看了学长的,他是+MAX,改成这个,果然快了,1300+MS。
Hash表的大小开10倍就行。开20倍与10倍时间基本没差距。
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; typedef __int64 LL; #define FileIn freopen("in.ads","r",stdin) #define FileOut freopen("out.ads","w",stdout) #define MAX 400005 LL s[5][205]; LL Hash[MAX]; bool used[MAX]; int hash(LL x) { int h = x % MAX; if(h < 0) h += MAX; while(used[h] && Hash[h] != x) h = (h+1) % MAX; return h; } int main() { int z,n; scanf("%d",&z); while(z--) { bool no = true; memset(used,false,sizeof(used)); scanf("%d",&n); for(int i=0;i<5;i++) for(int j=0;j<n;j++) scanf("%I64d",&s[i][j]); for(int i=0;i<n;i++) for(int j=0;j<n;j++) { LL sum = - (s[0][i] + s[1][j]); int h = hash(sum); used[h] = true; Hash[h] = sum; } for(int i=0;i<n;i++) for(int j=0;j<n;j++) for(int k=0;k<n;k++) { LL sum = s[2][i] + s[3][j] + s[4][k]; int h = hash(sum); if(used[h]) { no = false; goto bingo; } } bingo: puts(no?"No":"Yes"); } return 0; }