@Moritz 2019-03-26T04:27:12.000000Z 字数 6398 阅读 512

第五章 C++与STL入门

aoapc_2nd C++ 所有文稿

5.1 从C到C++

5.1.1 C++版框架

题目输入量大时，不推荐用C++的流输入。不过流可以加速，方法是关闭和stdio同步，即调用ios::sync_with_stdio(false)
```
while (scanf("%d%d",&a,&b)==2) printf("%d\n",a+b);//注意取地址符&和返回值
```
algorithm头文件包含几个常用算法
```
int a,b,c;
cin>>a>>b;
c=min(a,b);
int d[20];
vector<int> e;//初始化略
sort(d,d+12);
sort(e.begin(),e.end());
int p=lower_bound(d,d+12,a)-d;
```
sort可以排序的类型需要定于”小于“运算符

lower_bound函数返回一个迭代器，p的数值是数组d中大于或等于x的一个数的位置与首元素位置的距离，该数（若存在）即为d[p+2]。

5.2 STL初步

5.2.1 排序与检索

例题 5-1 大理石在哪儿

#include <iostream>
#include <algorithm>
#include <stdlib.h>
using namespace std;
const int MAXN=10000;
int main()
{
    int N,Q,x,kase=0,a[MAXN];
    /*scanf()的返回值是成功赋值的变量数量, 发生错误时返回EOF，变量名前加取地址符&*/
    while(scanf("%d%d",&N,&Q)==2&&N){//N=0时停止输入
        printf("CASE# %d:\n",++kase);
        for(int i=0;i<N;i++) scanf("%d",&a[i]);
        sort(a,a+N);//STL排序，参数为指针/迭代器
        while(Q--)
        {
            scanf("%d",&x);
            int p=lower_bound(a,a+N,x)-a;//-a后得到和a地址（下标）相差数
            if(a[p]==x) printf("%d found at %d\n",x,p+1);//题目中数组序号为1~N，所以p+1
            else printf("Not found.\n");
        }
    }
    return 0;
}

5.2.2 不定长数组vector

例题5-2太烦了，写了一半，未完成。 -2019.2.27

5.2.3 集合set

例题 5-3 安迪的第一个字典

#include <iostream>
#include <set>
#include <string.h>
#include <sstream>
using namespace std;
int main()
{
    string s,buf;
    set<string> dict;
    while(cin>>s)
    {
        if (s=="00") break;
        for(int i=0;i<s.length();i++)
        {
            if (isalpha(s[i])) s[i]=tolower(s[i]);//把大写转化成小写
            else s[i]=' ';//非字母的变为空格，字符串流中再读入则会拆分成两个单词
        }
        cout<<s<<endl;
        stringstream ss(s);
        while(ss>>buf) dict.insert(buf);
    }
    /*注意迭代器不能比较，终止条件只能写成不等于尾后迭代器*/
    for(auto it=dict.begin();it!=dict.end();it++)
        cout<<*it<<endl;
    return 0;
}

5.2.4 映射：map

map就是从键key到值value的映射。因为重载了[]运算符，map像是数组的”高级版“。例如可以用一个map<string,int> month_name来表示“月份名字到月份编号”的映射，然后用month_name["July"]=7这样的方式来赋值。

例题 5-3 反片语

#include <iostream>
#include <map>
#include <string>
#include <set>
#include <algorithm>
#include <vector>
using namespace std;
/*用函数实现标准化功能并单向传递值：便于标准化后遍历vector（未标准化的）元素查看其标准化形式（不改变元素的前提下）是否数量多于一，如果不是，则插入set中输出（未标准化的形式）*/
string sta(string s)
{
    for(int i=0;i<s.length();i++)
    {
        if (isalpha(s[i])) s[i]=tolower(s[i]);
    }
    sort(s.begin(),s.end());//必须用迭代器，不能用s[0]和s[s.length()]（Why?）
    return s;
}
int main()
{
    string s;
    vector<string> v;
    set<string> se;
    map<string,int> m;
    while(cin>>s)
    {
        if (s[0]=='#') break;
        v.push_back(s);
        s=sta(s);
        if (!m.count(s)) m[s]=0;//返回map中键值等于key的元素的个数，键值为标准化字符串，值为个数
        m[s]++;
        //cout<<s<<"  "<<m[s]<<endl;
    }
    for(int i=0;i<v.size();i++)
    {
        if (m[sta(v[i])]==1) se.insert(v[i]);
    }
    for(auto it=se.begin();it!=se.end();it++) cout<<*it<<endl;
    return 0;
}

