ふわわあのへや競プロとか、好きなこと、いろいろ。

C/C++(競プロ) チートシート

文字列

  • 不等号で比較ができる
  • 範囲指定置換はs.replace(start,len,"String");
  • char複数置換はreplace(all(s), 'before', 'after');

STLのリスト

なまえ条件
lower_bound\ge val
upper_bound>> val

となる最初のitrを返す

(lower|upper)_bound(all(a), val);

添字を求めるには:

lower_bound(all(a), val) - a.begin()

経路探索

名前計算量辺の重み備考
幅優先O(E)O(E)11
Bellman FordO(VE)O(VE)実数負ループ検出可
DijkstraO((E+V)logV)O((E+V) \log V)
Warshall–FloydO(V3)O(V^3)実数全組み合わせに対して求められる,負ループ検出可

オーダーを下げたい

  • 二分探索
  • デバッグ出力を消したら通るかもね (cerrでも時間はかかるので注意)
  • 経路探索はアルゴリズムを見直そう
  • めんどくさい実装はだいたいSTLにあるらしい.計算量節約になるかも…?

演算子優先順位

優先順位演算子結合性
1::
2a++ a-- type() type{} a() a[] . ->
3++a --a +a -a ! ~ (type) *a &a sizeof co_await new new[] delete delete[]
4a.b a->b
5a*b a/b a%b
6a+b a-b
7<< >>
8<=>
9< <= > >=
10== !=
11&
12^
13\|
14&&
15\|\|
16a?b:c throw co_yield = += -= *= /= %= <<= >>= &= ^= \|=
17,