校门外的树：区间处理与标记法的C++实践（洛谷P1047）

题目思路解析

这道题目要求我们计算在移除多个区间内的树木后，马路上剩余的树木数量。关键在于高效处理可能重叠的多个区间，并准确统计被移除的树木。

核心思考路径

1. 问题建模：将马路抽象为0到l的连续区间
2. 区间处理：标记所有需要移除树木的区间
3. 结果计算：统计未被标记的树木数量

关键考核知识点

1. 数组标记法（⭐⭐⭐⭐⭐）

• 布尔数组：用数组元素表示树木存在状态
• 区间标记：将移除区间内的元素设为true
• 状态统计：遍历统计未被标记的元素

2. 区间合并处理（⭐⭐⭐）

• 重叠区间：处理多个区间可能重叠的情况
• 端点处理：包含区间的两个端点
• 效率优化：避免重复标记已移除的树木

3. 输入输出处理（⭐⭐）

• 多组数据输入：正确处理m组区间数据
• 边界值处理：验证u和v的合法性
• 结果输出：按要求格式输出剩余树木数

C++完整实现

解法一：布尔数组标记法

#include <iostream> #include <vector> using namespace std; int main() { int l, m; cin >> l >> m; vector<bool> trees(l + 1, false); // false表示树存在 while (m--) { int u, v; cin >> u >> v; for (int i = u; i <= v; ++i) { trees[i] = true; // true表示树被移除 } } int count = 0; for (int i = 0; i <= l; ++i) { if (!trees[i]) ++count; } cout << count << endl; return 0; } 

解法二：区间端点优化法

#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int l, m; cin >> l >> m; vector<pair<int, int>> intervals; while (m--) { int u, v; cin >> u >> v; intervals.emplace_back(u, v); } // 按区间起点排序 sort(intervals.begin(), intervals.end()); int removed = 0; int last = -1; for (auto& interval : intervals) { int u = interval.first, v = interval.second; if (u > last) { removed += v - u + 1; last = v; } else if (v > last) { removed += v - last; last = v; } } cout << (l + 1 - removed) << endl; return 0; } 

代码解析与优化

1. 空间优化技巧

// 使用bitset减少空间占用 #include <bitset> bitset<10001> trees; // 替代vector<bool> 

2. 输入处理优化

// 快速IO加速 ios::sync_with_stdio(false); cin.tie(nullptr); 

3. 复杂度分析

测试用例分析

常见错误与修正

错误1：数组越界

vector<bool> trees(l); // 错误：少一个元素 for (int i = 0; i <= l; ++i) // 越界访问 

修正：

vector<bool> trees(l + 1); 

错误2：端点处理错误

for (int i = u; i < v; ++i) // 错误：漏掉v端点 

修正：

for (int i = u; i <= v; ++i) 

错误3：计数错误

int count = l - removed; // 错误：忘记+1 

修正：

int count = l + 1 - removed; 

竞赛技巧总结

1. 问题抽象：将实际问题转化为区间处理问题
2. 数据结构选择：根据数据范围选择合适的数据结构
3. 边界检查：特别注意区间的端点处理
4. 测试验证：设计多种测试案例验证算法

拓展思考

1. 变形问题2：动态区间增加和查询
   • 使用线段树数据结构
   • 支持区间更新和区间查询
2. 进阶挑战：处理超大l值（如1e9）
   • 使用离散化和区间合并
   • 减少空间使用量

变形问题1：求被移除次数最多的树

vector<int> count(l+1); // 记录每棵树被移除的次数 

"校门外的树问题教会我们如何用编程解决现实中的空间规划问题，是算法竞赛中经典的区间处理案例。"

关注并私信【校门外的树】可获得资源：

• 区间合并算法详解