华为 · dfs · 算法编程题
华为 dfs n ≤ 1e5 时限 1 秒 / 256 MB

题目描述

在坐标轴的整数点 1 n 上给出 m 条闭区间线段，第 i 条线段用其端点 [st_i,ed_i] 描述。
现在要从这 m 条线段中选择若干条，使得每个整数点被至少两条所选线段覆盖。求满足条件的选择方案数量；两种方案视为不同，当且仅当存在某条线段在两方案中的"选/不选"状态不同。
答案对 P=998244353 取模。

输入输出

输入描述
第一行输入整数 n,m(2≤ n≤ 10^5,1≤ m≤ 10) 。
随后 m 行，每行两个整数 st_i,ed_i （ 1≤ st_i<ed_i≤ n ） 描述一条线段。
输出描述
输出满足条件的方案数对 998244353 取模的结果。

样例共 1 组

样例 1
输入
5 4
4 5
1 5
3 5
1 4
输出
3

算法解析依据充分

考点：dfs

数据规模 n ≤ 1e5 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：n ≤ 1e5，m ≤ 10
  • 复杂度门槛：只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：dfs

一条路走到底再回溯，适合枚举全部方案与连通性判定。

思路框架（dfs 通法 · 非本题专属）

  1. 定义递归函数（当前状态、已选集合、累计答案）。
  2. 写终止条件，达到终止条件时结算答案。
  3. 枚举下一步的所有选择，做选择 → 递归 → 撤销选择（回溯）。
  4. 大规模的连通块统计可用 DFS/BFS 染色标记。

实现要点：回溯时务必把状态恢复干净；必要时加剪枝（可行性剪枝、最优性剪枝）。

复杂度：时间 O(状态数) ｜ 空间 O(递归深度)

该范式的通法易错点

  • 回溯时忘记撤销状态，答案被污染。
  • 没有剪枝导致指数级爆炸超时。

对照本题

  • 数据规模 n ≤ 1e5，只允许 O(n log n) 及更优，朴素 O(n²) 会超时。

样例

样例 1

  • 输入：5 4 / 4 5 / 1 5 / 3 5 / 1 4
  • 输出：3

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：华为机试编程模拟题5；2024年秋招-蔚来汽车-后端岗笔试。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解