HDU 6022---MG loves set（K-D樹），hduk-d

HDU 6022---MG loves set（K-D樹），hduk-d

題目鏈接

 

Problem Description MG is an intelligent boy. One day he was challenged by the famous master called Douer: 
if the sum of the square of every element in a set is less than or equal to the square of the sum of all the elements, then we regard this set as ”A Harmony Set”. 
Now we give a set with n different elements, ask you how many nonempty subset is “A Harmony Set”.
MG thought it very easy and he had himself disdained to take the job. As a bystander, could you please help settle the problem and calculate the answer?   Input The first line is an integer T which indicates the case number.(1<=T<=10)
And as for each case, there are 1 integer n in the first line which indicate the size of the set(n<=30).
Then there are n integers V in the next line, the x-th integer means the x-th element of the set(0<=|V|<=100000000).

 

Output As for each case, you need to output a single line.
There should be one integer in the line which represents the number of “Harmony Set”. 

 

Sample Input 3 4 1 2 3 4 5 1 -1 2 3 -3 6 0 2 4 -4 -5 8   Sample Output 15 12 25   題意：

 

思路：

看到題目數據的范圍n<=30 ，枚舉考慮每一個子集肯定會超時，所以這個辦法不行了。怎麼樣降低復雜度呢？

先化簡一下，設子集為{x，y，z}滿足題目要求，則x*x+y*y+z*z<=(x+y+z)*(x+y+z) 即xy+yz+xz>=0  ,所以本題就是求一個集合有多少非空子集滿足集合中元素兩兩乘積的和大於等於0； 

巧妙地思想：把集合分成前後兩半，設前一半集合的任意一個子集的和為Xi 兩兩之間乘積的和為Yi ,後一半集合的任意一個子集的和為Xj 兩兩之間乘積的和為Yj 可以發現(a+b)*(c+d)+ab+cd>=0是子集{a,b,c,d}滿足題意的要求，那麼Xi*Xj+Yi+Yj>=0就是判斷當前由這兩個子集合起來得到的子集是否滿足題意的要求。最後用K-D樹優化即可。

 

官方題解如下： 

 

代碼如下：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long LL;
const int N=1000005;
LL a[40];
int flag[4*N];
int idx;

struct Node
{
    LL f[2];
    LL mx[2];
    LL mn[2];
    int size;
    bool operator<(const Node& s)const
    { return f[idx]<s.f[idx]; }
}A[N],B[N],tr[4*N];

void update(int i)
{
    int s=1;
    if(flag[i<<1])
    {
        for(int k=0;k<=1;k++)
        {
            if(tr[i<<1].mn[k]<tr[i].mn[k]) tr[i].mn[k]=tr[i<<1].mn[k];
            if(tr[i<<1].mx[k]>tr[i].mx[k]) tr[i].mx[k]=tr[i<<1].mx[k];
        }
        s+=tr[i<<1].size;
    }
    if(flag[i<<1|1])
    {
        for(int k=0;k<=1;k++)
        {
            if(tr[i<<1|1].mn[k]<tr[i].mn[k]) tr[i].mn[k]=tr[i<<1|1].mn[k];
            if(tr[i<<1|1].mx[k]>tr[i].mx[k]) tr[i].mx[k]=tr[i<<1|1].mx[k];
        }
        s+=tr[i<<1|1].size;
    }
    tr[i].size=s;
}

void build(int l,int r,int i,int deep) 
{
    if(l>r) return;
    int mid=(l+r)>>1;
    idx=deep;
    flag[i]=1;
    flag[i<<1]=0; flag[i<<1|1]=0;

    nth_element(B+l,B+mid,B+r+1);
    for(int k=0;k<=1;k++)
       tr[i].mx[k]=tr[i].mn[k]=tr[i].f[k]=B[mid].f[k];

    build(l,mid-1,i<<1,1-deep);
    build(mid+1,r,i<<1|1,1-deep);
    update(i);
}
int check(LL x1,LL y1,LL x2,LL y2)
{
    if(x1*x2+y1+y2>=0) return 1;
    return 0;
}
int count(Node p,int i)
{
    int re=0;
    re+=check(tr[i].mn[0],tr[i].mn[1],p.f[0],p.f[1]);
    re+=check(tr[i].mn[0],tr[i].mx[1],p.f[0],p.f[1]);
    re+=check(tr[i].mx[0],tr[i].mn[1],p.f[0],p.f[1]);
    re+=check(tr[i].mx[0],tr[i].mx[1],p.f[0],p.f[1]);
    return re;
}
int query(Node p,int i)
{
    if(!flag[i]) return 0;
    if(count(p,i)==4) return tr[i].size;
    int re=check(p.f[0],p.f[1],tr[i].f[0],tr[i].f[1]);
    if(count(p,i<<1)) re+=query(p,i<<1);
    if(count(p,i<<1|1)) re+=query(p,i<<1|1);
    return re;
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
          scanf("%lld",&a[i]);
        int mid=n/2;
        int tt=(1<<mid);
        int tot1=0,tot2=0;
        for(int i=0;i<=tt-1;i++)
        {
            A[tot1].f[0]=0;
            A[tot1].f[1]=0;
            for(int k=1;(1<<(k-1))<tt;k++)
            {
                if((1<<(k-1))&i)
                {
                    A[tot1].f[1]+=A[tot1].f[0]*a[k];
                    A[tot1].f[0]+=a[k];
                }
            }
            tot1++;
        }
        int tt2=1<<n;
        for(int i=0;i<tt2;i+=tt)
        {
            B[tot2].f[0]=0;
            B[tot2].f[1]=0;
            for(int k=mid+1;(1<<(k-1))<tt2;k++)
            {
                if((1<<(k-1))&i)
                {
                    B[tot2].f[1]+=B[tot2].f[0]*a[k];
                    B[tot2].f[0]+=a[k];
                }
            }
            tot2++;
        }
        /*for(int i=0;i<tot1;i++)
        cout<<A[i].f[0]<<" "<<A[i].f[1]<<endl;
        cout<<"-----------------"<<endl;
        for(int i=0;i<tot2;i++)
        cout<<B[i].f[0]<<" "<<B[i].f[1]<<endl;*/
        build(0,tot2-1,1,0);
        int ans=-1;
        for(int i=0;i<tot1;i++)
        {
            ans+=query(A[i],1);
        }
        printf("%d\n",ans);
    }
    return 0;
}