0%

铺设道路

原题

利用差分数组解决

直接画图就可以发现,连续的,一个层次的道路可以同时解决,不需要额外成本.直接求出所有”层次”的第一个位置即可,即为差分中正的项.

阅读全文 »

dijkstra

一种单源最短路算法,是一种贪心算法,yj一般使用堆优化

不用堆优化是$O(n^2)$,堆优化后是$O((m+n)logn)$

阅读全文 »

Nim游戏

$n$堆石子,每堆$a_i$个,两个玩家轮流取走任意一堆中的任意多个石子,不可不取,取走最后一个物品的人获胜

阅读全文 »

递归与递推

“一个实际问题的遍历,就是对其状态空间的划分,提取,抽象和归纳,实现对状态空间的遍历,并提升效率”

阅读全文 »

Dinic

  • 在残量网络上BFS建立分层图
  • 在分层图上DFS求增广路
    阅读全文 »

基本公式

正弦定理

$a/sinA=b/sinB=c/sinC=2R$

其中R为三角形的外接圆半径

余弦定理

$a^2=b^2+c^2-2bc *cosA$

阅读全文 »

最小生成树

即无向图的最小权值生成树,有kruskal和prim两种算法

prim主要用于边稠密图,尤其是完全图

kruskal适用于稀疏图

阅读全文 »