算法竞赛集训笔记（一）stl

算法竞赛集训笔记（一） c++stl

基础内容，从hello world谈起

#include <iostream>
using namespace std;
int main()
{
    cout<<"hello world!"<<endl;
    return 0;
}

c语言的头文件在c++全部可以使用，但是要把.h后缀去掉，在前面加上c

#include<manth.h>
#include<cmath>

c++中，所有标准库前面的东西都要加std::,为此我们写下using namespace std，但是起名时容易和库函数冲突，比如（prev,next,sort,count不可以再用了），避免冲突，改写一下常见变量名

count ->cnt
next  ->nxt
prev  ->prv

另外，将endl替换为”“,最后换行效果是一样的，但是endl可以清空缓存区，使用c++写代码尽量使用endl即可

c++中一些新的数据类型 bool string 这些是包含在中的

bool flag1=true;
bool flag2=1;
cout<<flag;    // 1

char* str="hello";
string str="hello"
cout<<str;   //hello

c++输入

cin>>number //scanf("%d",&number)
cin>>str    //scanf("%s",str)
cin.getline(str,1000) 
//scanf("%s",str) 这里的str必须用 
//char str[100]声明，
//而不可以 string str或者char*str
getline(cin,str) //这里的str则必须是string类型的

cin判断EOF

while(cin>>a)
{
    //代码主题
}

与c语言比较，cin比sacnf慢不少，而且输入小数用printf更方便。总体来说，用printf和scanf在速度上更有保证，有效避免TLE。

c++语法特性

动态开辟内存

int* number =new int;
int* arr=new int[100];
int *carr=(int*)malloc(100*sizeof(int));

引用

理解为没有*的指针,用于简化代码，避免了解引用的过程。

void swap(int& a,int& b)
{
    int c=a;
    a=b;
    b=c;
}

函数重载

c++中。函数是以函数名＋参数列表来区分的，两个函数可以名字相同，但是参数列表和返回值不同，函数部分参数可以省略，没有提供参数时用缺省值代替

int add(int a,int b)
{
    return a+b;
}
int add(int a)
{
    return a;
}
int minus(int a,int b=0)
{
    return a-b;
}
int main()
{
    add(0);
    add(0,0);
    minus(0)  //默认b=0;

}

算法竞赛中常用默认参数这一特性

struct特性(项目用)

构造函数，初始化函数。

c++标准库（重点）

今日重点

<vector> <string> <algorithm>

以后还会见到

<queue> <stack> <set> <map>
<bitset> <functional> <complex>

c标准库常用函数回顾

<cstring>

strlen(str)//字符串长度
strcmp (str1,str2) //字符串比较
strcpy (str1,str2) //字符串拷贝str2 到str1中
memset(a,0,sizeof(a)) //暴力清空

<cstdlib.h>

qsort() //快排
rand()//随机数
malloc() free() //动态内存分配

<ctime>

time(0) 1970到现在的秒数
clock() 程旭启动到目前的毫米数

vector

#include <iostream>
#include <vector>
using namespace std
int main()
{
    vector<int> arr[100];
    vector<int> list;
    for(int i=0;i<100;i++)
    {
        scanf("%d",&arr[i]);
        cout<<arr[i]<<endl;
    }
    for (int i=0;i<100;i++)
    {
        int a=0;
        cin>> a;
        list.push_back(a);
        printf("%d",list[i]);
    }
}

我们一般把vector当做链表看待使用，也就是第二种方式，这可以方便的处理不定长数组。 STL中的指针被称为迭代器

vector<int> arr1(100);
int arr2[100];
vector<int>::iterator p1;
int *p2;

常见操作

list.size();//数组元素个数   O(1)
list.clear();//一键清空数组 O(n)
list.empty();// 数组是否为空 O(1)
list.begin()； //首元素迭代器
list.end()；//最后一个元素的下一个元素的迭代器（此元素在数组中不存在）
list.erase(p1) //删除某个迭代器所在位置的元素 O(n) 这和实际的链表有区别，链表应该是O(1)
list.push_back(1)  //在数组最后添加元素  O(1);
list.pop_back(1) //删除数组最后一个元素  O(1);

### string

字符串string可以看成一个特殊的vector

string str="hello";
str.size();   //O（n） 但是vector O(1)
str.insert(1,"aaa"); //下标为1处插入一个字符或字符串
// 1也可以更换为某一个迭代器
str.c_str() //返回一个c语言字符串 用于printf()
str.append(str2); //str2拼接到str后面
str ==str2;
str+=str2;
str+='a';   //拼接

algorithm算法函数

sort快排

int arr[] {2,3,1,5,4};
int n=5;
sort(arr,arr+5);//sort(开始元素指针，最后一个元素的下一个元素的指针) 复杂度O(nlogn),升序排序



//若vector？
vector<int> arr 2,3,1,5,4
sort(arr.begin(),arr.end());

关键的点是必要时要写好比较函数cmp。下面给出一个比较函数坐标的例子

struct Point
{
    int x,y;
}
Point points[1110];
bool cmp(Point a,Point b)
{
    if(a.x!=b.x)
    {
        return a.x<b.x;
    }
    return a.y<b.y;
}
int main()
{
    sort(points,points+10,cmp);
}

min。max也是函数

nth_element(arr.begin(),arr.begin()+2,arr.end());
//第三号元素站在了应有的位置，左边都是比他小的，右边都是比他大的，左右未必排好序