Yuhang's Blog

Category : Mathematics

桥(洛谷P2685)题解

给定一张无向图, 有边权, 可能有重边和自环. 我们用$p_0$表示原图上从节点$1$到$n$的一条最短路. 对图上的任意一条边$e$, 设$p(e)$是删去边$e$后的从$1$到$n$的最短路, 设$f(e)$是$p(e)$的... Read more

CodingMathematics

扩展中国剩余定理

考虑$\mathbb{Z}$上的线性同余方程组 $x \equiv a_i \bmod n_i$, 其中$i = 1, .., r$. 则该方程组有解, 当且仅当对于任意$i\not= j$, 都有$a_i \equiv a_j \bmod \text{gcd} (n_i, n_j)$. Read more

Mathematics

赌徒摊分问题

和另外两个朋友去吃饭，饭局结束玩德州扑克，说好拿出饭钱的90元按照游戏结束后的筹码分布进行摊分。牌局开始的时候每人有30个筹码；牌局结束，我剩下68个筹码，朋友A剩下22个，朋友B输光了。怎样分摊账单合理呢？ Read more

Mathematics