Ghastlcon

違う青空 見上げている

树上分治笔记

(不)经过自己

树上分治笔记 - Ghastlcon   CONTENT ENCRYPTED ...

GDKOI 2018

来玩 Mini Metro

$\text{GDKOI }2018$ 再次感觉跟去年的画风完全不同。 资瓷左老师讲课 上去提了下大样例的问题并不知道明年有没有 想看 $\text{Solution}$ 的直接翻 $\text{Catalog}$ 。 (然而事实上并没有写) 本篇就是划水记,随便记点东西。或许等到我真的 $\text{AFO}$ 之后来看,说不定会找到零碎的回忆吧。 $\text{Day ...

SMOJ 2018.01

SMOJ 2018.01 - Ghastlcon   CONTENT ENCRYPTED ...

(Ex)GCD 的正确性证明

(a, b) = (b, a mod b)

忽然发现貌似只会默写 $\text{(Ex)GCD}$ 的模板…… 证明(扩展)欧几里得算法的正确性。 $\text{GCD}$ 设 $\gcd(a,b)=k$ 。 则有 $x=\frac{a}{k},y=\frac{b}{k}$,且 $a,b\geq 1$ 。 这相当于 $a$ 是由 $x$ 个 $k$ 组成,而 $b$ 则由 $y$ 个 $k$ 组成(即相乘)。 因此得 ...

(Ex)CRT 笔记

≡=∑

(Ex)CRT 笔记 - Ghastlcon   CONTENT ENCRYPTED ...

SMOJ 2017.12

SMOJ 2017.12 - Ghastlcon   CONTENT ENCRYPTED ...

带花树笔记

高斯费马 树上开花

带花树笔记 - Ghastlcon   CONTENT ENCRYPTED ...

NOIp 2017

结论题?再见

NOIp 2017 - Ghastlcon   CONTENT ENCRYPTED ...

SPFA 的 SLF 优化

优化却是退化

SPFA 的 SLF 优化 - Ghastlcon   CONTENT ENCRYPTED ...

流 & 割 & 路

路径的经过就是割

最大流 $f$ 很熟悉吧。 最小割 $c$ 也很熟悉吧。 最大最小定理这里就不证了。 最短路 $p$ 这里指的是对偶图的最短路。 只有平面图才会有对偶图。 平面图的认识是非常感性的:如果能够把这个图“摊开”,使得所有的边都互不交叉,那么这个图就叫做平面图。 对偶图? 把原图的面看成点就得到了对偶图。 很神奇吧。 如果让对偶图的边权等于原图的对应边权,那么平...