【算法杂谈 + 好题分享】图论中的懒标记 LazyTag 思想
想必读者第一次听说懒标记 (LazyTag) 是在线段树区间修改中，其实懒标记思想在图论及更多方面中也有应用。其核心思想在于「延迟计算 」，即通过标记的方式记录对某个有相同性质的对象（如线段树的区间、图中的连通块等）的 整体操作，而不是立即操作每个元素。 一、并查集维护连通性——The 2025 ICPC Latin America Championship D. Dangerous City Description 给定无向图，有点权。路径权值定义为路径上（含端点）所有点权最大值，定义 f(u,v)f(u, v)f(u,v) 为所有 uuu 到 vvv 路径中值最小的一条。对每个 uuu 求 su=∑v=1nf(u,v)s_u = \displaystyle \sum_{v=1}^n f(u, v)su=v=1∑nf(u,v)。n,m⩽3⋅105n,m \leqslant 3\cdot 10^{5}n,m⩽3⋅105。 Notes 将点权转化为边权，设 u−vu-vu−v 的边权 w=max{wu,wv}w=\max\lbrace w_{u},w_{v}...
〔主机註記〕第 60 周主机註記 (Mar.31 - Apr.6)
第 60 周主机註記 月 (Mar.31) 火 (Apr.1) 水 (Apr.2) 二十 主机はたち了。我什麽時候送生日禮物呢？ 神經 好想發瘋，但包會被罵神經病的（暴躁）（毀滅）。主机表示會被罵就別說。 萬事 我們有邀請賽三選一的機會。其實想在 final 之前打一場，西安大上分，長春沒去過也可以考慮。不過去哪裏都是連續三周，可惜，要是能把南昌踢了真是萬事大吉。最終決定長春（閃亮）。 有老師群裏一人一句話，顯得我們很民主。 被訪 主机說長的特漂亮的不適合做訪談員，做訪談的最好長得老實巴交的。訪談就是找你聊天，跟你說的目的未必是真實目的。我之前還想過這問題，特別想被訪談，被新院的漂亮姐姐訪談。呃長的漂亮不是重點，主要是這種形式。他們在講話方面都很有招，和他們聊天很舒服。真的特別想被訪談。 監考 校賽監考。 牛客沒有給我線上管理權限，好氣，我能不能登你們號，不理我，好氣。我想看榜，我想看神人代碼，我還好想喝果茶，好氣。 主机部長挺牛的，看上去是那種，前一分鐘還在打球，後一分鐘就 void bfs()。這裏還有好多大神，Java...
在老师发的资源包里
[{"url":"/img/posts/diary/250325/1.webp","alt":"","title":""}]
〔主机註記〕第 59 周主机註記 (Mar.24 - Mar.30)
第 59 周主机註記 月 (Mar.24) 火 (Mar.25) 水 (Mar.26) 木 (Mar.27) 金 (Mar.28) 土 (Mar.29) 日 (Mar.30)
Codeforces Round 1012 (Div. 1) A B1 C1
2089A - Simple Permutation 从小往大顺着选，如果不是素数就选个稍微大一点的让结果是素数。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172#include <bits/stdc++.h>using namespace std;using ll = long long;constexpr int N = 5e5 + 5;vector<int> prime;int mint[N]; // 最小素因子 bool is_prime(int x) { return mint[x] == x;}signed main() { ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr); for...
〔主机註記〕第 58 周主机註記 (Mar.17 - Mar.23)
第 58 周主机註記 月 (Mar.17) 火 (Mar.18) 水 (Mar.19) 木 (Mar.20) 金 (Mar.21) 土 (Mar.22) 激发 港科广本科生区域赛拿奖一人十五万人民币奖学金，我感觉这个比不报销，更能激发人类潜能。 日 (Mar.23)
Educational Codeforces Round 174 A - F
（一个月前的比赛） 2069A - Was there an Array? 12345678910111213141516171819202122232425262728293031#include <bits/stdc++.h>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr); int t; cin >> t; while (t--) { int n; cin >> n; n -= 2; vector<int> b(n); for (int i = 0; i < n; i++) { cin >> b[i]; } bool flag = 1; for (int i =...
LLM：
[{"url":"/img/posts/diary/250314/1.webp","alt":"","title":""}]
Codeforces Round 1009 (Div. 3) E - G
2074E - Empty Triangle Hint 1 随机化 平面上 nnn 个点是毫无规律的，就算每个点问一次也只能问到 3×753\times 753×75 个点，这个数远小于 150015001500，想要让每个点地位平等，考虑随机。 Hint 2 从一个已知的三角形往里缩 相比包含特殊点的三角形，不包含的三角形其面积相对较小。而且包含特殊点的三角形内部一定有答案。如果问到一个包含特殊点的三角形，想法是往里缩，直到找到答案。 具体地，如果问到 x−y−zx-y-zx−y−z 里面包含 uuu，可能会考虑继续问 x−y−ux-y-ux−y−u 或 x−u−zx-u-zx−u−z 或 u−y−zu-y-zu−y−z。这里有好几种选择，用随机数选。 123456789101112131415161718192021222324252627282930#include <bits/stdc++.h>using namespace std;mt19937_64...
Codeforces Round 1008 (Div. 1) A - C
2077A/2078C - Breach of Faith 取较大的 n2+1\dfrac{n}{2}+12n+1 个放在奇数位，较小的放在偶数位。 12345678910111213141516171819202122232425262728293031323334353637#include <bits/stdc++.h>using namespace std;using ll = long long;int main() { int J; cin >> J; while (J--) { int n; cin >> n; vector<int> a(n * 2); for (int i = 0; i < n * 2; i++) { cin >> a[i]; } sort(a.begin(), a.end()); ...