《算法竞赛进阶指南》学习总结 #include<algorithm>

2020-12-13 05:27

阅读：524

标签：运算解释操作 shuffle 算法 style 配套 ever 字典序

今天下午大致学完了进阶指南中algorithm头文件下的内容，在这里进行一个总结。

reverse翻转

顾名思义，reverse进行的操作就是翻转原来的顺序，理解非常简单，故不赘述。

操作样例：

#includeusing namespace std;
vectorint>a;
int b[233];
int main() 
{
    int na,nb;
　　//vector的实现
    scanf("%d",&na);
    for(int i=0;i)
    {
        int x;
        scanf("%d",&x);
        a.push_back(x);
    }
    reverse(a.begin(),a.end());
    for(int i=0;i)
    printf("%d ",a[i]);
    coutendl;
　　//数组下的实现
    scanf("%d",&nb);
    for(int i=1;i)
    scanf("%d",&b[i]);
    reverse(b+1,b+1+nb);
    for(int i=1;i)
    printf("%d ",b[i]);
    return 0;
}

unique去重

unique的含义仍然很好理解ovo,我也不说太多了，函数返回值可以是去重后的元素个数，比如：

int m=unique(a.begin(),a.end())-a.begin();

int n=unique(b+1,b+1+len)-b-1;

操作样例：

#includeusing namespace std;
vectorint>a;
int b[233];
int na,nb;
int main( )
{
    scanf("%d",&na);
    for(int i=0;i)
    {
        int x;
        scanf("%d",&x);
        a.push_back(x);
    }
    int ma=unique(a.begin(),a.end())-a.begin();
    for(int i=0;i)
    printf("%d ",a[i]);
    coutendl;
    scanf("%d",&nb);
    for(int i=1;i)
    scanf("%d",&b[i]);
    int mb=unique(b+1,b+1+nb)-b-1;
    for(int i=1;i)
    printf("%d ",b[i]);
    return 0;
}

random_shuffle随机打乱

用法和reverse相同，我都懒得写代码了...

sort快速排序

想必sort的一般用法大家都很熟悉了，不再赘述，但vector我以前倒没有接触过。

我看网上有很多博客介绍，但似乎都不太清晰，所以自己摸索出了一种比较麻烦占空间但简单易懂的方法，希望dalao指点。

操作实例：

#includeusing namespace std;
struct node
{
    int x,y;
};
node b[233];
vectora;
bool operator const node &a,const node &b)
{
    return a.xb.x;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i)
    {
    scanf("%d%d",&b[i].x,&b[i].y);
    a.push_back(b[i]);        
    }
    sort(a.begin(),a.end());
    for(int i=0;i)
    printf("%d %d\n",a[i].x,a[i].y);
    return 0;
}

permutation全排列

组合数学大家一定多多少少都有所了解，全排列指的就是A(n,n)式的所有排列方法，也就是说五选五。

next_permutation()会取得[first,last)所标示之序列的下一个排列组合;

利用next_permutation的返回值，判断是否全排列结束如果没有下一个排列组合，便返回false;

否则返true; STL提供了两个用来计算排列组合关系的算法; 分别是next_permutation和prev_permutation;

下一个全排列（next_Permutation）前一个全排列（prev_permutation）

简单来说

next_permutation
按照字典序由小到大的全排列

prev_permutation
按照字典序由大到小的全排列

二者返回值为true/false 用来判断是否还有下一个排列全排列的输出正常的for循环即可

注：两者为互逆运算

#includeusing namespace std;
int a[25],b[25];
int main()
{
    int n1,n2;
    cout"对next_permutation的操作\n"; 
    cin>>n1;
    for(int i=1;i)
    cin>>a[i];//输入数据应该是一组数据全排列中字典序不为最大的一类 
    do
    {
        for(int i=1;i)
        cout" ";
        coutendl;
    }while(next_permutation(a+1,a+1+n1));
    coutendl;
    cout"对prev_permutation的操作\n"; 
    cin>>n2;
    for(int i=1;i)
    cin>>b[i];//输入数据应该是一组数据全排列中字典序不为最小的一类 
    do
    {
        for(int i=1;i)
        cout" ";
        coutendl;
    }while(prev_permutation(b+1,b+1+n2));
    return 0;
}

lower_bound与upper_bound

l_b的作用是在一个区间内寻找第一个大于等于x的元素的位置，u_b是查找
第一个大于x的元素的位置，返回值就是其位置。

当然还有其他操作，比如它有一个很重要的作用就是和unique函数配套使用进行离散化，后续我会在STL的总结中具体解释。

#includeusing namespace std;
vectorint>a;
int b[233];
int na,nb,xa,xb;
int main()
{
    scanf("%d%d",&na,&xa);
    for(int i=0;i)
    {
        int x;
        scanf("%d",&x);
        a.push_back(x);
    }
    printf("%d\n",lower_bound(a.begin(),a.end(),xa)-a.begin());
    scanf("%d%d",&nb,&xb);
    for(int i=1;i)
    {
        scanf("%d",&b[i]);
    }
    printf("%d\n",upper_bound(b+1,b+1+nb,xb)-b);
    return 0;
}

我的总结主要以代码为主，algorithm下的函数都简单易懂，没有用太多的文字说明，都是自己手打测试的操作实例，多测试几组数据，自然就明白了。

如果有不对的地方，希望dalao指正。>w

《算法竞赛进阶指南》学习总结 #include

标签：运算解释操作 shuffle 算法 style 配套 ever 字典序

原文地址：https://www.cnblogs.com/valentino/p/11141123.html

上一篇：Windows 应用程序结构

下一篇：LESS-Middleware：Node.js 和 LESS 的完美搭配

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：《算法竞赛进阶指南》学习总结 #include<algorithm>
文章链接：http://soscw.com/essay/31045.html

亲，登录后才可以留言！

《算法竞赛进阶指南》学习总结 #include<algorithm>

评论

热门文章

推荐文章

最新文章

置顶文章

《算法竞赛进阶指南》学习总结 #include&lt;algorithm&gt;

评论

热门文章

推荐文章

最新文章

置顶文章

《算法竞赛进阶指南》学习总结 #include<algorithm>