首页 > 代码库 > 清澄 A1485. Catch The Penguins 抓企鹅
清澄 A1485. Catch The Penguins 抓企鹅
试题来源
2013中国国家集训队论文答辩
问题描述
Xyz带着他的教徒们乘着科考船一路破冰来到了南极大陆,发现这里有许许多多的企鹅。邪恶的Xyz想要抓很多企鹅回去开动物园,当宠物玩。但动物保护协会很快赶来,他必须尽快行动!
我们把南极大陆看成一个三维直角坐标系。
有N只企鹅,每只企鹅会在一定的时刻的出现,第i只企鹅在Ai时刻出现在坐标为(Bi,Ci,Di)的地方。
Xyz要在某一时刻在某一地方(X,Y,Z)撒一张大网,将(0,0,0)到(X,Y,Z)这个大长方体里的企鹅全都网进去捕捉回家(还没出现的企鹅就不会被捉进去了)。
为了快准狠而且保证不铺张浪费网,Xyz想知道不同时间不同地点撒网能抓到几个企鹅(这样的询问有Q个)。然后他再行动。
我们把南极大陆看成一个三维直角坐标系。
有N只企鹅,每只企鹅会在一定的时刻的出现,第i只企鹅在Ai时刻出现在坐标为(Bi,Ci,Di)的地方。
Xyz要在某一时刻在某一地方(X,Y,Z)撒一张大网,将(0,0,0)到(X,Y,Z)这个大长方体里的企鹅全都网进去捕捉回家(还没出现的企鹅就不会被捉进去了)。
为了快准狠而且保证不铺张浪费网,Xyz想知道不同时间不同地点撒网能抓到几个企鹅(这样的询问有Q个)。然后他再行动。
输入格式
第一行一个整数N表示企鹅个数。
第二行到N+1行每行四个实数(Ai,Bi,Ci,Di),表示企鹅的出现时间和位置
第N+2行一个整数Q表示询问个数。
接下来Q行每行四个实数(T,X,Y,Z),表示询问的时间和位置。
第二行到N+1行每行四个实数(Ai,Bi,Ci,Di),表示企鹅的出现时间和位置
第N+2行一个整数Q表示询问个数。
接下来Q行每行四个实数(T,X,Y,Z),表示询问的时间和位置。
输出格式
输出共Q行,每行一个整数,回答每个询问能抓到几个企鹅。
样例输入
1
0 0 0 0
2
1 1 1 1.0
1 1 1 -1
0 0 0 0
2
1 1 1 1.0
1 1 1 -1
样例输出
1
0
0
数据规模和约定
共20个数据
数据1~3 N,Q<=1000
数据4~6 N,Q<=5000
数据7~10 N,Q<=10000
数据11~14 N<=30000,Q<=10000
数据15~18 N<=10000,Q<=30000
数据19~20 N,Q<=30000
数据1~3 N,Q<=1000
数据4~6 N,Q<=5000
数据7~10 N,Q<=10000
数据11~14 N<=30000,Q<=10000
数据15~18 N<=10000,Q<=30000
数据19~20 N,Q<=30000
位运算。
四维分开计算。
按照某个维度从小到大排序询问和企鹅。用bitset状态压缩记录这一维中满足询问要求的企鹅有哪些。
然后求四维度答案的交集。
1 /*by SilverN*/ 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<bitset> 8 using namespace std; 9 const int mxn=30010;10 int n;11 struct qe{12 double w[5];13 int id;14 }a[mxn],q[mxn];15 bitset<30010> b[30010];16 int ans[mxn];17 int D=0;18 int cmp(const qe a,const qe b){return a.w[D]<b.w[D];}19 int main(){20 int i,j;21 scanf("%d",&n);22 for(i=1;i<=n;i++){23 scanf("%lf%lf%lf%lf",&a[i].w[1],&a[i].w[2],&a[i].w[3],&a[i].w[4]);24 a[i].id=i;25 }26 int Q;27 scanf("%d",&Q);28 for(i=1;i<=Q;i++){29 scanf("%lf%lf%lf%lf",&q[i].w[1],&q[i].w[2],&q[i].w[3],&q[i].w[4]);30 q[i].id=i;31 b[i].set();32 }33 for(i=1;i<=4;i++){34 D=i;35 sort(a+1,a+n+1,cmp);36 sort(q+1,q+Q+1,cmp);37 int hd=1;38 bitset<30010>res;39 res.reset();40 for(j=1;j<=Q;j++){41 while(a[hd].w[D]<=q[j].w[D] && hd<=n){42 res[a[hd].id]=1;43 hd++;44 }45 b[q[j].id]&=res;46 }47 }48 for(i=1;i<=Q;i++)printf("%d\n",b[i].count());49 return 0;50 }
清澄 A1485. Catch The Penguins 抓企鹅
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。