eJOI2019 Problem C. T - Covering 题解

问题描述

在一个 $m \times n$ 的网格中，每个格子有一个非负权值 $a_{ij}$。给定 $k$ 个特殊格子 $(r_i, c_i)$，要求：

1. 每个特殊格子必须作为一个 T 形拼板的中心
2. T 形拼板有四种方向（上、下、左、右），每个拼板覆盖中心及相邻的三个格子
3. 拼板不能重叠，且不能超出网格边界
4. 要求最大化被覆盖格子的权值和

如果不存在合法方案，输出 No；否则输出最大权值和。

数据范围：$1 \le k \le nm \le 10^6$，$0 \le a_{ij} \le 10^3$

核心观察

1. T 形拼板的结构

以中心 $(r, c)$ 为例，四种方向覆盖的格子：

• 上：$(r-1, c), (r, c), (r+1, c), (r, c-1)$
• 下：$(r-1, c), (r, c), (r+1, c), (r, c+1)$
• 左：$(r, c-1), (r, c), (r, c+1), (r-1, c)$
• 右：$(r, c-1), (r, c), (r, c+1), (r+1, c)$

关键点：每个 T 形拼板覆盖 4 个格子，其中中心格子必须是特殊格子，其他三个是普通格子。

2. 冲突分析

两个特殊格子如果距离太近，它们的 T 形拼板可能会重叠：

• 如果两个特殊格子曼哈顿距离 ≤ 2，它们可能冲突
• 特别是当它们在同一行或同一列且距离为 2 时，一定会冲突
• 距离为 1 时（相邻），某些方向组合可能导致重叠

3. 图论建模

我们可以将问题转化为图论问题：

• 每个特殊格子是一个节点
• 如果两个特殊格子的拼板可能重叠，则在它们之间连边
• 我们需要为每个节点选择一种方向（上、下、左、右）
• 边的约束：相邻节点不能选择导致重叠的方向

这类似于图着色或约束满足问题。

进一步分析

1. 局部结构

考虑两个特殊格子 $(r_1, c_1)$ 和 $(r_2, c_2)$：

• 如果 $\max(|r_1-r_2|, |c_1-c_2|) > 2$：它们永远不会冲突
• 如果 $\max(|r_1-r_2|, |c_1-c_2|) = 2$：可能冲突，取决于具体位置和方向
• 如果 $\max(|r_1-r_2|, |c_1-c_2|) = 1$（相邻）：可能冲突

2. 权值计算

对于特殊格子 $(r, c)$，选择不同方向时，覆盖的权值和不同：

• 上：$a_{r-1,c} + a_{r,c} + a_{r+1,c} + a_{r,c-1}$
• 下：$a_{r-1,c} + a_{r,c} + a_{r+1,c} + a_{r,c+1}$
• 左：$a_{r,c-1} + a_{r,c} + a_{r,c+1} + a_{r-1,c}$
• 右：$a_{r,c-1} + a_{r,c} + a_{r,c+1} + a_{r+1,c}$

注意：需要检查方向是否合法（不能超出网格边界）。

3. 图的性质

根据数据范围的子任务提示：

• 子任务 1：特殊格子之间距离 > 2 → 没有冲突，每个可以独立选择最大方向
• 子任务 3：特殊格子之间距离 ≠ 2 → 只有相邻（距离=1）可能冲突
• 子任务 4：所有特殊格子在同一行 → 简化为一维问题

一般情况算法设计

1. 冲突图构建

对于每个特殊格子 $i$，检查所有 $j > i$：

• 如果 $\max(|r_i-r_j|, |c_i-c_j|) \le 2$，则可能冲突，需要详细检查
• 具体检查方法：枚举 $i$ 的 4 种方向和 $j$ 的 4 种方向，如果存在格子重叠，则记录冲突

优化：由于 $k$ 可能很大，不能检查所有 $O(k^2)$ 对。 实际上，冲突只可能发生在距离 ≤ 2 的格子间，因此可以：

• 将所有特殊格子按 $(r, c)$ 排序
• 对于每个格子，只检查周围 $5 \times 5$ 区域内的其他特殊格子

