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() { ...
【组合计数杂谈】三道 Bingo 游戏题（备份）
本文涉及的知识点：组合数公式，古典概型，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 思想
本系列教程「以题带讲」，以典型题目为载体，着重讲解知识点的适用条件和使用方法，而规避复杂的理论推导。 我不擅长数学，对 CF 和区域赛的数学题，从简单计算到数论组合都望而却步。「tag 是数学吗那不做了。」 可能是因为网上的教程大多是罗列定理，给出大段证明，最后放几个例题链接。我没有耐心和能力读完整篇文章。
【算法杂谈 + 好题分享】图论中的懒标记 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)
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...