洛谷P3717 [AHOI2017初中组] cover 题解 c++

题目链接

题目

​

1.题目内容

题目理解起来很容易，在n×n的网格图‌（坐标从1开始）中，给定m个探测器及其探测半径r，统计‌能被至少一个探测器覆盖的网格点数量‌。探测器覆盖范围是以其坐标为中心、半径为r的圆形区域。

---

2.难度

入门（虽然难度不像）

---

3.题目所需知识点

• 模拟
• 搜索
• 枚举
• 差分
• 数学（欧氏距离计算）
  欧式距离计算

---

4. 思路

• 这是一个典型的网格覆盖问题，建立一个二维数组，通过遍历网格点并检查每个点是否在任意探测器的覆盖范围内来解决。模拟即可。

• 解题方法列举

暴力枚举法

1. 初始化n×n的标记数组为false。
2. 遍历每个探测器，以其为中心遍历网格点。
3. 计算网格点与探测器的欧几里得距离，判断是否在探测半径内。
4. 标记覆盖的网格点。
5. 统计标记为true的网格点数量。

差分优化法

1. 将圆形覆盖转化为矩形区域覆盖。
2. 计算每个探测器能覆盖的最大矩形边界。
3. 遍历矩形区域内的网格点，判断是否在探测半径内。
4. 标记并统计覆盖的网格点数量。

！！DFS可行性分析‌

• 理论可行但效率低‌：
  若以每个探测器为起点DFS遍历相邻点并标记覆盖，时间复杂度与暴力法相同（O(m-n²)）且实现更复杂‌。

• ‌适用场景局限‌：
  仅当问题扩展为“连续覆盖区域”时DFS有优势，本题无此需求‌。

---

5.复杂度分析

• **时间复杂度 **
  初始化阶段‌：O(1)，只是初始化差分数组 ‌处理每个探测器‌：O(m)，每个探测器处理时间为常数 ‌计算前缀和‌：O(n²)，需要遍历整个网格 ‌总时间复杂度‌：O(m + n²)
  相比暴力枚举法的O(m·n²)，差分优化法显著提高了效率，特别是当m较大时。

• 空间复杂度
  ‌差分数组‌：O(n²)，需要存储n×n的差分矩阵 ‌总空间复杂度‌：O(n²) 与暴力法相同，但实际应用中差分数组可以优化为一维数组进一步减少空间使用。

---

6.边界条件处理

‌网格边界处理‌：
使用max(1, x-r)和min(n, x+r)确保计算范围不超出网格边界防止数组越界访问。

‌圆形覆盖与矩形近似的误差‌：
差分法使用矩形近似圆形覆盖，会包含一些实际不在圆形范围内的点需要在标记后额外检查欧式距离，但这样会失去差分法的效率优势
实际应用中，如果允许近似解，可以直接使用矩形近似

‌多探测器重叠区域‌：
差分数组自动处理重叠区域的计数
最终统计时只需判断覆盖次数是否大于0

‌小半径特殊情况‌：
当r=0时，只覆盖探测器所在点
当r很小时，可能只覆盖探测器周围的4个点

‌大半径特殊情况‌：
当r≥n时，探测器可能覆盖整个网格

！！需要特别处理这种情况以避免不必要的计算

---

7.代码片段分析

• 变量、数据结构定义

#include<bits/stdc++.h>
using namespace std;
bool a[105][105]={false}; // 标记  点是否被覆盖
int n, m, r; 
int x, y;  //数轴
int dx, dy; //和(0, 0) 的水平距离 
int cont;  //记录覆盖点 

• 核心代码

暴力枚举法

    for(int i=0; i<m; i++){
        cin>>x>>y;  // 遍历以(x,y)为中心的正方形区域
        for(int i = max(1, x-r); i <= min(n, x+r); i++){     
            for(int j = max(1, y-r); j<=min(n, y+r); j++){	
                 dx=i-x;   
				 dy=j-y;   //两行用于计算点 (i, j) 与中心点 (x, y) 之间的水平和垂直距离
                if(dx*dx+dy*dy <= r*r){// 计算欧氏距离平方
                    a[i][j]=true;     //true的是可被覆盖的 
                }
            }
        }
    }

 for(int i = max(1, x-r); i <= min(n, x+r); i++){     
            for(int j = max(1, y-r); j<=min(n, y+r); j++){	

这段代码是一个双重循环，用于遍历以点 (x, y) 为中心、边长为 2r 的正方形区域内的所有点 (i, j)，同时确保这些点不会超出 n×n 的网格范围。

if(dx*dx+dy*dy<=r*r)

为避免浮点数运算，直接比较距离的平方与半径的平方（r²）。

• 计数

for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            if(a[i][j]) cont++;     //遍历，如果被标记，累加
        }
    }

---

差分优化法具体实现代码

以下是具体实现代码，讲解在代码中：

include<bits/stdc++.h>
using namespace std;

int diff[110][110]; // 差分数组
int n, m, r;
void add(int x1, int y1, int x2, int y2){
    diff[x1][y1]++;
    diff[x1][y2+1]--;
    diff[x2+1][y1]--;
    diff[x2+1][y2+1]++;
}

int main(){
    cin>>n>>m>>r;
    
    // 处理每个探测器
    for(int k=0; k<m; k++){
        int x, y;
        cin>>x>>y;
        
        // 计算覆盖的矩形边界
        int x1=max(1, x-r);
        int y1=max(1, y-r);
        int x2=min(n, x+r);
        int y2=min(n, y+r);
        
        // 标记矩形区域
        add(x1, y1, x2, y2);
    }
    
    // 计算前缀和得到实际覆盖情况
    int cnt=0;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            diff[i][j]+=diff[i-1][j]+diff[i][j-1]-diff[i-1][j-1];    
            // 前缀和核心代码，用于统计被探测器覆盖的网格点数量
            if(diff[i][j]>0) cnt++;
        }
    }
    
    cout<<cnt;
    return 0;
}

不懂前缀和的搜这个：前缀和

---

8.AC代码

#include<bits/stdc++.h>
using namespace std;
bool a[105][105]={false}; // 标记  点是否被覆盖
int n, m, r; 
int x, y;  //数轴
int dx, dy; //和(0, 0) 的水平距离 
int cont;  //记录覆盖点 
int main(){
    cin>>n>>m>>r;

     for(int i=0; i<m; i++){
        cin>>x>>y;  // 遍历以(x,y)为中心的正方形区域
        for(int i = max(1, x-r); i <= min(n, x+r); i++){     
            for(int j = max(1, y-r); j<=min(n, y+r); j++){	
                 dx=i-x;   
				 dy=j-y;   //两行用于计算点 (i, j) 与中心点 (x, y) 之间的水平和垂直距离
                if(dx*dx+dy*dy <= r*r){// 计算欧氏距离平方
                    a[i][j]=true;     //true的是可被覆盖的 
                }
            }
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(a[i][j]) cont++;     //遍历，如果被标记，累加
        }
    }
    cout<<cont;
    
    return 0;
}

---

9.推荐题目

P1146 硬币翻转 （模拟搜索题）
P3741 小果的键盘 （字符串搜索题）
P1553 数字反转（升级版） （字符串操作题）

---

附 更多的测试样例

样例1
输入
3 1 2
2 2

输出：
9

---

样例2
输入
2 2 1
1 1
1 1

输出：
3

---

样例3
输入
1 1 0
1 1

输出：
1

---

如果对你有帮助，点个赞再走吧！谢谢！