HDU 4022 Bombing【STL 继续练习】

今天真是各种sb,弱爆了。
果然以后做网预的时候就应该第一道水题用STL各种水。
闲话少说。
本题题意略,直接说做法。
首先,必需的是离散化。sort+MAP是我的离散化方法,个人觉得这样虽然慢,但是好写。
后面的就八仙过海各显神通了。什么用十字链表模拟啊,什么multiset啊,什么vector啊,什么数组直接标记啊,不一而足,水题就要用水题的方法做。
我是vector做的。
开了200000个vector分别用来存储离散化后的每行及每列中元素的个数。
每次查询的时候,将对应行/或者列的size输出,然后对其中每个元素在另外一边(行/列)用upper/lower_bound查存在性,存在的都删除erase,然后将本行/列清空clear。
一开始就是WA在此处了,因为有重复坐标的点,而set的一般写法无法处理这种情况,想了半天最后用了vector+二分。太蛋疼了。
还RE了一次,因为对于vector来说,erase作为动态删除会使其周围元素的指针改变,会发生内存泄漏、指针悬挂等现象,所以果断要用erase的范围删除操作[low,up)。
没啥说的,复杂度均摊下来很小,因为不会重复统计,所以顶多是NlogN的复杂度,再加上离散化的复杂度,整体NlogN。

老话,STL能做,为啥要手写?出题卡STL的就是sb,不解释;至于什么叫卡STL,各位大牛都懂得。
今天弱爆了,就这样吧。
附代码:
#include <iostream>
#include 
<cstdio>
#include 
<set>
#include 
<map>
#include 
<vector>
#include 
<cmath>
#include 
<algorithm>
using namespace std;
#define maxn 100005
struct point
{
    
int x,y;
    point(){}
    point(
int a,int b):x(a),y(b){}
}p[maxn];
int x[maxn],y[maxn];
int n,m;
vector 
<int> X[maxn],Y[maxn];
map 
<int,int> MX,MY;
vector 
<int> ::iterator xlow,xup,ylow,yup,idx,idy;
int main()
{
    
while(scanf("%d %d",&n,&m) == 2 && (n || m))
    {
        MX.clear();
        MY.clear();
        
for(int i = 1;i <= n;i++)
        {
            
if(!X[i].empty())
                X[i].clear();
            
if(!Y[i].empty())
                Y[i].clear();
        }
        
for(int i = 0;i < n;i++)
        {
            
int a,b;
            scanf(
"%d %d",&a,&b);
            p[i] 
= point(a,b);
            x[i] 
= a;
            y[i] 
= b;
        }
        sort(x,x 
+ n);
        sort(y,y 
+ n);
        
int cntx = 1,cnty = 1;
        
for(int i = 0;i < n;i++)
        {
            
if(MX[x[i]] == 0)
                MX[x[i]] 
= cntx++;
            
if(MY[y[i]] == 0)
                MY[y[i]] 
= cnty++;
        }
        
for(int i = 0;i < n;i++)
        {
            p[i].x 
= MX[p[i].x];
            p[i].y 
= MY[p[i].y];
            idx 
= lower_bound(X[p[i].x].begin(),X[p[i].x].end(),p[i].y);
            X[p[i].x].insert(idx,p[i].y);
            idy 
= lower_bound(Y[p[i].y].begin(),Y[p[i].y].end(),p[i].x);
            Y[p[i].y].insert(idy,p[i].x);
        }
        
for(int i = 0;i < m;i++)
        {
            
int mod,d;
            scanf(
"%d %d",&mod,&d);
            
if(mod == 0)
            {
                d 
= MX[d];
                printf(
"%d\n",X[d].size());
                
if(X[d].empty())
                    
continue;
                
for(idx = X[d].begin();idx != X[d].end();idx++)
                {
                    
int p = *idx;
                    ylow 
= lower_bound(Y[p].begin(),Y[p].end(),d);
                    yup 
= upper_bound(Y[p].begin(),Y[p].end(),d);
                    Y[p].erase(ylow,yup);
                }
                X[d].clear();
            }
            
else
            {
                d 
= MY[d];
                printf(
"%d\n",Y[d].size());
                
if(Y[d].empty())
                    
continue;
                
for(idy = Y[d].begin();idy != Y[d].end();idy++)
                {
                    
int p = *idy;
                    xlow 
= lower_bound(X[p].begin(),X[p].end(),d);
                    xup 
= upper_bound(X[p].begin(),X[p].end(),d);
                    X[p].erase(xlow,xup);
                }
                Y[d].clear();
            }
        }
        puts(
"");
    }
}

posted on 2011-09-10 19:10 BUPT-[aswmtjdsj] @ Penalty 阅读(1375) 评论(0)  编辑 收藏 引用 所属分类: 数据结构HDU Solution Report 乱搞


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2011年9月>
28293031123
45678910
11121314151617
18192021222324
2526272829301
2345678

导航

统计

常用链接

留言簿(1)

随笔分类(150)

随笔档案(71)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