算法竞赛入门经典（第2版）笔记--第5章

C++部分特性整理
1.C语言大部分头文件在c++中仍可以适用，但推荐在C头文件之前加一个小写的字母c，然后去掉.h后缀。如cstdio,cstring,cmath,cctype

2.C++中可以使用流简化输入输出操作，但缺点是运行太慢

3.头文件iostream和algorithm里定义的内容放在std名称空间，可以用using namespace std的方法把std里的名字导入默认空间。这样就可以用cin代替std::cin,cout代替std::cout,min代替std::min

4.声明数组时，数组大小可以使用const声明的常数，而不是用#define声明常数

5.C++中引用是变量的别名，可以在一定程度上代替C中的指针。按照传引用(by reference)的方式，而不是传值(by value)方式传递参数，若在函数内改参数的值，也会修改到函数的实参。
例：使用引用交换两个变量的方法如下：

#inclued<iostream>
using namespace std;

void swap2(int &a,int &b){
    int t=a; a=b; b=t;
}

int main(){
    int a=3,b=4;
    swap2(a,b);
    cout<<a<<" "<<b<<endl;
    return 0;
}

6.C++提供了string类型用来替代c语言中的字符数组。cin/cout可以直接读写string类型（速度有点慢），却不能读写字符数组，string类型还可以像整数那样相加。
考虑这样一个问题：输入数据的每行包括若干个（至少一个）以空格隔开的整数，输出每行中所有整数之和。

#include<iostream>
#include<string>
#include<sstream>
using namespace std;

int main(){
    string line;
    while (getline(cin,line)){
        int sum=0,x;
        stringstream ss(line);
        while (ss>>x) sum+=x;
        cout<<sum<<endl;
    }
    return 0;
}

首先用getline函数读取一行数据，然后用这一行创建一个字符串流–ss，之后只需像读取cin那样读取ss即可。
*注：虽然string和sstream都很方便，但string很慢，sstream更慢，应谨慎使用

7.C++中结构体和模板使用实例

#include <iostream>
using namespace std;

template<typename T>
struct Point{
    T x,y;
    Point(T x=0,T y=0):x(x),y(y){}
};

template<typename T>
Point<T> operator + (const Point<T>& A,const Point<T>&B){
    return Point<T>(A.x+B.x,A.y+B.y);
}

template<typename T>
ostream& operator << (ostream &out,const Point<T>& p){
    out<<"("<<p.x<<","<<p.y<<")";
    return out;
}

int main(){
    Point<int> a(1,2),b(3,4);
    Point<double> c(1.1,2.2),d(3.3,4.4);
    cout<<a+b<<" "<<c+d<<endl;
    return 0;
}

例题5-1 大理石在哪儿(Where is the Marble?,UVa10474)
此题非常简单，只需先排序后查找即可。可使用alogrithm头文件中的sort和lower_bound分别完成所需操作并简化代码，函数使用方法如下：
sort函数有三个参数：
（1）第一个是要排序的数组的起始地址。
（2）第二个是结束的地址（最后一位要排序的地址的下一地址）
（3）第三个参数是compare函数，即排序的方法，若省略此参数则默认用”<”进行排序
lower_bound()返回一个 iterator,它指向在[first,last)标记的有序序列中可以插入value，而不会破坏容器顺序的第一个位置，而这个位置标记了一个不小于value 的值

#include <iostream>
#include <algorithm> 
using namespace std;
int main(){
    int a[10000];
    int n,q,kase=0,x,i;
    while (cin>>n>>q && n){
        for (i=0;i<n;i++)
            cin>>a[i];
        sort(a,a+n);    //排序 
        printf("CASE# %d:n",++kase);
        while (q--){
            cin>>x;
            /*
            for (i=0;i<n;i++)
                if (a[i]==x){
                    printf("%d found at %dn",x,i+1);
                    break;
                }
            if (i==n)
                printf("%d not foundn",x);
            */
            int p=lower_bound(a,a+n,x)-a;   //在已排序数组a中寻找x 
            if (a[p]==x)
                printf("%d found at %dn",x,p+1);
            else
                printf("%d not foundn",x);
        }
    }
}

(algorithm头文件中的sort可以给任意对象排序，包括内置类型和自定义类型，前提是该类型定义了”<”运算符,或着需传入额外的比较函数。排序之后可以用lower_bound查找大于或等于x的第一个位置。待排序/查找的元素可以放在数组里，也可以放在vector里。前者用sort(a,a+n)的方式调用，后者用sort(v.begin(),v.end())的方式调用。)

