1. 函数传入数组时，能用引用&就用引用&，因为不用引用传参会复制数组，时间会变长

   • 要去想一想这个数组传入函数后其内部元素会被改变么？/ 改变后对后续有无影响？

2. 习惯定义一个const int N = 1e5 + 7; // 题目的数据范围，顺便const ind MOD; // 取模

   • 一维vector初始化: vector<int> arr(N);
   • 二维vector初始化:vector<vector<int>> arr(N, vector<int>(N));

3. 输入输出: 统一使用std::cin 和std::cout
   output through std::cout is synchronized with stdout, and input with std::cin is synchronized with stdin.

   // 可以用下面两句来解除cin cout对stream的绑定和 iostream的输入输出缓存
   std::ios::sync_with_stdio(false);
   std::cin.tie(nullptr);
   
   // std::cin 
   std::cin >> n >> m;
   
   // std::cout
   std:cout << "YES\n";
   for (int i = 0; i < m; ++i) {
       std::cout << -1 << res[i] << "\n"[i == m - 1];  // 控制缓冲区大小
   }
   
   
   //启用后就不能用scanf()和printf()了

   循环内用scanf()和printf()； 循环外用cin >> 和cout <<

   如果要输入字符串怎么弄?

   • 循环外：推荐 string s，cin >> s

   • 循环内：推荐 char[MAX_N]，然后按%s读入， 注意char数组的以\0结尾的特性，因此预定义长度要比输入的最大长度大1。

     while (m --) {
         char str[max_n];
         scanf("%s", str);
     }

   • 需要读入一行(即把空格也读进来）: getline(cin, s);

4. pair的sort排序会优先排序左端点first，如果左端点一样再按右端点right排序

5. 构造自定义排序的priority_queue、sort、map、set

   • 在自定义结构体内重载operator <（大根堆）， 重载operator >（小根堆）

   • 构造一个cmp函数对象Functor，重载operator()，重载operator()的意义

     // 大根堆 greater
     struct cmp {
         bool operator ()(ListNode* a, ListNode* b) const {
             return a->val < b->val;
         }
     };
     
     // 小根堆 less
     struct cmp {
         bool operator ()(ListNode* a, ListNode* b) const {
             return a->val > b->val;
         }
     };
     
     priority_queue<Node, vector<Node>, cmp> pq;

   • 构造一个lambda表达式

     auto cmp = [](ListNode* a, ListNode* b){
         return a->val > b->val;
     };
     
     // 小根堆
     priority_queue<Node, vector<Node>, decltype(cmp)> pq(cmp);

6. 字典在C++中和python中的定义:

   #include <unordered_map>
   
   using namespace std;
   // C++中用hash map可以实现
   unordered_map<string, int> dic = {{"type", 0}, {"color", 1}, {"name", 2}};

   dic = {"type": 0, "color": 1, "name": 2}

7. next在C++中是关键字，所以一般取nxt表示下一个, 对应pre表示上一个,还有cur当前

8. 求一个vector中最大值最小值的最快方式是用max_element()和min_element()，注意返回的是地址要解引用

   #include <algorithm>
   
   using namespace std;
   
   vector<int> arr;
   
   int mx = *max_element(arr.begin(), arr.end());
   int mn = *min_element(arr.begin(). arr.end());

9. if中的判断简写

   if (j) ⇔ if (j > 0)
   if (!j) ⇔ if (j == 0) ⇔ if (j == false)
   if (~j) ⇔ if (j == -1)
   if (j & 1) ⇔ if (j % 2 == 1) //判断是否是奇数

10. 数学

    #include <cmath>
    // 绝对值
    abs(x)
    // 开方 [向下取整]
    sqrt(1.0 * x)
    // log
    log(2)

11. 操作符可以用op来记录

    while (m --) {
        char op[2];
    	scanf("%s", op); //注意用%s，字符串读入，可以忽略空格
    	if(op[0] == 'I') {
            // 插入操作
            
        } else if (op[0] == 'Q') {
            // 查询操作    }
    }

12. memset初始化数组 (memset是按每个字节来初始化的)

    #include <cstring>
    
    // 0 8位全是0; -1 8位全是1
    memset(arr, 0, sizeof arr)
    memset(arr, -1, sizeof arr)
    // 当以16进制初始化时，要确保其能转为8位2进制
    memset(arr, 0x3f, sizeof arr);

13. 时间复杂度对于一个算法来说，可以决定算法是否会超出时间限制，与题目数据范围结合可以快速确定解决该问题会用到什么样的算法，比如我们拿到一道题看到数据范围是1e5，那么我们可以判定这道题的时间复杂度需要控制在O(n)或者O(nlogn)的级别，因此可以判断出这道题可能是O(n)的DP，可能是双指针或者是二分答案等等

    各种例子

    • 复杂度在${O(1)}$的，基本就是各种数学知识或者脑筋急转弯，n的量级基本不受限制
    • 二分查找等复杂度为${O(logn)}$，n一般在${10^9}$这个量级内
    • 单调栈、单调队列、差分数组、BFS、DFS、贪心、哈希、前缀和、一维动态规划等复杂度为${O(n)}$，n一般可以在${10^6}$这个量级内
    • 排序、（堆）优先队列、BFS、DFS、图、分治、二分查找、字典树、线段树、并查集等复杂度为${O(nlogn)}$，n一般在${10^5}$这个量级内
    • 二维动态规划等复杂度为${O(n^{2})}$，n一般在${10^3}$这个量级内
    • 三维动态规划等复杂度为${O(n^{3})}$，n一般在${10^2}$这个量级内

• 状态压缩等复杂度为$O(2^{n})$，n一般在16左右

14. 5分钟写不出来就直接看题解，但是不要边看边写，看完之后在不借助任何帮助的情况下自己写一遍

15. https://www.acoier.com/tags/

16. kuangbin专题

17. 剑指Offer 33.二叉搜索树的后续遍历序列，这道题，再次印证了二叉搜索树是一种变相的递增序列

18. BFS走二维图

    // 定义方向:上右下左 0 1 0
    vector<int> dx = {0, 1, 0, -1};
    vector<int> dy = {-1, 0, 1, 0};

19. 频繁调用的函数可以设为inline函数， 更新：inline在C++中已经没有内联的含义了

    // ----以下inline关键字均无效
    // 图的存储
    inline void add (int u, int v, int w);
        
    // 手写堆的up和down函数
    inline void up(int u)
    inline void down(int u)

20. 出现段错误Segmentation Fault，可以用删代码法(主要删包含访问数组的循环)排除问题。

21. 做图论问题，一定要看请是有向图还是无向图，无向图一定要把M的范围扩成2倍，不然容易TLE,在图论中，存储也是比较怪的一点，有向图只存一条边，无向图可以看成双向有向图，存两条边。无向图最多存n * (n - - 1)，考虑自环n * n；有向图最多n(n -1) / 2。

    const int N = 1e5 + 7;
    const int M = 2 * 1e5'

22. 清楚有些操作是可以分拆的，如加减乘除；有些操作是不可以分拆的=(如求max，求最大公约,最小公倍数),这时候可以考虑使用线段树优化

    已知了一个序列中的max，你去掉末尾的数，就求不出当前序列的max

23. 到底是leetcode上的动态写法更好还是普通形式的静态写法比较好。还是一般静态，为了leetcode上一些专门的题型而去刷一些动态写法，如链表和二叉搜索树。

24. 右操作数命名为Node& rhs 为right hand size https://leetcode.cn/submissions/detail/385963390/

25. unordered_set和unordered_map不能直接以pair等复杂(自定义)类型作为键名 参考

    // 如需使用，你需要自定义一个hash函数，然后在声明时将其传入
    struct SimplePairHash {
        std::size_t operator()(const std::pair<int, int>& p) const {
            return p.first ^ p.second;
        }
    };
    
    std::unordered_set<std::pair<int, int>, SimplePairHash> S;

    类似的还有n元组tuple

26. 从执行效率上来说，数组要比哈希表快上不少

    虽然时间复杂度一样，但哈希表的更新和查询复杂度为均摊 $O(1)$，而定长数组的的更新和查询复杂度则是严格$O(1)$ 。

27. while(cin >> n, n != 0) 或者while(scanf("%d", &n) != EOF)可以处理没有特判的输入结尾。
    像这种逗号表达式，其返回值是看该行最后一个表达式的值。

28. Yxc时间复杂度分享

    1. $n \leq 30$, 指数级别, dfs $+$ 剪枝, 状态压缩 dp
    2. $n \leq 100=>O\left(n^3\right)$, floyd, $\mathrm{dp}$, 高斯消元
    3. $n \leq 1000=>O\left(n^2\right), O\left(n^2 \log n\right)$, dp, 二分, 朴素版Dijkstra、祈素版Prim、 Bellman-Ford
    4. $n \leq 10000=>O(n * \sqrt{n})$, 块状链表、分块、莫队
    5. $n \leq 100000 \Rightarrow O(n \log n) \Rightarrow>$ 各种sort, 线段树、树状数组、set/map、heap、拓扑 排序、dijkstra+heap、prim+heap、Kruskal、spfa、求凸包、求半平面交、二分、 CDQ分治、整体二分、后缀数组、树链剖分、动态树
    6. $n \leq 1000000=>O(n)$, 以及常数较小的 $O(n \log n)$ 算法 $=>$ 单调队列、 hash、双指针扫描、并查集, $\mathrm{kmp} 、 \mathrm{AC}$ 自动机, 常数比较小的 $O(n \log n)$ 的做法: sort、树状数 组、heap、dijkstra、spfa
    7. $n \leq 10000000=>O(n)$, 双指针扫描、 kmp、AC自动机、线性监素数
    8. $n \leq 10^9 \Rightarrow O(\sqrt{n})$, 判断质数
    9. $n \leq 10^{18} \Rightarrow O(\log n)$, 最大公约数, 快速幂, 数位DP
    10. $n \leq 10^{1000} \Rightarrow O\left((\log n)^2\right)$, 高精度加减乘除
    11. $n \leq 10^{100000}=>O(\log k \times \log \log k), k$ 表示位数, 高精度加减、FFT/NTT

29. 对于题目和一些边界问题，如果0-base的数组不会出现边界问题，就用0-base的，否则用1-base的

30. 概念区分
    子集合：数组中的所有元素可以任意组合后的子集，当然，空集是任意数组的子集。
    子序列：原序列中可以不连续的一段。
    子数组（子串）：原序列中必须连续的一段。
    但是无论是子序列和子数组，他们都可以看作是原数组的一部分，而且不会改变原来数组中元素的相对位置。而子集合是可以改变原来数组中元素的相对位置的

31. 打leetcode周赛时，如果提交后WA了，可以马上把WA的数据赋值到代码框中的注释里去

32. 取余;如果只需判断被除数是否能整除除数(不关心商，只关心mod 是否==0)，可以对被除数取模来缩小这个数的范围（取模后的得到的余数，保留了这个被除数的性质）

    出自周赛经验：https://leetcode.cn/problems/find-the-divisibility-array-of-a-string/

33. acm模式，顺序

    #include <iostream>   // 头文件
    
    using namespace std;
    
    // typedef long long LL; // typedef
    using int64 = long long;
    
    const int N = 1e5 + 7;// const常量
    
    struct Node{          // 结构体 
    	
    }
    					  
    int res;              // 全局变量
    vector<int> arr;
    
    void func () {        // 函数
        ...
        res += 1;
    }
    
    int main() {          // main函数
        
        return 0;
    }

34. 关于空格的问题，个人习惯4字符对齐还是推荐两侧都加空格：

35. DP和记忆话搜索是可以互相推导的，DP尽管记录的是长度，但是可以逆推求最优方案。

36. 除法向上取整m，可以在被除数先加上m - 1

    // 被除数x, 除数m
    int v = x / m            // 向下取整，默认
    int v = (x + m - 1) / m; // 向上取整
    
    #include <math>
    v = floor(v);            // 向下取整
    v = ceil(v)              // 向上取整

37. 树状数组值域很大就离散化，线段树值域很大就动态开点

38. 字符串的分割，按指定字符分割

    vector<string> split(string& s, char delim) {
      	stringstream ss(s);
        string item;
        vector<string> res;
        while (getline(ss, item, delim)) {
            res.emplace_back(item);
        }
        return res;
    }