一、数组
#include <iostream>
#include <algorithm>
#include <cstring>
void array_study(void)
{
    static int cnt;   //static静态变量修饰符，静态变量相当于只能在该函数中使用的全局变量，
    //自动初始化为0，即在调用该函数时，只有第一次调用才会初始化，之后的调用都会直接跳过初始化这一步
    int a[10],b[10];    //局部数组最大长度大概为510000;
    //全局数组最大长度大概为490000000即4*(10^8)，二维数组为22000*22000
    memset(a,-1,sizeof(a)); //memset按字节初始化，1位8个字节，int为32位，此为将值全赋值为-1
    memset(a,0,sizeof(a));  //将a全赋值为0，初始化
    memcpy(b,a,sizeof(a));  //数组拷贝函数
    //cout<<(char)98<<endl; //b
    //字符串为字符数组后面加上'\0'
    char arr[10]="Hello";   //用字符串初始化字符数组
    //空：0,\0,null,NULL,false
    cout<<arr+1<<endl;  //数组首地址改为arr+1,即输出一个数组，输入同理
    cout<<*(arr+1)<<endl;   //输出一个值
    int ar[10]={1,2,3,4,5};//将前k个数放到最后面
    reverse(ar,ar+5);//reverse翻转函数，参数为起点，终点，左闭右开
    reverse(ar,ar+2);
    reverse(ar+2,ar+5);//45123
    puts("a");  //puts自动换行
    char s[100]="comic";
    cout<<sizeof(s)<<endl;
    //scanf("%s",s);//遇到空格，回车等结束读取，或用cin
    //fgets(s,sizeof(s),stdin);//fgets取代gets，读取一行到字符串中，fgets会把回车读进来
    //cin.getline(s,sizeof(s));//接收一行字符串，需指明接收长度，即第二个参数
    //cout<<s<<endl;
    cout<<strlen(s)<<endl;  //不读取\0，且strlen是遍历了整个字符串（一层循环），
    //因此使用时要提前用变量存下来节约时间
    char c[100]="domic";
    strcpy(c,s);
    cout<<strcmp(s,c)<<endl;  //相等则返回0
    for(int i=0;s[i];++i)   //不用strlen作为结束条件，因为需循环计算，当s[i]为\0时结束
        cout<<s[i]-'a'<<"  ";   //将a,b,c···映射为1,2,3···
    for(int i=0;s[i];++i)
        cout<<i+'a'<<" ";   //将1,2,3···变为a,b,c···
}

二、字符串string
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
void string_study(void)//string,空间可变字符串，不需要设定空间
{
    string s="comic";
    string a=s; //string直接拷贝
    string b(10,'x');   //重复10次x
    //cin>>a;//遇到空格，回车等结束，不能用scanf
    //getline(cin,a);//类似fgets，读取一行
    cout<<a;
    printf("%s\n",a.c_str());   //返回字符数组，不能直接用printf
    puts(b.c_str());
    cout<<a.empty()<<endl;  //string是否为空
    cout<<a.size()<<endl;   //string大小,strlen为O(N),size为O(1)
    cout<<a.length()<<endl; //与size等价
    a+=s;   //string 拼接
    cout<<(a==s)<<endl; //==,<,<=,>,>=,!=
    string s1="Hello",s2="world";
    string st=s1+','+s2+'!';    //在相加时，参与对象都会被转换成string类型
    cout<<st<<endl; //string相加时，+两边至少有一个值需要为string型，且为从左至右相加
    for(char c:st){
        c=c+1;
        cout<<c<<' ';//c的改变不会使得st改变
    }
    cout<<endl;//c++范围遍历，格式为：单个元素数据类型 c:string名，顺次遍历
    for(char &c:st){
        c=c+1;  //加上&,使得当c的值变化时，st的值也随之改变
    }
    for(auto &c:st){    //auto自动类型推导，让编译器自己去猜，猜不出来会报错
        c--;
    }
    cout<<st<<endl;
    for(auto &c:st)
        c=(c-'a'+1)+'a';    //处理后c仍为char类型
    cout<<st<<endl;
    st.pop_back();  //删除string中最后一个元素
    cout<<st.substr(0,3)<<endl;   //截取部分字符串,从0开始截取长度为3的字符串,若无长度则默认截取到结尾
    st.assign("ABC");   //将字符串的内容修改为ABC,还可以设置修改范围
    st.swap(a); //交换字符串st与a
    a.push_back('a');   //在末尾添加一个字符
    a.append("DEF");    //在末尾添加一个字符串
    a.insert(0,"z");    //在位置为0处添加字符串
    reverse(a.begin(),a.end());     //借助algorithm中的reverse实现string的逆序
    a.replace(0,3,"abc");
    a.erase(6);     //删除6后面的所有值
    //a.clear();  //删除a中所有值
    cout<<a<<endl;
    cout<<a.find('a')<<endl;    //成功查找则返回位置，失败返回-1
    cout<<a.find("abc")<<endl;
    char * str;
    a.copy(str,3,0);    //拷贝到字符数组str中
    cout<<str<<endl;
    cout<<a.compare("xx")<<endl;       //字符串比较，相等返回0，小于返回-1，大于返回1
    cout<<a.back()<<endl;   //字符串最后一个元素
    cout<<a.front()<<endl;  //字符串第一个元素
    string x="1223";
    cout<<stoi(x);  //stoi将string转化为整数
    cout<<atoi(x.c_str());  //atoi将字符数组转化为整数
}