5.2.5 栈、队列与优先队列

例题 5-5 集合栈计算机

暂未完成。 -2019.2.27

注意STL内置集合操作set_union和set_intersection

例题 5-6 团队队列

#include <iostream>
#include <queue>
#include <map>
#include <stdio.h>
using namespace std;
const int maxt=1010;
int main()
{
    int t,number;
    /*记录团队编号*/
    map<int,int> team;
    scanf("%d",&t);
    for(int i=1;i<=t;i++)//第i个团队的成员
    {
        int n,x;
        scanf("%d",&n);//第i个团队有t人
        while(n--)
        {
            scanf("%d",&x);
            team[x]=i;
        }
    }
    /*模拟命令*/
    queue<int> q,q2[maxt];//q为团队队列，q2[i]为团队i内成员队列
    while(1)
    {
        char cmd[10];
        scanf("%s",cmd);//cmd作为数组首元素已经是地址，不用加&
        if (cmd[0]=='S') break;
        else if (cmd[0]=='E')
        {
            int x;
            scanf("%d",&x);
            if(q2[team[x]].empty()) q.push(team[x]);//team[x]为队员x所在的团队名
            q2[team[x]].push(x);
        }
        else if (cmd[0]=='D')
        {
            cout<<q2[q.front()].front()<<endl;//q.front()为团队编号
            q2[q.front()].pop();
            if (q2[q.front()].empty()) q.pop();
        }
    }
    return 0;
}

队列中，用q.push(x)和q.pop()来进行元素的入队和出队操作，q.front()和q.back()取首尾元素，以及q.size()和q.empty()函数。

STL的优先队列也定义在<queue>中，用priority_queue<int> pq来声明，越小的整数优先级越低，只要元素定义了“小于”运算符，就可以使用优先队列。返回优先级最高的元素方法由queue的front()变为top()。越小的整数优先级越大的优先队列可以写成priority_queue<int,vector<int>,greater<int> > qq。

使用自定义方式比较优先级，详见书本P119

生成随机数

核心函数是cstdlib中的rand()，需要随机数的程序在最开始执行一次srand(time(MULL))来初始化随机数种子。

vector、set和map都很快（*注意vector并不是所有操作都很快，push_front()操作会引起所有元素往后移动，实际上是很慢的），其中vector的速度接近数组，set和map的速度远远超过”用一个vector保存所有值，然后逐个元素进行查找“时的速度。

5.3 应用：大整数类

5.3.1 大整数类BigInteger

5.3.2 四则运算

5.3.3 比较运算符

5.4 竞赛题目举例

5.5 习题

5-1 代码对齐

5-2 Ducci序列

根据题目条件“输入保证最多1000步就会变成0或者循环”，思路则可以确定为循环1000次，若不为0，则判断为循环

#include <iostream>
#include <vector>
#include <stdlib.h>
using namespace std;
int main()
{
    int n,x,t=1010;
    bool turn_0=true;
    cin>>n;
    vector<int> v1,v2{0,0,0,0};//注意，vector的下标访问不可以创建元素！！
    for(int i=0;i<n;i++)
    {
        cin>>x;
        v1.push_back(x);
    }
    while(t--)
    {
        turn_0=true;
        for(int i=0;i<n-1;i++)
        {
            v2[i]=abs(v1[i]-v1[i+1]);//注意，vector的下标访问不可以创建元素！！
            if(v2[i]!=0) turn_0=false;
        }
        v2[n-1]=abs(v1[n-1]-v1[0]);
        if(v2[n-1]!=0) turn_0=false;
        if (turn_0) {cout<<"ZERO"<<endl;break;}
        v1=v2;
    }
    if (!turn_0) cout<<"LOOP"<<endl;
    return 0;
}

《习题选解》书上采用set判断重复，重写后代码如下

