模板库

算法库

reverse 字符串，数组翻转

string s = "12345";
int a[] = {1, 2, 3, 4, 5};
reverse(s.begin(), s.end());
s="54321";
reverse(a, a + 5);
//a{5,4,3,2,1};

rotate 将区间内的元素旋转

vector<int> v{2, 4, 2, 0, 5, 10, 7, 3, 7, 1};
sort 0 1 2 2 3 4 5 7 7 10  
//简单地旋转到左侧 1 2 2 3 4 5 7 7 10 0
rotate(v.begin(), v.begin() + 1, v.end());
//简单地旋转到右侧  0 1 2 2 3 4 5 7 7 10
rotate(v.rbegin(), v.rbegin() + 1, v.rend());

is_sorted( begin(digits), end(digits)) 是否升序

//返回false bool
int digits[] = {3, 1, 4, 1, 5};
is_sorted( begin(digits),  end(digits))

vector<int> v1 {1, 2, 3};
is_sorted(begin(v1),end(v1));

lower_bound 返回指向第一个不小于给定值的元素的迭代器

int a[]={1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6};
vector<int> data = { 1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6 };
int lower = lower_bound(data.begin(), data.end(), 4)-data.begin();
int lower2 = lower_bound(a, a+13, 4)-a;

upper_bound 返回指向第一个大于给定值的元素的迭代器

int a[]={1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6};
vector<int> data = { 1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6 };
int  upper = upper_bound(data.begin(), data.end(), 4)-data.begin();
int  upper2 = upper_bound(a, a+13, 4)-a;

binary_search 判断一个元素是否在区间内

int a[]={1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6};
vector<int> data = { 1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6 };
bool flag = binary_search(a,a+13,1);
bool flag2 = binary_search(data.begin(),data.end(),1);

merge 归并 合并两个已排序的区间

vector<int> v1 = { 1, 1, 2, 3, 3, 3 },v2={ 3, 4, 4, 4, 5, 5, 6};
vector<int> dst;
merge(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(dst));

int a[]={1, 3,5},b[]={2,4,6};
vector<int> v;
merge(a,a+3,b,b+3,back_inserter(v));

set_difference 计算两个集合的差集

vector<int> v1 {1, 2, 5, 5, 5, 9};
vector<int> v2 {2, 5, 7};
vector<int> diff;
set_difference(v1.begin(), v1.end(), v2.begin(), 
               v2.end(), inserter(diff, diff.begin()));

set_intersection 计算两个集合的交集

vector<int> v1{1,2,3,4,5,6,7,8};
vector<int> v2{5,7,9,10};
sort(v1.begin(), v1.end());
sort(v2.begin(), v2.end());
vector<int> v_intersection;
set_intersection(v1.begin(), v1.end(),
                 v2.begin(), v2.end(),back_inserter(v_intersection));

max_element 返回区间内的最大元素

vector<int> v{ 3, 1, -14, 1, 5, 9 };
int a[]={1,2,3,4,5,7};
vector<int>::iterator result;
result = max_element(v.begin(), v.end());
int x=*max_element(a, a+6);

min_element 返回区间内的最小元素

vector<int> v{ 3, 1, -14, 1, 5, 9 };
int a[]={1,2,3,4,5,7};
vector<int>::iterator result;
result = min_element(v.begin(), v.end());
int x=*min_element(a, a+6);

is_permutation 判断一个序列是否为另一个序列的排列组合

vector<int> v1{1, 2, 3, 4, 5};
vector<int> v2{3, 5, 4, 1, 2};
bool flag=is_permutation(v1.begin(), v1.end(), v2.begin())

next_permutation 按字典顺序产生区间内元素下一个较大的排列组合

string s = "aba";
sort(s.begin(), s.end());
do {
    cout << s << '\n';
} while(next_permutation(s.begin(), s.end()));

prev_permutation 按字典顺序产生区间内元素下一个较小的排列组合

