【算法入门知识】

vector:

• erase(): O(n)复杂度

  string.length()也是O(n)复杂度

queue:

• 无法通过迭代器遍历queue，只能不断pop再push

string:

• length()为O(n)复杂度
• append后字符串。
• erase(pos,size_n)，从pos位置开始删除指定数量的元素，erase(pos)删除pos后的所有元素。要注意的是删除后字符串长度改变，并且下标提前。
• find查找字串，成功返回起始下标，否则返回string::npos。
• push_back(char a)。
• include中有：to_string()函数。
• substr(int off,int len):若pos的值超过了string的大小，则抛出异常，若pos + len 超过了string大小，则只会拷贝到末尾，也可以substr(off)，默认拷贝后面所有字符
• 一般来说用容器存储字符串都是用string类型，而不是char*，因为string默认好了ascii码的排序方法，如果用char*的话要自己重新定义比较函数

lower_bound()

• 用于二分查找。lower_bound()在first和last中的前闭后开区间，进行二分查找。返回从first开始的第一个大于或等于val的元素的地址。如果所有元素都小于val，则返回last的位置。

注意，不是所有容器都可以通过该方法来得到排序的序号。一般只有vector,像set容器，我们需要自己写一个树状数组来实现该功能

priority_queue

• 默认大顶堆：priority_queue a。反之，priority_queue, greater > c，这样就是小顶堆，不能默认声明

map

• 若map已经存在某个关键字时，insert操作是不能再插入数据的，但是用数组方式就不同了，它可以覆盖以前该关键字对应的值。所以推荐使用数字下标方式。
• find返回迭代器指向当前查找元素的位置否则返回map::end()的位置。在map/set创建排序类operator()后加上const。
• 若某一键值已经存在，Insert不会替代而是失效。

multimap

• 和map容器相比，multimap未提供at()成员方法，也没有重载[ ] 运算符。
  • 这意味着，map容器中通过指定键获取指定键值对的方式，将不再适用于multimap容器。
    其实这也很好理解，因为multimap容器中指定的键可能对应多个键值对，而不再是一个。
    另外，由于maltimap容器可存储多个具有相同键的键值对，因此lower_bound()、upper_bound()、equal_range()以及count()方法经常会用到。

find(int pos,int pos+n,int value)

• 对于数组返回的是查找的元素的物理地址，用它来减去第一个地址不就得到了下标，不存在则NULL。对于STL容器返回的是迭代器，不存在则是end。（特例：vector可以以迭代器减begin得到下标）

int index = iterator - begin，目前仅发现适用于vector

cin 和 getline

• ”从流中提取数据时std::cin 函数从终端输入是跳过前导空白符(空格 tab 回车等 不会出现在终端的符号)，即cin从第一个非空白符开始读，直到下一个是空白符或文件结束为止（此时空白符在缓冲区中，可用getchar()吸收）
• getline可以读取空格
• cin.getline(char *p,int size)，p是指针
• getline(cin,string)是处理字符串（string类),在#include空间，注意不是string.h，通常使用这个

atoi

• 头文件stdlib.h，int num = atoi(str.c_str())

通过使用memset可以快速地对高维数组等进行初始化，但是需要注意无法初始化程1之类的数值。

扩：fill和memset函数区别：

DFS经验

• 行是数组第一维，列是第二维，在定义dx、dy时特别要注意。
• visit数组记得给最初进入的dfs点标志。
• 只有遍历完全后才返回false

分离数字技巧：一个数，想从低位得到位数，用取余10。从高位得到位数，用除10。

例如，12345%10 = 5,12345%100 = 45（低位）。12345/10 = 1234,12345/100 = 123（高位）。

关于整除的一个技巧： 假如求一个能被k整除最小值min，可以将min = submin / k * k，此时submin也许有更好的途径去求。要注意的是，一般都是有整数要求，此时是 :
m i n = ⌈ s u b m i n / k ⌉ ∗ k min = lceil submin/k rceil * k min=⌈submin/k⌉∗k