例题5-2 木块问题(The Blocks Problem,UVa101)
由于每个木块堆的高度不确定，用vector这一数据结构来存储非常合适。vector是一个不定长数组，可以用clear()清空，resize()改变大小，用push_back()和pop_back()在尾部添加和删除元素，用empty()测试是否为空。vector之间可以直接赋值或者作为函数的返回值，像是“一等公民”一样。此题代码是vector这一数据结构的典型应用。另外此题还包含着处理输入指令的技巧，即提取出指令之间的共同点，编写函数以减少重复代码。

#include <iostream>
#include <vector>
#include <string>
using namespace std;

vector<int> pile[30];   //每个pile[i]是一个vector 
int n;

//找木块a所在的pile和height,以引用的形式返回调用者 
void find_block(int a,int& p,int&h){
    for (p=0;p<n;p++)
        for (h=0;h<pile[p].size();h++)
            if (pile[p][h]==a)
                return;
}

//把第p堆高度为h的木块上方的所有木块移回原位 
void clear_above(int p,int h){
    for (int i=h+1;i<pile[p].size();i++){
        int m=pile[p][i];
        pile[m].push_back(m);   //把木块放回原位 
    }
    pile[p].resize(h+1);    //pile[p]中只保留0-h的元素 
}

//把第pa堆高度为h及其上方的木块整体移动到pb堆的顶部 
void pile_onto(int pa,int pb,int h){
    for (int i=h;i<pile[pa].size();i++)
        pile[pb].push_back(pile[pa][i]);
    pile[pa].resize(h); 
}

int main(){
    string s1,s2;
    int a,b;
    scanf("%d",&n);
    for (int i=0;i<n;i++)
        pile[i].push_back(i);
    while (cin>>s1 && s1!="quit" && cin>>a>>s2>>b){
        int pa,pb,ha,hb;
        find_block(a,pa,ha);
        find_block(b,pb,hb);
        if (pa==pb)
            continue;
        if (s1=="move")
            clear_above(pa,ha);
        if (s2=="onto")
            clear_above(pb,hb);
        pile_onto(pa,pb,ha); 
    }
    for (int i=0;i<n;i++){
        printf("%d:",i);
        if (!pile[i].empty())
            for (int h=0;h<pile[i].size();h++)
                printf(" %d",pile[i][h]);
        printf("n");
    }
    return 0;
}

例题5-3 安迪的第一本字典(Andy’s First Dictionary,UVa10815)
此题是set集合的典型应用实例。set容器中每个元素只能出现一次且是有序的，不支持下标访问元素。自定义类型也可以构造set，但同样需定义小于运算符。

#include <iostream>
#include <string>
#include <set>
#include <sstream>
using namespace std;

set<string> dict;   //string集合 

int main(){
    string s,buf;
    while (cin>>s){
        for (int i=0;i<s.length();i++)
            if (isalpha(s[i]))
                s[i]=tolower(s[i]);
            else
                s[i]=' ';
        stringstream ss(s);
        while (ss>>buf)
            dict.insert(buf);
    }
    for (set<string>::iterator it=dict.begin();it!=dict.end();it++)
        cout<<*it<<endl;
    return 0;
}

此题中还使用到了迭代器，这里简要摘录一些有关迭代器的概念和用法

容器中都拥有成员begin和end，其中begin成员复制返回指向第一个元素(或第一个字符)的迭代器，而end成员返回指向容器（或string对象）尾元素的下一个位置的迭代器

例题5-4 反片语 (Ananagrams,UVa156)
此题是map和vector的综合应用。解题关键在于先把每个单词“标准化”，即全部转化为小写字母并排序后，在放到map中统计已标准化单词的出现次数。map是从键到值的映射，重载了[]运算符，具体介绍见下图：

set和map都支持insert,find,count和remove操作，并且可以按照从小到大的顺序循环遍历其中的元素。map还提供了“[]”运算符，使得map可以像数组一样使用，事实上，map也称为“关联数组”。

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

map<string,int> cnt;    //记录经"标准化"后单词的出现次数
vector<string> words; 

//将单词s进行"标准化" 
string standardize(const string& s){
    string temp=s;
    for (int i=0;i<s.length();i++)
        temp[i]=tolower(temp[i]);
    sort(temp.begin(),temp.end());
    return temp;
}

int main(){
    string s;
    while (cin>>s){
        if (s[0]=='#')
            break;
        words.push_back(s);
        string s1=standardize(s);
        if (cnt.count(s1)==0)
            cnt[s1]=0;
        cnt[s1]++;
    }
    vector<string> ananagrams;
    for (int i=0;i<words.size();i++)
        if (cnt[standardize(words[i])]==1)
            ananagrams.push_back(words[i]);
    sort(ananagrams.begin(),ananagrams.end());
    for (int i=0;i<ananagrams.size();i++)
        cout<<ananagrams[i]<<endl;
    return 0;
}

例题5-5 集合栈计算机(The SetStack Computer,UVa12096)
此题为每个不同的集合映射为一个唯一的ID，将不同集合的集合转化为对应的ID的集合。同时用到了栈这一先进后出的数据结构，通过push(),pop()完成入栈和出栈操作,top()取栈顶元素。

