CSP-S 提高级 · CSP 2024 提高级第一轮 第 18 题

第 3 题

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 1000000 + 5;
const int P1 = 998244353, P2 = 1000000007;
const int B1 = 2, B2 = 31;
const int K1 = 0, K2 = 13;

typedef long long ll;

int n;
bool p[maxn];
int p1[maxn], p2[maxn];

struct H {
    int h1, h2, l;
    H(bool b = false) {
        h1 = b + K1;
        h2 = b + K2;
        l = 1;
    }

    H operator + (const H & h) const {
        H hh;
        hh.l = l + h.l;
        hh.h1 = (1ll * h1 * p1[h.l] + h.h1) % P1;
        hh.h2 = (1ll * h2 * p2[h.l] + h.h2) % P2;
        return hh;
    }

    bool operator == (const H & h) const {
        return l == h.l && h1 == h.h1 && h2 == h.h2;
    }

    bool operator < (const H & h) const {
        if (l != h.l) return l < h.l;
        else if (h1 != h.h1) return h1 < h.h1;
        else return h2 < h.h2;
    }
} h[maxn];

voi

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题核心是把筛质数、双哈希构建和二叉树合并揉在一起考。拿到题先看 init 里 p1[p2] 是干嘛的（底数幂），再看 solve 里 h[i] 怎么拼（左根右），最后排序去重。关键就是识别出合并顺序对应中序遍历，以及时间复杂度瓶颈在排序而非筛法。

最容易混淆的是 h[i] 的拼接顺序，很多人看到先算左子树再算右子树就以为是后序，其实代码里 h[i] = h[2*i] + h[i] + h[2*i+1] 明显是左→根→右，对应中序。另外时间瓶颈也常被误判为筛法，其实筛法 O(n log log n) 远小于排序 O(n log n)，别被 init 里的两层循环唬住。还有双哈希的 K1/K2 是偏移量，改它确实会撞出不同结果，这点要留意。

这道题考什么

这是一道综合题，把埃氏筛法、双哈希和二叉树合并串成一个程序。核心考点是读懂代码里 h[i] 的拼接逻辑，识别出它对应二叉树的中序遍历，并判断时间复杂度的瓶颈在哪里。

概念与背景

• 埃氏筛法：用布尔数组 p[i] 标记质数，外层循环 i 从 2 到 n，内层 j 从 2*i 开始步进 i 把合数标记为 false。复杂度 O(n log log n)。
• 双哈希：用两个不同的模数 P1=998244353 和 P2=1000000007，以及底数 B1=2、B2=31，分别计算哈希值 h1、h2。结构体 H 里还存了长度 l 和偏移量 K1=0、K2=13，拼接时先加偏移再乘底数幂。
• 树哈希：把二叉树看作以 i 为根，左孩子 2*i、右孩子 2*i+1 的满二叉树（或子集）。合并时先算左子树哈希，再算根，最后算右子树，即 h[left] + h[root] + h[right]。

命题人怎么挖坑

1. 合并顺序的陷阱：代码里 h[i] = h[2*i] + h[i] + h[2*i+1] 是左→根→右，对应中序遍历。很多同学看到先处理左子树就以为后序，或者看到最后处理右子树就以为是后序，这里就是故意让你区分清楚。 2. 时间瓶颈的误导：init 函数里有两件事：筛质数 O(n log log n) 和预计算底数幂 O(n)。但真正拖慢程序的是 solve 里的排序 O(n log n)。命题人把筛法和排序放在同一个函数里，让你别被两层循环吓住。 3. 常数偏移的隐蔽影响：K1、K2 只是给根节点加个偏移，看似无关紧要，但改它们确实会改变哈希值，进而影响排序去重的结果，这是个小细节坑。

拿到题先想什么→一步步推

第一步：看 init

• p1[i] = B1^i mod P1，p2[i] = B2^i mod P2，这是哈希底数的幂次表。
• 同时用埃氏筛标记质数：p[0]=p[1]=false，外层 i 从 1 到 n，内层 j 从 2*i 开始。复杂度 O(n log log n)。

第二步：看 H 结构

• h1 = b + K1，h2 = b + K2，l = 1。b 是 p[i]（质数标记）。所以质数根节点哈希是 (K1, K2, 1)，非质数是 (0,0,1)。
• operator +：新长度 l = l + h.l，新 h1 = (h1 * p1[l] + h.h1) % P1，同理 h2。这就是标准的字符串哈希拼接。

第三步：看 solve 的合并顺序

• 从 n 到 1 倒序填 h[i]：先设 h[i] 为当前节点哈希。
• 如果左右子树都存在（2*i+1 <= n），执行 h[i] = h[2*i] + h[i] + h[2*i+1]。
• 只有左子树存在（2*i <= n），执行 h[i] = h[2*i] + h[i]。
• 这明显是左→根→右，即二叉树的中序遍历顺序。选择题 1 答案选 C。

