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

The Bloom of Youth

本博客已搬家至http://kuangqi.me

 
 
 

日志

 
 

C++ STL学习笔记——容器  

2010-03-07 15:32:12|  分类: 编程之美 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

今天去OJ刷水题,与其说去刷题,不如说是去学C++标准库。现将学习成果记录下来。

 

1.使用map容器进行单词统计

题目地址:http://acm.bnu.edu.cn/contest/problem_show.php?pid=4045

大意:统计一篇文章中每个单词的出现次数。将大于3次的单词按字典序输出。

分析:传统方法要自己实现单词查找操作,还要对单词进行排序。调试复杂,代码长度通常会超过1000字节。

使用C++map容器实现,无需用户实现查找操作,由于map容器在标准库中通常以树结构实现,所以其元素的顺序不是由用户管理的。换句话说,无论如何插入元素,在用户看来元素都是有序的。由于map树形结构的特点,不能使用下标顺序访问元素,而需要使用迭代器遍历。

Code:

#include <iostream>

#include <string>

#include <map>

#include <ctype.h>

using namespace std;

void lcase(string *s)

{

     int l=s->length();

     for(int i=0;i<l;i++)

     {

         if(isupper((*s)[i])) (*s)[i]+=32;

     }

}

int main()

{

    map<string,int> m;

    string str;

    while(cin>>str)

    {

         lcase(&str);

        m[str]++;

    }

     map<string,int>::iterator i;    

     map<string,int>::iterator ii;

     ii=m.end();

     int count=0;

     for(i=m.begin();i!=ii;i++)

     {

         if(i->second>=3 && count<10)

         {

              cout<<i->first<<endl;

              count++;

         }

     }

}

 

2.使用vector容器简化排序操作

题目地址:http://acm.bnu.edu.cn/contest/problem_show.php?pid=4166

大意:对对象(结构体)进行排序,对前三项求和输出

分析:在做这道题的时候听到某大牛的抱怨——my_qsort调了半个小时了……囧

通常做法是建两个(甚至更多)数组,存几个元素,然后自己写排序。稍好一点的办法是调用C标准库的qsort。用Cqsort函数在这道题是可以的,可是qsort是一个不稳定的排序,对于一些要求稳定排序的题目不适用。比如BNUOJ的《YC大牛的判题任务》

C++标准库中的vector是一个连续的存储结构,具有很高的随机访问效率(跟数组一样),可以使用下标访问元素。调用C++标准库的sort函数进行排序,如果要求稳定排序,只需将sort改成stable_sort

Code:

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

struct toy

{

    int num;

    double value;

    int price;

};

int cmp(toy a,toy b)

{

    return a.value>b.value;

}

int main()

{

    int n;

    toy t;

    int joy,price;

    vector<toy> vec;

    scanf("%d",&n);

    for(int i=1;i<=n;i++)

    {

        scanf("%d%d",&joy,&price);

        t.num=i;

        t.value=(double)joy/price;

        t.price=price;

        vec.push_back(t);

    }

    sort(vec.begin(),vec.end(),cmp);

    printf("%d\n",vec[0].price+vec[1].price+vec[2].price);

    printf("%d\n%d\n%d\n",vec[0].num,vec[1].num,vec[2].num);

}

 

3.使用stack容器优化种子填充算法(非递归)

题目地址:http://acm.bnu.edu.cn/contest/problem_show.php?pid=4165

大意:对8-连通的区域进行填充,统计每个区域的大小

分析:写这道题的经历比较曲折。先是狂喜,以为很水,题目都没读完就下手写。直接写了一个递归的4向的种子填充。发现样例不过。再读题才发现是要填充8-连通区域的,汗啊……

好不容易改成了8向的,样例过了,再次狂喜。交上去竟然是Runtime Error....

再读题,发现数据范围是750*750.数组已经开够了,唯一的可能就是爆栈了。去USACO找来这道题的数据,测到第七组数据时就爆栈了,这个数据是100*150的,对于极限情况的数据就可想而知了。

看来这道题不能用递归方法来做了。不递归的话,要用自己实现的栈结构(或者队列)代替系统栈。这种方法要申请大量的内存以防止栈溢出,空间利用率较低。

使用C++ STL中的stack容器,可以方便的使用栈结构,而且其空间的申请和释放是由标准库实现的,无需用户干预。

Code

#include <cstdio>

#include <stack>

using namespace std;

struct point

{

     int x;

     int y;

     point(int xx,int yy)

     {

         x=xx;

         y=yy;

     }

};

int floodfill(int x,int y,int w,int h,char** m,char fill,char unfill)

{

     stack<point> stk;

     point p(x,y);

     stk.push(p);

     int sum=0;

     while(!stk.empty())

     {

         x=stk.top().x;

         y=stk.top().y;

         stk.pop();

         if(m[y][x]!=fill)

         {

              m[y][x]=fill;

              sum++;

         }

          else continue;

         if(y!=0 && m[y-1][x]==unfill) {stk.push(point(x,y-1));}//

         if(y!=h && m[y+1][x]==unfill) {stk.push(point(x,y+1));}//

         if(x!=0 && m[y][x-1]==unfill) {stk.push(point(x-1,y));}//

         if(x!=w && m[y][x+1]==unfill) {stk.push(point(x+1,y));}//

         if(x!=0 && y!=0 && m[y-1][x-1]==unfill) {stk.push(point(x-1,y-1));}//左上

         if(x!=0 && y!=h && m[y+1][x-1]==unfill) {stk.push(point(x-1,y+1));}//左下

         if(x!=w && y!=0 && m[y-1][x+1]==unfill) {stk.push(point(x+1,y-1));}//右上

         if(x!=w && y!=h && m[y+1][x+1]==unfill) {stk.push(point(x+1,y+1));}//右下

     }

     return sum;

}

 

int main()

{

     char **map;

     int w,h;scanf("%d%d",&w,&h);getchar();

     map=new char*[h];

     for(int i=0;i<h;i++)

     {

         map[i]=new char[w+1];

         gets(map[i]);

     }

     int fill='1';

     int max=0;

     for(int i=0;i<h;i++)

     {

         for(int j=0;j<w;j++)

         {

              if(map[i][j]=='.')

              {

                   int n=floodfill(j,i,w-1,h-1,map,fill++,'.');

                   if(max<n) max=n;

              }

         }

     }

     printf("%d\n",max);

}

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

历史上的今天

评论

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

页脚

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