凌晨一点我终于把牛客每日一题里标记了三天的“不点两面(hard version)”在tracker上划掉了。这题我第一天看题面觉得是个组合博弈第二天推了半天发现是个序列DP第三天才把线段树维护DP矩阵的细节调通。回头看它其实是那种非常典型的“easy版本很友好hard版本直接教你做人”的题目但只要你把状态定义和合并规则想清楚AC就是一晚上搞定的事。这篇复盘主要写给三类人一是正在备战笔试、面试的朋友这类带区间查询的DP题在牛客和各大厂笔试里越来越常见二是想系统维护刷题进度、用tracker管理每日一题的朋友我会把我自己的tracker字段设计、补题节奏一并分享出来三是单纯想看看hard version到底hard在哪的读者。先把题面、思路、完整代码和踩坑记录都摆清楚最后再聊聊tracker这套方法论怎么配合着用。1. 先看题这道“不点两面”到底在考什么1.1 题面里的“两面”是什么意思“不点两面”这个标题乍一看像麻将术语实际上它描述的是一个非常朴素的规则有一排n张牌每张牌有一个价值w[i]你可以决定“点”或者“不点”这张牌“点”了就拿到它的价值。但相邻的两张牌不能同时被点也就是说牌面上不能出现相邻两张同时翻面的情况——这就是“不点两面”的由来。这种说法听起来有点玄换成人话就是给你一个数组选一些位置要求被选中的位置两两不相邻求最大权值和。这个模型在DP题里太经典了很多朋友应该一眼就认出来了这就是带权最大独立集在一条链上的版本。easy version一般就是给你这个数组问一次全局答案O(n)的线性DP直接带走。但hard version不会这么温柔。它会在这个基础上加一个操作给你q次区间查询每次给定l和r问你数组在[l, r]这个子段上的最大权值和是多少。n和q的数量级都能到5×10^5这时候你不可能每次查询都从头到尾DP一遍那样复杂度是O(nq)直接爆炸。1.2 easy version 和 hard version 差在哪easy version的做法是维护两个变量遍历一遍数组就能得到答案。设f[i][0]表示前i个位置且第i个位置不选的最大价值f[i][1]表示前i个位置且第i个位置选的最大价值转移非常简单当前位不选f[i][0] max(f[i-1][0], f[i-1][1])当前位选f[i][1] f[i-1][0] w[i]最后答案取max(f[n][0], f[n][1])。这个递推是O(n)的但问题是它只能回答“整个数组的答案”没法回答“某个子段的答案”。你可能会想前缀和能不能搞不能因为最大权值和的DP结果不满足可减性f[r]的信息里并没有办法直接剔除f[l-1]之前的部分。这就要换个思路了如果把每个区间看成一个“状态转换器”那我们要找一种能把两个相邻区间拼起来的运算。这种运算一旦满足结合律就能用线段树来维护——每个线段树的节点存一个区间查询区间时把这些节点的“状态转换器”按顺序合并起来一次查询只要O(log n)。这就是hard version的核心考点动态DP的区间合并思想。2. 从线性DP到矩阵合并hard version的思路是怎么长出来的2.1 朴素DP只能过easy很多人拿到hard version的第一反应是“我能不能离线处理”或者“我能不能用莫队”。莫队确实可以维护DP的增量但这个题的查询是静态区间查询用莫队属于大炮打蚊子而且DP状态在增删端点时并不好维护因为删除一个元素会让整个DP结果重新计算。所以不要走莫队这条路正规解法就是线段树。那线段树节点里要存什么既然要支持合并单存一个“区间最大价值”肯定不够因为合并两个区间的时候需要知道左区间右端点是否被选以及右区间左端点是否被选否则没法判断中间相邻的两个位置是否冲突。于是很自然地每个区间要按左右端点的选择状态分成四种情况来存。2.2 为什么线段树能维护DP线性DP能被线段树维护本质上是因为DP的转移可以看成一种“半环”上的矩阵乘法。你从左到右扫描数组每到一个位置就做一次状态转移而线段树的每个叶子节点其实就存着“从空区间到包含这一位的区间”的状态转移矩阵。两个相邻区间合并就等于两个转移矩阵相乘。矩阵乘法天然满足结合律所以线段树的区间合并是合法且高效的。这个思想比这道题本身重要得多。它被称为“动态DP”在很多题目里都有变体最大子段和可以用线段树维护本质也是把子段合并看成一个半群运算树上带修改的DP可以用树链剖分配合矩阵乘法来做。理解了这里以后再遇到“带修改的DP”或者“区间查询的DP”就有底了。2.3 四个状态怎么定义合并公式怎么推我给每个线段树节点定义四个值分别表示这个区间在不同端点状态下的最大价值dp00左端点不选右端点不选dp01左端点不选右端点选dp10左端点选右端点不选dp11左端点选右端点选注意这里的“端点选”指的是区间的左右边界位置有没有被选中。对一个叶子节点只有一个位置来说如果我们不选这个位置那么它的左端点和右端点都是不选状态所以只有dp000是合法状态如果我们选这个位置那它既是左端点又是右端点所以dp11w[i]合法。而dp01和dp10在这种“区间只有一个点”的情况下是不可能出现的因为同一个点不可能左端不选、右端选。所以叶子节点的初始化是node.dp00 0; node.dp01 -INF; node.dp10 -INF; node.dp11 w[l];现在关键来了怎么把两个相邻区间合并。假设左区间是L右区间是R它们相邻的位置是L的右端点和R的左端点。根据题意这两个位置不能同时被选所以在枚举左右状态组合时必须排除“L右端点1且R左端点1”的组合。举个例子合并结果的状态定义为结果区间的左端点状态和右端点状态。结果区间的左端点就是L的左端点结果区间的右端点就是R的右端点所以合并公式要遍历L左端状态、L右端状态、R左端状态、R右端状态四个维度但中间的冲突只发生在L右端和R左端。写出来就是res.dp00 max({L.dp00 R.dp00, L.dp00 R.dp10, L.dp01 R.dp00}); res.dp01 max({L.dp00 R.dp01, L.dp00 R.dp11, L.dp01 R.dp01}); res.dp10 max({L.dp01 R.dp00, L.dp01 R.dp10, L.dp11 R.dp00}); res.dp11 max({L.dp01 R.dp01, L.dp01 R.dp11, L.dp11 R.dp01});为什么每个公式只有三项因为每种结果状态下中间冲突组合最多有三个合法方案。比如dp00要求结果左端不选、右端不选那L的左端状态必须是0R的右端状态必须是0此时L的右端状态和R的左端状态可以是(0,0)、(0,1)、(1,0)但(1,1)会被排除所以正好三项。这份合并代码是整个题的核心写的时候一定要保证每个状态都枚举到了漏一项都可能导致WA。3. 完整实现查询一个区间只要O(log n)3.1 代码骨架build query merge当四个状态和合并函数都确定之后剩下的就是线段树的常规操作了。我用的是数组实现的线段树建树和查询都很直观直接上完整代码#include bits/stdc.h using namespace std; typedef long long ll; const ll INF 4e18; const int MAXN 500005; struct Node { ll dp00, dp01, dp10, dp11; }; int n, q; ll w[MAXN]; Node tree[MAXN 2]; Node mergeNode(const Node L, const Node R) { Node res; res.dp00 max({L.dp00 R.dp00, L.dp00 R.dp10, L.dp01 R.dp00}); res.dp01 max({L.dp00 R.dp01, L.dp00 R.dp11, L.dp01 R.dp01}); res.dp10 max({L.dp01 R.dp00, L.dp01 R.dp10, L.dp11 R.dp00}); res.dp11 max({L.dp01 R.dp01, L.dp01 R.dp11, L.dp11 R.dp01}); return res; } void build(int p, int l, int r) { if (l r) { tree[p].dp00 0; tree[p].dp01 -INF; tree[p].dp10 -INF; tree[p].dp11 w[l]; return; } int mid (l r) 1; build(p 1, l, mid); build(p 1 | 1, mid 1, r); tree[p] mergeNode(tree[p 1], tree[p 1 | 1]); } Node query(int p, int l, int r, int ql, int qr) { if (ql l r qr) { return tree[p]; } int mid (l r) 1; if (qr mid) return query(p 1, l, mid, ql, qr); if (ql mid) return query(p 1 | 1, mid 1, r, ql, qr); Node left query(p 1, l, mid, ql, mid); Node right query(p 1 | 1, mid 1, r, mid 1, qr); return mergeNode(left, right); } int main() { scanf(%d%d, n, q); for (int i 1; i n; i) scanf(%lld, w[i]); build(1, 1, n); while (q--) { int l, r; scanf(%d%d, l, r); Node ans query(1, 1, n, l, r); ll res max({ans.dp00, ans.dp01, ans.dp10, ans.dp11}); printf(%lld\n, res); } return 0; }这里我偷了个懒mergeNode里的max用了C11的initializer_list写法编译器要支持C11以上。如果不放心可以改成嵌套max效果一样。查询时如果区间跨越了mid先查左区间再查右区间最后按原顺序合并这个顺序不能反因为相邻关系有方向。3.2 几个必须注意的实现细节第一个细节是负无穷的选择。不要用int的最小值因为会有加法运算两个合法状态相加可能得到很大的负数如果用-0x3f3f3f3f这种级别万一某个非法状态被加了两次变成负数仍然可能被max误选。稳妥的做法是用-4e18这种数值或者干脆用long long的最小值除以4。我习惯用-4e18因为任何合法状态都不会小于这个数量级而且两个负数相加也不会溢出到让人觉得合法。第二个细节是单点区间状态。有些朋友写叶子节点时会习惯把所有状态初始化成0认为“空区间”就是全0这在最大子段和里没错但在这里不行。原因刚才说过单点选的时候dp11是w[i]单点不选的时候dp00是0dp01和dp10这两种“左端点不选、右端点选”的状态在长度为1的区间里没有物理意义必须置为负无穷。如果你把它们全置成0查询单点区间时会错误地得到一个0价值的解。第三个细节是无符号溢出和类型。w[i]可能是负数加上q次查询的结果也要用long long所以所有状态我都用long long。遇到最坏情况比如n5e5、每个w[i]1e9单个区间的最大价值能到2.5e14int绝对装不下。这个属于一眼就能看出来的坑但还是值得提醒一句。4. 复杂度、评测考量与一道hard题的完整验证流程4.1 复杂度估算建树复杂度是O(n)每次区间查询会访问线段树上O(log n)个节点每个节点的merge是常数时间所以单次查询是O(log n)总复杂度O((n q) log n)。n和q都是5×10^5时log n大概是19总操作量大约两千万次C跑下来非常稳。这里要注意的是线段树常数其实不大但如果你用了递归查询注意开编译优化否则某些牛客的评测机上可能卡在边界时间上。再算空间tree数组开4倍n每个Node包含4个long long也就是32字节4 × 5e5 × 32 64MB。牛客一般给256MB完全够用。但如果哪天遇到内存给得紧的题可以把四个状态压缩成两个数组或者用结构体的时候注意对齐不过这就是锦上添花了。4.2 覆盖hard version的边界测试写完之后不要急着交先造几组数据自测。我的自测顺序是这样的全正数数组比如[1, 2, 3, 4, 5]整段查询应该得到9选2和4或选1、3、5。全负数数组比如[-1, -2, -3]答案应该是-1因为最优解是只选最大的那个负数不能选空集。单点区间查询l等于r时答案应该是w[l]和0之间的较大值。等等这里有个逻辑要小心题意是“你可以决定点或者不点”在单点查询时不点就是0点了就是w[l]。但如果全负数答案是0还是负数“不选任何牌”是合法解吗这取决于题面是否允许空集。我做的这个版本是允许不点任何牌的所以单点全负数答案应该是0而不是那个负数。如果题面要求至少选一张那答案就是max(w[l], -INF)之类边界会不一样。大家交题前一定要确认这一点不同题目对空集的处理差异很大。两个元素时[5, -100]整段查询应该选5不能两个都选所以答案是5[5, 6]则选6。我在本地用暴力DP对拍了20组随机数据n取到10q取到20每一次随机l和r把线段树查询结果和直接DP结果对比全部一致才交。这个小流程值得养成习惯写hard题不拍一拍总觉得自己在赌评测机。5. 用tracker管理每日一题顺便聊聊我补完这题的流程5.1 tracker表怎么设计说回“牛客tracker”这个话题。很多朋友刷题靠的是“今天打开牛客做一题做完关掉”但这种模式对hard题很不友好因为hard题往往不是30分钟能搞定的。我自己从去年开始维护一个刷题tracker其实就是一张表格但字段设计花了一点心思日期题目标题题目编号难度算法标签状态补题日期复盘链接备注2025-01-10不点两面(hard version)牛客每日一题hardDP、线段树补题完成2025-01-13本篇文章卡在合并状态2025-01-09某题牛客每日一题mid前缀和AC---这个表格的核心思想是“同一道题要出现三次才算真正结束”第一次出现是当天第一次写不管写没写出来第二次是补题时间第三次是复盘时间也就是写题解或对拍验证的时候。hard题尤其需要这种节奏因为你当天写不出来很正常但如果不把它留在tracker里下周就彻底忘了自己还欠着一道题。我用的是Notion表格配合一个简单的按状态筛选视图status列为“待补”的题会单独列出来每天打开先看这个视图。如果你习惯本地文件用CSV或Markdown表格也一样重点不是工具而是“有记录、有状态、有补题触发机制”。5.2 遇到hard题的正确打开姿势我自己从这道题里总结的hard题处理流程是这样的拿到题先花15分钟想想不出来不要硬磕把题目标题、算法方向猜测、卡住的点记进tracker然后去干别的事。第二天再花15分钟重新读题不写代码只推导状态定义和转移。这一道“不点两面”我第一次就卡在了“怎么把两个区间的DP合并”上第二天换了个思路去想“如果我能拿到所有子区间的四个状态能不能拼出答案”一下就通了大半。所以大家如果tracker里堆了一堆hard题没补别焦虑。把状态从“未补”改成“尝试中”给自己设个15分钟限制比硬坐两小时效率高得多。第三天的复盘环节试着把题面、自己的思路、最终解法浓缩成三行写进备注——这个过程才是tracker给刷题带来的最大价值。6. 我在调试这道题时踩过的坑6.1 合并时漏掉中间状态第一次写mergeNode的时候我天真地以为“dp00 dp00”就代表中间两个都不选“dp11 dp11”代表中间两个都选但不合法所以只写了合法的三项。结果漏了dp01dp01这种组合。比如左区间右端不选、右区间左端不选但结果区间的两端都是选状态这种方案在计算dp11时是可能产生更大价值的。当时不分青红皂白把所有“中间有一个选”的组合都排除了导致答案偏小。后来我把所有16种组合列出来标注哪些合法哪些非法才发现合法组合每种状态都是3个。强烈建议第一次接触这类线段树DP矩阵的朋友手写一个26行的小表横轴是L右端状态纵轴是R左端状态标出(1,1)非法其余合法然后逐个枚举结果状态。这个表写一次就再也不会搞混了。6.2 初始化与精度/类型问题另一个让我WA了两发的坑就是负无穷。第一次我用的-0x3f3f3f3f在单点查询、权值都是负数时非法状态和合法状态相加后出现了“假合法”的值导致答案出错。后来我把所有状态打印出来才发现某个非法状态被其他状态加了好几次负无穷被“稀释”成了一个小负数反而成了最大值。解决方式就是用-4e18保证任何合法运算都无法超过它。还有个很容易忽略的点w[i]可能是负数且很大如果你用int读入后续比较和加法都会出问题。这种题一眼看上去是DP实际上藏着对类型敏感的考察直接全开long long是最省心的。6.3 若干变体环和带修把这个题再往深处走一层它还有很多变体值得你在tracker里标注。比如数组变成环形首尾相邻不能同时选做法是枚举第一个位置选或不选分别做两次线段树查询取较大值。又比如把“相邻不能同时选”改成“相邻不能同时不选”那就是另一个DP问题但整体的矩阵维护框架不变。再比如支持单点修改w[i]那只需要在线段树上update一个位置还是O(log n)。这些变体都围绕同一个核心当你发现一个DP可以被表示成“区间状态合并”那么线段树就是你天然的武器。我每次遇到这类题都会在tracker备注里写上“动态DP/矩阵线段树模板题”方便以后复习时快速定位。最后分享一个实用的复盘习惯写完hard题强迫自己再写一遍“一句话题解”比如这道题就是“每个节点存四种端点状态的DP值合并时排除左右相邻同时取用线段树保证区间查询复杂度”。这句话看起来简单但它能帮你把一道题抽象成模式下次再遇到就不会慌。这套“题面拆解→状态设计→线段树合并→边界对拍→tracker复盘”的打法我现在已经用在所有hard题上了。说不上有多高效但至少每天打开tracker的时候不会一眼望去全是没补的红标。这道“不点两面”总算被我亲手点掉了下一个hard题正在排队呢。