Contents

1. c格式输出
   ①%md 右对齐输出。
   ②%0md 右对齐输出，不够前面补0。
   ③%.mf 浮点数保留m位小数。
   

   #include<cstdio>
   int main() {
       int a = 123,b = 1234567;
       double c = 1.234,d = 1.2;
       printf("%5d\n",a);  //  123
       printf("%5d\n",b);  //1234567
       printf("%05d\n",a); //00123
       printf("%05d\n",b); //1234567
       printf("%.1f\n",c); //1.2
       printf("%.1f\n",d); //1.2
       return 0;
   }

2. 要将大数组开在main函数之外（10⁶级别），因为主函数内部申请的局部变量来自系统栈，申请空间较小；函数外部申请的全局变量来自静态存储区，允许申请的空间较大。
   

3. 头文件#include

   isalpha(大小写字母)
   islower（小写字母）
   isupper（大写字母）
   isalnum（大小写字母加数字）
   isblack（space和\t）
   isspace(space,\t,\r,\n)
   isdigit(判断数字)

4. 输出百分号：printf(“%%”);

5. memset(数组名，值，数组大小)，使用前要加上#include<string.h>，初值建议取0或-1。

   #include<cstdio>
   #include<cstring>
   int main() {
       int a[5] = {1,2,3,4,5};
       memset(a,0,sizeof(a));
       //0 0 0 0 0
       for (int i=0;i<5;i++)
           printf("%d ",a[i]);
       printf("\n");
       memset(a,-1,sizeof(a));
       //-1 -1 -1 -1 -1
       for (int i=0;i<5;i++)
           printf("%d ",a[i]);
       return 0;
   }

6. 以数组作为函数参数，一维不需要写长度，二维需要写长度。与其他局部变量不同，传入后对其进行修改等同于对原参数的修改。

7. 递归

   int F(int n) { return n==0 ? 1 : F(n-1)*n; }

8. 指针和数组

   int a[10]={0},b=1;
   int* p1,p2,p3;  //p1为int*型，p2,p3为int型
   int* p1,*p2,*p3;//p1,p2,p3都是int*型
   p1 = a;  //p1指向a[0] 此时 a == &a[0] a+i == &a[i]
   p2 = &b; //p2指向b

9. 浮点数的比较
   浮点数在经过大量运算后，可能会损失精度，需要引入一个极小数eps对结果进行修正。一般，两个浮点数之差的绝对值小于eps，可认为两浮点数相等,否则是不等于关系。一般eps取10^-8。

   const double eps = 1e-8;

10. 日期处理
    计算日期之间的差值是一件繁琐的工作。可以采用手动模拟的方式，直接计算差值。
    

11. 进制转换
    将P进制x转换成Q进制存放到z数组中，分为两步：
    ①将P进制转换成10进制。
    ②将10进制转换成Q进制。
    

int y = 0,weight = 1，num = 0;//weight是权重
while (x != 0){
    y = y + ( x % 10 ) * weight;
    x = x / 10;
    weight = weight * P;
}
do {//用do...while而不用while可以不用将y=0的情形单独拿出来
    z[num++] = y % Q;//z[0]~z[nun-1]是Q进制的低位到高位
    y = y / Q;
}while (y != 0);

11. 选择排序
    

    void selectSort(int A[]){
        for (int i = 0;i < A.length(); i++){
            int min = i;
            for (int j = 0;j < A.length(); j++)
                if (A[j] < A[min]) min = j;
            if (min != i) swap(A[i],A[min]);
        }
    }    

12. 插入排序

    void insertSort(int A[]){
        for (int i = 1; i < A.length(); i++){
            int j = i;
            while (j > 0 && A[j-1] > A[j]){
                swap(A[j-1],A[j])
                j--;
            }
        }
    }

13. 全排列输出1~3

    #include<cstdio>
    int n,P[11],h[11] = {0};
    void generateP(int index){
        if (index == n + 1){
            for (int i = 1;i <= n;i++)
                printf("%d",P[i]);
            printf("\n");
            return;
        }
        for (int x = 1;x <= n; x++){
            if (h[x] == 0){
                P[index] = x;
                h[x] = 1;
                generateP(index + 1);
                h[x] = 0;
            }
        }
    }
    int main(){
        n = 3;
        generateP(1);
        return 0;
    }

