"玲珑杯"ACM比赛 Round #18 A 计算几何你瞎暴力

题目链接: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;
}

 

 

 

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注