有趣的游戏 (HGOI 2019.2.15 T2)

2019-02-15 13:49:45


题目大意:

给出三组数,再给出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;
}