#include <iostream>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
using namespace std;

#define ALL(x)  x.begin(),x.end()
#define INS(x)  inserter(x,x.begin())

typedef set<int> Set;
map<Set,int> IDcache;   //把集合映射成ID
vector<Set> Setcache;   //根据ID取集合 

//查找给定集合的ID,如果找不到,分配一个新ID 
int ID(Set s){
    if (IDcache.count(s))
        return IDcache[s];
    Setcache.push_back(s);  //添加新集合 
    return IDcache[s]=Setcache.size()-1;
}

int main(){
    int t,n;
    cin>>t;
    while (t--){
        cin>>n;
        stack<int> s;
        while (n--){
            string op;
            cin>>op;
            if (op[0]=='P')
                s.push(ID(Set()));
            else if (op[0]=='D')
                s.push(s.top());
            else{
                Set s1=Setcache[s.top()];
                s.pop();
                Set s2=Setcache[s.top()];
                s.pop();
                Set x;
                if (op[0]=='U')
                    set_union (ALL(s1),ALL(s2),INS(x));
                if (op[0]=='I')
                    set_intersection (ALL(s1),ALL(s2),INS(x));
                if (op[0]=='A'){
                    x=s2;
                    x.insert(ID(s1));
                }
                s.push(ID(x));
            }
            cout<<Setcache[s.top()].size()<<endl;   
        }
        cout<<"***"<<endl;
    } 
    return 0;
}

例题5-6 团体队列(Team Queue,UVa540)
此题为队列这一先进先出数据结构的应用，通过push()和pop()进行入队和出队的操作，front()取队首元素()。同时再一次应用到了map映射集合，将队员与其对应团队序号相对应。

#include <iostream>
#include <queue>
#include <map>
using namespace std;
int main(){
    int n,t,kase=0,x;
    while (scanf("%d",&t) && t){
        printf("Scenario #%dn",++kase);

        //记录所有团队成员的编号       
        map<int,int> team;  //team[x]表示编号为x的人所在的团队编号
        for (int i=0;i<t;i++){
            scanf("%d",&n);
            while (n--){
                scanf("%d",&x);
                team[x]=i;
            }
        }

        char cmd[10];
        queue<int> q,qteam[1000];   //q是团队队列，qteam是每个团队的队列 

        while (true){
            scanf("%s",cmd);
            if (cmd[0]=='S')
                break;
            if (cmd[0]=='E'){
                scanf("%d",&x);
                int t=team[x];
                if (qteam[t].empty())   //如果队列中没有x所在团队的队员，则让x所在团队入队 
                    q.push(t);
                qteam[t].push(x);
            }
            else if (cmd[0]=='D'){
                int t=q.front();
                printf("%dn",qteam[t].front());
                qteam[t].pop();
                if (qteam[t].empty())   //若此团队所有队员已出队，则整个团队出队 
                    q.pop();
            }
        }
        printf("n");
    }
    return 0;
}

例题5-7 丑数(Ugly Numbers,UVa136)
此题应用了优先队列。由于对于任意的丑数x，2x、3x和5x也都是丑数，故可以用一个优先队列保存所有已生成的丑数，每次取出最小的丑数，生成3个新的丑数。此外用一个集合来判断一个丑数是否已经生成过。
queue头文件中提供了优先队列，用priority_queue定义(后跟的尖括号内定义元素类型)，通过push()和pop()进行入队和出队的操作，top()取队首元素()。自定义类型也可以组成优先队列，但必须为每个元素定义一个优先级。

#include <iostream>
#include <queue>
#include <set>
using namespace std;
int main(){
    const int coeff[3]={2,3,5};
    typedef long long LL;
    priority_queue<LL,vector<LL>,greater<LL> > pq;
    set<LL> s;
    pq.push(1);
    s.insert(1);
    for (int i=1;;i++){
        LL x=pq.top();
        pq.pop();
        if (i==1500){
            printf("The 1500'th ugly number is %d.n",x);
            break;
        }
        for (int j=0;j<3;j++){
            LL m=x*coeff[j];
            if (s.count(m)==0){
                s.insert(m);
                pq.push(m);
            }
        }
    }
    return 0;
}

