算法标签

• 状态压缩动态规划
• 子集枚举
• 位运算

题目解析

这个问题要求我们通过删除行和列来使得剩余表格的元素和等于目标值 $s$。由于 $h, w \leq 15$，我们可以使用状态压缩的方法来枚举所有可能的行和列组合。

关键思路

1. 问题本质：删除行和列等价于选择保留哪些行和哪些列。最终表格的和就是所有被保留的单元格的和。

2. 状态表示：用两个位掩码 maskR 和 maskC 分别表示保留的行和列。

3. 预处理：对于每个行掩码和列掩码的组合，计算对应的子矩阵和。但直接枚举所有 $2^h \times 2^w$ 种组合会超时（$2^{30} ≈ 10^9$）。

4. 优化策略：

   • 先枚举行子集，计算每行在列方向上的前缀和
   • 对于每个行子集，使用动态规划或双指针在列方向上寻找和为特定值的子集

5. 可行性判断：检查是否存在行子集和列子集，使得对应的子矩阵和等于 $s$。

算法步骤

1. 读入 $h, w$ 和矩阵数据
2. 预处理每行的前缀和数组
3. 枚举行子集（位掩码）：
   • 计算该行子集下，每列的和（列和数组）
   • 使用哈希表记录列子集的和及其掩码
4. 对于每个行子集，检查是否存在列子集使得总和 = $s$
5. 如果找到解，构造操作序列：
   • 删除的行 = 未被行掩码选中的行
   • 删除的列 = 未被列掩码选中的列
6. 输出操作序列

复杂度分析

• 时间复杂度：$O(2^h \times w)$ 或 $O(2^h \times 2^w)$ 的优化版本
• 空间复杂度：$O(2^w)$ 用于存储列子集信息

代码实现

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

typedef long long ll;

int h, w;
ll s;
vector<vector<ll>> a;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> h >> w;
    a.assign(h, vector<ll>(w));
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> a[i][j];
        }
    }
    cin >> s;
    
    // 预处理每行的前缀和
    vector<vector<ll>> rowPrefix(h, vector<ll>(w + 1, 0));
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            rowPrefix[i][j + 1] = rowPrefix[i][j] + a[i][j];
        }
    }
    
    // 枚举行子集
    for (int maskR = 1; maskR < (1 << h); maskR++) {
        vector<ll> colSum(w, 0);
        for (int j = 0; j < w; j++) {
            for (int i = 0; i < h; i++) {
                if (maskR >> i & 1) {
                    colSum[j] += a[i][j];
                }
            }
        }
        
        // 预处理列的前缀和
        vector<ll> colPrefix(w + 1, 0);
        for (int j = 0; j < w; j++) {
            colPrefix[j + 1] = colPrefix[j] + colSum[j];
        }
        
        // 使用哈希表记录列子集的和
        unordered_map<ll, int> sumToMask;
        for (int maskC = 1; maskC < (1 << w); maskC++) {
            ll total = 0;
            for (int j = 0; j < w; j++) {
                if (maskC >> j & 1) {
                    total += colSum[j];
                }
            }
            sumToMask[total] = maskC;
        }
        
        // 检查目标值
        if (sumToMask.count(s)) {
            int maskC = sumToMask[s];
            
            // 构造操作序列
            vector<pair<int, int>> operations;
            
            // 删除行（未被选中的行）
            for (int i = h - 1; i >= 0; i--) {
                if (!(maskR >> i & 1)) {
                    operations.push_back({1, i + 1}); // 题目中行号从1开始
                }
            }
            
            // 删除列（未被选中的列）
            for (int j = w - 1; j >= 0; j--) {
                if (!(maskC >> j & 1)) {
                    operations.push_back({2, j + 1}); // 题目中列号从1开始
                }
            }
            
            cout << "YES\n";
            cout << operations.size() << "\n";
            for (auto& op : operations) {
                cout << op.first << " " << op.second << "\n";
            }
            return 0;
        }
    }
    
    cout << "NO\n";
    return 0;
}

优化版本（处理大数据）

对于 $h, w \leq 15$ 的情况，上面的代码已经足够。但如果数据规模更大，可以考虑以下优化：

1. 双向搜索：分别处理行的一半和另一半，然后合并结果
2. 折半枚举：当 $h$ 或 $w$ 较大时，将问题分成两半处理

总结

本题的关键是将行和列的选择分开处理，通过预处理和状态压缩来降低复杂度。算法充分利用了 $h, w \leq 15$ 的条件，使得状态压缩成为可行的解决方案。