题目链接:http://www.ifrog.cc/acm/problem/1143
题意:略。
思路:看到x,y,z的范围很小,所以就想到先统计每个点上有多少教室,然后直接暴力枚举每个点到另一个点的距离,结果记录在sum数组中,然后求个前缀和就好,因为最大距离只有30,所以对于大于30的直接输出sum[30]就好,类型要开long long,不然会WA。
#pragma comment(linker, "/STACK:102400000,102400000") #include <map> #include <set> #include <stack> #include <queue> #include <cmath> #include <string> #include <vector> #include <cstdio> #include <cctype> #include <cstring> #include <sstream> #include <cstdlib> #include <iostream> #include <algorithm> #define MOD 1e9+7 #define lson root<<1,l,mid #define rson root<<1|1,mid+1,r #define DBN1(a) cerr<<#a<<"="<<(a)<<"\n" #define DBN2(a,b) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n" #define DBN3(a,b,c) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n" #define DBN4(a,b,c,d) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n" #define DBN5(a,b,c,d,e) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<"\n" #define DBN6(a,b,c,d,e,f) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<", "<<#f<<"="<<(f)<<"\n" #define clr(a,x) memset(a,x,sizeof(a)) using namespace std; typedef long long ll; const int maxn=5e4+5; const int INF=0x3f3f3f3f; const double PI=acos(-1.0); template<typename T> inline T gcd(T&a,T&b){return b==0?a:gcd(b,a%b);} template<typename T> inline T lcm(T&a,T&b){return a/gcd(a,b)*b;} template<typename T> inline T read(T&x){ x=0;int _f=0;char ch=getchar(); while(ch<'0'||ch>'9')_f|=(ch=='-'),ch=getchar(); while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x=_f?-x:x; } int T,n,q; ll sum[35]; ll status[15][15][15]; bool vis[15][15][15][15][15][15]; int main(){ for (read(T);T;T--){ read(n),read(q); clr(sum,0); clr(status,0); clr(vis,false); for (int i=1;i<=n;i++){ int x,y,z;read(x),read(y),read(z); status[x][y][z]++; } for (int i=0;i<=10;i++) for (int j=0;j<=10;j++) for (int k=0;k<=10;k++) for (int l=0;l<=10;l++) for (int m=0;m<=10;m++) for (int n=0;n<=10;n++){ if (!status[i][j][k] || !status[l][m][n] || vis[i][j][k][l][m][n] || vis[l][m][n][i][j][k]) continue; if (i==l && j==m && k==n){ sum[0]+=status[i][j][k]*(status[i][j][k]-1)/2; vis[i][j][k][l][m][n]=vis[l][m][n][i][j][k]=true; continue; } int t=abs(i-l)+abs(j-m)+abs(k-n); vis[i][j][k][l][m][n]=vis[l][m][n][i][j][k]=true; sum[t]+=status[i][j][k]*status[l][m][n]; } for (int i=1;i<=30;i++) sum[i]+=sum[i-1]; for (int i=1;i<=q;i++){ int r;read(r); if (r>30) printf("%lld\n",sum[30]); else printf("%lld\n",sum[r]); } } return 0; }