【题解】磁力块
题目链接
解题思路
这道题目中,我们为了更快的排除一些不可选的磁力块,可以选择分块。总体以 m 从大到小排序,块内以 dis 排序(颠倒过来应该也可以)。即以两个对于吸引的决定项排序。
我们设 k 是大小交替的一块(即需要考虑的,但并不是全部都满足 m <now.p)。先记录下每一块的最大最小值,O(sqrt(n))查找。如果 now.p<maxn[k],则表示这一块是 k。(当然可能没有大小交替的块,k 查找到的则是第一个全部大于 now.p 的,我们可以和 k 一样考虑,不影响答案。)
对于 k 前面的,由于所有 m 都符合,只需要考虑 dis,如果 dis[i]>now.r,则说明这块中它和它之后的都不可取了,直接跳到下一块。当然我们需要设 fi 和 la 作为块的头和尾,每次取一个数都要 fi[i]++;
对于 k,我们不可以直接 fi[i]++。因为有一种情况“大小大”,我们取的是小的,但是大的却被排除了,明显不对。所以我们维护一个 vis 数组对于这种奇坑无比的情况进行特判。
代码
#include<bits/stdc++.h>
using namespace std;
const int inf=1e9+7;
long long xx,yy,pl,rl;
int num,n;
struct stone{
long long x,y,m,p,r,dis;
}s[250005];
bool vis[250005];
//m<=p,dis<=r;
int fi[5005],la[5005];
int maxn[5005],minn[5005];
bool cmp(stone aa,stone bb){
return aa.m<bb.m;
}
bool cmpp(stone aa,stone bb){
return aa.dis<bb.dis;
}
int sq;
void rd(){
scanf("%lld%lld%lld%lld%d",&xx,&yy,&pl,&rl,&n);
for(int i=1;i<=n;i++){
vis[i]=false;
scanf("%lld%lld%lld%lld%lld",&s[i].x,&s[i].y,&s[i].m,&s[i].p,&s[i].r);
s[i].r=s[i].r*s[i].r;
s[i].dis=(xx-s[i].x)*(xx-s[i].x)+(yy-s[i].y)*(yy-s[i].y);
}
}
void init(){
sort(s+1,s+1+n,cmp);
sq=sqrt(n);
num=sq;
for(int i=1;i<=num;i++){
fi[i]=(i-1)*sq+1,la[i]=min(n,i*sq);
}
if(sq*sq<n){
num++;
fi[num]=sq*sq+1;
la[num]=n;
}
for(int i=1;i<=num;i++){
maxn[i]=s[la[i]].m,minn[i]=s[fi[i]].m;
sort(s+fi[i],s+la[i]+1,cmpp);
}
}
queue<stone> q;
int main(){
rd();
init();
int gett=0;
stone tmp;
tmp.dis=0,tmp.m=0,tmp.p=pl,tmp.r=rl*rl,tmp.x=xx,tmp.y=yy;
q.push(tmp);
stone now;
while(gett!=n&&!q.empty()){
now=q.front();
q.pop();
int k=1;
while(k<=num&&now.p>=maxn[k])k++;//第一块
for(int i=1;i<k;i++){
for(int j=fi[i];j<=la[i];j++){
if(s[j].dis>now.r)break;//由于在一块之内是按照dis排序的,所以当前dis>r,则所有之后的dis都大于r
if(vis[j])fi[i]++;
if(s[j].m<=now.p&&!vis[j]){
gett++;
q.push(s[j]);
fi[i]++;
vis[j]=true;
}
}
}
if(k<=num&&now.p>=minn[k]){
for(int j=fi[k];j<=la[k];j++){
if(s[j].dis>now.r)break;
if(s[j].m<=now.p&&!vis[j]){
gett++;
q.push(s[j]);
vis[j]=true;
}
}
}
}
printf("%d\n",gett);
return 0;
}