三、结构体，输入输出，time，goto，浮点数比较
编程题里1s内大概是运行进行1e7~1e8数量级的运算，超过的话就会TLE了
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <ctime>
const double eps=1e-6;
int z[100000];//全局数组默认都初始化为0，全局变量会放到堆空间，没有空间限制（有内存限制）
//main中有空间限制(栈)
struct stu{
    string name;
    int score,height;
    stu(){}
    stu(string n,int s,int h):name(n),score(s),height(h){}    //结构体的构造函数
};
void struct_study(void)
{
    struct stu ss = {"zhangsan",18,170};        //两种初始化方法
    //struct stu ss("zhangsan",18,170);
    //class 和 struct 类似，区别是class默认成员变量为私有，struct默认成员变量为公有，
    class中既有函数又有变量，struct中一般只有变量
}

bool decimal_compare(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);    //加速cin,cout读入输出
    char x;
    cin >> x;
    scanf(" %c",&x);    //scanf读入单个字符时，在%c前加个空格，防止回车的影响
    cout << x;
    char op[2];
    scanf("%s",op); //当想读入单个字符时，用字符串读入，这样就不会读入多余的空格和回车
    cout << op[0] << endl;//然后再对单个字符op[0]做处理

    int start_time=clock();
    double a=1.232345;
    double b=a*a;
    b=sqrt(b);
    return (fabs(a-b)<eps);
    cout<<clock()-start_time<<endl;    //计算运行时间，单位为ms

    for(int i = 0; i < 10; ++i)
        for(int j = 0; j < 10; ++j)
            for(int k = 0; k < 10; ++k)
                goto end;   //goto,跳出多重循环时使用，可以跳到指定的位置
    end:;  //直接从循环中跳到end:这里
}

四、vector
#include <iostream>
#include <vector>
struct stu{
    string name;
    int score,height;
    stu(){}
    stu(string n,int s,int h):name(n),score(s),height(h){}    //结构体的构造函数
};
void vector_study(void)
{
    vector<int> arr;    //自动变长是倍增思想
    vector<int> array{1,2,3};   //初始化，若函数返回值为vector,则可return {a,b,c···}
    vector<vector<int>> arra;   //vector二维数组，即{{1,2},{1,3},{3,4,5}···}等
    vector<int> a({11,111,1111});  //vector动态int型可变长数组
    vector<int> b[123]; //vector二维数组，第一维为静态（123），第二维为动态
    vector<string> str;
    vector<bool> boo;   //vector内可以套各种各样的东西，形成如字符串数组，bool数组
    vector<stu> c;  //结构体类型vector
    cout<<a.size();     //vector大小,函数与string的类似
    cout<<a.empty();
    arr.clear();  //清空vector内容
    //迭代器，类似于指针 / 数组下标的概念
    vector<int>::iterator it=a.begin(); //此时it就相当于a(数组名),即a[0]的地址
    *it=3;  //a[0]=3
    for(int i=0;i<a.size();++i)     //iterator第一种迭代方式
        cout<<a[i]<<" ";
    cout<<endl;
    for(vector<int>::iterator it=a.begin();it<a.end();it++)    //第二种迭代的方式
        cout<<*it<<" ";     //begin(),end()左闭右开
    cout<<endl;
    //或用auto
    for(auto i=a.begin();i<a.end();++i)
        cout<<*i<<" ";
    cout<<endl;
    for(auto x:a)      //第三种迭代的方式，即string中的范围遍历
        cout<<x<<" ";
    cout<<endl;
    cout<<a.front()<<endl;  //等价于a.
    // begin()和a[0]
    cout<<a.back()<<endl; //返回最后一个元素，等价于a.end()-1 和 a[a.size()-1]
    a.push_back(5); //在vector最后添加一个元素
    a.pop_back();   //删除最后一个元素，时间复杂度均为O(1)
    cout<<(a==arr)<<endl;     //vector具有比较功能，即<,>,==等，依次比较每一位数大小
    copy(a.begin(),a.end(),arr.begin());    //将a.begin()-a.end()赋值到arr上
    arr = a;    //直接赋值
}

