首页 > 代码库 > 玲珑杯 round18 A 计算几何瞎暴力
玲珑杯 round18 A 计算几何瞎暴力
题目链接 : http://www.ifrog.cc/acm/problem/1143
当时没看到坐标的数据范围= =看到讨论才意识到,不同的坐标最多只有1k多个,完全可以暴力做法,不过也要一些技巧。
首先注意数很大可能爆int,用LL得话注意强制转换或者全设为LL,假如 int a=50000,b=a; LL sum=a*b; 则会爆出,除非ab都是LL 或者 sum=(LL)a*(LL)b;
还有就是R最大就是30,我们不妨设ans[i]表示R<=i的组合个数,做一个前缀和方便快速询问。
对于R>30的询问视作30即可。还有一点这里做坐标的映射是一开始想要用map+pair...不熟练搞了半天放弃了,,,,
看到别人的 vis[x][y][z]++的时候我感觉自己的脑子白长了。。。。
这样一来就方便多了复杂度也大大降低
#include<bits/stdc++.h> using namespace std; #define LL long long LL vis[11][11][11]; LL ans[31]; struct room { LL x,y,z; }P[50005]; LL dis(room A,room B){return abs(A.x-B.x)+abs(A.y-B.y)+abs(A.z-B.z);} int main() { int q,t,n,m,i,j,k,r; cin>>t; while(t--){memset(vis,0,sizeof(vis));k=0; memset(ans,0,sizeof(ans)); scanf("%d%d",&n,&q); for(i=1;i<=n;++i){room _; scanf("%lld%lld%lld",&_.x,&_.y,&_.z); if(!vis[_.x][_.y][_.z]++) P[++k]=_; } for(i=1;i<=k;++i){ for(j=i;j<=k;++j){ LL d=dis(P[i],P[j]); LL n1=vis[P[i].x][P[i].y][P[i].z]; LL n2=vis[P[j].x][P[j].y][P[j].z]; if(i==j){ ans[d]+=(n1)*(n1-1)/2; } else{ ans[d]+=n1*n2; } } } for(i=1;i<=30;++i) ans[i]+=ans[i-1]; while(q--){ scanf("%d",&r); if(r>30) r=30; printf("%lld\n",ans[r]); } } return 0; }
玲珑杯 round18 A 计算几何瞎暴力
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。