注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Minary_Acdream

http://f10.moe/

 
 
 

日志

 
 

[hdu] 4400 Mines ----------金华网络赛1001  

2012-09-25 00:26:25|  分类: 2012金华网络赛 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
  这道题的意思也和扫雷差不多,就是引爆一个雷在它的曼哈顿距离内的雷会一起爆炸。已经爆掉的雷不会再爆。
  给出雷的序号,问在这个雷被引爆时,有几个雷会一起爆炸。
 
  因为很菜=。 =、、所以在看了题解后才有点感觉。。
  先将横坐标离散化(羞愧的讲在这题之前不知道离散化是什么=。 =、、),然后把点放到相应的multiset容器里去。
  查询时二分下X坐标的范围,再对范围内的每个multiset再二分Y坐标。
  这里用到的是lower_bound()和upper_bound()函数。
  先介绍一下这两函数。
  函数lower_bound(first,last,val)在first和last中的前闭后开区间进行二分查找,返回大于或等于val的第一个元素位置。如果所有元素都小       于val,则返回last的位置,且last的位置是越界的。
  函数upper_bound(first,last,val)在first和last中的前闭后开区间进行二分查找,返回小于或等于val的第一个元素位置。如果所有元素都大   于val,则返回last的位置,且last的位置是越界的。


  然后大神们说这个真解可能是KD-Tree或者树套树。


Mines

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 381    Accepted Submission(s): 123


Problem Description
Terrorists put some mines in a crowded square recently. The police evacuate all people in time before any mine explodes. Now the police want all the mines be ignited. The police will take many operations to do the job. In each operation, the police will ignite one mine. Every mine has its "power distance". When a mine explodes, any other mine within the power distance of the exploding mine will also explode. Please NOTE that the distance is Manhattan distance here.

More specifically, we put the mines in the Cartesian coordinate system. Each mine has position (x,y) and power distance d.

The police want you to write a program and calculate the result of each operation.
 

Input
There are several test cases.
In each test case:
Line 1: an integer N, indicating that there are N mines. All mines are numbered from 1 to N.
Line 2…N+1: There are 3 integers in Line i+1 (i starts from 1). They are the i-th mine’s position (xi,yi) and its power distance di. There can be more than one mine in the same point.
Line N+2: an integer M, representing the number of operations.
Line N+3...N+M+2 : Each line represents an operation by an integer k meaning that in this operation, the k-th mine will be ignited. It is possible to ignite a mine which has already exploded, but it will have no effect.

1<=M<=N<=100000,0<=xi,yi<=10^9,0<=di<=10^9

Input ends with N=0.
 

Output
For each test case, you should print ‘Case #X:’ at first, which X is the case number starting from 1. Then you print M lines, each line has an integer representing the number of mines explode in the correspondent operation.
 

Sample Input
3 0 0 0 1 1 2 2 2 2 3 1 2 3 0
 

Sample Output
Case #1: 1 2 0
 

Source
 

Recommend
zhoujiaqi2010



#include<iostream>
#include<algorithm>
#include<queue>
#include<set>
using namespace std;

struct Mines
{
int n,y;
Mines();
Mines(int a,int b):y(a),n(b){}
bool operator<(const Mines &c)const{
return y < c.y;
}
};

int X,N;
int test[100001],x[100001],y[100001],d[100001];
int vis[100001];
queue<int>q;
multiset<Mines>p[100001];

int main()
{
int j,t = 0;
while(cin>>N,N != 0)
{
for(int i = 0;i < N;i ++){
scanf("%d %d %d",&x[i],&y[i],&d[i]);
test[i] = x[i];
}
sort(test,test + N);
X = unique(test,test + N) - test;
//unique(num,mun+n)返回的是num去重后的尾地址
for(int i = 0;i < X;i ++) p[i].clear();
for(int i = 0;i < N;i ++){
j = lower_bound(test,test + X,x[i]) - test;
p[j].insert(Mines(y[i], i));
}
memset(vis,0,sizeof(vis));
int m; cin>>m;
printf("Case #%d:\n", ++t);
while(m --)
{
int k; cin>>k; k--;
if(vis[k]){
cout<<"0"<<endl;
continue;
}
vis[k] = 1;
q.push(k);
int cnt = 0;
while(!q.empty())
{
++cnt;
multiset<Mines>::iterator yl,yr;
k = q.front();
q.pop();
int l = lower_bound(test,test + X,x[k]-d[k])-test;
int r = upper_bound(test,test + X,x[k]+d[k])-test;
for(int i = l;i < r;i ++){
int dy = d[k] - abs(x[k] - test[i]);
yl = p[i].lower_bound(Mines(y[k]-dy, 0));
yr = p[i].upper_bound(Mines(y[k]+dy, 0));
for (multiset<Mines>::iterator it = yl; it != yr; ++it)
if (!vis[it->n]) {
vis[it->n] = 1;
q.push(it->n);
}
p[i].erase(yl, yr);
}
}
printf("%d\n", cnt);
}

}
}

/*
1<=M<=N<=100000,0<=xi,yi<=10^9,0<=di<=10^9
Sample Input
3
0 0 0
1 1 2
2 2 2
3
1
2
3
0


Sample Output
Case #1:
1
2
0*/



  评论这张
 
阅读(360)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018