14. 最大公约数

    int gcd(int a,int b){ return b == 0 ? a : gcd(b, a % b);}

15. 最小公倍数
    a和b的最大公约数为x，则a和b的最小公倍数为a * b / x;

16. 进行分数运算用到乘法的时候可能会溢出，需要用long long型保存。

17. 素数的判断

    bool isPrime(int n){
        if (n <= 1) return false;
        for (int i=2;i*i<=n;i++)
            if ( n % i == 0 ) return false;
        return true;
    }

18. 质因子分解
    原理：对一个正整数n来说，如果它存在[2,n]范围内的质因子，要么这些质因子全部小于等于sqrt(n)，要么只有一个大于sqrt(n)的质因子，其余质因子全小于n。
    先开个质因子数组fac={2,3,5,7,11,13,17,19,23,29}。基本够了，再多就超int范围了。
    ①枚举1~sqrt(n)范围内的所有质因子p，判断p是否是n的因子。
    ②如果①结束后n大于1，说明有一个大于sqrt(n)的质因子，要将其记录下来。
    最后要注意的是n=1的情况要特殊判断。

    if (n % prime[i] == 0){
        fac[num].x = prime[i];
        fac[num].cnt = 0;
        while (n % prime[i] == 0){
            fac[num].cnt++;
            n /= prime[i];
        }
        num++;
    }
    if (n != 1){
        fac[num].cnt++;
        fac[num++].cnt = 1;
    }

19. !n中有多少个质因子p

    //非递归版
    int cal(int n,int p){
        int ans = 0;
        while (n){
            ans += n / p;
            n /= p;
        }
        return ans;
    }
    //递归版
    int cal(int n,int p){
        if (n < p) return 0;
        return n / p + cal(n / p,p);
    }

20. 计算$C_{n}^{m}$
    1) 原理：$C_{n}^{m}$ = $C_{n-1}^{m}$ + $C_{n-1}^{m-1}$

    long long res[67][67] = {0};
    long long C(long long n,long long m){
        if ( m == 0 || m == n) return 1;
        if (res[n][m] != 0) return res[n][m];
        return res[n][m] = C(n-1, m) + C(n-1, m-1);
    }

    long long C(long long n,long long m){
        long long ans = 1;
        for (long long i = 1; i <= n; i++)
            ans = ans * (n - m + i) / i;
        return ans;
    }

21. 计算$C_{n}^{m}$%p

    int res[1010][1010] = {0};
    int C(int n,int m,int p){
        if ( m == 0 || m == n) return 1;
        if (res[n][m] != 0) return res[n][m];
        return res[n][m] = (C(n-1, m) + C(n-1, m-1)) % p;
    }

22. vector
    vector是动态数组，其长度可以根据需要改变。在STL容器中，只有vector和string才允许使用v.begin()+1这种迭代器加上整数的写法。
    常用函数：
    1) push_back(): 添加元素。
    2) pop_back(): 删除元素。
    3) size(): 求元素个数。
    4) clear(): 清空所有元素。
    5) insert(): 插入元素。
    6) erase(): 删除元素。一般用两种方式: 删除单个和删除区间[a,b)内的元素。

    #include<iostream>
    #include<vector>
    using namespace std;
    void print(vector<int> v){//打印v
        for (int i=0;i<v.size();i++)
            cout << v[i] << " ";
        cout << endl;
    }
    int main(){
        vector<int> v;
        //v2申请n个空间，并将其全部初始化为1
        vector<int> v2(n,1);
        //初始化二维vector,最后一个空间是b[m-1][n-1]
        vector<vector<int> > b(m, vector<int>(n));
        //push_back添加元素
        for (int i=0;i<5;i++)
            v.push_back(i);
        print(v);				 //0 1 2 3 4 
        //pop_back删除末尾元素
        v.pop_back();
        print(v);				 //0 1 2 3
        //size和clear求元素个数以及清空元素
        cout << v.size() << endl; //4
        v.clear();
        cout << v.size() << endl; //0
        //v被清空，再将元素添加进去
        for (int i=0;i<5;i++)
            v.push_back(i);
        print(v);				//0 1 2 3 4
        //insert插入元素
        v.insert(v.begin()+2,10);
        print(v);				//0 1 10 2 3 4
        //erase的两种方式
        v.erase(v.begin()+1);	 
        print(v);				//0 10 2 3 4
        v.erase(v.begin(),v.begin()+2);
        print(v);				//2 3 4
        return 0;
    }