2. 约束图的性质

对于两个冲突的特殊格子，它们的合法方向组合是受限的。 我们可以为每对冲突的格子 $(i, j)$ 建立约束：

• 如果 $i$ 选择方向 $d_i$，那么 $j$ 不能选择某些方向 $d_j$

这可以建模为 2-SAT 问题：

• 每个格子有 4 种可能的方向 → 4 个布尔变量
• 但需要约束：每个格子必须选择恰好一种方向
• 冲突约束：某些方向组合不能同时选择

3. 2-SAT 建模

对于格子 $i$，创建 4 个布尔变量 $x_{i,d}$ 表示是否选择方向 $d$。 约束：

1. 至少一个方向：$x_{i,0} \lor x_{i,1} \lor x_{i,2} \lor x_{i,3} = true$
2. 至多一个方向：对于任意 $d_1 \neq d_2$，$\lnot x_{i,d_1} \lor \lnot x_{i,d_2} = true$
3. 冲突约束：对于格子 $i, j$，如果方向 $d_i$ 和 $d_j$ 冲突，则 $\lnot x_{i,d_i} \lor \lnot x_{j,d_j} = true$

4. 带权重的 2-SAT

我们需要最大化权值和，而不仅仅是判断可行性。 这可以通过：

• 二分答案：检查是否存在方案使得总权值 ≥ $mid$
• 最小割/最大流：将 2-SAT 与权重结合
• DP on Tree：如果冲突图是树或森林

实际上，由于冲突只发生在局部，图可能是稀疏的，甚至可能是二分图。

更实用的方法：独立集建模

1. 冲突图的补图

考虑冲突图的补图：如果两个格子的某些方向组合不冲突，则在它们之间连边。 但我们需要为每个格子选择一个方向，这相当于在补图中找大小为 $k$ 的独立集（每个格子一个节点，但每个格子有 4 个节点对应不同方向）。

2. 转化为最大权独立集

为每个"方向节点"赋予权值（该方向覆盖的权值和）。 约束：

1. 对于同一个格子，至多选一个方向节点
2. 对于冲突的方向节点，不能同时选择

这实际上是最大权独立集问题，在一般图中是 NP-hard。 但由于冲突是局部的，图可能有特殊结构。

3. 基于距离的分析

观察发现：如果两个特殊格子曼哈顿距离 ≥ 3，它们的所有方向组合都不冲突。 因此，冲突图实际上是局部稠密但全局稀疏的。

针对数据范围的算法

子任务 1 ($k \le 10^3$，距离 > 2)

最简单情况：所有格子独立，答案 = $\sum_{i=1}^k \max(\text{方向权值})$

子任务 5 ($k \le 10$)

暴力枚举：$4^{10} = 1048576$ 种可能，可以暴力检查。

子任务 6 ($k \le 10^3$)

可以使用带剪枝的搜索或DP：

• 按某种顺序（如行优先）处理格子
• 维护已覆盖的格子集合
• 剪枝：如果当前部分已冲突，回溯

一般情况 ($k \le 10^6$)

需要更高效的算法。注意到：

1. 冲突是局部的
2. 网格最多 $10^6$ 个格子，但 $k$ 可能接近 $nm$
3. 权值范围小 ($0 \le a_{ij} \le 1000$)

一个可行思路：贪心 + 调整

1. 初始：每个格子选择权值最大的方向
2. 检查冲突，调整冲突的格子
3. 调整时尽量保持权值最大

但由于是求精确解，贪心可能不是最优。

实现方案（针对中等规模）

以下实现针对 $k \le 1000$ 的情况，使用回溯搜索 + 剪枝。

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

typedef long long ll;

struct Point {
    int r, c;
    int idx;  // 在特殊格子数组中的索引
};

int m, n, k;
vector<vector<int>> a;
vector<Point> special;
vector<vector<int>> dir_values;  // dir_values[i][d]: 格子i选择方向d的权值
vector<bool> valid_dir[4];       // valid_dir[d][i]: 方向d对格子i是否合法

