算法总结（持续更新）

• 在c++当中为了区别和C语言相同的标准库，c++的标准库都用c开头 C语言都用.h结尾

• 优化cin读入速度

std::ios::sync_with_stdio(false);
std::cin.tie(0);

便捷操作

1.循环读入，遇到0停止

#include <iostream>
using namespace std;
int main()
{
    int a,b,c=0;
    while(cin >> a >> b,a || b)
    {
        c++;
    }
    cout << c;
    return 0;
} 

字符使用

• ASCII码

  A~Z	65 ~ 90
  a~z	97~112

  相差32位

常用库

stdio.h

• C语言标准库

bits/stdc++.h

#include <bits/stdc++.h>
using namespace std;

• 专用于蓝桥杯竞赛万能头文件

math.h

• 常用数学函数库

1. int abs(int i) ; 求整型的绝对值
2. double sqrt (double); 开平方
3. double pow(double x,double y); 计算x的y次幂

algorithm

• 算法函数库

1. max(),min(),abs()

   max(x,y)和min(x,y)分别返回x和y中的最大值和最小值，且参数必须是两个。

   abs(x) 返回x的绝对值。x必须为整数，浮点型的绝对值要用math头文件下的fabs

2. swap()

   swap(x,y)用来交换x和y的值

3. __gcd(a,b)

   两个数的最大公约数

4. sort()

   排序默认从小到大,修改cmp的属性来改变排序方式

   sort( a, a+n ,cmp);

   #include 
   #include 
   using namespace std;
   struct num
   {
       int a, b;
   };
   num n[3];
   bool cmp(num aa, num bb)
   {
       if (aa.a != bb.a)
       {
           return aa.a < bb.a;
       }
       return aa.b << bb.b;
   }
   int main()
   {
   
       for (int i = 0; i < 3; i++)
       {
           cin >> n[i].a >> n[i].b;
       }
       sort(n, n + 3,cmp);
       for (int i = 0; i < 3; i++)
       {
           cout << n[i].a << " ";
       }
       cout << endl;
       for (int i = 0; i < 3; i++)
       {
           cout << n[i].b << " ";
       }
       cout << endl;
       return 0;
   }

5. nth_element(arrs.begin(), arrs.begin() + 2, arrs.end());

   把数组第n小的数放在数组的地n个位置，保证左边的数比他小右边的数比他大

6. reverse()

   容器类型的要用begin()和end()来指定反转的区域，数组类型的直接用int类型即可

   reverse(a,a+n);

7. lower_bound( , , )

8. next_permutation全排列把一组数所有可能的排列方式全部列出 （前提是序列的初始状态是有序的）

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int s[] = {1,9,3,4,5};
    int sum = 0;
    sort(s,s+5);
    do{
        cout << s[0] << " " << s[1] << " " << s[2] << " " << s[3] << " " << s[4] << endl;
        sum++;
    }while(next_permutation(s,s+5));
    cout <<  "end:" << s[0] << " " << s[1] << " " << s[2] << " " << s[3] << " " << s[4] << endl;
    cout << "一共有：" << sum << " 种排列方法" << endl; 
    return 0;
} 

ctype.h

• 字符转换

1. tolower() 将大写字母转换为小写字母
2. toupper() 将小写字母转换为大写字母

vector

• 变长数组，倍增的思想

1. ​ size() 返回元素个数
2. ​ empty() 返回是否为空
3. ​ clear() 清空
4. ​ front()/back()
5. ​ push_back()/pop_back()
6. ​ begin()/end()
7. ​ [] 支持数组序
8. ​ a.assign(n,222); 将n个元素赋值给a
9. ​ a.at(i)输出指定位置数据

for (int i = 0; i < a.size(); i++) cout << a.at(i) << " ";

