hdu7141 Ball(排序)(bitset)

给出$n$个点，定义两点间的距离为曼哈顿距离，求这样的三点的方案数，满足三点两两距离(有$3$个数)中的中位数为质数。$n\le 2000$；测试数据$T\le 10$；时间限制$10s$

$O(n^3)$显然是可做但是不行的一种方法。

很自然想，那能不能枚举距离为质数的两点，然后看看以这条边为中位数的方案数有多少个(记两点的距离为$p$)。进一步，那么就要求出某个点连接这两个点，它们的距离一个比$p$大，一个比$p$小。

肯定不能每一次都去看看哪些点比$p$大，哪些比$p$小。我们可以考虑先对所有的边进行一次排序，从小到大的枚举两两距离，这样枚举上去，就能保证之前的边是比现在小的，之后的是比现在大的。每一个点用一个bitset存，如果$dis(i,j)$的距离枚举过了(就是说对于以后点而言是较小的)，那么让t[i].set(j)，t[j].set(i)，$t$是刚刚说的bitset。这样对于每条当前边的两个端点，某一位上$t[i]$是$1$，那么$t[j]$ 得是0；或者是$t[i]$是$0$，$t[j]$是$1$。这样的一个比较可以用异或实现。所以$ans$加上$t[i{]}^t[j]$二进制下$1$的个数即可。

最终$O(n^2(\log n+n/W))=O(n^3/W)$。($W$为评测机运算位数)

#include
#define dis(i,j) abs(x[i]-x[j])+abs(y[i]-y[j])
using namespace std;
const int N=2005,M=2e5+10;

int x[N],y[N];
struct HH
{
	int s,x,y;
}a[N*N];int cnt;
bool cmp(HH h1,HH h2)
{
	return h1.s<h2.s;
}
bitset<N> t[N];

int v[M],pr[M];//debug bool v[N];
void prime()
{
	for(int i=2;i<=(int)2e5;i++)
	{
		if(!v[i])
		{
			pr[++pr[0]]=i;
			v[i]=i;
			//printf("%d ",i);
		}
		for(int j=1;j<=pr[0];j++)
		{
			if(pr[j]>v[i] || pr[j]*i>(int)2e5) break;
			v[pr[j]*i]=pr[j];
		}
	}
}

void solve()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) t[i].reset();
	cnt=0;
	for(int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]);
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++) a[++cnt]={dis(i,j),i,j};
	sort(a+1,a+cnt+1,cmp);
	long long ans=0;
	for(int i=1;i<=cnt;i++)
	{
		if(v[a[i].s]==a[i].s) ans+=(t[a[i].x]^t[a[i].y]).count();
		t[a[i].x].set(a[i].y);
		t[a[i].y].set(a[i].x);
	}
	//cerr<<"ans";//hdu上不能用cerr
	printf("%lld\n",ans);
}

int main()
{
	prime();
	int T;
	scanf("%d",&T);
	while(T--) solve();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63