五、栈，双端队列
#include <iostream>
#include <stack>
#include <deque>
void stack_deque_study(void)
{
    stack<int> s;   //栈，先入后出，只能在栈顶（即尾部）出栈入栈
    s.push(1);  //入栈，stack为push，无push_back
    cout<<s.top()<<endl;    //输出栈顶元素
    s.pop();    //弹出栈顶元素

    deque<int> d;//双端队列，可在两端进行高效插入，删除操作的线性连续存储空间
    //但总的来说比stack,queue等要慢一些
    //类似queue与vector的结合体,与queue相比可以进行数组的随机访问
    //与vector相比可以在队头进行O(1)的插入删除操作
    d.push_front(111);    //队头插入
    d.push_back(2222);     //队尾插入
    for(auto i=d.begin();i<d.end();++i)     //支持iterator,begin()->end()
        cout<<*i<<" ";
    cout<<endl;
    for(int i=0;i<d.size();++i)     //数组类型的随机访问，可用d[i]来表示
        cout<<d[i]<<" ";
    cout<<endl;
    cout<<d.front()<<endl;  //返回队头元素
    d.pop_back();       //弹出队尾元素
    cout<<d.back()<<endl;   //返回队尾元素
    d.pop_front();      //弹出队头元素
    d.clear();
}

六、队列，堆
#include <iostream>
#include <queue>
void queue_study(void)
{
    //头文件#include<queue>中包含queue和priority queue(堆)两个容器
    queue<int> a;   //queue，队列，即循环队列，先入先出，即队头弹出，队尾插入
    a.push(1);  //入队，插入到队头，queue为push，无push_back
    a.pop();    //出队，弹出队头元素
    a.front();  //返回队头元素
    a.back();   //返回队尾元素
    //注意点，队列和优先队列无clear(),其他容器都有clear()
    a=queue<int>();     //通过初始化实现队列的清空

    priority_queue<int> b;  //优先队列-堆，默认为大根堆，即插入随意，输出时每次弹出堆中最大的元素
    b.push(1);
    b.top();    //返回最大值
    b.pop();    //出队，弹出根元素，即最大值
    priority_queue<int,vector<int>,greater<int>> c;     //小根堆
    priority_queue<pair<int,int>> q;    //pair，双关键字的二元组
cout << q.top().first << endl;//返回pair第一个元素

    struct sch{
        int a,b;
        bool operator< (const sch& t) const
        //!!!当自写结构体为堆时，若要大根堆，则需在结构体内修改operator后的符号为<即可
        //若要小根堆则修改operator后的符号为>即可
        {
            return a < t.a;
        }
    };//结构体记得加分号
    priority_queue<sch> s;  //自定义结构体作为堆，默认为大根堆，小根堆的话重载比较运算符即可
    s.push({1,2});
    cout << s.top().a;//s.top().a或s.top().b
}