1. ​ 支持比较运算，按字典序

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<int> a(10,-3);
    int i=a.size();
    for(auto x : a) cout << x << ' ';
    cout << endl;
    a.clear();
    if(a.empty()) cout << "YES" << endl;
    else cout << "NO" << endl;



    vector<int> b;
    for(int i =0;i<6;i++) b.push_back(i);
    b.push_back(99); 
    for(auto x : b) cout << x << " ";
    cout << endl;
    b.pop_back();
    for(auto x : b) cout << x << " ";
    cout << endl;
    for (auto i =b.begin(); i != b.end();i++) cout << *i << " ";
    cout << endl;
    cout << endl;

    return 0;
} 

• sort(alls.begin(), alls.end());//排序
  alls.erase(unique(alls), alls.end());//去重

pair<int, int>

• 类似于构造体可以拥有多个属性

1. first, 第一个元素
2. second, 第二个元素
3. 支持比较运算，以first为第一关键字，以second为第二关键字（字典序）

#include <iostream>
//#include <bits/stdc++.h>
#include <vector>
using namespace std;
int main()
{
    //pair<int ,string> p;
    //p = make_pair(10 , "wyc");
    //cout << p.first << " "<< p.second;
    pair <int , int>p;
    int a[50];
    int n,o[50];
    cin >> n;
    for(int i=0;i<n;i++)
        cin >> a[i];
    for(int i=0;i<n;i++)
        if(a[i] > 0) p.first = a[i];
        else if(a[i] < 0) p.second =a[i];
    cout << p.first << endl << p.second << endl;
} 

string

• 字符串

1. ​ szie()/length() 返回字符串长度
2. ​ empty() 是否为空
3. ​ clear() 清空
4. ​ substr(起始下标，(子串长度)) 返回子串
5. ​ c_str() 将string转化成char便于使用printf()输出

#include 
#include 
using namespace std;
int main()
{
    string st1 = "Hello";
    string st2 = " 1123333";
    string st3 = "Hello";
    cout << "字符串长度：" << st1.length() << "/" << st1.size() << endl;
    cout << "插入：wangzun233" << endl;
    st1.insert(5, " wangzun233");//在下标为5的位置插入字符/字符串
    printf("%s\n", st1.c_str());//将string转化成char便于使用printf()输出
    st1.append(st2);
    printf("%s\n", st1.c_str());
    if (st1.empty()) cout << "Yes" << endl;
    else cout << "No" << endl;
    st1.clear();
    printf("%s\n", st1.c_str());
    return 0;
}

cstring

1. ​ memset( )暴力清空、初始化

list

• 链表

1. lt.push_back(i);//在尾部插入元素
2. lt.push_front(6);//在头部插入元素
3. lt.pop_front();//删除头部元素
4. lt.pop_back();//删除尾部元素
5. lt.remove(6);//删除所有指定元素

#include <iostream>
#include <list>
using namespace std;
void print(list<int> lt)
{
    list<int>::iterator it; //声明一个迭代器
    for (it = lt.begin(); it != lt.end(); it++) {
        cout << *it << " ";
    }

}
int main()
{
    list<int> lt;
    for (int i = 0; i < 10; i++)
        lt.push_back(i);//在尾部插入元素
    print(lt);
    cout << endl;
    lt.push_front(6);//在头部插入元素
    lt.push_front(6);
    print(lt);
    cout << endl;
    lt.pop_front();//删除头部元素
    lt.pop_back();//删除尾部元素
    print(lt);
    cout << endl;
    lt.push_front(6);
    lt.push_front(6);
    lt.push_front(6);
    print(lt);
    cout << endl;
    lt.remove(6);//删除所有指定元素
    print(lt);
    cout << endl;
    return 0;
}

queue

• 队列

1. ​ size()
2. ​ empty()
3. ​ push() 向队尾插入一个元素
4. ​ front() 返回队头元素
5. ​ back() 返回队尾元素
6. ​ pop() 弹出队头元素

#include <iostream>
#include <stdio.h>
#include <queue> 
using namespace std;
int main()
{
    queue<int> a;
    for (int i=0;i<10;i++) a.push(i);
    a.push(55);
    cout << a.front() << endl;
    cout << a.back() << endl;
    a.pop();
    cout << a.front() << endl;

    return 0;
}

priority_queue,

• 堆，优先队列，默认是大根堆

