题目大意：给出n个教室的坐标(三维)以及求任意两点间距离的方式，q次询问，对每次询问输出距离小于R的坐标对数。
解题思路：
一、【真丶暴力】
先离线存取每个点坐标，然后两层循环求出所有可能组合的情况，将结果存在答案数组里，因为数组里存的是距离等于R的组合种类数，而题目要求的是距离大于等于R的组合种类数，所以需要从前往后更新一下答案数组。最后对于每次询问，直接输出结果即可。
注：因为两坐标间距离最大为30，所以当R超过30时，将其看作30就可以了。
Mycode: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
using namespace std;
typedef long long LL;
const int MAX = 50000+5;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
int t, n, q, tem, ans;
struct node
{
int x, y, z;
};
int dis(node a, node b)
{
return (abs(a.x-b.x) + abs(a.y-b.y) + abs(a.z - b.z));
}
int main()
{
scanf("%d",&t);
while(t--)
{
int aa[35];
node a[MAX];
scanf("%d%d",&n,&q);
for(int i = 0; i < n; ++i)
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
for(int i = 0; i < n; ++i)
{
for(int j = i+1; j < n; ++j)
{
++aa[dis(a[i], a[j])];
}
}
for(int i = 1; i <= 30; ++i)
aa[i] += aa[i-1];
while(q--)
{
scanf("%d",&tem);
if(tem >= 30)
printf("%d\n",aa[30]);
else
printf("%d\n",aa[tem]);
}
}
return 0;
}
显然，这样做会TLE，毕竟n的范围达到了5 * 1e4。再读读题，这时才意识到坐标范围为[0，10]。根据这个条件可以得到思路二。
二、【技巧丶暴力】
用三维数组记录每个点出现的次数，然后遍历每个坐标，根据其出现次数得到组合时出现的情况。
注：
(1).两坐标相同时，其可能的组合种类数为 n!/n 即 n $\times$ (n-1)/2 <n为坐标的个数>
(2).两坐标不同时，其可能的组合种类数为 n $\times$ m / 2 <n,m分别为两坐标的个数>
Mycode: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
using namespace std;
typedef long long LL;
const int MAX = 10005;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
int n, q, t, tem;
int a, b, c, x, y, z;
LL aa[35];
LL dex[15][15][15];
int dis(int aa, int bb, int cc, int xx, int yy, int zz)
{
return abs(aa-xx)+abs(bb-yy)+abs(cc-zz);
}
int main()
{
scanf("%d",&t);
while(t--)
{
memset(aa, 0, sizeof(aa));
memset(dex, 0, sizeof(dex));
scanf("%d%d",&n,&q);
while(n--)
{
scanf("%d%d%d",&x,&y,&z);
++dex[x][y][z];
}
for(a = 0; a <= 10; ++a)
for(b = 0; b <= 10; ++b)
for(c = 0; c <= 10; ++c)
if(dex[a][b][c])
for(x = 0; x <= 10; ++x)
for(y = 0; y <= 10; ++y)
for(z = 0; z <= 10; ++z)
if(dex[x][y][z])
{
tem = dis(a, b, c, x, y, z);
if(tem == 0)
aa[tem] += (dex[x][y][z])*(dex[x][y][z]-1)/2;
else
aa[tem] += dex[x][y][z]*dex[a][b][c];
}
for(int i = 1; i <= 30; ++i)
aa[i] /= 2;
for(int i = 1; i <= 30; ++i)
aa[i] += aa[i-1];
while(q--)
{
scanf("%d",&tem);
if(tem > 30)
tem = 30;
printf("%lld\n",aa[tem]);
}
}
return 0;
}
