第一次听到男人八题这四个字我还以为是哪位博主起的标题党名字。后来才知道这是算法竞赛圈里流传了很多年的一个说法指楼教主在 POJ 上留下的那批题目——题面看着平平无奇难度却是断层式的于是被社区戏称为男人八题意思是能把这八道独立啃下来基本功基本就没什么可挑剔的了。我打算从第一题开始一道一道重新做一遍把当年没想通的地方、后来才慢慢悟出来的思维方式都老老实实记下来。如果你是刚学完并查集、想找个够硬的题练手的人或者你早就听说过这个名号但一直没敢点开那这篇东西应该能帮你少走点弯路。这篇先聊第一题重点不在代码有多长而在于它逼着你完成一次建模转换——把区间上的奇偶性问题改写成点与点之间的异或约束关系。1. 男人八题这八道题到底强在哪第一题又凭什么是它1.1 楼教主与男人八题这个说法的由来楼教主这个称呼在算法竞赛圈里几乎是自带光环的。他在 TopCoder、Google Code Jam 这类比赛上的战绩属于第一梯队后来转去做工程方向也做得风生水起。而男人八题这个带点江湖气的名字来自他在 POJPKU Online Judge上挂的一批题目题号集中在 1733 到 1742 这一小段区间里题量不多但每一道的思维跨度都很大。这个称呼的潜台词其实很朴素——这些题不靠模板堆砌也不靠数据规模吓人而是靠你想不到。你可能会写点分治可能会写多重背包但把算法名字抹掉之后你能不能在十分钟内判断出这道题该往哪个方向走这才是它真正在筛的东西。也正因为如此这批题在社区里被反复讨论成了很多人从会做题往会建模过渡的一个重要台阶。我个人的看法是这类题的训练价值不在题目本身而在于它们强迫你建立一个习惯先把问题用最朴素的语言重述一遍看看它到底在问什么再去找对应的结构。很多人卡住不是因为不会算法而是因为跳过这一步拿着熟悉的模板硬套越套越远。1.2 题单版本之争我按 POJ 编号顺序把第一题定为 1733先交个底。男人八题具体是哪八道网上流传的版本并不完全统一有的按难度排有的按题材排不同博客列出来的题号也会有出入。我这边采用的是一个比较常见的做法直接按 POJ 题号从小到大排。这样一来打头的那道就落在 1733 上也就是那道关于 01 串区间奇偶性的题——Parity game。按这个顺序这八道大致会覆盖这些方向区间奇偶关系判定、最小环、连通图计数、石子合并的最优策略、多重背包的优化、博弈中的对称构造、插接式状态压缩以及树的路径统计。你会发现它们几乎不重复每一道都是一个独立的知识块。这也是我认为它值得按顺序刷的原因刷完一遍你的知识版图会被补齐而不是在原地反复强化同一个点。排第一的 1733从题面看是最朴素的——没有图没有环没有状态压缩只有一堆区间描述。但它的建模门槛一点不低甚至可以说是这八道里转换最漂亮的一道。这也是我把它放在第一个讲的原因因为它最能体现这批题的核心气质。1.3 第一题的门槛不难在算法模板难在建模这一步先把结论说在前面这道题的最终代码不到六十行核心就是带权并查集加一次离散化任何一个学过并查集的人看完代码都能照着敲出来。但如果你第一次做大概率会对着题面发呆很久因为你很难立刻意识到区间里 1 的个数是奇数还是偶数这件事和并查集有什么关系。这里有个认知差会写并查集的人很多但知道什么时候该用带权并查集的人少一截。普通并查集只能回答你和我是不是一伙的而带权并查集的强项是回答你我之间是什么关系。第一题的所有难度都集中在这个判断上——你要先意识到问题在问关系才会想到去用能表达关系的工具。所以这一篇我会花比较多篇幅在为什么要这样建模上代码反而是最后才出现的。做这类题想清楚的那一瞬间后面的东西都是水到渠成想不清楚写再多也是白写。这也是我这些年带新人时反复强调的一点先花十分钟想明白问题结构比花十分钟debug要划算得多。2. 把区间奇偶性翻译成端点之间的异或约束2.1 前缀和区间信息天然是两个前缀之差题目给的是一个长度为 n 的 01 序列然后给出若干条描述每条形如从第 l 位到第 r 位1 的总个数是偶数或奇数。这些描述可能有互相矛盾的地方问的是最多能接受前面多少条。拿到这种区间统计的题第一个条件反射应该是前缀和。设 S[i] 表示前 i 位里 1 的个数那么区间 [l, r] 里 1 的个数就等于 S[r] - S[l-1]。这一步转换没有任何技术含量但它是整道题的转折点——因为原本分散在区间里的信息被压缩成了两个端点 S[l-1] 和 S[r] 之间的关系。我特别喜欢用记账来类比这件事。你有一本流水账S[i] 是截止第 i 天的累计支出。想知道 3 月到 5 月花了多少不需要翻三个月里每一笔记录只需要用 5 月末的累计数减去 2 月末的累计数。前缀和的意义就是这个它把一段时间内的信息变成了两个时间点的差值。一旦你接受了这个视角题目里所有描述就都不再是区间了而是两个前缀之间的关系。这是第一步也是最关键的一步。2.2 取模 2 之后减法和异或是一回事接下来是奇偶性。题目只关心 1 的个数是奇数还是偶数也就是关心 (S[r] - S[l-1]) 对 2 取模的结果。这里有个很顺手的小性质在模 2 的世界里减法、加法、异或是完全一样的运算。为什么因为模 2 下只有 0 和 1 两个值减法 0-1 会借位变成 -1但 -1 mod 2 等于 1正好和 0 xor 1 1 一致。你可以把所有情况列一遍验证0-00 对应 0 xor 000-1≡1 对应 0 xor 111-01 对应 1 xor 011-10 对应 1 xor 10。四种情况全部吻合。这个性质的意义在于复杂的减法被换成了更容易处理、也更容易合并的异或。于是区间内 1 的个数是偶数就等价于S[l-1] 和 S[r] 的奇偶性相同用异或表达就是 S[l-1] xor S[r] 0而是奇数则等价于两者奇偶性不同即 S[l-1] xor S[r] 1。我给这种转换起了个名字叫把约束翻译成投票。每条描述其实就是在说这两个点要么站同一队异或为 0要么站对立面异或为 1。题目问的是按顺序听这些说法听到第几句的时候前面所有说法已经不可能同时成立了。2.3 换个说法这其实是一个增量加边的冲突检测问题到了这里问题已经彻底变形了。我们把每个出现过的前缀下标也就是每个 S 的位置当成图上的一个节点每条描述当成一条边边上的权值是 0 或 1含义是两端点的奇偶性是否相同。然后我们按顺序一条一条地把边加进去问第一次出现矛盾是在哪一条。什么叫矛盾就是新加的这条边所声明的两端关系和前面已经加进去的边推导出来的关系对不上。比如前面已经告诉你 A 和 B 同奇偶、B 和 C 不同奇偶那么 A 和 C 必然不同奇偶这时候如果你再来一条A 和 C 同奇偶整个系统就崩了。这个模型其实和二分图染色判矛盾是同一类东西只不过这里的关系不是单一的不同而是带权值的相同/不同。它有个很好的性质只要没有矛盾那么任意两点之间的关系就是唯一确定的。因为异或是一个可以沿着路径传递的量——从 A 走到 B把路上所有边权异或起来得到的就是 A 和 B 之间的关系而且不管你走哪条路径结果都一样不然就矛盾了。顺便交代一下规模。题目里的 n 可能大到十亿级别但描述的条数只有几千条。这意味着涉及到的前缀下标最多也就几万个完全塞得进数组但前提是你得做离散化。n 大这件事在这里不是用来卡时间的而是用来堵死直接开数组存前缀和这条路的——你必须放弃真的去构造那个序列。3. 带权并查集凭什么能回答两点之间是什么关系3.1 普通并查集只答通不通答不了什么关系普通并查集的能力边界很清楚它能快速告诉你两个元素是不是属于同一个集合但集合内部谁和谁什么关系它一概不知。因为它在合并的时候只记了这两个集合是一家人了没记是怎么成为一家人的。而这道题的核心诉求恰好是是什么关系。每次加边之前我们都要回答两个问题这两点现在连通吗如果连通它们之间的关系和这条边声明的一致吗如果不连通那就把它们所在的集合合并并且记录下这两个集合之间需要保持什么关系。这就要求并查集在维护集合结构的同时额外维护每个元素相对于其代表元的关系。这个额外的关系就是所谓的权值。3.2 权值的定义d[x] 表示 x 到根之间的异或值我们定义 d[x] 为节点 x 与它的父节点之间的异或关系。在路径压缩完成之后父节点就是根节点所以 d[x] 可以直接理解为x 相对于根的关系值。0 表示 x 和根同奇偶1 表示不同。关键点在于这个 d[x] 是相对的不是绝对的。我们从头到尾都不知道也没必要知道每个 S[i] 到底是 0 还是 1我们只需要知道任意两个点之间的关系。这就像你不需要知道一群人身高的绝对值只需要知道谁比谁高——所有相对信息拼起来就足以判断新来的那个人到底站不站得下。这个相对而非绝对的特性是带权并查集能处理这类问题的根本原因。如果题目要求你求出每个 S[i] 的具体值那这个数据结构就撑不住了得换成别的思路。但幸运的是奇偶性约束从来只关心关系不关心绝对值。3.3 find 里的路径压缩顺序先递归后更新路径压缩是带权并查集里最容易写错的地方没有之一。普通并查集的压缩很简单把沿途所有点直接挂到根上就行。但带权版本不一样因为权值需要在压缩的过程中同步更新——原本 d[x] 记录的是 x 到父节点的关系压缩之后要变成 x 到根的关系。正确的写法是这样int find(int x) { if (fa[x] x) return x; int root find(fa[x]); // 第一步先让父节点完成压缩挂到根上 d[x] ^ d[fa[x]]; // 第二步此时 d[fa[x]] 已经是父到根的异或值 fa[x] root; // 第三步再把自己挂上去 return root; }顺序为什么不能换因为 d[x] 的更新依赖 d[fa[x]] 的新值。你必须先递归下去让父节点那一层先把路径压好d[fa[x]] 才会从父到祖父变成父到根。这时候你再用 d[x] ^ d[fa[x]]得到的才是 x 到根的关系。我见过最常见的错误写法是先把 fa[x] 改成 root再更新 d[x]。这样一改d[fa[x]] 取到的就是根节点自己的值通常为 0更新出来必然错。而且这种错误极其隐蔽小数据可能碰巧过大数据一挂一大片。3.4 合并的推导d[rx] d[x] ^ d[y] ^ w 是怎么来的当两个端点不在同一集合里时我们要把两个集合合并并且确定它们各自根之间的关系。这一步需要一点推导但推导本身很干净。假设 find(x) 得到根 rxfind(y) 得到根 ry此时 d[x] 是 x 到 rx 的异或值d[y] 是 y 到 ry 的异或值。这条边声明的是 x 和 y 之间的关系为 w也就是 val(x) xor val(y) w。我们想知道 rx 和 ry 之间应该是什么关系设它为 t即 val(rx) xor val(ry) t。把 val(x) 和 val(y) 分别用根来表示val(x) val(rx) xor d[x]val(y) val(ry) xor d[y]。代进去w val(x) xor val(y) d[x] xor val(rx) xor d[y] xor val(ry) d[x] xor d[y] xor t。把 t 解出来t d[x] xor d[y] xor w。于是合并就一行代码把 rx 挂到 ry 下面并令 d[rx] t。if (rx ! ry) { fa[rx] ry; d[rx] d[x] ^ d[y] ^ w; }有意思的是这个式子对方向是不敏感的。你把 ry 挂到 rx 下面写成 d[ry] d[x] ^ d[y] ^ w 也一样成立因为异或满足交换律t 的对称性让两种挂法都自洽。这一点在自查的时候很有用如果两种挂法推出来的式子长得不一样那一定是哪里推错了。3.5 同根时怎么判矛盾一行比较就够如果两个端点已经在同一个集合里说明它们之间的关系早就被前面的信息确定下来了而且这个关系就是 d[x] xor d[y]x 到根异或上 y 到根根的部分相互抵消。这时候只需要拿它和这条边声明的 w 比一下相等就无事发生继续往下走不等就说明出现了矛盾答案就是当前这条的编号减一。if (rx ry) { if ((d[x] ^ d[y]) ! w) { /* 矛盾输出 i-1 并结束 */ } }到这里整个算法的主体就齐了find 带权压缩、合并时算根的关系、同根时比关系。没有复杂的数据结构也没有花哨的技巧全部重量都压在建模和那几个递推式上。4. 十亿个位置怎么塞进数组离散化的正确姿势4.1 只保留真正出现过的端点n 可以大到十亿但我们真正关心的前缀下标只会出现在每条描述的端点里。每条描述贡献两个下标l-1 和 rm 条描述最多就是 2m 个不同的值。把它们全部收集起来、排序、去重就能得到一张紧凑的下标表。离散化的本质是重编号把稀疏但数值很大的原始下标映射成从 0 开始的一串连续整数。映射之后原来两点的关系完全保留因为我们只关心相等还是不等不关心具体数值。这也是为什么离散化对这类只有相对关系的题目特别适用——如果题目里出现了大小比较或者区间长度计算那就不能随便这么做了。提示离散化之前一定要先把 l-1 算出来再放进去不能只离散化 l 和 r回头再去查 l-1 的位置。4.2 那个 l-1 的坑顺序错了整道题都错这是我自己踩过的坑也是在评论区看到别人踩得最多的一个。原因很简单因为前缀和是 S[r] - S[l-1]参与运算的是 l-1 这个位置而不是 l。如果你先把所有的 l 和 r 丢进离散化数组回头再想查 l-1 的映射值那就只能二分查找一个可能根本不存在的值结果要么越界要么映射错位。正确做法非常直接在收集阶段就把 ql[i] - 1 和 qr[i] 两个值都放进数组。这样离散化之后任意一个参与过运算的下标都必然能在表里找到。这个坑之所以隐蔽是因为它不会报错只会让答案悄悄出错。小数据下你可能蒙混过关一到大样本就原形毕露。所以我建议你把先算 l-1 再离散化当成这条题目的肌肉记忆。4.3 完整实现与关键注释下面是我实际提交的版本C 编写读者可以对照着看每一步在做什么#include cstdio #include algorithm using namespace std; const int MAXM 5005; int n, m; int ql[MAXM], qr[MAXM], qw[MAXM]; int xs[MAXM 1], tot; // 离散化数组 int fa[MAXM 1], d[MAXM 1]; // 并查集父指针与权值 int find(int x) { if (fa[x] x) return x; int root find(fa[x]); // 先递归压好父节点 d[x] ^ d[fa[x]]; // 再用父到根的值更新自己 fa[x] root; return root; } int main() { if (scanf(%d%d, n, m) ! 2) return 0; tot 0; for (int i 1; i m; i) { char s[10]; scanf(%d%d%s, ql[i], qr[i], s); qw[i] (s[0] o) ? 1 : 0; // odd - 1, even - 0 xs[tot] ql[i] - 1; // 注意这里必须先算 l-1 xs[tot] qr[i]; } sort(xs, xs tot); tot unique(xs, xs tot) - xs; for (int i 0; i tot; i) { fa[i] i; d[i] 0; } for (int i 1; i m; i) { int x lower_bound(xs, xs tot, ql[i] - 1) - xs; int y lower_bound(xs, xs tot, qr[i]) - xs; int rx find(x), ry find(y); if (rx ry) { if ((d[x] ^ d[y]) ! qw[i]) { printf(%d\n, i - 1); // 第一个矛盾的编号减一 return 0; } } else { fa[rx] ry; d[rx] d[x] ^ d[y] ^ qw[i]; } } printf(%d\n, m); // 全部通过输出 m return 0; }代码里有两处容易被忽略的细节我单独拎出来说一下。第一处是qw[i] (s[0] o) ? 1 : 0;直接看首字母就能区分odd和even不需要完整字符串比较也不用担心大小写问题POJ 上的数据是全小写。第二处是输出的边界如果从头到尾都没出现矛盾答案是 m 而不是 m-1因为所有描述都能被满足。5. 跑通之后才发现这道题真正卡人的地方5.1 递归版 find 和迭代版 find 的取舍带权并查集的 find 一般都用递归写因为递归天然地完成了自底向上回溯更新这个过程。但它有个隐患路径长了会爆栈。这道题的总点数只有两万左右递归深度撑死也就这个量级所以实际跑起来没问题。不过如果你想把这道题当模板带走我建议还是老老实实用递归。原因在于迭代写法要在压缩过程中记录一整条路径然后再反向遍历更新权值逻辑复杂不少出错概率也高。为了省那点栈空间去写一个绕来绕去的迭代版性价比太低。真正需要担心爆栈的场景是点数达到百万级、而且有恶意构造的长链时那时再考虑按秩合并配合迭代压缩。5.2 为什么这道题必须先存后判不能边读边处理有个很自然的问题既然逻辑上是按顺序处理每条描述那我能不能读一条就处理一条发现矛盾立刻停答案是不能。因为离散化的前提是知道所有的端点你必须先把全部描述读完、收集完端点、做完排序去重才能开始处理。这意味着读入和处理被强制分成两个阶段中间夹着一次离散化。这个约束其实挺有意思它逼着你在写代码时先想清楚数据流。我见过一些实现一边读一边查映射表结果发现某个端点还没被加进表里只能现场插入再重新排序代码变得又长又脆。老老实实分两段走反而最清晰。5.3 内存和边界的几个小注意点数组大小要开到 2m 再加几个冗余位因为每条描述贡献两个端点m 条就是 2m 个候选值去重后只会更少但开数组时按最坏情况算最稳妥。我习惯写成MAXM 1再留一点余量这个习惯在竞赛里救过我不少次——多开的那几个元素不会浪费多少内存但少开一个就越界了。还有一点是初始化的时机。并查集和权值数组的初始化必须放在离散化之后因为此时才知道真实有多少个节点。如果你在离散化之前就把它们初始化到 2m 个虽然也能跑但会白白多做一堆无用功而且逻辑上不够干净。5.4 从这道题往外延伸的同类模型做完这道题我建议顺手把同一模型的几道变体也过一遍因为这类题的识别特征非常固定凡是给你一堆关于某两个位置关系的陈述问最多能成立多少条的基本都能往带权并查集上靠。具体的变体有把同奇偶/不同奇偶换成和相同/和不同把两点关系换成三点之间的捕食关系经典的种类并查集每个节点维护三种状态或者把关系值从 0/1 扩展到多个类别。它们的解法骨架完全一致只是权值的含义和合并时的运算规则稍有差别。你把这几种都写一遍就会发现它们其实是同一个东西换了件衣服。注意判断能不能用这个模型关键看两点——约束是不是二元关系以及这个关系是不是可传递且可合并。满足这两条八成就是它。6. 复盘这一题真正想训练的是什么能力回头再看这道题我觉得它的价值完全不在代码量上而在于它强制你走完了一整条建模链从区间统计到前缀和差值到模 2 意义下的异或再到带权并查集的关系维护。每一环都不难但把它们串起来的那根线是自己想出来的还是别人告诉你的完全是两种体验。我个人的经验是这类题最忌讳的就是看到题就搜题解。搜完之后你会觉得哦原来是这样然后合上页面过两天再做一遍还是不会。真正有效的方式是卡住的时候先别急着搜而是逼自己回答一个问题题目里的约束到底在描述什么把这句话用大白话写出来往往答案就浮出来了。这道题的大白话就是每个前缀要么和根一样要么和根不一样写到这一步带权并查集几乎是唯一的选择。最后一个实用建议这类题做完之后最好把核心的几行代码——带权 find、合并时的异或式、同根时的比较——单独抄到一个自己的模板文件里写清楚每行的含义。因为你在比赛里真正需要调用的就是这个骨架而不是整道题的题面。抄的过程也是复盘的过程抄过两三次之后这套东西就真正变成你自己的了。