磁力块

Description

在一片广袤无垠的原野上，散落着N 块磁石。每个磁石的性质可以用一个五元组 (x,y,m,p,r)描述，其中x,y 表示其坐标，m 是磁石的质量，p 是磁力，r 是吸引半径。若磁石 A 与磁石B 的距离不大于磁石A 的吸引半径，并且磁石B 的质量不大于磁石A 的磁力，那么A 可以吸引B。

小取酒带着一块自己的磁石L 来到了这篇原野的(x0,y0)处，我们可以视为磁石L 的坐标为(x0,y0)。小取酒手持磁石L 并保持原地不动，所有可以被L 吸引的磁石将会被吸引过来。在每个时刻，他可以选择更换任意一块自己已经获得的磁石（当然也可以是自己最初携带的L 磁石）在(x0,y0)处吸引更多的磁石。小取酒想知道，他最多能获得多少块磁石呢？

Input Format

第一行五个整数x0,y0,pL,rL,N，表示小取酒所在的位置，磁石L 磁力、吸引半径和原野上散落磁石的个数。

接下来N 行每行五个整数x,y,m,p,r，描述一块磁石的性质。

Output Format

输出一个整数，表示最多可以获得的散落磁石个数（不包含最初携带的磁石L）。

Sample Input

Sample Output

解析

显然我们可以建立一个\(bfs\)框架，队列中存储着每一次已经拿到的磁石，然后每次尝试用队头的磁石去吸引其他磁石，能够吸引到其他磁石就把磁石加入到队尾，直到队列为空。

那么我们需要解决的问题就是快速地判断哪些磁石能够被吸引，而判断是否能够被吸引的有两个关键信息："质量"和"距离"，我们考虑如下的分块算法：

对于前一种处理方式来说，均摊复杂度是\(O(1)\)的，总复杂度为\(O(\sqrt n)\)，对于朴素扫描的的那一段来说，时间复杂度也是\(O(\sqrt n)\)，所以总的时间复杂度就是\(O(n\sqrt n)\)。

\(Code:\)

#include <bits/stdc++.h>

using namespace std;

const int N = 250020 , SIZE = 5200;

struct magnet

{

    long long m,p,r,dis;

};

magnet a[N],st;

long long n,x_,y_,l[SIZE],r[SIZE],belo[N],T,size,ans,flag[N],Maxm[SIZE];

inline long long calc(long long x1,long long y1,long long x2,long long y2)

{

    return (x1-x2) * (x1-x2) + (y1-y2) * (y1-y2);

}

inline void input(void)

{

    scanf("%lld%lld%lld%lld%lld",&x_,&y_,&st.p,&st.r,&n);

    st.m = 0 , st.dis = 0 , st.r *= st.r;

    for (int i=1;i<=n;i++)

    {

        long long x,y,m,p,r;

        scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&p,&r);

        a[i] = (magnet){m,p,r*r,calc(x,y,x_,y_)};

    }

}

inline void setblocks(void)

{

    T = sqrt(n) , size = n/T;

    for (int i=1;i<=T;i++)

    {

        if ( i * size > n ) break;

        l[i] = (i-1) * size + 1;

        r[i] = i * size;

    }

    if ( r[T] < n ) T++ , l[T] = r[T-1] + 1 , r[T] = n;

    for (int i=1;i<=T;i++)

        for (int j=l[i];j<=r[i];j++)

            belo[j] = i;

}

inline bool compare_m(magnet p1,magnet p2)

{

    return p1.m < p2.m;

}

inline bool compare_d(magnet p1,magnet p2)

{

    return p1.dis < p2.dis;

}

inline void init(void)

{

    sort( a+1 , a+n+1 , compare_m );

    for (int i=1;i<=T;i++)

        Maxm[i] = a[r[i]].m , sort( a+l[i] , a+r[i]+1 , compare_d );

}

inline void bfs(void)

{

    queue < magnet > q;

    q.push(st);

    while ( !q.empty() )

    {

        magnet t = q.front();

        q.pop(); ans ++;

        for (int i=1;i<=T;i++)

        {

            if ( Maxm[i] <= t.p )

            {

                for (int j=l[i];j<=r[i];j++)

                {

                    if ( a[j].dis <= t.r )

                    {

                        if ( !flag[j] )

                            flag[j] = true , q.push(a[j]);

                    }

                    else {l[i] = j; break;}

                    if ( j == r[i] ) l[i] = r[i] + 1;

                }

            }

            else

            {

                for (int j=l[i];j<=r[i];j++)

                    if ( !flag[j] && a[j].dis <= t.r && a[j].m <= t.p )

                        flag[j] = true , q.push(a[j]);

                break;

            }

        }

    }

}

int main(void)

{

    input();

    setblocks();

    init();

    bfs();

    printf("%lld\n",ans-1);

    return 0;

}

<后记>

磁力

『磁力块 bfs 分块』

磁力块

Description

Input Format

Output Format

Sample Input

Sample Output

解析