七、集合set,multiset,unordered_set
#include <iostream>
#include <set>
#include <unordered_set>
void set_study(void)
{
    //set特点：有序，无重复！遍历元素时用迭代器实现
    //set相关容器-动态有序无重复元素的集合，有size(),empty(),clear()等函数
    set<int> s;     //不能包含重复元素，实现基础为红黑树中的平衡二叉搜索树
    multiset<int> m;    //可用有重复元素
    s.insert(12);   //插入元素,O(logN)
    auto x=s.find(12); //查找，成功则返回对应元素的迭代器，否则返回s.end()
    cout<<*x<<"***"<<endl;
    if(s.find(12) == s.end())   //判断元素12是否在set-s中存在,O(logN)
        cout<<"无该元素"<<endl;
    set<int>::iterator it=s.begin();    //set存在迭代器，但只能实现++,--操作，迭代器获取为O(1)
    ++it;   //即寻找有序集合中it的下一个元素（后继），O(logN)
    --it;   //即寻找有序集合中it的上一个元素（前驱）
    s.erase(it); //删除迭代器对应的元素，O(logN)
    s.erase(12); //删除集合中所有x,O(k+logN),k为删除元素个数
    s.count(12); //集合中x的个数,set返回1或0,multiset返回个数,其余函数multiset与set的相同,O(k+logN)
    //可用count判断一个元素是否在集合中，find也可
    auto a=s.lower_bound(12);   //查找大于等于x中最小元素的迭代器，二分，O(logN)，使用前应保证序列有序
    auto b=s.upper_bound(12);   //查找大于x中最小元素的迭代器
    unordered_set<int> us;//哈希表,无序不重复元素集合,无lower_bound和upper_bound以及迭代器的++，--
    //其余与set一致，查找，插入等操作均为O(1)，效率较高，但不支持二分
    unordered_multiset<int> um;     //无序可重复元素集合
    //unordered_set和unordered_multiset需要额外头文件#include <unordered_set>

    struct sch{
        int a,b;
        bool operator< (const sch& t) const 
        //当用自己写的结构体为堆时，若要大根堆，则需在结构体内重载<,若要小根堆则重载>
        {
            return a>t.a;
        }
    };
    set<sch> _struct;   //使用自定义结构体要重载‘<’运算符
}

八、键值对map，二进制串，pair
#include <iostream>
#include <map>
#include <unordered_map>
#include <bitset>
void map_study(void)
{//map实现原理，红黑树中的平衡二叉搜索树
    map<int,int> a;     //二元键值对,key和value可以为任意类型
    a[12]=1;    //"[]"为操作符，类似数组操作，返回value为O(logN)
    cout<<a[12]<<endl;
    map<string,vector<int>> b;
    b["xtu"]=vector<int>({1,2,3});
    cout<<b["xtu"][1]<<endl;
    b.insert({"stu",{1,2}});    //插入的是一个pair，即二元组
    cout<<(b.find("stu")==b.end())<<endl;   //find()参数为key，返回value对应的迭代器
    b.erase(it);    //erase删除对象为迭代器或pair
    b.erase({"xtu",1});
    unordered_map<int,int> um;  //不支持二分及迭代器的++,--,其余和map相同(虽然map本来就没什么二分233)
    //查找等操作效率都为O(1),比map快，所以一般不用map，而用unordered_map
    //unordered_map需要额外头文件#include <unordered_map>
    map<string, int> ma;//map的遍历
    for(map<string, int>::iterator it = ma.begin(); it != ma.end(); ++ it) 
        cout << it -> first << " " << it -> second << endl;//it->first/second
    for(map<string, int>::reverse_iterator it = ma.rbegin(); it != ma.rend(); ++ it)
        cout << it -> first << " " << it -> second << endl;//反向迭代器，从大到小输出

    bitset<100> bit;//定义了长度为100的01串,包括size(),empty()等,无clear(),支持所有位运算
    bit[1]=1;   //默认为0
    bit[3]=1;
    bit.set(12);    //将第12位默认设为1
    bit.set(11,0);  //把第11位设为0
    bit.reset(1);   //将第1位默认设为0
    cout<<"*"<<(bit&bit).count()<<endl; //位运算
    cout<<(bit|bit).count()<<"*"<<endl;
    cout<<bit.count()<<endl;    //返回01串中1的个数
    cout << bit.any() << endl;  //是否至少有1个1
    cout << bit.none() << endl; //是否全为0
    cout << bit.flip() << endl; //等价于~
    cout << bit.flip(1) << endl;    //把第一位求反

    pair<int,int> p;//普通二元组,可为任意类型,对pair类型进行排序时先按first进行排序
    //然后再排second，所以把要排序的元素放到first里，不要排序的放到second里
    p={2,3};    //pair赋值
    pair<int,int> q;
    q=make_pair(3,5);   //第二种赋值方法
    cout<<p.first<<" "<<p.second<<endl;     //依次输出二元组中第一个，第二个元素
    if(q > p) cout<<"1"<<endl;    //pair具有比较功能，依次比较pair中两个元素,类似字典序
    pair<int, pair<int,int>> pa;    //实现三元组
}

