O - Can you find it?

        这个题坑太多了,但是也学到了不少新技能。因为是3组数据,如果按照普通的多层嵌套循环超时是绝对的,所以,想想,能不能拆一个数组出来。于是把l,n两个数组拿出来组合之后在循环m数组,将x-x-mdata[mi]作为结果在ln组合数组(一开始没组合,TLE了)里面查找是否存在值,这个查找使用二分法查找,在网上看到二分法也是有讲究的,不恰当就也会超时,然后,提交,GG,why?why?看了一个和我思路几乎相同的大神的代码,发现几个亮点,新技能get有老司机带路就是爽。


  1. __int64    普通的32位int整型肯定不够用啊,于是replace,哈哈,偷了一下懒,当然,long long应该也是可以滴,这个使用好像有平台限制,以后要注意oj的说明情况。

  2. lnlen = unique(lndata,lndata+lnlen)-lndata;unique是个好东西啊,数据去重。

    在STL中unique函数是一个去重函数, unique的功能是去除相邻的重复元素(只保留一个),其实它并不真正把重复的元素删除,是把重复的元素移到后面去了,然后依然保存到了原数组中,然后 返回去重后最后一个元素的地址(比如这里用最后一个地址减去起始地址就可以获得新的长度),因为unique去除的是相邻的重复元素,所以一般用之前都会要排一下序。

  3. __int64 mid=(fBegin+fEnd)>>1; 位运算真的是个神奇的东西,使用位运算求平均值可以避免溢出问题。



Description

Give you three sequences of numbers A, B, C, then we give you a number X. Now you need to calculate if you can find the three numbers Ai, Bj, Ck, which satisfy the formula Ai+Bj+Ck = X. 
 

Input

There are many cases. Every data case is described as followed: In the first line there are three integers L, N, M, in the second line there are L integers represent the sequence A, in the third line there are N integers represent the sequences B, in the forth line there are M integers represent the sequence C. In the fifth line there is an integer S represents there are S integers X to be calculated. 1<=L, N, M<=500, 1<=S<=1000. all the integers are 32-integers. 
 

Output

For each case, firstly you have to print the case number as the form "Case d:", then for the S queries, you calculate if the formula can be satisfied or not. If satisfied, you print "YES", otherwise print "NO". 
 

Sample Input

3 3 3
1 2 3
1 2 3
1 2 3
3
1
4
10
 

Sample Output

Case 1:
NO
YES
NO



下面是我的代码:


#include <iostream>
#include <algorithm>
using namespace std;
const __int64 maxn=500;         //不用__int64鬼知道他数据有多大
const __int64 maxm=1000;
__int64 ldata[maxn], ndata[maxn], mdata[maxn], xdata[maxm], lndata[maxn*maxn];
__int64 l,n,m,s,x, lnlen;
bool ans;
void Init()
{
    ///初始化输出数据
    lnlen=0;
    for(__int64 i=0;i<l;i++)cin>>ldata[i];
    for(__int64 i=0;i<n;i++)cin>>ndata[i];
    for(__int64 i=0;i<m;i++)cin>>mdata[i];
    cin>>s;
    for(__int64 i=0;i<l;i++)for(__int64 j=0;j<n;j++)lndata[lnlen++]=ldata[i]+ndata[j];
    sort(mdata, mdata+m);       //排序,后面二分会用得到
    sort(lndata, lndata+lnlen);
    lnlen = unique(lndata,lndata+lnlen)-lndata;     //去重,新技能get
}
bool lnFind(__int64 fm)
{
    ///二分查找
    __int64 fBegin=0;
    __int64 fEnd=lnlen-1;
    while(fBegin<=fEnd)
    {
        __int64 mid=(fBegin+fEnd)>>1;       //不会溢出的平均计算,新技能get
        if(lndata[mid]==fm)return true;
        if(lndata[mid]<fm)fBegin=mid+1;
        if(lndata[mid]>fm)fEnd=mid-1;
    }
    return false;
}
void Print()
{
    while(s--)
    {
        cin>>x;
        if(x>lndata[lnlen-1]+mdata[m-1]||x<lndata[0]+mdata[0])
        {
            cout<<"NO"<<endl;
            continue;
        }
        for(__int64 mi=0;mi<m;mi++)
        {
            __int64 fx=x-mdata[mi];
            if(ans=lnFind(fx))break;
        }
        if(ans)cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
}
int main()
{
    __int64 icase=0;
    while(cin>>l>>n>>m)
    {
        Init();
        cout<<"Case "<<++icase<<":"<<endl;
        Print();
    }
    return 0;
}