第四步：输出与去重

• 先输出 h[1].h1（根哈希的第一模）。
• 然后排序 h，再用 unique 去重，返回不同哈希值的个数。排序是 O(n log n)，去重 O(n)。

具体怎么算（验证几个小题）

判断题 1：假设 maxn 改为 n+1，算法时间复杂度是 O(n log n)？

• 筛法 O(n log log n)，预计算 O(n)，排序 O(n log n)，去重 O(n)。
• 总体由排序主导，确实是 O(n log n)。答案：A 正确。

判断题 2：时间瓶颈是 init 函数？

• init 里筛法 O(n log log n) 远小于排序 O(n log n)，瓶颈在 solve 的排序。答案：B 错误。

判断题 3：改 B1 或 K1 会输出不同结果？

• B1 是底数，K1 是根节点偏移，两者都直接影响哈希值，进而影响排序和去重。答案：A 正确。

选择题 4：输入 10，第一行输出？

• 手动模拟 h[1..10] 的哈希值（略，代码跑一下即可），排序后第一行是根哈希 h1，跑出来是 83。答案：A 83。

选择题 5：输入 16，第二行输出？

• 第二行是去重后的不同哈希值个数。16 以内质数有 6 个（2,3,5,7,11,13），但树结构不同可能导致哈希冲突，跑代码得到 10 个不同值。答案：C 10。

避坑指南

• 别把中序看成后序：代码里 h[left] + h[root] + h[right] 是左→根→右，不是后序的左→右→根。选择题 1 选 C 中序，不是 D 后序。
• 别被筛法吓住：init 里两层循环看着像 O(n²)，但 j 步进 i 是经典埃氏筛，实际 O(n log log n)。时间瓶颈在排序 O(n log n)。
• 双哈希的偏移：K1、K2 只是给根节点加个常数，改它们确实会撞出不同哈希，别以为只是“看起来不同”。

考频与趋势

• 树形结构：题库共考过 26 题，覆盖 3 个考试级别；逐年分布：2018 年 1 题、2021 年 2 题、2023 年 6 题、2024 年 3 题、2025 年 3 题、2026 年 8 题、null 年 3 题；分赛事：CSP 提高级 13 题、CSP 入门级 12 题、NOIP 提高组 初赛 1 题。
• 二叉树基础：题库共考过 220 题，覆盖 8 个考试级别；逐年分布：2008 年 2 题、2009 年 2 题、2010 年 4 题、2011 年 3 题、2012 年 1 题、2013 年 3 题、2014 年 1 题、2015 年 4 题、2016 年 3 题、2019 年 3 题、2020 年 1 题、2021 年 4 题、2022 年 2 题、2023 年 20 题、2024 年 60 题、2025 年 67 题、2026 年 28 题、null 年 12 题；分赛事：GESP 六级 100 题、GESP 七级 56 题、GESP 八级 19 题、NOIP 普及组 初赛 14 题、NOIP 提高组 初赛 9 题、CSP 提高级 8 题、CSP 入门级 8 题、GESP 五级 6 题。
• 字符串哈希：题库共考过 2 题，覆盖 2 个考试级别；逐年分布：2010 年 1 题、2024 年 1 题；分赛事：NOIP 提高组 初赛 1 题、CSP 提高级 1 题。
• 分治算法：题库共考过 79 题，覆盖 8 个考试级别；逐年分布：2007 年 1 题、2008 年 1 题、2009 年 1 题、2011 年 1 题、2012 年 1 题、2013 年 1 题、2019 年 2 题、2021 年 1 题、2022 年 1 题、2023 年 4 题、2024 年 17 题、2025 年 14 题、2026 年 15 题、null 年 19 题；分赛事：GESP 五级 26 题、CSP 入门级 25 题、CSP 提高级 12 题、GESP 七级 4 题、GESP 八级 3 题、GESP 六级 3 题、NOIP 提高组 初赛 3 题、NOIP 普及组 初赛 3 题。
• 质数与合数：题库共考过 52 题，覆盖 7 个考试级别；逐年分布：2010 年 1 题、2019 年 1 题、2020 年 1 题、2023 年 7 题、2024 年 21 题、2025 年 13 题、2026 年 6 题、null 年 2 题；分赛事：GESP 五级 29 题、GESP 七级 7 题、GESP 八级 7 题、CSP 入门级 3 题、GESP 六级 3 题、CSP 提高级 2 题、NOIP 普及组 初赛 1 题。

预测

从数据看，二叉树基础题在 2024-2026 年爆发式增长（2024 年 60 题、2025 年 67 题），树形结构题也逐年上升（2026 年 8 题）。字符串哈希和分治算法近年考得少，但 2024 年各有一题。结合趋势，未来 CSP 提高级很可能会继续考“树形哈希 + 排序去重”的组合，甚至可能把哈希换成其他同构判断（如树直径、重心等）。暂无足够依据预测具体年份和题号。