📸 @letskendo ×4
奈良インターハイの競技1日目は、女子団体戦ベスト16、男子個人戦ベスト4がそろいました！ 本日の結果などはLET'S KENDOに掲載しています〜✋
http://www.letskendo.com
男子個人戦ベスト4（8/5開催）
・橋本(東福岡)×八⻆(四天王寺東)
・三浦(秋田商)×馬木(新田) #kendo #剣道 #レッツ剣道
原文 #剣道
奈良インターハイの競技1日目は、女子団体戦ベスト16、男子個人戦ベスト4がそろいました！ 本日の結果などはLET'S KENDOに掲載しています〜✋
http://www.letskendo.com
男子個人戦ベスト4（8/5開催）
・橋本(東福岡)×八⻆(四天王寺東)
・三浦(秋田商)×馬木(新田) #kendo #剣道 #レッツ剣道
原文 #剣道
Spotify
ohayashi
Ichiko Aoba · Windswept Adan · Song · 2020
🔑 并查集为什么适合“连通性”问题，却不适合“路径”问题
并查集（Union-Find / Disjoint Set Union, DSU）解决的核心不是“怎么走”，而是“是不是一伙的”。当图上的边会不断加入，而你反复想问两个点当前是否连通时，如果每次都重新跑一次 BFS 或 DFS，代价会越来越高；并查集的设计思路更直接：它不关心整条路径长什么样，只维护每个点属于哪个集合。
它之所以高效，关键在两个优化。一个是 path compression：每次
但并查集的“快”，是靠主动丢弃大量路径细节换来的。它只告诉你两个点最后是不是在同一个集合里，却不会保留“经过了哪些边”“路径长度是多少”“谁是父谁是子”的真实图结构。所以它特别适合回答 connectivity，却不适合回答 shortest path、具体路径恢复、拓扑先后关系 这类问题。很多人一看到图连起来了，就下意识想用并查集一路做到底，结果在需要距离、方向、层次的时候才发现信息早就没被保存下来。
真正容易踩坑的地方，恰恰在这里：你以为自己维护的是一棵“树”，其实维护的只是一个“集合代表关系”。例如在 Kruskal 中，并查集只负责判断“加这条边会不会成环”，真正决定最小生成树权值的是排序后的贪心过程，不是并查集本身；再比如有些题要求删除边后的动态连通性，普通并查集不支持高效删除，很多时候要改成离线倒序处理，而不是硬在原结构上减边。换句话说，并查集很强，但它强在边界明确：只管合并与查询连通，不管路径语义。
🧪 课后一题：无向图有 6 个点，初始互不连通。依次执行1 和 5 连通，因为 1-2-3 与 4-5 在 后合并成同一集合；6 和 1 不连通，因为 6 从未参与任何合并。
💡 易混淆点：并查集维护的是“属于同一个集合”而不是“图上的父子关系”或“实际路径”，
#CS
并查集（Union-Find / Disjoint Set Union, DSU）解决的核心不是“怎么走”，而是“是不是一伙的”。当图上的边会不断加入，而你反复想问两个点当前是否连通时，如果每次都重新跑一次 BFS 或 DFS，代价会越来越高；并查集的设计思路更直接：它不关心整条路径长什么样，只维护每个点属于哪个集合。
union(x, y) 把两个集合合并，find(x) 找到 x 所在集合的代表元，于是“x 和 y 是否连通”就变成比较 find(x) == find(y)。它之所以高效，关键在两个优化。一个是 path compression：每次
find 时，把沿途节点直接挂到根上，后面再找就更快；另一个是 union by rank/size：总把更小或更浅的树挂到更大或更高的树下面，避免结构退化。两者一起使用后，单次操作的均摊复杂度接近 O(1)，严格地说是 O(α(n))，这里的 α 是反 Ackermann 函数，在实际规模里几乎可以当常数看待。这也是为什么 Kruskal 最小生成树、离线连通性判断、朋友圈合并、岛屿归类这类题几乎都会优先想到并查集。但并查集的“快”，是靠主动丢弃大量路径细节换来的。它只告诉你两个点最后是不是在同一个集合里，却不会保留“经过了哪些边”“路径长度是多少”“谁是父谁是子”的真实图结构。所以它特别适合回答 connectivity，却不适合回答 shortest path、具体路径恢复、拓扑先后关系 这类问题。很多人一看到图连起来了，就下意识想用并查集一路做到底，结果在需要距离、方向、层次的时候才发现信息早就没被保存下来。
真正容易踩坑的地方，恰恰在这里：你以为自己维护的是一棵“树”，其实维护的只是一个“集合代表关系”。例如在 Kruskal 中，并查集只负责判断“加这条边会不会成环”，真正决定最小生成树权值的是排序后的贪心过程，不是并查集本身；再比如有些题要求删除边后的动态连通性，普通并查集不支持高效删除，很多时候要改成离线倒序处理，而不是硬在原结构上减边。换句话说，并查集很强，但它强在边界明确：只管合并与查询连通，不管路径语义。
🧪 课后一题：无向图有 6 个点，初始互不连通。依次执行
union(1,2)、union(2,3)、union(4,5)、union(3,5) 之后，1 和 5 是否连通？6 和 1 是否连通？答案：union(3,5)💡 易混淆点：并查集维护的是“属于同一个集合”而不是“图上的父子关系”或“实际路径”，
find 出来的根只是代表元，不等于原图里的起点、终点或最近公共祖先。#CS
🔐 哈希长度扩展：拼接式签名为什么一文不值
很多系统做消息完整性校验时，图省事会这么干：把密钥和消息直接拼起来，再算个哈希当签名。比如
SHA-256 这类 Merkle-Damgård 系哈希是分块处理的：消息被切成 64 字节的块逐块喂入，每块的输出作为内部状态继续参与下一块计算。于是出现一个致命特性：知道某个消息的哈希值，就等于拿到了处理完该消息后的内部状态。拿到状态就能假装"我已经算到这儿了"，继续往后面追加任意内容并算出新哈希，全程不需要知道 secret。唯一要猜的是 secret 的长度，因为它决定中间那段填充怎么写，而枚举几十种长度对工具来说毫无压力。这就是哈希长度扩展攻击（Hash Length Extension）。
现实中最出名的受害者是 2009 年的 Flickr API：签名方案就是
为什么 HMAC 不怕？HMAC 不是简单拼接，它把密钥派生出两个掩码，一个垫在消息前面算内层哈希，一个垫在结果前面算外层哈希，密钥被两层结构封住，长度扩展无从下手。防御口径很朴素：完整性校验一律用 HMAC，或者干脆用 SHA-3 这类海绵结构哈希；永远不要自己发明
🧪 场景分析：某订单接口用
答案：可以。SHA-256 是 Merkle-Damgård 结构，已知 H(secret m) 就能从内部状态继续追加。用 hashpump 这类工具，枚举猜出 secret 长度后，算出 H(secret原消息 补齐填充&discount=90) 作为新签名；把追加部分（含二进制填充）URL 编码后拼到参数串末尾，服务器 URL 解码得到的就是原消息加新参数，校验通过。这也解释了为什么修复不能靠给消息加随机盐了事，必须换成 HMAC。
💡 核心记忆：
#Security
很多系统做消息完整性校验时，图省事会这么干：把密钥和消息直接拼起来，再算个哈希当签名。比如
sig = SHA-256(secret + message)，服务器收到请求后自己重算一遍比对，一致就认定是可信来源发的。乍看没毛病，secret 藏在里面，攻击者不知道密钥就算不出合法签名。问题出在哈希算法自身的结构上。SHA-256 这类 Merkle-Damgård 系哈希是分块处理的：消息被切成 64 字节的块逐块喂入，每块的输出作为内部状态继续参与下一块计算。于是出现一个致命特性：知道某个消息的哈希值，就等于拿到了处理完该消息后的内部状态。拿到状态就能假装"我已经算到这儿了"，继续往后面追加任意内容并算出新哈希，全程不需要知道 secret。唯一要猜的是 secret 的长度，因为它决定中间那段填充怎么写，而枚举几十种长度对工具来说毫无压力。这就是哈希长度扩展攻击（Hash Length Extension）。
现实中最出名的受害者是 2009 年的 Flickr API：签名方案就是
md5(secret + 参数)，攻击者用一个合法请求的签名就能伪造出带额外参数的请求签名。今天仍能看到不少自研 Webhook 签名、游戏防作弊校验在用这种拼串哈希，几乎一测一个准。为什么 HMAC 不怕？HMAC 不是简单拼接，它把密钥派生出两个掩码，一个垫在消息前面算内层哈希，一个垫在结果前面算外层哈希，密钥被两层结构封住，长度扩展无从下手。防御口径很朴素：完整性校验一律用 HMAC，或者干脆用 SHA-3 这类海绵结构哈希；永远不要自己发明
hash(secret + message) 的变体。正经平台的 Webhook 签名（比如 Stripe）用的就是 HMAC-SHA256，不是没有原因的。🧪 场景分析：某订单接口用
sign = sha256(secret + "user=alice&price=100") 做签名，你截获了一个合法请求，参数和 sign 都可见。能否在不知道 secret 的情况下，伪造出追加 &discount=90（打一折）的请求并算出合法签名？💡 核心记忆：
hash(secret + message) 会把哈希内部状态整个交出去，消息完整性校验请认准 HMAC。#Security
📚 「を踏まえて」不是万能“基于”：它和「に基づいて」差在哪？
技术报告里很常见一种误用：明明想表达“看了前面的结果之后，做了判断和调整”，却一律写成「〜に基づいて」。其实这时更自然的往往是「〜を踏まえて」。它特别适合安全审计、实验复盘、论文讨论、需求修订这类场景：先有事实或前提，再据此做判断、改写设计、调整方案。
边界要抓清。「に基づいて」强调“有明确依据”，后面常接规则、定义、法令、规格、正式数据，语气像“依照……来做”。「を踏まえて」则不是机械照搬，而是“把前提情况考虑进去之后，再往下决定怎么做”，后面常接判断、改善、提案、设计变更。至于「をもとに」，语气更宽，偏“以……为素材/基础加工而成”，没有「を踏まえて」那种“考虑之后作判断”的味道。
所以，「先行研究に基づいて手法を設計した」更像“设计直接建立在既有理论或文献依据上”；而「先行研究の限界を踏まえて手法を設計した」则是在“看清前人不足之后”做出改进，这两个句子在研究写作里不能随便互换。
例如可以直接这样套用：
脅威分析の結果を踏まえて、認証フローにデバイス証明を追加した。
基于威胁分析结果并结合其含义，我们在认证流程中加入了设备证明。
先行研究の限界を踏まえて、本研究では評価指標にロバスト性を加えた。
鉴于先行研究的局限，本研究在评价指标中加入了鲁棒性。
ベンチマークの測定誤差を踏まえて、結果には95%信頼区間を併記した。
考虑到基准测试的测量误差，结果部分同时标注了 95% 置信区间。
反过来，如果你要写的是「仕様書に基づいて実装する」「法令に基づいてデータを管理する」，这里就别换成「を踏まえて」，因为重点不是“综合考虑后调整”，而是“按明确依据执行”。
💡 記憶ポイント：后面有判断、修正、提案、改善，用「を踏まえて」；后面是依照规则、定义、规格执行，用「に基づいて」 。如果你脑子里想的是“考虑到……之后，我们决定……”，大概率就是「を踏まえて」。
#日本語
技术报告里很常见一种误用：明明想表达“看了前面的结果之后，做了判断和调整”，却一律写成「〜に基づいて」。其实这时更自然的往往是「〜を踏まえて」。它特别适合安全审计、实验复盘、论文讨论、需求修订这类场景：先有事实或前提，再据此做判断、改写设计、调整方案。
边界要抓清。「に基づいて」强调“有明确依据”，后面常接规则、定义、法令、规格、正式数据，语气像“依照……来做”。「を踏まえて」则不是机械照搬，而是“把前提情况考虑进去之后，再往下决定怎么做”，后面常接判断、改善、提案、设计变更。至于「をもとに」，语气更宽，偏“以……为素材/基础加工而成”，没有「を踏まえて」那种“考虑之后作判断”的味道。
所以，「先行研究に基づいて手法を設計した」更像“设计直接建立在既有理论或文献依据上”；而「先行研究の限界を踏まえて手法を設計した」则是在“看清前人不足之后”做出改进，这两个句子在研究写作里不能随便互换。
例如可以直接这样套用：
脅威分析の結果を踏まえて、認証フローにデバイス証明を追加した。
基于威胁分析结果并结合其含义，我们在认证流程中加入了设备证明。
先行研究の限界を踏まえて、本研究では評価指標にロバスト性を加えた。
鉴于先行研究的局限，本研究在评价指标中加入了鲁棒性。
ベンチマークの測定誤差を踏まえて、結果には95%信頼区間を併記した。
考虑到基准测试的测量误差，结果部分同时标注了 95% 置信区间。
反过来，如果你要写的是「仕様書に基づいて実装する」「法令に基づいてデータを管理する」，这里就别换成「を踏まえて」，因为重点不是“综合考虑后调整”，而是“按明确依据执行”。
💡 記憶ポイント：
#日本語