1. 项目概述从“跳石头”到图论建模最近在带学生备赛蓝桥杯刷到这道P10914“跳石头”发现它是个非常典型的图论建模问题但内核又比普通的DFS/BFS搜索多了一层“集合去重”的思考。题目描述了一个简单的游戏规则一排编号1到n的石头每块石头i有一个权值c_i。你站在石头j上可以跳到石头j c_j如果不超过n或者跳到石头2j如果不超过n。游戏从某块石头x开始所有可能被经过的石头注意是“可能”意味着存在至少一条从x出发能到达该石头的路径的权值构成一个集合S_x得分就是这个集合的大小|S_x|。你需要找到从哪块石头开始能获得最大的得分。初看这题很多同学会下意识地想“这不就是从一个起点出发在图上做DFS或BFS把所有能到达的点找出来然后统计它们权值的不重复个数吗”这个思路方向是对的但直接这么干在n最大40000的情况下如果对每个起点都做一次完整的图遍历时间复杂度会爆炸。我们需要更聪明的办法。这道题的精髓在于它虽然要求我们枚举所有可能的起点但整个跳跃规则构建出的图结构是有规律的我们可以利用动态规划DP或记忆化搜索从后往前递推一次性算出所有起点的答案将复杂度降到O(n)或O(n log n)级别。接下来我就结合C实现拆解一下这道题的解题思路、核心算法以及编码中的那些坑。2. 核心思路拆解与算法选型2.1 问题本质可达性分析与权值集合首先我们要彻底理解题目在问什么。得分不是路径上权值之和也不是最长路径而是从起点x出发所有可能到达的节点的权值集合的大小。这里有两个关键点“可能”到达只要存在一条从x到石头y的路径无论这条路径怎么跳那么石头y就算被“经过”了。这意味着我们需要计算的是节点的可达性而不是某一条特定路径。权值集合多个不同的节点可能拥有相同的权值但得分只计算一次。所以我们最终关心的是所有可达节点的权值种类数。因此问题的核心可以分解为两步对于每个起点x计算出所有从x出发可达的节点集合然后统计这些节点对应权值的不重复数量。2.2 暴力搜索的局限性最直接的暴力方法是对于每个起点i (1 i n)执行一次图遍历DFS或BFS标记所有能从i到达的节点然后遍历这些节点用一个setint或unordered_setint来记录权值最后集合的大小就是得分。再取所有得分的最大值。我们来估算一下复杂度。对于每个起点最坏情况下可能需要遍历整个图虽然由于跳跃规则限制图是稀疏的。假设平均每个节点能到达m个其他节点那么一次遍历的复杂度是O(m)。对于n个起点总复杂度就是O(n * m)。在n40000时如果m也接近n那就是O(n²) ≈ 1.6e9显然会超时。题目给了20%的数据n20可能就是给暴力搜索留的活路但要想AC必须优化。2.3 优化方向记忆化搜索与逆向思维暴力法之所以慢是因为它做了大量重复计算。考虑两个起点x和y如果从x出发能到达y那么从x出发能到达的所有节点一定也包含从y出发能到达的所有节点因为到了y之后你可以继续从y开始的所有可能跳跃。更一般地这个跳跃关系构成了一个有向图。如果我们定义reachable[i]为一个集合表示从石头i出发所有可能到达的节点集合那么对于任意一条边 i - j都有reachable[i]包含{i} ∪ reachable[j]。这启发我们可以用记忆化搜索Memoization或动态规划DP的思路从后往前或者用DFS记忆化来计算每个节点的reachable集合。但直接存储集合本身仍然可能很大导致空间和时间开销大。进一步观察我们最终需要的不是节点集合而是权值集合的大小。而且权值c_i的范围也是1到n。一个更巧妙的思路是我们能否直接计算出从每个节点i出发能收集到的不同权值有哪些这里需要引入状态压缩的思想。因为n40000我们无法用一个长度为n的bool数组来为每个起点存储所有可能的权值那样是O(n²)空间。但是我们可以换一个角度用位运算或布尔数组记录“当前从某个节点出发已经覆盖了哪些权值”但这在传递时依然复杂。实际上更普适且清晰的思路是先构建整个图的可达性关系再利用“可达性”来推导“权值可达性”。具体有两种主流方法传递闭包 权值统计计算出图的传递闭包即任意两点是否可达然后对于每个起点i将所有可达点j的权值c_j加入集合。但计算传递闭包例如用Floyd-Warshall是O(n³)完全不可行。由于图是稀疏的且有特殊结构我们需要更高效的闭包计算。记忆化搜索 集合合并用DFS从每个未访问的节点开始搜索在回溯过程中将后继节点的可达权值集合合并到当前节点。合并操作尤其是集合去重是开销所在。考虑到n40000c_in一个可行的优化是用bitset来表示一个节点可达的权值集合。bitsetN可以在常数时间内进行位运算如或运算|合并两个集合非常快。N40001的bitset大小约为40001/8 ≈ 5KB。对于40000个节点如果每个节点都存一个bitset总内存约40000 * 5KB ≈ 200MB这通常超过了竞赛题目的内存限制通常256MB或512MB。但我们可以利用动态bitset如vectorbool或更紧凑的表示方法不过实现起来较复杂。2.4 最终算法确定反向建图 BFS/DFS 差分思想我查阅了网上一些AC的题解并结合自己的思考发现这道题有一个被忽略的突破口跳跃规则是确定的从每个点出发的出边最多只有两条jc_j 和 2j。因此整个图是一个每个节点出度最多为2的有向图。对于这样的图我们可以考虑反向建图。什么是反向建图原图是如果从j能跳到k就有一条边 j-k。反向建图则是如果从j能跳到k我们建立一条边 k-j。这意味着在反向图中如果有一条边 k-j表示从j可以到达k在原图中。为什么要反向建图因为题目要求的是“从x出发能到达哪些点”这等价于“在反向图中从哪些点出发能到达x”。但这样似乎没简化问题。关键点在于如果我们能预处理出所有节点通过反向边能到达的节点即原图中能到达它的节点然后利用这些信息来快速计算每个起点的得分吗一个精妙的做法是从后往前动态规划。定义dp[i]为一个bitset或布尔数组表示从节点i出发能访问到的权值集合用一个位掩码表示。但如前所述直接存bitset可能内存过大。更进一步的优化是我们并不需要为每个节点存储完整的权值集合只需要知道从该节点出发能访问到的权值种类数。但这样在合并时无法去重。实际上本题最简洁高效的AC解法是进行一遍DFS或BFS但配合一个全局的访问标记数组并利用递归返回值来传递信息。然而由于图可能有环比如从i跳到j又从j跳回i直接DFS会陷入死循环需要处理环。综合来看一个经过验证的可行算法步骤如下建图根据规则为每个节点i建立两条有向边i - ic_i (如果ic_i n) 和 i - 2i (如果2i n)。计算可达节点集对于每个节点i我们需要知道从i出发能到达的所有节点。这可以通过对每个节点i进行BFS/DFS实现但这样是O(n²)。优化方法是进行一次拓扑排序如果图是无环的或强连通分量缩点如果图有环。但我们的图由于有边i-2i很可能存在环例如1-2-4-1? 不一定但需要检查。实际上由于c_i是正整数且跳跃总是向编号更大的节点ic_i i, 2i i 当 i1所以这个图是一个有向无环图DAG因为每条边都是从编号小的节点指向编号大的节点。这是一个非常重要的性质在DAG上动态规划既然图是DAG我们就可以按照节点编号从大到小的顺序进行动态规划。定义f[i]为一个集合表示从节点i出发能经过的节点的权值集合。由于是DAG我们可以从后往前从n到1递推初始化f[i]为只包含自身权值c_i的集合。对于节点i它的后继节点是j1 i c_i(如果n) 和j2 2*i(如果n)。那么从i出发能经过的权值集合等于{c_i}并上f[j1]并上f[j2]如果后继存在。即f[i] {c_i} ∪ f[j1] ∪ f[j2]。集合的表示与合并我们需要高效地合并集合。由于权值范围是1~n我们可以用一个bitset来表示集合。bitset40001 f[i]表示集合第k位为1表示权值k在集合中。那么合并操作就是位或运算f[i] f[i] | f[j1] | f[j2]。同时设置f[i][c_i] 1。统计答案计算完所有f[i]后f[i].count()就是从i出发的得分。遍历所有i取最大值即可。复杂度分析时间我们需要处理n个节点每个节点最多合并两个bitset。bitset的位或运算可以认为是O(N/word_size)在C中bitset的位运算通常被优化为O(N/64)。N40001所以一次合并约625次64位运算。对于每个节点进行两次合并总运算量约为n * 2 * (40001/64) ≈ 40000 * 2 * 625 50,000,000次操作在1秒内可以完成。空间需要存储n个bitset每个约5KB总内存约200MB。这处于极限边缘但通常蓝桥杯环境的内存限制可能为256MB或512MB200MB是可行的但有些风险。如果内存超限我们可以尝试用vectorbitset40001但实际内存占用差不多。一个更好的优化是**由于我们是从后往前递推当计算完f[i]后f[j](ji) 可能不再需要但f[i]在计算更小的i时可能还需要因为边指向更大的j。所以不能立即释放。内存是主要瓶颈。注意这是基于bitset的解法。在实际竞赛中如果内存限制较紧如128MB可能需要更节省内存的方法例如用vectorint存储每个节点可达的权值列表并用哈希表去重但合并操作会更耗时。或者可以采用BFS从每个节点出发但用一个全局的bitset作为访问标记标记权值但这样需要n次BFS每次BFS重置bitset时间复杂度O(n²/64)可能也能勉强通过40000*40000/64 ≈ 25e6次位操作但不如DP优雅。考虑到蓝桥杯国赛的难度和常见环境bitset解法是通行的。下面我们就按照这个思路来实现。3. 代码实现与逐行解析3.1 数据结构定义与输入处理首先我们包含必要的头文件并定义最大常数。由于n最大40000权值c_i也n我们把bitset的大小设为40001索引从1到40000。#include iostream #include vector #include bitset #include algorithm using namespace std; const int MAXN 40005; // 稍微开大一点防止边界问题 int main() { int n; cin n; vectorint c(n 1); // 权值数组下标从1开始 for (int i 1; i n; i) { cin c[i]; } // 后续代码... }这里定义c数组时大小是n1是为了让下标从1开始与题目描述一致。3.2 核心DP数组初始化我们需要一个vector来存储每个节点的bitset。注意bitset的大小必须在编译时确定所以我们用bitsetMAXN其中MAXN40005。vectorbitsetMAXN f(n 1); // f[i] 表示从节点i出发能经过的权值集合 // 初始化每个节点至少能经过自身的权值 for (int i 1; i n; i) { f[i].set(c[i]); // 将c[i]对应的位设为1 }bitset的set(pos)函数将第pos位设置为1。注意bitset的位索引默认从0开始但我们的权值范围是1~n所以直接使用c[i]作为索引是没问题的因为c[i]1。当然更严谨的做法是f[i].set(c[i])这会将第c[i]位设为1。3.3 动态规划递推过程由于图是DAG边从小节点指向大节点我们可以从大到小遍历节点i这样当处理节点i时它的后继节点ic[i]和2*i如果存在一定大于i它们的f值已经计算好了。for (int i n; i 1; --i) { // 处理第一种跳法跳到 i c[i] int j1 i c[i]; if (j1 n) { f[i] | f[j1]; // 合并集合位或运算 } // 处理第二种跳法跳到 2*i int j2 2 * i; if (j2 n) { f[i] | f[j2]; } }这里的关键操作是f[i] | f[j1]这是一个bitset的位或赋值操作效果是将f[j1]中所有为1的位在f[i]中也设为1。这样就实现了集合的合并。注意我们之前已经将f[i]的c[i]位设为1所以这里不需要再额外添加自身权值。重要细节为什么从后往前遍历 因为对于任意节点i它的后继节点j1 ic[i] 和 j2 2*i 都满足 j1 i 且 j2 i当i1时。所以当我们从in开始递减遍历到1时对于当前的i它的后继节点j1和j2的编号都大于i因此它们的f值已经在之前的迭代中计算完成了。这满足了动态规划的“无后效性”。3.4 统计答案并输出递推完成后f[i]这个bitset中1的个数就是从节点i出发能获得的分值。我们遍历所有i找出最大值。int ans 0; for (int i 1; i n; i) { int score f[i].count(); // 计算bitset中1的个数即集合大小 if (score ans) { ans score; } } cout ans endl;bitset的count()函数返回其中设置为1的位的数量时间复杂度是O(N/word_size)对于40001位来说很快。3.5 完整代码整合将以上部分整合得到完整代码#include iostream #include vector #include bitset #include algorithm using namespace std; const int MAXN 40005; // 预留一点空间 int main() { ios::sync_with_stdio(false); cin.tie(nullptr); // 加速输入输出 int n; cin n; vectorint c(n 1); for (int i 1; i n; i) { cin c[i]; } // dp数组f[i]是一个bitset表示从i出发能经过的权值集合 vectorbitsetMAXN f(n 1); // 初始化每个节点至少能经过自身的权值 for (int i 1; i n; i) { f[i].set(c[i]); } // 从后往前DP因为图是DAG边从小节点指向大节点 for (int i n; i 1; --i) { int j1 i c[i]; if (j1 n) { f[i] | f[j1]; } int j2 2 * i; if (j2 n) { f[i] | f[j2]; } } // 统计答案 int ans 0; for (int i 1; i n; i) { ans max(ans, (int)f[i].count()); } cout ans endl; return 0; }4. 算法正确性证明与边界情况4.1 为什么这个DP是正确的我们需要证明按照上述递推公式计算出的f[i]确实等于从节点i出发所有可能经过的节点的权值集合。定义设S(i)为从节点i出发所有可能经过的节点的权值集合。归纳基础对于节点i如果它没有出边即ic[i] n且2*i n那么从i出发只能停留在i所以S(i) {c[i]}。我们的初始化f[i].set(c[i])正好对应这一点。归纳步骤假设对于所有编号大于i的节点jf[j]已经正确计算并等于S(j)。考虑节点i它最多有两个后继j1 ic[i]和j2 2*i。从i出发第一步有两种选择跳到j1或跳到j2如果合法。如果跳到j1那么之后所有可能经过的节点就是从j1出发能经过的节点同理如果跳到j2之后所有可能经过的节点就是从j2出发能经过的节点。此外无论怎么跳起点i本身也会被经过。因此从i出发所有可能经过的节点集合是{i}加上 从j1出发能经过的节点 加上 从j2出发能经过的节点。对应的权值集合就是{c[i]}∪S(j1)∪S(j2)。根据归纳假设f[j1] S(j1),f[j2] S(j2)。而我们递推中的操作f[i] | f[j1]; f[i] | f[j2];在已经设置f[i][c[i]]1的基础上正好计算了这个并集。所以f[i]也正确。由于我们是从大到小遍历i所以归纳假设成立DP正确。4.2 边界情况与注意事项数组越界在访问j1 i c[i]和j2 2*i时必须检查是否小于等于n。我们的代码中用了if (j1 n)和if (j2 n)来保护。权值作为bitset索引权值c[i]的范围是1~n我们直接用c[i]作为bitset的索引。这要求bitset的大小至少为n1。我们定义了MAXN40005足够容纳。内存使用这是本解法最大的潜在问题。vectorbitsetMAXN f(n1)占用的内存大约是(n1) * (MAXN/8) bytes。代入n40000, MAXN40005约为40001 * 5000 ≈ 200MB。这接近但通常不超过蓝桥杯国赛的内存限制常为256MB。如果担心内存超限可以尝试用bitset40001而不是bitsetMAXN但这样需要确保n40000。或者可以使用vectorbool来模拟bitset但vectorbool不是标准容器位操作可能慢一些。时间复杂度DP循环是O(n)每次循环中进行两次bitset的位或运算。bitset的位或运算复杂度是O(N/word_size)即O(40000/64)≈O(625)。所以总时间大约是40000 * 2 * 625 ≈ 50,000,000次位操作这在2秒内通常可以完成。5. 性能优化与替代方案虽然上述bitsetDP解法是主流且易于理解的但在极端情况下内存限制更紧或n更大时可能需要优化。这里讨论几种变体5.1 使用vectorbool替代bitsetbitset的大小必须在编译时确定这不够灵活。我们可以用vectorbool来动态创建位集每个vectorbool只存储从该节点出发可达的权值集合。但vectorbool的位运算不支持直接对整个容器进行位或需要手动循环或者用std::transform但效率可能较低。vectorvectorbool f(n 1, vectorbool(n 1, false)); // 初始化 for (int i 1; i n; i) f[i][c[i]] true; // DP递推 for (int i n; i 1; --i) { int j1 i c[i], j2 2 * i; if (j1 n) { for (int k 1; k n; k) { if (f[j1][k]) f[i][k] true; } } if (j2 n) { for (int k 1; k n; k) { if (f[j2][k]) f[i][k] true; } } } // 统计答案 int ans 0; for (int i 1; i n; i) { int cnt 0; for (int k 1; k n; k) cnt f[i][k]; ans max(ans, cnt); }这种方法的复杂度是O(n²)对于n40000来说是16亿次操作显然会超时。所以不可取。5.2 BFS/DFS 全局权值标记另一种思路是从每个节点i开始做BFS或DFS用一个全局的bool visited[N]数组来标记本次搜索中哪些权值已经出现过。每次BFS前清空visited数组。统计本次搜索中访问到的不同权值数量。vectorint c(n1); vectorvectorint graph(n1); // 邻接表 // 建图 for (int i 1; i n; i) { if (i c[i] n) graph[i].push_back(i c[i]); if (2 * i n) graph[i].push_back(2 * i); } int ans 0; vectorbool visited_val(n1, false); // 标记权值是否已计入 for (int start 1; start n; start) { fill(visited_val.begin(), visited_val.end(), false); queueint q; q.push(start); visited_val[c[start]] true; int count 1; // 至少包含起点权值 while (!q.empty()) { int u q.front(); q.pop(); for (int v : graph[u]) { if (!visited_val[c[v]]) { visited_val[c[v]] true; count; } q.push(v); // 注意即使权值已访问过节点仍需入队继续探索因为可能通过该节点到达其他权值未访问的节点 } } ans max(ans, count); }这个算法的时间复杂度是O(n * (VE))其中V是节点数E是边数。最坏情况下每个节点都可达几乎所有其他节点所以近似O(n²)也会超时。但我们可以加上节点访问标记来剪枝如果某个节点已经被访问过那么从该节点出发能到达的权值集合已经被合并到当前集合中可以不再重复探索。然而由于我们关心的是权值集合即使节点被访问过它的权值可能已经被记录但通过它可能到达的新节点权值未记录仍需探索。所以不能简单用节点访问标记来剪枝。因此BFS方法在n40000时难以通过。5.3 基于拓扑排序的DP既然图是DAG我们可以先进行拓扑排序然后按照拓扑序从后往前DP。不过由于节点编号天然满足拓扑序边从小节点指向大节点所以直接按编号从大到小遍历就是拓扑序不需要显式进行拓扑排序。我们的解法已经利用了这一点。5.4 内存优化技巧如果内存是瓶颈我们可以尝试不存储所有节点的完整bitset而是用时间换空间。例如对于每个节点i我们只存储一个vectorint表示从i出发能到达的权值列表并在合并时去重。但合并两个列表并去重的时间复杂度较高。或者我们可以用哈希表unordered_set来存储权值集合但内存开销也不小。一个折中的方案是使用bitset但分批处理。例如将权值范围分成若干块比如每块大小1000对每块分别进行DP。具体地我们进行多次DP每次只关心权值在某个区间内的节点。最后合并结果。但这样需要多次遍历时间可能增加。考虑到蓝桥杯的环境bitset解法在大多数情况下是可以通过的。如果遇到内存超限可以尝试将bitset改为vectorbool但使用引用或指针来减少拷贝或者尝试用int数组模拟位运算。6. 常见错误与调试技巧在实现和调试这道题时我遇到过一些典型的错误这里列出来供大家参考数组下标越界这是最常见的错误。在计算j1 i c[i]和j2 2*i时一定要检查是否 n。另外c数组和f数组的大小应该是n1索引从1开始。bitset大小不足bitsetN的N必须是一个编译时常量且N要大于等于可能出现的最大权值即n。如果n40000那么N至少需要40001。建议定义为const int MAXN 40005;留一点余量。DP顺序错误必须从后往前从n到1遍历。如果从前往后遍历当计算f[i]时它的后继节点f[j1]和f[j2]可能还没有计算因为j1, j2 i导致使用未初始化的值。忘记初始化自身权值在DP开始前必须将每个f[i]的c[i]位设为1。否则如果某个节点没有出边它的得分会被错误地计算为0。内存超限如果使用vectorbitsetMAXN f(n1)请估算内存。40000 * 40000 bit ≈ 200MB。如果题目内存限制是128MB可能会超。这时可以考虑用short或bool数组来存储每个节点可达的权值集合但需要更复杂的压缩。输出格式错误题目要求输出一个整数不要输出多余的空格或换行。输入读取优化对于n40000输入量不大但使用ios::sync_with_stdio(false); cin.tie(nullptr);可以加速输入输出避免卡常。调试技巧可以先用小数据测试比如n5手动模拟DP过程验证结果是否正确。对于每个节点i可以输出f[i].count()检查得分是否合理。如果怀疑DP顺序可以打印出每个节点i的后继节点j1和j2确保j1, j2 i。如果内存或时间超限可以尝试用bitset的test()和set()函数来验证位操作是否正确。7. 总结与扩展思考这道“跳石头”题目看似是一个简单的游戏模拟实则考察了对图论模型的抽象能力、对DAG上动态规划的应用以及对bitset优化集合运算的掌握。通过这道题我们可以学到问题转化将游戏规则转化为有向图将得分计算转化为节点可达性与权值集合的并集。利用图的性质识别出图是DAG因为边总是从小节点指向大节点从而可以使用基于拓扑序的DP。bitset优化当需要频繁合并集合且集合元素是有限范围内的整数时bitset可以通过位运算在常数时间内完成合并极大提高效率。这是处理状态压缩和集合运算的利器。时空权衡bitset解法用较大的内存约200MB换取了较低的时间复杂度约5e7次位操作。在竞赛中这种权衡往往是必要的。扩展思考如果跳跃规则改变比如可以往回跳例如跳到j - c[j]那么图就可能包含环。这时就需要先用强连通分量SCC算法缩点将环缩成一个点然后在DAG上DP。如果权值范围很大比如10^9就不能用bitset了。这时可能需要用哈希表unordered_set来存储集合但合并操作会更耗时。或者可以离线处理用并查集维护连通性再统计每个连通分量内不同权值的数量。如果题目问的不是最大得分而是从每个起点出发的得分那么我们的DP已经计算出了所有起点的得分直接输出即可。最后在竞赛中遇到这类题目关键是先分析数据范围再选择合适的算法。对于n40000O(n²)的暴力通常不可行必须寻找O(n log n)或O(n * bit)的优化。bitsetDP是一个非常重要的技巧值得熟练掌握。 蓝桥杯跳石头题解：图论建模与bitset优化动态规划
1. 项目概述从“跳石头”到图论建模最近在带学生备赛蓝桥杯刷到这道P10914“跳石头”发现它是个非常典型的图论建模问题但内核又比普通的DFS/BFS搜索多了一层“集合去重”的思考。题目描述了一个简单的游戏规则一排编号1到n的石头每块石头i有一个权值c_i。你站在石头j上可以跳到石头j c_j如果不超过n或者跳到石头2j如果不超过n。游戏从某块石头x开始所有可能被经过的石头注意是“可能”意味着存在至少一条从x出发能到达该石头的路径的权值构成一个集合S_x得分就是这个集合的大小|S_x|。你需要找到从哪块石头开始能获得最大的得分。初看这题很多同学会下意识地想“这不就是从一个起点出发在图上做DFS或BFS把所有能到达的点找出来然后统计它们权值的不重复个数吗”这个思路方向是对的但直接这么干在n最大40000的情况下如果对每个起点都做一次完整的图遍历时间复杂度会爆炸。我们需要更聪明的办法。这道题的精髓在于它虽然要求我们枚举所有可能的起点但整个跳跃规则构建出的图结构是有规律的我们可以利用动态规划DP或记忆化搜索从后往前递推一次性算出所有起点的答案将复杂度降到O(n)或O(n log n)级别。接下来我就结合C实现拆解一下这道题的解题思路、核心算法以及编码中的那些坑。2. 核心思路拆解与算法选型2.1 问题本质可达性分析与权值集合首先我们要彻底理解题目在问什么。得分不是路径上权值之和也不是最长路径而是从起点x出发所有可能到达的节点的权值集合的大小。这里有两个关键点“可能”到达只要存在一条从x到石头y的路径无论这条路径怎么跳那么石头y就算被“经过”了。这意味着我们需要计算的是节点的可达性而不是某一条特定路径。权值集合多个不同的节点可能拥有相同的权值但得分只计算一次。所以我们最终关心的是所有可达节点的权值种类数。因此问题的核心可以分解为两步对于每个起点x计算出所有从x出发可达的节点集合然后统计这些节点对应权值的不重复数量。2.2 暴力搜索的局限性最直接的暴力方法是对于每个起点i (1 i n)执行一次图遍历DFS或BFS标记所有能从i到达的节点然后遍历这些节点用一个setint或unordered_setint来记录权值最后集合的大小就是得分。再取所有得分的最大值。我们来估算一下复杂度。对于每个起点最坏情况下可能需要遍历整个图虽然由于跳跃规则限制图是稀疏的。假设平均每个节点能到达m个其他节点那么一次遍历的复杂度是O(m)。对于n个起点总复杂度就是O(n * m)。在n40000时如果m也接近n那就是O(n²) ≈ 1.6e9显然会超时。题目给了20%的数据n20可能就是给暴力搜索留的活路但要想AC必须优化。2.3 优化方向记忆化搜索与逆向思维暴力法之所以慢是因为它做了大量重复计算。考虑两个起点x和y如果从x出发能到达y那么从x出发能到达的所有节点一定也包含从y出发能到达的所有节点因为到了y之后你可以继续从y开始的所有可能跳跃。更一般地这个跳跃关系构成了一个有向图。如果我们定义reachable[i]为一个集合表示从石头i出发所有可能到达的节点集合那么对于任意一条边 i - j都有reachable[i]包含{i} ∪ reachable[j]。这启发我们可以用记忆化搜索Memoization或动态规划DP的思路从后往前或者用DFS记忆化来计算每个节点的reachable集合。但直接存储集合本身仍然可能很大导致空间和时间开销大。进一步观察我们最终需要的不是节点集合而是权值集合的大小。而且权值c_i的范围也是1到n。一个更巧妙的思路是我们能否直接计算出从每个节点i出发能收集到的不同权值有哪些这里需要引入状态压缩的思想。因为n40000我们无法用一个长度为n的bool数组来为每个起点存储所有可能的权值那样是O(n²)空间。但是我们可以换一个角度用位运算或布尔数组记录“当前从某个节点出发已经覆盖了哪些权值”但这在传递时依然复杂。实际上更普适且清晰的思路是先构建整个图的可达性关系再利用“可达性”来推导“权值可达性”。具体有两种主流方法传递闭包 权值统计计算出图的传递闭包即任意两点是否可达然后对于每个起点i将所有可达点j的权值c_j加入集合。但计算传递闭包例如用Floyd-Warshall是O(n³)完全不可行。由于图是稀疏的且有特殊结构我们需要更高效的闭包计算。记忆化搜索 集合合并用DFS从每个未访问的节点开始搜索在回溯过程中将后继节点的可达权值集合合并到当前节点。合并操作尤其是集合去重是开销所在。考虑到n40000c_in一个可行的优化是用bitset来表示一个节点可达的权值集合。bitsetN可以在常数时间内进行位运算如或运算|合并两个集合非常快。N40001的bitset大小约为40001/8 ≈ 5KB。对于40000个节点如果每个节点都存一个bitset总内存约40000 * 5KB ≈ 200MB这通常超过了竞赛题目的内存限制通常256MB或512MB。但我们可以利用动态bitset如vectorbool或更紧凑的表示方法不过实现起来较复杂。2.4 最终算法确定反向建图 BFS/DFS 差分思想我查阅了网上一些AC的题解并结合自己的思考发现这道题有一个被忽略的突破口跳跃规则是确定的从每个点出发的出边最多只有两条jc_j 和 2j。因此整个图是一个每个节点出度最多为2的有向图。对于这样的图我们可以考虑反向建图。什么是反向建图原图是如果从j能跳到k就有一条边 j-k。反向建图则是如果从j能跳到k我们建立一条边 k-j。这意味着在反向图中如果有一条边 k-j表示从j可以到达k在原图中。为什么要反向建图因为题目要求的是“从x出发能到达哪些点”这等价于“在反向图中从哪些点出发能到达x”。但这样似乎没简化问题。关键点在于如果我们能预处理出所有节点通过反向边能到达的节点即原图中能到达它的节点然后利用这些信息来快速计算每个起点的得分吗一个精妙的做法是从后往前动态规划。定义dp[i]为一个bitset或布尔数组表示从节点i出发能访问到的权值集合用一个位掩码表示。但如前所述直接存bitset可能内存过大。更进一步的优化是我们并不需要为每个节点存储完整的权值集合只需要知道从该节点出发能访问到的权值种类数。但这样在合并时无法去重。实际上本题最简洁高效的AC解法是进行一遍DFS或BFS但配合一个全局的访问标记数组并利用递归返回值来传递信息。然而由于图可能有环比如从i跳到j又从j跳回i直接DFS会陷入死循环需要处理环。综合来看一个经过验证的可行算法步骤如下建图根据规则为每个节点i建立两条有向边i - ic_i (如果ic_i n) 和 i - 2i (如果2i n)。计算可达节点集对于每个节点i我们需要知道从i出发能到达的所有节点。这可以通过对每个节点i进行BFS/DFS实现但这样是O(n²)。优化方法是进行一次拓扑排序如果图是无环的或强连通分量缩点如果图有环。但我们的图由于有边i-2i很可能存在环例如1-2-4-1? 不一定但需要检查。实际上由于c_i是正整数且跳跃总是向编号更大的节点ic_i i, 2i i 当 i1所以这个图是一个有向无环图DAG因为每条边都是从编号小的节点指向编号大的节点。这是一个非常重要的性质在DAG上动态规划既然图是DAG我们就可以按照节点编号从大到小的顺序进行动态规划。定义f[i]为一个集合表示从节点i出发能经过的节点的权值集合。由于是DAG我们可以从后往前从n到1递推初始化f[i]为只包含自身权值c_i的集合。对于节点i它的后继节点是j1 i c_i(如果n) 和j2 2*i(如果n)。那么从i出发能经过的权值集合等于{c_i}并上f[j1]并上f[j2]如果后继存在。即f[i] {c_i} ∪ f[j1] ∪ f[j2]。集合的表示与合并我们需要高效地合并集合。由于权值范围是1~n我们可以用一个bitset来表示集合。bitset40001 f[i]表示集合第k位为1表示权值k在集合中。那么合并操作就是位或运算f[i] f[i] | f[j1] | f[j2]。同时设置f[i][c_i] 1。统计答案计算完所有f[i]后f[i].count()就是从i出发的得分。遍历所有i取最大值即可。复杂度分析时间我们需要处理n个节点每个节点最多合并两个bitset。bitset的位或运算可以认为是O(N/word_size)在C中bitset的位运算通常被优化为O(N/64)。N40001所以一次合并约625次64位运算。对于每个节点进行两次合并总运算量约为n * 2 * (40001/64) ≈ 40000 * 2 * 625 50,000,000次操作在1秒内可以完成。空间需要存储n个bitset每个约5KB总内存约200MB。这处于极限边缘但通常蓝桥杯环境的内存限制可能为256MB或512MB200MB是可行的但有些风险。如果内存超限我们可以尝试用vectorbitset40001但实际内存占用差不多。一个更好的优化是**由于我们是从后往前递推当计算完f[i]后f[j](ji) 可能不再需要但f[i]在计算更小的i时可能还需要因为边指向更大的j。所以不能立即释放。内存是主要瓶颈。注意这是基于bitset的解法。在实际竞赛中如果内存限制较紧如128MB可能需要更节省内存的方法例如用vectorint存储每个节点可达的权值列表并用哈希表去重但合并操作会更耗时。或者可以采用BFS从每个节点出发但用一个全局的bitset作为访问标记标记权值但这样需要n次BFS每次BFS重置bitset时间复杂度O(n²/64)可能也能勉强通过40000*40000/64 ≈ 25e6次位操作但不如DP优雅。考虑到蓝桥杯国赛的难度和常见环境bitset解法是通行的。下面我们就按照这个思路来实现。3. 代码实现与逐行解析3.1 数据结构定义与输入处理首先我们包含必要的头文件并定义最大常数。由于n最大40000权值c_i也n我们把bitset的大小设为40001索引从1到40000。#include iostream #include vector #include bitset #include algorithm using namespace std; const int MAXN 40005; // 稍微开大一点防止边界问题 int main() { int n; cin n; vectorint c(n 1); // 权值数组下标从1开始 for (int i 1; i n; i) { cin c[i]; } // 后续代码... }这里定义c数组时大小是n1是为了让下标从1开始与题目描述一致。3.2 核心DP数组初始化我们需要一个vector来存储每个节点的bitset。注意bitset的大小必须在编译时确定所以我们用bitsetMAXN其中MAXN40005。vectorbitsetMAXN f(n 1); // f[i] 表示从节点i出发能经过的权值集合 // 初始化每个节点至少能经过自身的权值 for (int i 1; i n; i) { f[i].set(c[i]); // 将c[i]对应的位设为1 }bitset的set(pos)函数将第pos位设置为1。注意bitset的位索引默认从0开始但我们的权值范围是1~n所以直接使用c[i]作为索引是没问题的因为c[i]1。当然更严谨的做法是f[i].set(c[i])这会将第c[i]位设为1。3.3 动态规划递推过程由于图是DAG边从小节点指向大节点我们可以从大到小遍历节点i这样当处理节点i时它的后继节点ic[i]和2*i如果存在一定大于i它们的f值已经计算好了。for (int i n; i 1; --i) { // 处理第一种跳法跳到 i c[i] int j1 i c[i]; if (j1 n) { f[i] | f[j1]; // 合并集合位或运算 } // 处理第二种跳法跳到 2*i int j2 2 * i; if (j2 n) { f[i] | f[j2]; } }这里的关键操作是f[i] | f[j1]这是一个bitset的位或赋值操作效果是将f[j1]中所有为1的位在f[i]中也设为1。这样就实现了集合的合并。注意我们之前已经将f[i]的c[i]位设为1所以这里不需要再额外添加自身权值。重要细节为什么从后往前遍历 因为对于任意节点i它的后继节点j1 ic[i] 和 j2 2*i 都满足 j1 i 且 j2 i当i1时。所以当我们从in开始递减遍历到1时对于当前的i它的后继节点j1和j2的编号都大于i因此它们的f值已经在之前的迭代中计算完成了。这满足了动态规划的“无后效性”。3.4 统计答案并输出递推完成后f[i]这个bitset中1的个数就是从节点i出发能获得的分值。我们遍历所有i找出最大值。int ans 0; for (int i 1; i n; i) { int score f[i].count(); // 计算bitset中1的个数即集合大小 if (score ans) { ans score; } } cout ans endl;bitset的count()函数返回其中设置为1的位的数量时间复杂度是O(N/word_size)对于40001位来说很快。3.5 完整代码整合将以上部分整合得到完整代码#include iostream #include vector #include bitset #include algorithm using namespace std; const int MAXN 40005; // 预留一点空间 int main() { ios::sync_with_stdio(false); cin.tie(nullptr); // 加速输入输出 int n; cin n; vectorint c(n 1); for (int i 1; i n; i) { cin c[i]; } // dp数组f[i]是一个bitset表示从i出发能经过的权值集合 vectorbitsetMAXN f(n 1); // 初始化每个节点至少能经过自身的权值 for (int i 1; i n; i) { f[i].set(c[i]); } // 从后往前DP因为图是DAG边从小节点指向大节点 for (int i n; i 1; --i) { int j1 i c[i]; if (j1 n) { f[i] | f[j1]; } int j2 2 * i; if (j2 n) { f[i] | f[j2]; } } // 统计答案 int ans 0; for (int i 1; i n; i) { ans max(ans, (int)f[i].count()); } cout ans endl; return 0; }4. 算法正确性证明与边界情况4.1 为什么这个DP是正确的我们需要证明按照上述递推公式计算出的f[i]确实等于从节点i出发所有可能经过的节点的权值集合。定义设S(i)为从节点i出发所有可能经过的节点的权值集合。归纳基础对于节点i如果它没有出边即ic[i] n且2*i n那么从i出发只能停留在i所以S(i) {c[i]}。我们的初始化f[i].set(c[i])正好对应这一点。归纳步骤假设对于所有编号大于i的节点jf[j]已经正确计算并等于S(j)。考虑节点i它最多有两个后继j1 ic[i]和j2 2*i。从i出发第一步有两种选择跳到j1或跳到j2如果合法。如果跳到j1那么之后所有可能经过的节点就是从j1出发能经过的节点同理如果跳到j2之后所有可能经过的节点就是从j2出发能经过的节点。此外无论怎么跳起点i本身也会被经过。因此从i出发所有可能经过的节点集合是{i}加上 从j1出发能经过的节点 加上 从j2出发能经过的节点。对应的权值集合就是{c[i]}∪S(j1)∪S(j2)。根据归纳假设f[j1] S(j1),f[j2] S(j2)。而我们递推中的操作f[i] | f[j1]; f[i] | f[j2];在已经设置f[i][c[i]]1的基础上正好计算了这个并集。所以f[i]也正确。由于我们是从大到小遍历i所以归纳假设成立DP正确。4.2 边界情况与注意事项数组越界在访问j1 i c[i]和j2 2*i时必须检查是否小于等于n。我们的代码中用了if (j1 n)和if (j2 n)来保护。权值作为bitset索引权值c[i]的范围是1~n我们直接用c[i]作为bitset的索引。这要求bitset的大小至少为n1。我们定义了MAXN40005足够容纳。内存使用这是本解法最大的潜在问题。vectorbitsetMAXN f(n1)占用的内存大约是(n1) * (MAXN/8) bytes。代入n40000, MAXN40005约为40001 * 5000 ≈ 200MB。这接近但通常不超过蓝桥杯国赛的内存限制常为256MB。如果担心内存超限可以尝试用bitset40001而不是bitsetMAXN但这样需要确保n40000。或者可以使用vectorbool来模拟bitset但vectorbool不是标准容器位操作可能慢一些。时间复杂度DP循环是O(n)每次循环中进行两次bitset的位或运算。bitset的位或运算复杂度是O(N/word_size)即O(40000/64)≈O(625)。所以总时间大约是40000 * 2 * 625 ≈ 50,000,000次位操作这在2秒内通常可以完成。5. 性能优化与替代方案虽然上述bitsetDP解法是主流且易于理解的但在极端情况下内存限制更紧或n更大时可能需要优化。这里讨论几种变体5.1 使用vectorbool替代bitsetbitset的大小必须在编译时确定这不够灵活。我们可以用vectorbool来动态创建位集每个vectorbool只存储从该节点出发可达的权值集合。但vectorbool的位运算不支持直接对整个容器进行位或需要手动循环或者用std::transform但效率可能较低。vectorvectorbool f(n 1, vectorbool(n 1, false)); // 初始化 for (int i 1; i n; i) f[i][c[i]] true; // DP递推 for (int i n; i 1; --i) { int j1 i c[i], j2 2 * i; if (j1 n) { for (int k 1; k n; k) { if (f[j1][k]) f[i][k] true; } } if (j2 n) { for (int k 1; k n; k) { if (f[j2][k]) f[i][k] true; } } } // 统计答案 int ans 0; for (int i 1; i n; i) { int cnt 0; for (int k 1; k n; k) cnt f[i][k]; ans max(ans, cnt); }这种方法的复杂度是O(n²)对于n40000来说是16亿次操作显然会超时。所以不可取。5.2 BFS/DFS 全局权值标记另一种思路是从每个节点i开始做BFS或DFS用一个全局的bool visited[N]数组来标记本次搜索中哪些权值已经出现过。每次BFS前清空visited数组。统计本次搜索中访问到的不同权值数量。vectorint c(n1); vectorvectorint graph(n1); // 邻接表 // 建图 for (int i 1; i n; i) { if (i c[i] n) graph[i].push_back(i c[i]); if (2 * i n) graph[i].push_back(2 * i); } int ans 0; vectorbool visited_val(n1, false); // 标记权值是否已计入 for (int start 1; start n; start) { fill(visited_val.begin(), visited_val.end(), false); queueint q; q.push(start); visited_val[c[start]] true; int count 1; // 至少包含起点权值 while (!q.empty()) { int u q.front(); q.pop(); for (int v : graph[u]) { if (!visited_val[c[v]]) { visited_val[c[v]] true; count; } q.push(v); // 注意即使权值已访问过节点仍需入队继续探索因为可能通过该节点到达其他权值未访问的节点 } } ans max(ans, count); }这个算法的时间复杂度是O(n * (VE))其中V是节点数E是边数。最坏情况下每个节点都可达几乎所有其他节点所以近似O(n²)也会超时。但我们可以加上节点访问标记来剪枝如果某个节点已经被访问过那么从该节点出发能到达的权值集合已经被合并到当前集合中可以不再重复探索。然而由于我们关心的是权值集合即使节点被访问过它的权值可能已经被记录但通过它可能到达的新节点权值未记录仍需探索。所以不能简单用节点访问标记来剪枝。因此BFS方法在n40000时难以通过。5.3 基于拓扑排序的DP既然图是DAG我们可以先进行拓扑排序然后按照拓扑序从后往前DP。不过由于节点编号天然满足拓扑序边从小节点指向大节点所以直接按编号从大到小遍历就是拓扑序不需要显式进行拓扑排序。我们的解法已经利用了这一点。5.4 内存优化技巧如果内存是瓶颈我们可以尝试不存储所有节点的完整bitset而是用时间换空间。例如对于每个节点i我们只存储一个vectorint表示从i出发能到达的权值列表并在合并时去重。但合并两个列表并去重的时间复杂度较高。或者我们可以用哈希表unordered_set来存储权值集合但内存开销也不小。一个折中的方案是使用bitset但分批处理。例如将权值范围分成若干块比如每块大小1000对每块分别进行DP。具体地我们进行多次DP每次只关心权值在某个区间内的节点。最后合并结果。但这样需要多次遍历时间可能增加。考虑到蓝桥杯的环境bitset解法在大多数情况下是可以通过的。如果遇到内存超限可以尝试将bitset改为vectorbool但使用引用或指针来减少拷贝或者尝试用int数组模拟位运算。6. 常见错误与调试技巧在实现和调试这道题时我遇到过一些典型的错误这里列出来供大家参考数组下标越界这是最常见的错误。在计算j1 i c[i]和j2 2*i时一定要检查是否 n。另外c数组和f数组的大小应该是n1索引从1开始。bitset大小不足bitsetN的N必须是一个编译时常量且N要大于等于可能出现的最大权值即n。如果n40000那么N至少需要40001。建议定义为const int MAXN 40005;留一点余量。DP顺序错误必须从后往前从n到1遍历。如果从前往后遍历当计算f[i]时它的后继节点f[j1]和f[j2]可能还没有计算因为j1, j2 i导致使用未初始化的值。忘记初始化自身权值在DP开始前必须将每个f[i]的c[i]位设为1。否则如果某个节点没有出边它的得分会被错误地计算为0。内存超限如果使用vectorbitsetMAXN f(n1)请估算内存。40000 * 40000 bit ≈ 200MB。如果题目内存限制是128MB可能会超。这时可以考虑用short或bool数组来存储每个节点可达的权值集合但需要更复杂的压缩。输出格式错误题目要求输出一个整数不要输出多余的空格或换行。输入读取优化对于n40000输入量不大但使用ios::sync_with_stdio(false); cin.tie(nullptr);可以加速输入输出避免卡常。调试技巧可以先用小数据测试比如n5手动模拟DP过程验证结果是否正确。对于每个节点i可以输出f[i].count()检查得分是否合理。如果怀疑DP顺序可以打印出每个节点i的后继节点j1和j2确保j1, j2 i。如果内存或时间超限可以尝试用bitset的test()和set()函数来验证位操作是否正确。7. 总结与扩展思考这道“跳石头”题目看似是一个简单的游戏模拟实则考察了对图论模型的抽象能力、对DAG上动态规划的应用以及对bitset优化集合运算的掌握。通过这道题我们可以学到问题转化将游戏规则转化为有向图将得分计算转化为节点可达性与权值集合的并集。利用图的性质识别出图是DAG因为边总是从小节点指向大节点从而可以使用基于拓扑序的DP。bitset优化当需要频繁合并集合且集合元素是有限范围内的整数时bitset可以通过位运算在常数时间内完成合并极大提高效率。这是处理状态压缩和集合运算的利器。时空权衡bitset解法用较大的内存约200MB换取了较低的时间复杂度约5e7次位操作。在竞赛中这种权衡往往是必要的。扩展思考如果跳跃规则改变比如可以往回跳例如跳到j - c[j]那么图就可能包含环。这时就需要先用强连通分量SCC算法缩点将环缩成一个点然后在DAG上DP。如果权值范围很大比如10^9就不能用bitset了。这时可能需要用哈希表unordered_set来存储集合但合并操作会更耗时。或者可以离线处理用并查集维护连通性再统计每个连通分量内不同权值的数量。如果题目问的不是最大得分而是从每个起点出发的得分那么我们的DP已经计算出了所有起点的得分直接输出即可。最后在竞赛中遇到这类题目关键是先分析数据范围再选择合适的算法。对于n40000O(n²)的暴力通常不可行必须寻找O(n log n)或O(n * bit)的优化。bitsetDP是一个非常重要的技巧值得熟练掌握。