// 方向定义：0上, 1下, 2左, 3右
int dr_center[4] = {0, 0, 0, 0};
int dc_center[4] = {0, 0, 0, 0};
int dr_offsets[4][3] = {
    {-1, 1, 0},   // 上：上，下，左
    {-1, 1, 0},   // 下：上，下，右  
    {0, 0, 0},    // 左：左，右，上
    {0, 0, 0}     // 右：左，右，下
};
int dc_offsets[4][3] = {
    {0, 0, -1},   // 上
    {0, 0, 1},    // 下
    {-1, 1, 0},   // 左
    {-1, 1, 0}    // 右
};

// 检查方向是否合法（不超出边界）
bool check_valid(int idx, int dir) {
    int r = special[idx].r, c = special[idx].c;
    
    // 检查中心
    if (r < 0 || r >= m || c < 0 || c >= n) return false;
    
    // 检查三个扩展格子
    for (int t = 0; t < 3; t++) {
        int nr = r + dr_offsets[dir][t];
        int nc = c + dc_offsets[dir][t];
        if (nr < 0 || nr >= m || nc < 0 || nc >= n) return false;
    }
    
    return true;
}

// 计算方向权值
int calc_value(int idx, int dir) {
    int r = special[idx].r, c = special[idx].c;
    int sum = a[r][c];  // 中心
    
    for (int t = 0; t < 3; t++) {
        int nr = r + dr_offsets[dir][t];
        int nc = c + dc_offsets[dir][t];
        sum += a[nr][nc];
    }
    
    return sum;
}

// 检查两个格子的方向是否冲突
bool check_conflict(int i, int dir_i, int j, int dir_j) {
    Point &p1 = special[i], &p2 = special[j];
    
    // 收集格子i覆盖的所有位置
    set<pair<int, int>> cells_i, cells_j;
    
    cells_i.insert({p1.r, p1.c});
    for (int t = 0; t < 3; t++) {
        int nr = p1.r + dr_offsets[dir_i][t];
        int nc = p1.c + dc_offsets[dir_i][t];
        cells_i.insert({nr, nc});
    }
    
    cells_j.insert({p2.r, p2.c});
    for (int t = 0; t < 3; t++) {
        int nr = p2.r + dr_offsets[dir_j][t];
        int nc = p2.c + dc_offsets[dir_j][t];
        cells_j.insert({nr, nc});
    }
    
    // 检查交集
    for (auto &cell : cells_i) {
        if (cells_j.count(cell)) return true;
    }
    
    return false;
}

// 回溯搜索
ll best_sum = -1;
vector<int> best_choice;