string s = "aba";
sort(s.begin(), s.end(),greater<char>());
do {
    cout << s << '\n';
} while(prev_permutation(s.begin(), s.end()));

数值库

abs labs llabs 计算整数值的绝对值（ |x| ）
fabs 浮点值的绝对值（ |x| ） 
fmod fmodf fmodl 浮点除法运算的余数 
exp expf expl返回 e 的给定次幂（ ex ）
exp2 exp2 fexp2l 返回 2 的给定次幂（ 2x ）
expm1 expm1f expm1l 返回 e 的给定次幂减一（ ex-1 ）
log logf logl 计算自然（底 e ）对数（ ln(x) ）
log10 log10f log10l 计算常用（底 10 ）对数（ log10(x) ）
log2 log2f log2l 给定数的 2 为底的对数（ log2(x) ）
log1p log1pf log1pl 给定数的自然（底 e ）对数加 1 （ ln(1+x) ）
pow powf powl 求某数的给定次幂（ xy ）
sqrt sqrtf sqrtl 计算平方根（ √x ）
cbrt cbrtf cbrtl 计算立方根（ 3√x ）
hypot hypotf hypotl 计算二个给定数平方和的平方根（√x2+y2） 
sin sinf sinl 计算正弦（ sin(x) ）
cos cosf cosl 计算余弦（ cos(x) ）
tan tanf tanl 计算正切（ tan(x) ）
asin asinf asinl 计算弧（反）正弦（ arcsin(x) ）
acos acosf acosl 计算弧（反）余弦（ arccos(x) ）
atan atanf atanl 计算弧（反）正切（ arctan(x) ）
atan2 atan2f atan2l 弧（反）正切，用符号确定象限

string库

#include <string>

    string ss = "about you", s;
    int index, count,n;
    char ch;
    //位置都是对应下标表示
    //首字母
    char begin = ss.front();
    //尾字母
    char end = ss.back();
    cout << begin << " " << end << endl;
    //判空
    ss.empty();
    //返回字符串长度
    ss.size();
    //清空字符串
    ss.clear();
    //插入字符
    //在位置 index 插入 count 个字符 ch 的副本。
    index = 0, count = 3;
    ch = 'x';
    ss.insert(index, count, ch);
    cout << ss << endl;
    //在指定位置插入字符串s
    s = "test";
    ss.insert(1, s);
    cout << ss << endl;
//    在位置 index 插入范围 [s, s+count) 中的字符。范围能含有空字符。
    s = "abc";
    //2代表个数
    count = 2;
    ss.insert(0, s, 1, 2);
    cout << ss << endl;

    //erase
    s = "This is an example";
    cout << s << '\n';
// 擦除 "This "
    s.erase(0, 5);
    cout << s << '\n';
// 擦除 ' '
    s.erase(std::find(s.begin(), s.end(), ' '));
    cout << s << '\n';
// 从 ' ' 到字符串尾裁剪
    s.erase(s.find(' '));
    std::cout << s << '\n';
    // push_back  后附字符到结尾
    s.push_back('a');
    //pop_back 移除末尾字符
    s.pop_back();

/*    str   -   要比较的另一 string
    s   -   指向要比较的字符串的指针
    count1  -   此 string 要比较的字符数
    pos1  -   此 string 中要比较的首字符的位置
    count2  -   给定字符串要比较的字符数
    pos2  -   给定字符串的要比较的首字符位置*/
    int compare( size_type pos1, size_type count1, const basic_string& str,
                size_type pos2, size_type count2 )
    s.compare(0,2,"ss",0,2);