关于打表： 有些题会根据题意推出递归式，我们为提前求出所有索引对应的值以及索引边界，或者找出对应规律，叫打表。

CPP中代替JAVA.split()函数的技巧

• 利用getchar()吸收无效字符。

• 利用字符串getline和stringstream和cin共同达到目的。

  • 例如：

    while (getline(cin, tempLine))
    	{
    		int len = tempLine.length();
    		for (int i = 0; i < len; i++)
    		{
    			if (tempLine[i] == ':')
    				tempLine[i] = ' ';
    		}
    		stringstream s(tempLine);
    		string temp2 = "";
    		s >> temp2; //此时就可以得到被:分割的字符，可以先用vector用循环先存储起来
    	}
    

• 套用现成函数：

  void SplitString(const std::string& s, std::vector& v, const std::string& c)
  {
    std::string::size_type pos1, pos2;
    pos2 = s.find(c);
    pos1 = 0;
    while(std::string::npos != pos2)
    {
      v.push_back(s.substr(pos1, pos2-pos1));
   
      pos1 = pos2 + c.size();
      pos2 = s.find(c, pos1);
    }
    if(pos1 != s.length())
      v.push_back(s.substr(pos1));
  }
  

经验*：scanf和cin同时使用会导致部分编译器下的结果出错。最好同时只用一种。

经验：多项式极有可能会涉及大数，此时使用Java很好。

经验：全局数组能开到4e8 * int，栈能开到518028 * int。c++递归深度最深 20000多次。当超出递归深度时，要么转为非递归循环模式，要么是推出数学表达式使用循环推出。

“<<”：左移运算符，将运算符左边的操作数全部左移指定的位数，移出左边界被屏蔽，右边界用0填充空位，本质上是操作数乘上2ⁿ。例如：1 << n = 2 ⁿ ，n << 1 = 2 * n。

“>>” 大致功能类比左移，需要注意的是填补空位时若原先最高位是1，则填充1，若是0，则填充0。其本质是除上2ⁿ ，在c++中是向下取整。

按位与：&，例如a&b即a和b的二进制形式中每一位进行一一位与比较。

按与或：|

异或：^

非：~（取反）

常见应用："i&1"判断i是否位奇数

基本运算规则：

降幂运算推导：

当
a ⋅ c ≡ b ⋅ c ( m o d    m ) a cdot c equiv b cdot c(mod m) a⋅c≡b⋅c(modm)
求a、b之间的关系：

其中涉及一个知识点：(a-b)被m整除，代表a % m == b % m。

a ≡ b ( m o d    m / g c d ( m , c ) ) a equiv b(mod m/gcd(m,c)) a≡b(modm/gcd(m,c))

快速幂：反复平凡法

合数是指在大于1的整数中除了能被1和本身整除外，还能被其他数（0除外）整除的数，素数（质数）与之相反。

代码：

typedef long long ll;
ll mod_pow(ll x, ll n,ll mod)
{
    ll res = 1;
    while(n > 0)
    {
        if(n&1) res = res * x % mod;
        x = x * x % mod; //将x平方
        n >>= 1; //二进制右移
    }
    return res;
}

单位圆内接正n边形的面积公式

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-AeZUtd1R-1656484666232)(https://www.zhihu.com/equation?tex=n+%2F2+%2A%5Csin%282%5Cpi+%2Fn%29R%5E%7B2%7D+)]

柯西不等式：

c++中自己定义pi ： define pi 3.1415926

精度的控制，参考文章：小数点精度的控制——C++ - 知乎 (zhihu.com)

​ (28条消息) c++ 保留有效数字和小数位_吉大秦少游的博客-CSDN博客_c++ 有效数字

• 仅对数字长度来控制：仅使用setprecision(int num)，要注意头文件是iomanip，当整数部分无法显示完全会变成指数形式，同时会有舍入情况。

• 保留n位小数：结合setiosflags(ios::fixed)和setprecision(int num)

  double a = 3.141564;
  cout << setiosflags(ios::fixed) << setprecision(3) << a;            // a = 3.141