小明の雜貨鋪

存图方式 若不另加说明，以 u,vu,vu,v 表示两个点，www 表示边权，nnn 表示点数，mmm 表示边数。 直接存边 123456789101112131415struct Edge { int u, v, w;};vector<Edge> E;void add(int u, int v, int w) { E.push_back({ u, v, w }); }bool findedge(int u0, int v0) { for (auto [u,v,w] : E) if (u == u0 && v == v0) return 1; return 0;}void dfs(int u) { if (vis[u]) return; vis[u] = 1; for (auto e : E) if (e.u == u) dfs(e.v);} 查询边 Θ(m)\Theta(m)Θ(m)，遍历某点的出边...

將圖像轉換爲 ASCII 字符畫 123456789101112131415161718192021222324252627282930from PIL import Imageascii_chars = "@%#*+=-:. " # 灰度遞減 def scale_gray(x): scale = (len(ascii_chars) - 1) / 255 return ascii_chars[int(x * scale)]def image2ascii(image_path, out_width = 100): image = Image.open(image_path) org_width, org_height = image.size org_aspect_radio = org_height / org_width / 2.75 out_height = int(out_width * org_aspect_radio) image_resized = image.resize((out_width,...

「我的大腦才不是垃圾場！信息斷食！奪回專註，還我清凈！」閱讀記錄

单调栈与单调队列 题意 给定一个环，判断有多少元素满足：所有以这个元素为起始的区间的和非负。(普及 +/ 提高, VJwin2C - 好消息，坏消息) Step1 断环为链 注意所需的数组范围变大，N 应改为 2*N。 123int n = read();for (int i = 1; i <= n; ++i) a[i + n] = a[i] = read(); // 断环为链for (int i = 1; i <= 2 * n - 1; ++i) s[i] = s[i - 1] + a[i]; // 前缀和 Step2 单调队列 熟知可以用前缀和表示区间之和，如区间 k~l 等于 a[l]-a[k-1]，那么要判断区间和是否为正数，只要最小前缀和是否大于前面数的和。以前缀和作为单调队列，维护单调队列是递增的，以保证留下最小的元素。 需计算 kkk 的个数，满足 ∀i∈[k,k+n], ak+ak+1+⋯+ak+n⩾0\forall i\in[k,k+n],~a_k+a_{k+1}+\dots+a_{k+n} \geqslant...

本文需要重写。 Disjoint Set Union 併查集 一些常用： 求元素 kkk 所在連通圖的元素數量 Sk={1⩽i⩽n ∣find⁡(k)=find⁡(i)}S_k=\left\{1\leqslant i\leqslant n ~\vert\operatorname{find}(k)=\operatorname{find}(i)\right\}Sk​={1⩽i⩽n ∣find(k)=find(i)}： 123for (int i = 1; i <= n; ++i) { Sk += find(k) == find(i);} 求連通圖總數 S={1⩽i⩽n ∣find⁡(i)=i}S=\left\{1\leqslant i\leqslant n ~\vert\operatorname{find}(i)=i\right\}S={1⩽i⩽n ∣find(i)=i}，至少需要 S−1S-1S−1 條線才能將所有連通圖連通： 123for (int i = 1; i <= n; ++i) { ans +=...

本文需要重写。 Disjoint Set Union (Uno-Find Set) 路径压缩： 1234int fa[N];inline void init(int n) { for (int i = 1; i <= n; ++i) fa[i] = i; }int find(int x) { return x == fa[x] ? x : (fa[x] = find(fa[x])); }inline void uno(int x, int y) { fa[find(x)] = find(y); } 按秩合併： 123456789int fa[N], rnk[N];inline void init(int n) { for (int i = 1; i <= n; ++i) fa[i] = i, rnk[i] = 1; }int find(int x) { return x == fa[x] ? x : (fa[x] = find(fa[x])); }inline...