//    int compare( size_type pos1, size_type count1, const CharT* s, size_type count2 )
    s.compare(0,2,"ss",2);
    // find 于字符串中寻找字符
    //rfind 寻找子串的最后一次出现
    //size_type find( const CharT* s, size_type pos, size_type count )
    s = "This is a string";

    // 从 string 开始搜索
    n = s.find("is");

    // 从位置 5 开始搜索
    n = s.find("is", 5);

    // 寻找单个字符
    n = s.find('a');
    if (n == string::npos) {
        std::cout << "not found\n";
    } else {
        //找到那个位置到结束，包括找到那个位置
        std::cout << "found: " << s.substr(n) << '\n';
    }

   /* pos   -   将被替换的子串起始位置
    count   -   将被替换的子串长度
    first, last   -   将被替换的字符范围
    str   -   用于替换的 string
    pos2  -   用于替换的子串起始位置
    count2  -   用于替换的字符数
    cstr  -   指向用于替换的字符串的指针
    ch  -   用于替换的字符值
    first2, last2   -   用于替换的字符范围*/
    string str("The quick brown fox jumps over the lazy dog.");
    str.replace(10, 5, "red");
    str.replace(str.begin(), str.begin() + 3, 1, 'A');

    std::cout << str << '\n';
  /*  pos   -   要包含的首个字符的位置
    count   -   子串的长度*/
    std::string a = "0123456789abcdefghij";

    // count 为 npos ，返回 [pos, size())
    std::string sub1 = a.substr(10);
    std::cout << sub1 << '\n';
    //abcdefghij
    // pos 和 pos+count 都在边界内，返回 [pos, pos+count)
    std::string sub2 = a.substr(5, 3);
    //567
    std::cout << sub2 << '\n';

容器库

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
vector<int> v, v2[5];
vector<pair<int, int> > ans;
map<string, int> m;
multiset<int> mus;
multimap<string, int> mum;
set<int> set;
stack<int> st;
queue<int> qu;
priority_queue<int> pq;
priority_queue<int, vector<int>, greater<int> > q2;
set<int>::iterator it;
set<int>::reverse_iterator rit;


set
唯一键的集合，按照键排序
map
键值对的集合，按照键排序，键是唯一的
multiset
键的集合，按照键排序
multimap
键值对的集合，按照键排序
stack
堆栈适配器（LIFO）
queue
改写容器来提供队列（FIFO数据结构）
priority_queue
改写容器来提供优先级队列

vector
a.assign(b.begin(), b.begin()+3); //b为向量，将b的0~2个元素构成的向量赋给a
a.assign(4,2); //是a只含4个元素，且每个元素为2
front 访问第一个元素
back 访问最后一个元素
迭代器 begin() end()
反向迭代器 rbegin() rend();
empty 检查容器是否为空
size 返回容纳的元素数
max_size 返回可容纳的最大元素数
clear 清除内容
insert 插入元素
erase 擦除元素
push_back 将元素添加到容器末尾
pop_back 移除末元素

map,multimap
迭代器 begin() end()
反向迭代器 rbegin() rend();
empty 检查容器是否为空
size 返回容纳的元素数
max_size 返回可容纳的最大元素数
clear 清除内容
insert 插入元素
erase 擦除元素
count 返回匹配特定键的元素数量
find 寻找带有特定键的元素
lower_bound 返回指向首个不小于给定键的元素的迭代器
upper_bound 返回指向首个大于给定键的元素的迭代器

set,multiset
迭代器 begin() end()
反向迭代器 rbegin() rend();
empty 检查容器是否为空
size 返回容纳的元素数
max_size 返回可容纳的最大元素数
clear 清除内容
insert 插入元素
erase 擦除元素
count 返回匹配特定键的元素数量
find 寻找带有特定键的元素
lower_bound 返回指向首个不小于给定键的元素的迭代器
upper_bound 返回指向首个大于给定键的元素的迭代器

stack
top 访问栈顶元素
empty 检查容器是否为空
size 返回容纳的元素数
push 向栈顶插入元素
pop 删除栈顶的元素

queue
front 访问第一个元素
back 访问最后一个元素
empty 检查容器是否为空
size 返回容纳的元素数
push 向栈顶插入元素
pop 删除栈顶的元素

