算法拾遗 2018.11.27

剩下的新内容应该不算多了。这里打算尽快把算法拾遗结束,然后开始刷题,还有继续学习新算法。


碎片五 STL相关

STL的容器的说明方式大都相似,通过一些方法来实现相应功能。

栈:

压入:s.push(x);

弹出:s.pop();

取栈顶但不弹出:s.top();

返回栈大小(元素个数):s.size();

判断栈空:s.empty();

队列:

与栈不同的有取队首:q.front()

优先队列:

默认为大根堆,插入和删除的复杂度是O(logn)。取队首:q.top()

变小根堆:priority_queue<int,vector,greater > q;

双端队列:

这个我不怎么用。

入队首 push_front

弹出队首 pop_front

访问队首 front

入队尾 push_back

弹出队尾 pop_back

访问队尾 back

向量

暂时还没想到有更合适的使用方法。想到如果是多组输入而又要对输入数据进行较大程度的预处理的话,vector不失为一个离线存储的好方法。

时间吗……啊……哈哈哈……

一般操作就是push_back,pop_back,或者求个size什么的。

对组

注意是#include <utility> !不是#include <pair>!

它可以作为一个小型结构体来使用,把两个数据打包成一个小复合结构,用.first,.second进行访问。

我感觉挺好用的啊,为啥总有人不喜欢用这个呢。。。

集合与映射

需要#include ,和数学上定义的集合相似,内部不可以有相同的元素。它和map很像,但是又和map稍有不同。set和map不同的原因是它们的迭代器不相同。map使用pair这种配对的数据,并根据pair中第一个元素的值进行排序,而set的iterator并不具备天生的pair类型的元素,直接根据其中的元素进行排序。

简单说来,map要同时存储两个数据,但是set一个就可以。

向map里面插入数据的方法有两种。其中最常用的仍然是认为它是一个数组,用数组下标进行存取。数组下标的类型就是map定义里的第一个类型,其值对应第二个类型。除此之外,还可以使用insert方法进行插入。但是要注意一下名称空间的问题。。

mapStudent.insert(map<int, string>::value_type (1, "student_one"));

如果感觉比较麻烦,也可以用insert插入一个pair代替。

mapStudent.insert(pair<int, string>(1, "student_one"));

(但不管怎样还是第一种比较好用,我个人建议用第一种,如果你需要在人前装逼的话可以用第二个,但是小心翻车

我其实想重点说的是遍历。学迭代器一个很重要的用途就是用来遍历像map,set这种关联容器,因为它们的下标有可能是不连续的。这种时候使用for循环下标的方法可能就会不适用,迭代器就在这里派上用场了。

(以前向迭代器为例)

map<int, string>::iterator iter;
    for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
        cout << iter->first << " " << iter-> second << endl;

行吧这个算法拾遗就到这了QAQ今天肝了一天的STL的ppt,这一部分自己也能复习个差不多了。。。。。

碎片六 搜索

大概的看下框架。

void dfs(int dep){
    if (dep==n+1){
        //执行输出操作
        return; 
    } 
    //可以在这里加一些特殊边界什么的,最后直接return就好 
    for 枚举每个可能的位置或者决策或者方案{ 
        //可以在这里加一些剪枝什么的 

        if (这个方案合法){
            打标记
            dfs(dep+1); 
            删除标记//这个时候已经回溯了 
        } 

    }
}


void bfs(int s){
    queue<int> q;
    q.push(s);
    vis[s] = true;
    while (!q.empty()){
        int u = q.front();
        q.pop();
        for (遍历所有与u相邻的节点){
            if (当前找到的扩展节点为解){
                执行输出操作 
            } 

            if (!vis[u]){
                q.push(u);
                vis[u] = true;
            }
        }
    }
    return ;
}

感觉挺纠结的。。我是应该继续复习NOIP算法还是应该接着向下学……


-------------本文结束,感谢您的阅读转载请注明原作者及出处-------------

知识无价,码字不易。对您有用,敬请打赏。金额随意,感谢关心。