hdu-7141 Ball （bitset）

传送门：Problem - 7141

题意：在m*m的棋盘上有n个点，问你有多少种选择方案 每次选三个点并求出两两间的曼哈顿距离 使得中位数的曼哈顿距离是个质数。

分析：显然可以预处理出任意两点间的曼哈顿距离，然后枚举质数曼哈顿距离时尝试有多少个第三方点满足条件。本来以为是类似于矩阵数点之类的，但是围绕一个点的曼哈顿距离是不规则的，况且还有两个点，我们需要一些特殊的处理方法。考虑对曼哈顿距离排序后使用bitset，dp[i][k]=1表示点k到i的距离小于当前距离，每次加上(dp[a]^dp[b]).count()即可。

代码：
 

#include<bits/stdc++.h>
using namespace std;
#define int long long
// #define int __int128
#define pii pair<int,int>
#define endl '\n'//交互题需要endl刷新//
const int maxn=1e6+5;

const int N=1e7;
int flag[N+10];//flag[i]=0 i是质数 
int prime[N+10];
int cnt;

void init()
{
    flag[0]=1,flag[1]=1;//0和1不是质数
    for(int i=2;i<=N;i++)
    {
        if(flag[i]==0) prime[++cnt]=i;
        for(int j=1;j<=cnt&&prime[j]*i<=N;j++)
        {
            flag[i*prime[j]]=1;
            if(i%prime[j]==0) break;//根据唯一分解定理，每个数只在prime[j]是其最小因子时被标记(12=2*6!=4*3)
        }
    }
}

int x[2005],y[2005];
bitset<2005>dp[2005];

struct node
{
    int a,b,dis;
}e[2005*2005];

int cal(int a,int b)
{
    return abs(x[a]-x[b])+abs(y[a]-y[b]);
}

bool cmp(node c,node d)
{
    return c.dis<d.dis;
}

void solve()
{
    int n,m;
    cin>>n>>m;

    for(int i=1;i<=n;i++) dp[i].reset();

    for(int i=1;i<=n;i++)
    {
        cin>>x[i]>>y[i];
    }
    int ct=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            e[++ct]={i,j,cal(i,j)};
        }
    }

    sort(e+1,e+ct+1,cmp);

    int ans=0;
    for(int i=1;i<=ct;i++)
    {
        int a=e[i].a,b=e[i].b,dis=e[i].dis;
        if(!flag[dis]) ans+=(dp[a]^dp[b]).count();
        dp[a][b]=dp[b][a]=1;
    }
    cout<<ans<<endl;
}
 
signed main()
{
    init();
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t=1;
    cin>>t;
    while(t--) solve();
}