priority_queue  默认是从大大小，栈顶为最大值
top 访问栈顶元素
empty 检查容器是否为空
size 返回容纳的元素数
push 向栈顶插入元素
pop 删除栈顶的元素

deque
front 访问第一个元素
back 访问最后一个元素
迭代器 begin() end()
反向迭代器 rbegin() rend();
empty 检查容器是否为空
size 返回容纳的元素数
max_size 返回可容纳的最大元素数
clear 清除内容
insert 插入元素
erase 擦除元素
push_back 将元素添加到容器末尾
pop_back 移除末元素
push_front 插入元素到容器起始
pop_front 移除首元素

*it是值
it->ff,it->ss;

几何

n条直线最多分平面问题

题目大致如:n条直线，最多可以把平面分为多少个区域。
  可能你以前就见过这题目，这充其量是一道初中的思考题。
  但一个类型的题目还是从简单的入手，才容易发现规律。
  当有n-1条直线时，平面最多被分成了f（n-1）个区域。
  则第n条直线要是切成的区域数最多，就必须与每条直线相交且不能有同一交点。
  这样就会得到n-1个交点。这些交点将第n条直线分为2条射线和n-2条线断。
  而每条射线和线断将以有的区域一分为二。这样就多出了2+（n-2）个区域。

     故：f(n)=f(n-1)+n

                  =f(n-2)+(n-1)+n

                  ……

                  =f(1)+1+2+……+n

                  =n(n+1)/2+1

折线分平面（hdu2050）

根据直线分平面可知，由交点决定了射线和线段的条数，进而决定了新增的区域数。
  当n-1条折线时，区域数为f（n-1）。为了使增加的区域最多，则折线的两边的线段要和n-1条折线的边，
  即2*（n-1）条线段相交。那么新增的线段数为4*（n-1），射线数为2。
  但要注意的是，折线本身相邻的两线段只能增加一个区域。

   故：f(n)=f(n-1)+4(n-1)+2-1

                  =f(n-1)+4(n-1)+1

                 =f(n-2)+4(n-2)+4(n-1)+2

                 ……

                 =f(1)+4+4*2+……+4(n-1)+(n-1)   

                 =2n^2-n+1

封闭曲线分平面问题

题目大致如设有n条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，
且任何三条封闭曲线不相交于同一点，问这些封闭曲线把平面分割成的区域个数。
    当n-1个圆时，区域数为f(n-1).那么第n个圆就必须与前n-1个圆相交，
  则第n个圆被分为2（n-1）段线段，增加了2（n-1）个区域。
      故
                f(n)=f(n-1)+2(n-1)     

            =f(1)+2+4+……+2(n-1)

            =n^2-n+2

平面分割空间问题（hdu1290）

由二维的分割问题可知，平面分割与线之间的交点有关，即交点决定射线和线段的条数，从而决定新增的区域数。
试想在三维中则是否与平面的交线有关呢？当有n-1个平面时，分割的空间数为f（n-1）。
要有最多的空间数，则第n个平面需与前n-1个平面相交，且不能有共同的交线。
即最多有n-1 条交线。而这n-1条交线把第n个平面最多分割成g（n-1）个区域。
（g（n）为（1）中的直线分平面的个数）此平面将原有的空间一分为二，则最多增加g（n-1）个空间。



    故：f=f(n-1)+g(n-1)  
          g(n)=n(n+1)/2+1

              =f(n-2)+g(n-2)+g(n-1)

              ……

              =f(1)+g(1)+g(2)+……+g(n-1)

              =2+(1*2+2*3+3*4+……+(n-1)n)/2+（n-1）

              =(1+2^2+3^2+4^2+……+n^2-1-2-3-……-n )/2+n+1

              =(n^3+5n)/6+1

用N个三角形最多可以把平面分成几个区域

a[i]=a[i-1]+6*(i-1)