Tsinsen 1485 Catch The Penguins 抓企鹅 —

Tsinsen 1485 Catch The Penguins 抓企鹅 ——Bitset

阅读量：5937 次

发布时间：2019-06-19

本文共 2579 字，大约阅读时间需要 8 分钟。

【题目分析】

刚开始想的是KD-Tree去暴力求解。

写了半天还没有暴力得的分数多（说好的nlogn呢）

直接按照四个维度排序。

然后扫一遍，用bitset去维护，然后对于四个维度小于一个询问的结果取一个交就可以了。

Bitset大法好。

【代码】

垃圾KD-Tree

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                using namespace std;#define maxn 500005#define mlog 16#define F(i,j,k) for (int i=j;i<=k;++i)#define inf (1e18)void Finout(){ #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin);// freopen("out.txt","w",stdout); #endif}struct node{double d[4],mn[4],mx[4];int siz,l,r;}t[maxn],now;int n,q,D,rt,tot=0,m;bool operator < (node x,node y){return x.d[D]
                
                 l?build(l,mid-1,(dir+1)%4):0; t[mid].r=mid
                 
                  =0&&t[o].mx[i]<=now.d[i]); else flag=0; } { if (t[o].mn[i]>=0&&t[o].mn[i]<=now.d[i]); else flag=0; } } return flag;}void print(int o){ if (!o) return; printf("%d t[o].mn[0]=%f t[o].mn[1]=%f t[o].mx[0]=%f t[o].mx[1]=%f l :%d r: %d\n",o,t[o].mn[0],t[o].mn[1],t[o].mx[0],t[o].mx[1],t[o].l,t[o].r); print(t[o].l); print(t[o].r);}bool din(int o){ int flag=1; F(i,0,3) { if (t[o].d[i]>=0&&t[o].d[i]<=now.d[i]); else flag=0; } return flag;}bool out(int o){ int flag=1; F(i,0,3) { if ((t[o].mx[i]>now.d[i]&&t[o].mn[i]>now.d[i])||(t[o].mx[i]<0&&t[o].mn[i]<0)); else flag=0; } return flag;}int query(int o){ if (!o) return 0; if (in(o)){return t[o].siz;} else { int ret=0; if (din(o)) ret+=1; if (t[o].l) { if (out(t[o].l)); else ret+=query(t[o].l); } if (t[o].r) { if (out(t[o].r)); else ret+=query(t[o].r); } return ret; }}int main(){ Finout(); F(i,0,3) t[0].mx[i]=inf,t[0].mn[i]=-inf; scanf("%d",&m);n=1; F(i,1,m) { int flag=1; F(j,0,3) { scanf("%lf",&t[n].d[j]); if (t[n].d[j]<0) flag=0; } if (flag) n++; } n--; rt=build(1,n,1); scanf("%d",&q); F(i,1,q) { int flag=1; F(j,0,3) { scanf("%lf",&now.d[j]); if (now.d[j]<0) flag=0; } if (flag) printf("%d\n",query(rt)); else printf("0\n"); }}

有趣的Bitset

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 using namespace std;#define maxn 30010#define F(i,j,k) for (int i=j;i<=k;++i)int Getint(){ int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9') {if (ch=='-') f=-1; ch=getchar();} while (ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();} return x*f;}bitset
                 
                   b[maxn],now;struct node{double d[4];int id;}a[maxn],q[maxn];int n,m,D;bool cmp(node x,node y){return x.d[D]