void dfs(int idx, ll current_sum, vector<int> &choice, vector<set<pair<int, int>>> &covered) {
    if (idx == k) {
        if (current_sum > best_sum) {
            best_sum = current_sum;
            best_choice = choice;
        }
        return;
    }
    
    // 剪枝：估算最大可能值
    ll max_possible = current_sum;
    for (int i = idx; i < k; i++) {
        int max_dir_val = 0;
        for (int d = 0; d < 4; d++) {
            if (valid_dir[d][i]) max_dir_val = max(max_dir_val, dir_values[i][d]);
        }
        max_possible += max_dir_val;
    }
    if (max_possible <= best_sum) return;
    
    // 尝试当前格子的所有合法方向
    for (int d = 0; d < 4; d++) {
        if (!valid_dir[d][idx]) continue;
        
        // 检查是否与已选格子冲突
        bool conflict = false;
        Point &p = special[idx];
        
        // 收集当前方向覆盖的格子
        vector<pair<int, int>> cells;
        cells.push_back({p.r, p.c});
        for (int t = 0; t < 3; t++) {
            int nr = p.r + dr_offsets[d][t];
            int nc = p.c + dc_offsets[d][t];
            cells.push_back({nr, nc});
        }
        
        // 检查是否与之前覆盖的格子冲突
        for (auto &cell : cells) {
            if (covered[idx].count(cell)) {
                conflict = true;
                break;
            }
        }
        
        if (conflict) continue;
        
        // 选择这个方向
        choice[idx] = d;
        
        // 更新覆盖集合（只记录与后续格子可能冲突的部分）
        // 实际上，我们只需要记录当前格子覆盖的位置
        // 对于冲突检查，我们可以在后续递归中直接比较
        
        dfs(idx + 1, current_sum + dir_values[idx][d], choice, covered);
        
        // 回溯
        choice[idx] = -1;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> m >> n;
    a.resize(m, vector<int>(n));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
        }
    }
    
    cin >> k;
    special.resize(k);
    for (int i = 0; i < k; i++) {
        cin >> special[i].r >> special[i].c;
        special[i].idx = i;
    }
    
    // 初始化方向信息
    dir_values.resize(k, vector<int>(4, 0));
    for (int d = 0; d < 4; d++) {
        valid_dir[d].resize(k, false);
    }
    
    for (int i = 0; i < k; i++) {
        for (int d = 0; d < 4; d++) {
            valid_dir[d][i] = check_valid(i, d);
            if (valid_dir[d][i]) {
                dir_values[i][d] = calc_value(i, d);
            }
        }
    }
    
    // 检查每个格子是否至少有一个合法方向
    for (int i = 0; i < k; i++) {
        bool has_valid = false;
        for (int d = 0; d < 4; d++) {
            if (valid_dir[d][i]) {
                has_valid = true;
                break;
            }
        }
        if (!has_valid) {
            cout << "No" << endl;
            return 0;
        }
    }
    
    // 构建冲突关系（只记录可能冲突的格子对）
    vector<vector<int>> conflicts(k);
    for (int i = 0; i < k; i++) {
        for (int j = i + 1; j < k; j++) {
            // 快速判断：如果距离 > 2，不可能冲突
            if (abs(special[i].r - special[j].r) > 2 || 
                abs(special[i].c - special[j].c) > 2) {
                continue;
            }
            
            // 详细检查所有方向组合
            bool may_conflict = false;
            for (int d1 = 0; d1 < 4 && !may_conflict; d1++) {
                if (!valid_dir[d1][i]) continue;
                for (int d2 = 0; d2 < 4; d2++) {
                    if (!valid_dir[d2][j]) continue;
                    if (check_conflict(i, d1, j, d2)) {
                        may_conflict = true;
                        break;
                    }
                }
            }
            
            if (may_conflict) {
                conflicts[i].push_back(j);
                conflicts[j].push_back(i);
            }
        }
    }
    
    // 回溯搜索
    vector<int> choice(k, -1);
    vector<set<pair<int, int>>> covered(k);
    best_sum = -1;
    
    dfs(0, 0, choice, covered);
    
    if (best_sum == -1) {
        cout << "No" << endl;
    } else {
        cout << best_sum << endl;
        
        // 如果需要输出方案，可以输出best_choice
        // for (int i = 0; i < k; i++) {
        //     cout << i << ": " << best_choice[i] << endl;
        // }
    }
    
    return 0;
}

优化建议

对于 $k \le 10^3$，上述回溯算法可能仍然较慢。可以进一步优化：

1. 排序：按度（冲突数）从大到小排序，先处理约束多的格子
2. 启发式：优先选择权值大的方向
3. 记忆化：使用状态压缩DP，但状态空间可能太大
4. 转化为二分图匹配：如果图结构特殊

理论上的最优算法

对于一般情况，这个问题是 NP-hard 的（可以归约到 3-SAT 或最大独立集）。 但在实际数据中，由于网格结构和距离限制，可能存在多项式算法：

• 如果冲突图是二分图：可以使用最大权匹配
• 如果冲突图是弦图：可以多项式求解最大权独立集
• 基于树宽动态规划：如果树宽小

总结

本题是组合优化问题，核心挑战在于：

1. 处理局部冲突约束
2. 在大搜索空间中寻找最大权值方案
3. 平衡算法复杂度和实际性能

对于竞赛，通常需要根据数据范围选择合适算法：

• 小 $k$：暴力搜索
• 中等 $k$：回溯+剪枝
• 大 $k$：需要利用图结构特性或近似算法

实际实现时，还需要注意内存和时间的优化，特别是 $k$ 接近 $10^6$ 时。