小明の雜貨鋪

數據結構第十講：圖的遍歷的最小生成樹

第 41 周主机註記 月曜日 (Nov.18) 火曜日 (Nov.19) 水曜日 (Nov.20) 木曜日 (Nov.21) 金曜日 (Nov.22) 土曜日 (Nov.23) 日曜日 (Nov.24)

CF2031A. Penchick and Modern Monument 123456789101112131415161718192021222324#include <bits/stdc++.h>using namespace std;int main() { int t; cin >> t; while (t--) { int n; cin >> n; vector<int> cnt(n); for (int i = 0; i < n; i++) { int x; cin >> x; x--; cnt[x]++; } int maxx = 0; for (int i = 0; i < n; i++) { maxx =...

數據結構第九講：圖的基本概念

第 40 周主机註記 月曜日 (Nov.11) 火曜日 (Nov.12) 水曜日 (Nov.13) 木曜日 (Nov.14) 金曜日 (Nov.15) 土曜日 (Nov.16) 日曜日 (Nov.17)

音源外链来自网易云音乐，歌词翻译来自 ラグトレイン / 延误列车（罗马音翻译）——稲葉曇 - 哔哩哔哩，略有修改 table { border-collapse: collapse; /* 合并边框，确保没有双线 */ border: 0; /* 设置表格边框为 0，即不显示边框 */ width: 100%; /* 根据需要设置表格宽度 */ } table tr td:first-child { font-family: YuMin; font-size: 18px; font-weight: 500; padding: 12px; /* 增加单元格的内边距 */ letter-spacing: 1.2px; } table tr td:last-child {font-size: 18px;} ruby rt { font-size: 12px; vertical-align: 0.5em; /* baseline, sub, super, top, text-top,...

真實、、我現在的電子筆記乃至整個網站都沒什麼實質性內容。 ​用 css 堆砌起的空殼罷了。 2024-11-11 19:05

CF2028E. Alice’s Adventures in the Rabbit Hole 博弈部分：Alice 只能往根走。Queen 一定是让 Alice 往根的反方向走，哪怕这个点的父亲的某个儿子是叶子节点。 树部分：所以问题化为以每个点为起点，有 12\cfrac{1}{2}21​ 概率向上移动，另 12\cfrac{1}{2}21​ 概率向最近叶子方向的子节点移动，问到根的概率。 这是个树上随机游走问题。设 fuf_{u}fu​ 表示 uuu 到其父亲的概率，则 fu=12+12fufvf_{u}=\cfrac{1}{2}+\cfrac{1}{2}f_{u}f_{v}fu​=21​+21​fu​fv​，其中 vvv 是最近叶子方向的子节点，解得 fu=12−fvf_{u}=\cfrac{1}{2-f_{v}}fu​=2−fv​1​。由于叶子的 fu=0f_{u}=0fu​=0，递推计算从这个叶子向上每个节点的概率分别为 0,12,23,…0, \cfrac{1}{2}, \cfrac{2}{3}, \dots0,21​,32​,… 为...