23. set
    set翻译为集合，是一个内部自动有序且不含重复元素的容器。set中的值默认升序排列，只能通过迭代器访问。常用函数如下:
    1) insert(): 插入元素。
    2) find(): 查找元素，结果返回迭代器。
    3) erase(): 删除某一元素或者删除某一区间元素。
    4) size(): 求容器内元素个数。
    5) clear(): 清空所有元素。

    #include<iostream>
    #include<set>
    using namespace std;
    void print(set<int> s){
        for (set<int>::iterator it=s.begin();it!=s.end();it++)
            cout << *it << " ";
        cout << endl;
    }
    int main(){
        set<int> s;
        set<int>::iterator it;
        for (int i=0;i<5;i++)
            s.insert(i);
        print(s);       //0 1 2 3 4
        //insert
        s.insert(3);    //尝试将3插入set中，但是set中已经有3
        print(s);       //0 1 2 3 4
        //find
        it = s.find(3);
        cout << *it << endl; //3
        //erase
        s.erase(s.find(2));
        print(s);       //0 1 3 4
        s.erase(s.find(0),s.find(3));
        print(s);       //3 4
        //size clear
        cout << s.size() << endl;//2
        s.clear();
        cout << s.size() << endl;//0
        return 0;
    }

24. string
    读入和输出字符串只能用cin和cout,如果非要用%s输出，要将其用c_str()转换。访问方式有下标访问和迭代器访问两种方式，一般用下标访问就可以满足要求。
    1) ==、!=、<、<=、>、>=可以按字典序比较大小。
    2) +=: 两个string类型可以直接用+=拼接起来。
    3) length()/size(): 返回string的长度。
    4) insert(): 几种常用插入方法(将s2(或部分)插入s1某处):
    ①s.insert(int pos,string s2): 将s2插入s的pos处。
    ②s.insert(int pos,string s2,int pos2,int n): 将s2从pos开始的n个字符插入到s的pos处。
    ③s.insert(int pos,int count,char c): 将count个字符c插入到s的pos处。
    5) erase(): 删除单个元素和删除区间中的元素。
    ①s.erase(int pos,int n): 从pos下标开始删除n个字符。
    ②s.erase(int pos): 删除pos下标及之后的字符。
    6) replace(): 替代。
    ①s.replace(int pos,int n,string s2): 把s2从pos位开始，长度为n的字符替换为s2。
    7) substr(): 截取元素。
    ①s.substr(int pos,int len): 返回从pos位开始，长度为len的子串。
    8) find(): 查找子串。
    ①s.find(string s2): 当s2是s的子串时，返回其在s中第一次出现的位置；否则返回string::npos
    ①s.find(string s2,int pos): 从第pos位开始匹配s2，返回情况和上面相同。
    9) string::npos: 作为find函数失配时的返回值。
    10) clear(): 清空string中的元素。
    11)append()：在字符串后添加字符

    #include<iostream>
    #include<string>
    using namespace std;
    int main(){
        string s,s2;
        s = "Nice to ";
        s2 = "meet you.";
        //输出字符串的两种方式
        cout << s1 << endl;
        printf("%s",s2.c_str());
        //按字典序比较大小 输出"s < s2"
        if (s >= s2) cout << "s >= s2" << endl;
        else cout << "s < s2" << endl;
        //+=拼接
        s = s + s2;
        cout << s << endl; //Nice to meet you.
        //length()/size()
        cout << s.length() << " " << s.size() << endl;//17 17
        //insert()
        s.insert(0,s2);   //在s[0]处插入s2
        cout << s << endl;//meet you.Nice to meet you.
        s.insert(0,s2,5,4);//在[0]处插入s[5]~s[8]共4个字符
        cout << s << endl;//you.meet you.Nice to meet you.
        s.insert(0,3,'a');//在s[0]处插入3个字符a
        cout << s << endl;//aaayou.meet you.Nice to meet you.
        //erase()
        s.erase(1,4);     //送s[1](包含)开始删除四个字符
        cout << s << endl;//au.meet you.Nice to meet you.
        s.erase(10);      //删除s[10](包含)之后的字符
        cout << s << endl;//au.meet yo
        //replace()
        s.replace(0,3,"Nice to ");
        cout << s << endl;//Nice to meet yo
        //substr()
        s = s.substr(1,8);
        cout << s <<endl;//ice to m
        //find
        cout << s.find("to") << endl;//4
        s += "to";
        cout << s << endl;//ice to mto
        s.append(2,'1');//ice to mto11
        cout << s.find("to",6) << endl;//8
        //string::npos
        //输出NOT FIND
        if (string::npos != s.find("to",10))
            cout << "FIND" << endl;
        else cout << "NOT FIND" << endl;
        s.clear();
        cout << s.size();//0
        return 0;
    }