九、位运算，常用库函数
#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
bool cmp(int a,int b)   //从左至右看排序
{
    return a>b;     //从大到小排
}
struct per{
    int x,y;
    bool operator <(const per & p) const
    {
        return x<p.x;
    }
} p[5];
bool cmp_2(struct per a,struct per b)   //结构体cmp
{
    return a.x>b.y;
}
void func_study(void)
{
    int a=14;
    int k=2;
    cout<<(a>>k&1)<<endl;   //求a转化为二进制后第k位数（从左往右）
    for(int i=1;i<5;++i)
        cout<<(a>>i&1);
    cout<<endl;
    cout<<(~k)<<endl;   //not,取反
    cout<<(a^k)<<endl;  //xor,异或
    lowbit_a = a & (-a);
    //lowbit（n）取出非负整数n在二进制表示下最低位的1，以及它后面的0构成的数值,lowbit=n&(-n)

    vector<int> v({5,4,3,2,1});
    int arr[] = {1,2,3,4,5};
    reverse(v.begin(),v.end());     //翻转vector，起点到终点，左开右闭
    reverse(arr,arr+5);     //翻转数组，起点到终点，左开右闭
    for(auto x:v)
        cout<<x<<" ";
    cout<<endl;
    auto ptr=lower_bound(v.begin(),v.end(),3);  
    //查找，二分查找大于等于3的元素，返回对应迭代器，前提是数组为从小到大排序好的
    cout<<*ptr<<endl;
    auto pt=upper_bound(v.begin(),v.end(),3);   //查找严格大于3的元素，返回对应迭代器
    int l=lower_bound(v.begin(),v.end(),3)-v.begin();   //返回查找到的元素的下标
    cout<<l<<endl;

    vector<int> x({1,1,1,2,2,3,3,4});
    int m=unique(x.begin(),x.end())-x.begin();  
    //unique将排序好的数组进行去重，原理是把不重复的数依次放到前面，最后返回重复的数的第一个位置
    cout<<"m:"<<m<<endl;    //m即为不重复的元素个数，实际上x经过unique后为1,2,3,4,1,1,2,3
    返回位置为第一个1即第4个数的位置
    //数组也是上述类似unique用法
    x.erase(unique(x.begin(),x.end()),x.end());//vector去重一般是先sort,再unique结合erase使用
    for(int i=0;i<m;++i)
        cout<<x[i]<<" ";
    cout<<endl;
    srand(time(0));     //设置随机数种子
    random_shuffle(v.begin(),v.end());  //将数组随机打乱，生成随机数据
    sort(v.begin(),v.end());    //排序,O(nlogn),默认从小到大排序
    sort(v.begin(),v.end(),greater<int>()); //从大到小排序
    sort(v.begin(),v.end(),cmp);    //通过自己定义的cmp函数来规定排序方式
    for(int i=5;i>0;--i){
        p[i].x=i;
        p[i].y=-1;
    }
    //sort(p,p+5,cmp);    //结构体排序第一种方式，用cmp
    sort(p,p+5);    //结构体排序第二种方式，结构体内部重载小于号或大于号
}
int a[10] = {8, 6, 3, 7}, k = 0, n = 4;
nth_element(a, a + k, a + n);//(数组起始地址，要求的第k个元素地址，数组的结束地址)
cout << a[k] << endl;   //返回数组中第k小的元素   

vector<int> a{45, 3, 4, 1};
int k = 0;
nth_element(a.begin(), a.begin() + k, a.end());
cout << a[k];

杂
debug添加变量:数组：*(int(*)[10])(arr)
    vector:比如说有一个长度为3的vector v，如果想要查看v[0]的值，就在添加查看中写 *(&v[0])
    如果想要查看整个数组的值，就可以写*(&v[0])@3，@后面的数字表示想要查看的长度
n进制转10进制求和，数组转
for(int i=0;i<len;++i){
    sum=sum*进制+a[i];
}
用scanf（“”，%s）,gets（），getchar()时，前面加上一个getchar()吸收回车;

全错排公式:d[n]=(n-1)*(d[n-1]+d[n-2])
错排公式:d(n,m)=d(m,m)+c(n,m);

判断两数相等可以用异或，如
if(!(a ^ b))
    printf("a == b");
一个圈有n个数，起始位置为point（0<=point<n），则顺时针移动num个数后的新位置point为
point = (point + num) % n;
逆时针移动num个数后的位置point为
**point** = (point - num % n + n) % n;

开全局数组比较大，最大约等于5*10^8，也就是开不到10^9级别的数组
当遇到这种情况，可以考虑离散化。所以一般全局数组，一维可以开到10^8,二维可以开到10^4.

sstream:作用：从字符串中读取各种信息 #include <sstream>
   string str;
   getline(cin,str);    //读入 "20 xtu 20 3.14"
   stringstream ssin(str);
   int a,b;
   double c;
   string s;
   ssin >> a >> s >> b >> c;
   cout << a <<endl << s << endl << b << endl << c <<endl;
输出：20 xtu 20 3.14