题解

代码如下

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int M, N, K, L, D;
    cin >> M >> N >> K >> L >> D;

    vector<int> row_cut(M, 0); // row_cut[i] = 第 i 行与 i+1 行之间的通道能阻断的对数（i 从 0 开始，对应行号 i+1）
    vector<int> col_cut(N, 0); // col_cut[j] = 第 j 列与 j+1 列之间的通道能阻断的对数（j 从 0 开始，对应列号 j+1）

    for (int i = 0; i < D; ++i) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        // 转为 0-indexed 更易处理，但题目用 1-indexed 输入
        --x1; --y1; --x2; --y2;

        if (x1 == x2) { // 左右相邻 → 影响列间隙
            int c = min(y1, y2); // 列间隙位置（0-indexed 列号，对应题目中第 c+1 列右侧）
            col_cut[c]++;
        } else if (y1 == y2) { // 上下相邻 → 影响行间隙
            int r = min(x1, x2); // 行间隙位置（0-indexed 行号，对应题目中第 r+1 行下方）
            row_cut[r]++;
        }
    }

    // 提取所有行间隙候选：(频次, 行号)
    vector<pair<int, int>> rows;
    for (int i = 0; i < M - 1; ++i) { // 行间隙共 M-1 个：0 ~ M-2
        rows.emplace_back(-row_cut[i], i + 1); // 负频次实现降序；i+1 是题目要求的 1-indexed 行号
    }
    sort(rows.begin(), rows.end());
    vector<int> ans_row;
    for (int i = 0; i < K && i < rows.size(); ++i) {
        ans_row.push_back(rows[i].second);
    }
    sort(ans_row.begin(), ans_row.end()); // 升序输出

    // 同理处理列
    vector<pair<int, int>> cols;
    for (int j = 0; j < N - 1; ++j) {
        cols.emplace_back(-col_cut[j], j + 1);
    }
    sort(cols.begin(), cols.end());
    vector<int> ans_col;
    for (int i = 0; i < L && i < cols.size(); ++i) {
        ans_col.push_back(cols[i].second);
    }
    sort(ans_col.begin(), ans_col.end());

    // 输出
    for (int i = 0; i < ans_row.size(); ++i) {
        if (i) cout << ' ';
        cout << ans_row[i];
    }
    cout << '\n';
    for (int i = 0; i < ans_col.size(); ++i) {
        if (i) cout << ' ';
        cout << ans_col[i];
    }
    cout << '\n';
}