1. ​ push() 插入一个元素
2. ​ top() 返回堆顶元素
3. ​ pop() 弹出堆顶元素
4. ​ 定义成小根堆的方式：priority_queue<int, vector, greater> q;

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
int main()
{
    priority_queue<int> a;
    for(int i=0;i<10;i++) a.push(i);//大跟堆 
    cout << a.top() << " ";
    a.pop();
    cout << a.top() << endl;


    priority_queue<int> b;
    for (int i=0;i<10;i++) b.push(-i);//小根堆
    cout << b.top() << " ";
    b.pop();
    cout << b.top() << endl;

    priority_queue<int,vector<int>,greater<int>> c;
    for (int i=0;i<10;i++) c.push(i);//小根堆
    cout << c.top() << " ";
    c.pop();
    cout << c.top();

    return 0;
} c++

stack

• 栈

1. ​ size()
2. ​ empty()
3. ​ push() 向栈顶插入一个元素
4. ​ top() 返回栈顶元素
5. ​ pop() 弹出栈顶元素

#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;
int main()
{
    stack<int> a;
    for (int i=0;i<10;i++) a.push(i);
    cout << a.top() << " " << endl;
    for (auto i =a.top(); i < a.size();i--) cout << i << " ";
    //stack不支持遍历 
    a.pop();
    cout << endl << a.top();
}

deque

• 双端队列,时间复杂度较高

1. ​ size()
2. ​ empty()
3. ​ clear()
4. ​ front()/back()
5. ​ push_back()/pop_back()
6. ​ push_front()/pop_front()
7. ​ begin()/end()
8. ​ []
9. ​ a.at(i)输出指定位置数据

for (int i = 0; i < a.size(); i++) cout << a.at(i) << " ";

set(unordered_set), map, multiset, multimap

• 基于平衡二叉树（红黑树），动态维护有序序列
• 共性

1. ​ size()
2. ​ empty()
3. ​ clear()
4. ​ begin()/end()
5. ​ ++, – 返回前驱和后继，时间复杂度 O(logn)
   ​

set/multiset

1. ​ insert() 插入一个数
2. ​ find() 查找一个数
3. ​ count() 返回某一个数的个数
4. ​ erase()
   1. 输入是一个数x，删除所有x O(k + logn)
   2. 输入一个迭代器，删除这个迭代器
5. ​ lower_bound()/upper_bound()
   1. lower_bound(x) 返回大于等于x的最小的数的迭代器
   2. upper_bound(x) 返回大于x的最小的数的迭代器

map/multimap

1. ​ insert() 插入的数是一个pair
2. ​ erase() 输入的参数是pair或者迭代器
3. ​ find()
4. ​ [] 时间复杂度是 O(logn)
5. ​ lower_bound()/upper_bound()

map/unordered_map

• 类似于字典
• 存储键值对，键不重复，维护键的顺序
• map可以看做一个超级数组，可以把字符串或者其他类型当做数组的下标

1. –operator[]
2. –insert
3. –erase
4. –clear
5. –find
6. –count
7. –lower_bound
8. –upper_bound

#include <iostream>
#include <map>

using namespace std;

int main() {
    map<string, string,greater<string>> m;//默认升序，现在是降序
    m.insert({"2", "zhang"});
    m.insert(make_pair("1", "li"));
    m.insert(make_pair("1", "Xiao"));//插不进去

    cout << m["2"] << endl;
    m["1"] = "Ali";

    for (auto it = m.begin(); it != m.end(); it++) {
        cout << it->first << "" << it->second << endl;
    }

    cout<<"===================="<<(m.find("3")==m.end())<<endl;
    return 0;
}

bitset

• 圧位

1. ​ bitset<10000> s;
2. ​ ~, &, |, ^
3. ​ , <<
4. ​ ==, !=
5. ​ []
6. ​ count() 返回有多少个1
7. ​ any() 判断是否至少有一个1
8. ​ none() 判断是否全为0
9. ​ set() 把所有位置成1
10. ​ set(k, v) 将第k位变成v
11. ​ reset() 把所有位变成0
12. ​ flip() 等价于~
13. ​ flip(k) 把第k位取反