25. map
    map翻译为映射，可以将任何基本类型映射到任何基本类型。可以通过下标和迭代器访问。其中的内容会根据键从小到大自动排序。常用函数如下:
    1) find(key): 返回键为key的映射的迭代器。
    2) erase(): 删除某一个键值对或一个区间内的键值对。
    ①erase(it)或者erase(key):it为需要删除的元素的迭代器，时间复杂度为O(1)。key为需要删除的映射的键，时间复杂度为O(logN)。
    ②erase(it,it2): 删除迭代器it和迭代器it2之间的所有映射，左闭右开。
    3) size(): 获得map中映射的对数。
    4) clear(): 清空map中的所有元素。

26. queue
    queue翻译为队列，先进先出。常用函数如下:
    1) push(): push(x)将x压入队列。
    2) front()、back() : 分别获取队首元素和队尾元素，在使用前必须判断queue是否为空。
    3) pop(): 令队首元素出列。
    4) empty(): 检测queue是否为空。
    5) size(): 返回queue中元素的个数。

27. priority_queue
    priority_queue翻译为优先队列，其底层使用堆实现的。在优先队列中，队首元素一定是当前队列中优先级最高的那一个，默认数字大（字典序大）优先级大。常用函数:
    1) push(): push(x)将x压入队列。
    2) top(): 获得队首元素（即堆顶元素），在使用前需要判断优先队列是否为空。
    3) pop(): 令队首元素出队。
    4) empty(): 判断是否为空。
    5 size(): 获取优先队列中元素的个数。
    优先队列内元素优先级的设置：
    1) 基本数据类型的优先级设置：

    //数字大（字典序大）的在队首
       priority_queue<int> q;
       priority_queue<int,vector<int>,less<int> > q;
       //数字小（字典序小）的在队首
       priority_queue<int,vector<int>,greater<int> > q;

    2. 结构体排序: 只能重载<。下面定义水果价格高的优先级高，位于队首（和sort相反）。

    struct fruit{
        string name;
        int price;
        friend bool operator < (fruit a,fruit b){
            return a.price < b.price;
        }
    };
    int main(){
        priority_queue<fruit> q;
    }

28. stack
    stack翻译为栈，先进后出。使用top()和pop()前要判断栈是否为空。常用函数为:
    1) push(): 压元素进栈。
    2) top(): 获得栈顶元素。
    3) pop(): 弹出栈顶元素。
    4) empty(): 检测stack是否为空。
    5) size(): 返回stack中元素数量。
    

29. pair
    pair一般作为map的键值对进行插入。用first和second表示键值对。在使用时应该添加头文件#include。由于添加map头文件#include

    #include<map>
    #include<iostream>
    using namespace std;
    int main(){
        map<string,int> m;
        m.insert(make_pair("ASDF",1));
        m.insert(pair<string,int>("HHHH",3));
        /*输出
        ASDF 1
        HHHH 3
        */
        for (auto it=m.begin();it!=m.end();it++)
            cout << it->first << " " << it->second<< endl;
        return 0;
    }

30. 转换

    string s = to_string(123);//int转string

31. 输入流（乙级-1009）

    //本题用栈更方便
    #include<iostream>
    #include<string>
    #include<vector>
    #include<sstream>
    using namespace std;
    int main()
    {
        string temp,in;
        vector<string> word;
        int count=0,i;
        getline(cin,in);
        istringstream ss(in);
        while (ss >> temp)
            word.push_back(temp);
    }

32. 按格式输入输出(乙级1054)
    sscanf() – 从⼀一个字符串串中读进与指定格式相符的数据
    sprintf() – 字符串串格式化命令，主要功能是把格式化的数据写⼊入某个字符串串中

    sscanf(a, "%lf", &temp);//不要漏了&    
    sprintf(b, "%.2f",temp);