随机数及STL测试
1.cstlib中的rand()可生成闭区间[0,RAND_MAX]内均匀分布的随机函数，其中RAND_MAX至少为32767。
2.在精度要求不高的情况下，可以在执行rand()之后先除以RAND_MAX,得到[0,1]之间的随机实数，扩大n倍后四舍五入，得到[0,n]之间的均匀整数。
3.可以用cstdlib中的srand函数初始化随机数种子。如果需要程序每次执行时使用一个不同的种子，可以用ctime中的time(NULL)为参数调用srand。一般来说，只在程序执行的开头调用一次srand。
4.把vector作为参数或者返回值时，应尽量改成用引用方式传递参数，以避免不必要的值被复制。
5.测试时往往使用assert。其用法时”assert(表达式)”，当表达式为假时强行终止程序，并给出错误提示。
6.vector,set,map都很快(并不是所有操作)，其中vector的速度接近数组(但仍有差距)，而set和map的速度也远远超过了”用一个vector保存所有值，然后逐个元素进行查找”时的速度。set和map每次插入、查找、删除的时间和元素个数的对数呈线性关系。尽管如此，在一些对时间要求非常高的题目中，STL有时会成为性能瓶颈。
下面是利用随机数测试sort函数的例子：

#include <iostream>
#include <algorithm>
#include <ctime>
#include <vector>
#include <cassert>
using namespace std;

void fill_random_int(vector<int> &v,int cnt){
    v.clear();
    for (int i=0;i<cnt;i++)
        v.push_back(rand());
}

void test_sort(vector<int> v){
    sort(v.begin(),v.end());
    for (int i=0;i<v.size()-1;i++)
        assert(v[i]<=v[i+1]);
}

int main(){
    vector<int> v;
    srand(time(NULL));
    fill_random_int(v,1000000);
    test_sort(v);
    return 0;
}

例题5-8 Unix Is 命令(UVa 400)
此题没什么难度，关键在于输出的细节控制处理，书中的处理方式比较巧妙，值得借鉴。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void print(const string s,int len,char extra){
    cout<<s;
    for (int i=0;i<len-s.length();i++)
        cout<<extra;
}

int main(){
    int n;
    while (cin>>n && n){
        string s;
        vector<string> v;
        int maxlen=0;
        for (int i=0;i<n;i++){
            cin>>s;
            v.push_back(s);
            if (s.length()>maxlen)
                maxlen=s.length();
        }
        sort(v.begin(),v.end());
        int col=(60-maxlen)/(maxlen+2)+1;
        int row=(n-1)/col+1;
        //printf("maxlen=%d col=%d row=%dn",maxlen,col,row);
        for (int i=0;i<60;i++)
            cout<<"-";
        cout<<endl;
        for (int r=0;r<row;r++){
            for (int c=0;c<col;c++){
                int index=c*row+r;
                if (index<n)
                    print(v[index],c==col-1?maxlen:maxlen+2,' ');
            }
            cout<<"n";
        }   
    }
}

例题5-9 数据库(Database,UVa1592)
此题若直接写四重循环枚举r1,r2,c1,c2会超时。解决方法是只枚举c1和c2，然后从上到下扫描各行。每次碰到一个新的行r,把c1,c2两列的内容作为一个二元组存到一个map中。如果map中的键值已存在，该二元组映射到的就是所要求的r1,而当前行就是r2。二元组的存储用到了“集合栈计算机”中的技巧，不直接存储字符串，而是给所有字符串分配一个编号，二元组中存放的为字符串对应的编号。

#include <iostream>
#include <vector>
#include <map>
#include <string>
using namespace std;

typedef pair<int,int> PII; //表示(r,c1),(r,c2)中所存字符串对应的id组成的二元组 
int n,m,db[10005][15],cnt;
map<string,int> id; //为每个不同的字符串分配不同的id 

int ID(const string s){
    if (id.count(s)==0)
        id[s]=++cnt;
    return id[s];
}

void find(){
    for (int c1=0;c1<m-1;c1++)
        for (int c2=c1+1;c2<m;c2++){
            map<PII,int> d; //键为PII对，值为行 
            for (int r=0;r<n;r++){
                PII p=make_pair(db[r][c1],db[r][c2]);
                if (d.count(p)) {
                    printf("NOn");
                    printf("%d %dn",d[p]+1,r+1);
                    printf("%d %dn",c1+1,c2+1);
                    return;
                }
                d[p]=r;
            } 
        } 
    printf("YESn"); 
}

int main(){
    //freopen("D:\input.txt","r",stdin);
    //freopen("D:\output.txt","w",stdout);
    while (cin>>n>>m){
        getchar();
        id.clear();
        for (int r=0;r<n;r++){
            string s;
            getline(cin,s);
            int lastpos=-1;
            for (int c=0;c<m;c++){
                int p=s.find(',',lastpos+1);
                if (p==string::npos)
                    p=s.length();
                db[r][c]=ID(s.substr(lastpos+1,p-1-lastpos));
                lastpos=p;
            }

        }
        find();
    }
    return 0;
}

最后

以上就是典雅汽车为你收集整理的算法竞赛入门经典（第2版）笔记--第5章的全部内容，希望文章能够帮你解决算法竞赛入门经典（第2版）笔记--第5章所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。