Hello World
Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub. Quick Start Create a new post 1$ hexo new "My New Post" More info: Writing Run server 1$ hexo server More info: Server Generate static files 1$ hexo generate More info: Generating Deploy to remote sites 1$ hexo deploy More info: Deployment
Codeforces Round 1016 (Div. 3) G（二进制比大小）
CF2093G. Shorten the Array 题意 给定长度为 nnn 的数组 aaa，从中找出两个数 ai,aja_{i},a_{j}ai,aj 满足 ai⊕aj⩾ka_{i}\oplus a_{j} \geqslant kai⊕aj⩾k，并最大化两数距离（即最大化 j−i+1j-i+1j−i+1），输出这个最大距离。找不到则输出 −1-1−1。 思路 两数异或最大可以用字典树，但本题有个更好写的做法。 比大小问题，可以转化为判断相等。 给定 bbb，枚举 b += lowbit(b)（其本质是把 bbb 的一个 0 变 1，低位都变 0）。如果 a⩾ba \geqslant ba⩾b，那么必然存在一个枚举结果 b′b'b′，满足 aaa 同样位数变 0 后与 b′b'b′ 相同。 比如 bbb 是 10110，一个数大于等于 bbb，只能是 1011?、11??? 或 1??? 这几种形式。而枚举 b += lowbit(b)，刚好会得到 10110 →\to→ 11000 →\to→ 100000 →\to→ 1000000...
〔主机註記〕第 61 周主机註記 (Apr.7 - Apr.13)
第 61 周主机註記 月曜日 (Apr.7) 豪赌 我好想转专业，转专业还没重新高考重填志愿来的容易。一肚子火。唉，志愿调剂也是碰运气，我还是想想研究生吧。去年那形式也不咋样，太玄学了。感觉转专业真是一场豪赌，除了转树脂，政院这种的以外，或者转信通好歹还有笔试科目，转其他的风险都很大啊。 火曜日 (Apr.8) 踢了 南昌换西安，把南昌踢了皆大欢喜。 气煞 主机说上一次小测写错了一道题，气煞我也。唉，分奴。 短袖 我感觉北京快穿短袖了，室内太热了，一出门还可以但是室内真的太热了。想看主机穿短袖。 草莓 我想吃草莓，回宿舍就吃。昨天睡昏迷忘記吃了，但願沒有壞掉。 如果我淩晨三點坐在鋼琴湖邊會有人來抓我嗎……如果有的話我選擇去通惠河。 草莓發黴了，好傷心。 水曜日 (Apr.9) 翻了一圈 G 題都是用字典樹寫的，我在群裏分享思路。群友說我 smart，so clever，好厲害不到一年上黃。我又哭又笑是爲什麽。 我感觉课内讲的东西过时，很普遍，我们也在讲很多被淘汰的方法理论。 ...
Teza Round 1 (Codeforces Round 1015, Div. 1 + Div. 2) A-D
2084A - Max and Mod A 题先看样例，猜测 nnn 为偶数时无解。结合题意知只能是 ?,?,2,3,4,…,n−1?,?,2,3,4,\dots,n-1?,?,2,3,4,…,n−1 的形式。 如果 nnn 是奇数，为了保证 max{a2,a3} mod 3=2\max\lbrace a_{2},a_{3} \rbrace \bmod 3=2max{a2,a3}mod3=2，不能按样例取 a2=na_{2}=na2=n，应该是 a2=1a_{2}=1a2=1。最终构造出 n,1,2,3,4,…,n−1n,1,2,3,4,\dots,n-1n,1,2,3,4,…,n−1。 如果 nnn 是偶数，nnn 放在 a1a_{1}a1 或者 a2a_{2}a2 都不行，因此无解。 12345678910111213141516171819202122#include <bits/stdc++.h>using namespace std;signed main() { ...
【算法杂谈 + 好题分享】图论中的懒标记 LazyTag 思想
本系列教程「以题带讲」，以典型题目为载体，着重讲解知识点的适用条件和使用方法，而规避复杂的理论推导。 我不擅长数学，对 CF 和区域赛的数学题，从简单计算到数论组合都望而却步。「tag 是数学吗那不做了。」 可能是因为网上的教程大多是罗列定理，给出大段证明，最后放几个例题链接。我没有耐心和能力读完整篇文章。
【算法杂谈 + 好题分享】图论中的懒标记 LazyTag 思想
本文涉及的知识点：组合数公式，古典概型，Min-Max 反演及推广，卷积优化思想，状态压缩思想与状态压缩 DP，快速数论变换 NTT，快速数论变换 NTT，快速沃尔什变换 FWT。 本系列教程「以题带讲」，以典型题目为载体，着重讲解知识点的适用条件和使用方法，而规避复杂的理论推导。 我不擅长数学，对 CF 和区域赛的数学题，从简单计算到数论组合都望而却步。「tag 是数学吗那不做了。」 可能是因为网上的教程大多是罗列定理，给出大段证明，最后放几个例题链接。我没有耐心和能力读完整篇文章。 例题 2024 ICPC World Finals Astana B. Bingo for the Win! 题意 Bingo 游戏，nnn 个人每人要抢 kkk 个数，主持人按随机顺序依次报数，报到每个数 [1,109][1,10^{9}][1,109]...
【算法杂谈 + 好题分享】图论中的懒标记 LazyTag 思想
有三件物品可供选择，物品甲重量为 3，物品乙重量为 8，物品丙重量为 5。有一个背包，问选择任意件物品放入背包后，背包总重为 8 的方案数。 列出所有的可能： 选甲，选乙，选丙； 选甲，选乙，选丙； 选甲，选乙，不选丙； 选甲，不选乙，选丙； 选甲，不选乙，不选丙； 不选甲，选乙，选丙； 不选甲，选乙，不选丙； 不选甲，不选乙，选丙； 不选甲，不选乙，不选丙。 每个物品 X 都有两种状态：选 X 或不选 X，而且每个物品的状态相互独立，直接用一个式子表达： （选甲 或 不选甲）且（选乙 或 不选乙）且（选丙 或 不选丙） 这个逻辑表达式包含了上面全部八种情形。这里 且 的含义是，如果 A 且 B，那么 A 必须执行，B 也必须执行。 把物品重量一并列入上面的表达式中： （重量为 3 或 重量为 0）且（重量为 8 或 重量为 0）且（重量为 5 或 重量为 0） 这样写虽然能表达所有的情况，但文字太多还是太麻烦了。希望选取一些数学符号，完全转化为数学表达式。 观察这个式子： （重量为 3 或 重量为 0）且（重量为 8 或 重量为...
【算法杂谈 + 好题分享】图论中的懒标记 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...
〔主机註記〕第 59 周主机註記 (Mar.24 - Mar.30)
第 59 周主机註記 月曜日 (Mar.24) 火曜日 (Mar.25) 水曜日 (Mar.26) 木曜日 (Mar.27) 金曜日 (Mar.28) 土曜日 (Mar.29) 日曜日 (Mar.30)