有趣的游戏 （HGOI 2019.2.15 T2）

## 题目大意： 给出三组数，再给出Q个询问，问能否通过从三组数中每组选一个数，使他们的和为询问的数。 ## 数据范围： 每组数的个数不超过1000个，询问数不超过100000个。所有数和不超过int ### 做法一： 正常人好像都是用Hash的，对于第一组和第二组的和Hash一下，然后对于每个询问，枚举第三组中的数，减掉后看有没有被Hash过 ### 做法二 其实理论上应该会T，但是可能数据比较水，或者说数据无法做到卡我的程序。 我是先把第一组和第二组的和先存到一个数组里，然后去重，假设去重后有m个数 然后对于询问，看第三组能不能和那个m个数组成x，假设第三组有n个数，我们这个环节可以少于O（n+m）处理完 也就是总的时间复杂度是O(Q*(n+m)+(排序啊，去重啊一点点时间)) 话说我自己出的100,100,100,100000的数据好像都跑了2秒，但是题目数据就是没有T。。 ``` #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int A,B,C,D,cnt=0; int a[10100],b[10100],c[10100],d[2000100]; int main() { scanf("%d%d%d",&A,&B,&C); for(int i=1;i<=A;i++) scanf("%d",&a[i]); sort(a+1,a+A+1); for(int i=1;i<=B;i++) scanf("%d",&b[i]); sort(b+1,b+B+1); for(int i=1;i<=C;i++) scanf("%d",&c[i]); sort(c+1,c+C+1); for(int i=1;i<=A;i++) for(int j=1;j<=B;j++) d[++cnt]=a[i]+b[j]; sort(d+1,d+cnt+1); cnt=unique(d+1,d+cnt+1)-d-1; scanf("%d",&D); while(D--) { int x,flag=0,j=cnt; scanf("%d",&x); for(int i=1;i<=C;i++) { while(d[j]+c[i]>x && j>0) j--; if(!j) break; if(d[j]+c[i]==x) {flag=1;break;} } if(flag) printf("YES\n"); else printf("NO\n"); } return 0; } ```