专栏文章

区间问题复习

WWilliam2022
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minziqx6
此快照首次捕获于
2025/12/02 10:54
3 个月前
此快照最后确认于
2025/12/02 10:54
3 个月前
查看原文
整理前的笔记

区间处理专题

无效区间剔除规则

在处理区间问题时，我们常需要剔除无效区间，主要分为两种情况：
  1. 被包含的区间（留大不留小）：当一个小区间完全被一个大区间包含时，我们保留大的区间
  2. 包含别的区间（留小不留大）：当一个区间包含其他小区间时，我们保留小的区间
剔除后，剩下的区间集合中将不存在包含关系，区间之间的关系变得清晰明了。

排序规则与处理方法

区间问题的难点在于确定正确的排序规则和处理顺序：

A1 留大不留小策略

  1. 左端点正序，右端点倒序：使用"老人干掉新人"方式，坏区间不进入答案
  2. 右端点正序，左端点正序：使用栈结构，"新人干掉老人"

A2 留小不留大策略

  1. 左端点正序，右端点倒序：使用栈型处理
  2. 右端点正序，左端点倒序：坏区间不进入答案
一般情况下推荐使用不让坏区间进入答案的方法。

思维方法

处理区间问题时，可以采用简化问题的方法：每次考虑一个被剔除的非法区间，分析它加入当前合法区间集会产生什么影响。对于A1和A2策略：
  1. 使用栈结构剔除非法区间
  2. 防止坏区间加入合法集合

区间与二维平面的对应关系

区间也可以看作二维平面上的点，横坐标表示左端点，纵坐标表示右端点。这种视角转换有时能帮助我们更好地理解区间之间的关系。
具体不展开。

胖子占座问题分析

问题描述

有 mm 个座位，nn 个胖子，每个胖子 ii 要霸占区间 [li,ri][l_i, r_i] 的座位，然后你需要求出其左右空挡之类的信息。

解决方法

  1. 离散化处理：如果区间范围较大，可以先进行离散化
  2. 学生思维：
    • 并查集链表
    • 线段树
    • 图论建模

B1 高效解法

pii 是 pair<int,int>
使用set<pii>存储当前已落座胖子的区间：
CPP
bool fit(int l,int r,int &L,int &R){
  set<pii>::iterator it;
  it=s.lower_bound({l,r}); 
  if(it->first <=r)return 0; // 被占座
  R=it->fi-1;
  it--;
  if(l<= it->second)return 0;
  L=it->second+1;
  return 1;
}

区间覆盖与选择问题

C1 最少区间覆盖问题

先使用A1策略（留大不留小）预处理区间，然后使用贪心算法选择覆盖区间。

C2 最多不重叠区间问题

先使用A2策略（留小不留大）预处理区间，然后使用贪心算法选择不重叠区间。

例题：国旗计划（SCOI2015）

问题特点

本题 = C1 + 环形 + 强选 - A1

跳跃

在C1中，每个元素一定会有一个后继，我们可以预处理出后继然后跳，优化常数，然后就能想到二分，优化复杂度。

解决方法

  1. 断环为链：将环形问题转化为线性问题
  2. 贪心算法：使用C1贪心策略，但需要处理环形特性
  3. 预处理跳跃：使用倍增法预处理每个区间的跳跃目标

倍增法实现

CPP
// 预处理倍增表
for (int j = 1; j < LOG; j++) {
    for (int i = 1; i <= 2*n; i++) {
        nxt[i][j] = nxt[nxt[i][j-1]][j-1];
    }
}

注意事项

  1. 边界处理：nxt[2*n][0] = 2*n
  2. 答案调整：由于环形特性和计算方式，最终答案可能需要加1或2
  3. 无解情况：需要特别处理无法完成覆盖的情况（本题没有）

例题：会议中心（APIO2009）

问题特点

本题 = C2 + 方案字典序最小 + 求方案

解决方法

  1. 正常处理：先使用C2策略选择最多不重叠区间
  2. 字典序最小：按字典序贪心放置区间（使用 B1 方法），同时检查可行性和最优性
  3. 可行性检查：使用公式calc(L, l-1) + calc(r+1, R) + 1 == calc(L, R)

实现细节

CPP
// 检查放置区间[l, r]是否可行
bool check(int L, int R, int l, int r) {
    return calc(L, l-1) + calc(r+1, R) + 1 == calc(L, R);
}

注意事项

  1. 统一无答案处理：无答案时返回统一值（如0或m+1）
  2. 二分查找优化：使用二分查找加速决策过程

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...