number theory and brainteaser and minimax
2021-07-12
Number Theory
// High accuracy
...
reject sampling and reservoir sampling and random
2021-07-11
-
说明 随机数部分，考察的是比如对一个形状进行均匀采样，或者从随机数A生成B。采样其中一种叫做“reject sampling”，直到采到需要的样本才停止，可以计算其期望。
-
Reject Sampling
Read More
line sweeping
2021-07-10
Line Sweep
// 1272. Remove Interval
Read More
geometry
2021-07-09
Geometry
- Knowledge point:
叉乘：cross product，既可以表示面积，也可以用来计算方向。如果为0，就是共线的，如果p1 x p2为正，那么p1在p2顺时针方向，右手定则。对于三点的时候，可以平移点，计算叉乘计算方向；另外叉乘可以用来看左转还是右转，计算p02,...
Read More
bit manipulation
2021-07-08
Bit Manipulation
Read More
divide and conquer
2021-07-07
Divide and Conquer
// Merge sort.
Read More
sort
2021-07-06
// Sort: merge sort & quick sort is more important
// Te...
Read More
binary search
2021-07-05
- Basic template: stt + 1; stt + (fin - stt)/2; get result from stt and fin.
- 理论：二分查找，通过二分查找，trie，KMP，哈希表来进行；遍历排序，heap，quick sort；数组类型的就是前缀后缀，以及单调栈全部过一遍。
Read More