vector<int> du,zero;
set<vector<int>> dus;
int n,x;cin>>n;
for(int i=0;i<n;i++)
{
    cin>>x;
    du.push_back(x);
    zero.push_back(0);
}
dus.insert(du);
for(int i=0;i<1010;i++)
{
    int t=du[0];//注意用临时变量存储在循环中被改变的du[0]
    for(int j=0;j<n-1;j++) du[j]=abs(du[j]-du[j+1]);
    du[n-1]=abs(du[n-1]-t);
    if (du==zero) break;
    else if (dus.count(du)) break;
    else dus.insert(du);
}
if (du==zero) cout<<"ZERO"<<endl;
else cout<<"LOOP"<<endl;

主要利用vector重载等号运算符==可以直接进行比较，set的count()函数查找重复序列。

5-3 卡片游戏

比较简单，n数值不大，思考有没有更简便的方法可以根据输入n直接算出最后结果。

5-4 交换学生

思路是用map以一个包含两个元素的数组为键值，如果找得到元素位置对调的数组键值，则代表匹配成功。

map<int[2],int> can;
int n;
while (scanf("%d",&n)==1&&n)
{
    can.clear();
    int m=0;
    while (n--)
    {
        int a[2];
        cin>>a[0]>>a[1];
        int b[2]={a[1],a[0]};
        if (can.count(b))
        {
            can[a]=1;
            can[b]=1;
            m--;
        }
        else
        {
            can[a]=0;
            m++;
        }
    }
    bool com=true;
    for(auto &i:can)
        if (i.second==0)
        {com=false;break; }
if (com) cout<<"YES"<<endl;
else cout<<"NO"<<endl；
}

但报错为array used as initializer，不懂，未解决。 -2019.3.1

然后（学会了pair之后）改为运用pair版本

map<pair<int,int>,int> can;
int n;
while (scanf("%d",&n)==1&&n)
{
    can.clear();
    int m=0;
    while (n--)
    {
        int a,b;
        cin>>a>>b;
        if (can.count(make_pair(b,a)))//表示pair的方法，目前只会make_pair
        {
            can[make_pair(b,a)]=1;
            can[make_pair(a,b)]=1;
            m--;
        }
        else
        {
            can[make_pair(a,b)]=0;
            m++;
        }
    }
    bool com=true;
    for(auto &i:can)
    {
        if (i.second==0)
        {
            com=false;
            break;
        }
    }
    if (com) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}

注意pair的运用，用make_pair表示（其他表示法暂时不会）
用范围for语句遍历map时，键值用it.first访问，元素值用it.second访问

5-5 复合词

大脑进入停机预备阶段

思路：如果是复合词的话，排序必然在该单词前半部分对应的单词的后方并且字符串长度更长，在set中查找后半部分的单词即可。

/*未施工完毕的代码*/
#include <iostream>
#include <set>
#include <stdlib.h>
#include <string.h>
#include <iterator>
using namespace std;
int main()
{
    int len=0;
    string s;
    set<string> dict;
    while(cin>>s) dict.insert(s);
    len=(*(dict.begin())).length();
    auto it=dict.begin();
    for(auto i:dict)
    {
        if ((i).length()>len)
        {
            string st;
            for(int c=len;c<(i).length();c++) st+=(i)[c];
        }
        else
        {
            len=(i).length();
            it=i;//错误，迭代器没有=运算符，WHY？
        }
    }
    return 0;
}

以下为习题选解上的答案

set<string> words;
string word,left,right;
while(cin>>word) words.insert(word);
for(const auto& s: words)
{
    for(int j=1;j<s.size();j++)
    {
        left.assign(s,0,j);//string类的assign函数（没想到吧！
        if (words.count(left))
        {
            right.assign(s,j,s.size()-j);
            if (words.count(right)) {cout<<s<<endl;break;}
        }
    }
}

思路主要卡壳与不知道怎么拆分字符串，其实一个简单的assign函数即可。

assign函数：
- str.assign(n,ch)：用n个字符ch为字符串赋值
- str.assign(str,n)：用str的开始n个字符串赋值
- str.assign(str,indec,len)：子串以index索引开始，长度为len

5-6 对称轴

数学题，如果存在对称轴x=m，那么m一定是所有点x坐标的平均值。

其实看漏题目了，题目要求找的对称轴是竖线：)

2019.3.2