天梯赛赛前总结

某些函数后面有带小括号的注解，小括号中各参数的顺序就是传入的参数的顺序。

stl

• queue
  声明：queue name;（其他容器如无特别标注则声明方式与此相同）

  函数：front,back,empty,size,push,pop,swap(c++11)

  比较运算符：==,<=,>=,<,>,!=:按照字典序比较两个queue(c++20)

• priority_queue
  函数：top,empty,size,push,pop,swap

• stack
  函数：top,empty,size,push,pop,swap(c++11)

  比较运算符：==,<=,>=,<,>,!=:按照字典序比较两个stack(c++20)

• map/unordered_map
  声明：map<first值类型,last值类型> name;

  函数：[], begin,end,rbegin,rend,empty,size,clear,insert,erase,find,lower_bound（返回指向首个不小于给定键的元素的迭代器 ）,upper_bound

  tips：如果map的键值是一个struct，那么需要定义比较(<)。定义方法：bool operator <(const item &a){return x < a.x}(以x升序)，unordered_map则不需要定义比较；一定要使用mp.lower_bound()而不是lower_bound(),直接用lower_bound()时间复杂度是不对的。

• set/multiset
  函数：begin,end,rbegin,rend,empty,size,clear,insert,erase,find,lower_bound,upper_bound

  tips：对于multiset，在erase时，如果只想擦除一个值的一个元素，不能使用erase(x)，一个较好的实现方式是erase(find(x));一定要使用st.lower_bound()而不是lower_bound(),直接用lower_bound()时间复杂度是不对的。

• vector
  函数：begin,end,rbegin,rend,empty,size,clear,insert(在pos前插入x/在pos前插入cnt个x),erase(擦除pos处的元素/擦除[first, last)处的元素),push_back,pop_back,lower_bound,upper_bound

  比较运算符：==,<=,>=,<,>,!=:按照字典序比较两个vector(c++20中移除)

• bitset
  函数：[],count,size,二进制操作,set(pos,val),flip(pos)(翻转指定位)

  声明：bitset<长度> name。

bfs

注意每往队列里扔一个元素就要把vis标记为1，否则时间复杂度可能有问题。

字符串

以 string 为模板。

• size
• insert：(在pos处插入cnt个ch)(在pos处插入s)
• erase：(擦除pos处字符)(擦除从pos处开始的len个字符)
• find：(查找字符串s在pos处之后的首次出现位置)返回值是首个字符的下标,如果没有则返回s.npos
• rfind：(查找字符串s在pos处之后的最后一次出现位置)返回值是首个字符的下标,如果没有则返回s.npos
• substr：(获得从pos处开始的len个字符构成的字符串)
• 比较运算符<,=,<=...：字典序比较
• +=：拼接两个字符串
• getline(cin,ss)：读入带空格的字符串

输入格式

对于scanf，printf：

"%02d"：两位整数（例如13,02,05）。

"%.2lf"：两位double（例如0.13,0.02,0.05）。

杂项

memset赋足够大值用0x3f，0和-1可以直接赋。

关闭输入输出流以加速读写：

std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);

常用算法

Floyd：

for (int k = 1; k <= n; k++) {
        for (int x = 1; x <= n; x++) {
            for (int y = 1; y <= n; y++) {
                f[x][y] = min(f[x][y], f[x][k] + f[k][y]);
            }
        }
    }

并查集

void find(size_t x) { return pa[x] == x ? x : pa[x] = find(pa[x]); }

dijkstra

struct edge {
  int v, w;
};

struct node {
  int dis, u;

  bool operator>(const node& a) const { return dis > a.dis; }
};

vector<edge> e[maxn];
int dis[maxn], vis[maxn];
priority_queue<node, vector<node>, greater<node> > q;

void dijkstra(int n, int s) {
  memset(dis, 63, sizeof(dis));
  dis[s] = 0;
  q.push({0, s});
  while (!q.empty()) {
    int u = q.top().u;
    q.pop();
    if (vis[u]) continue;
    vis[u] = 1;
    for (auto ed : e[u]) {
      int v = ed.v, w = ed.w;
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        q.push({dis[v], v});
      }
    }
  }
}