P11122 [ROIR 2024 Day 1] 表格游戏 题解

DHT666 · 2025-01-08 20:56:46 · 题解

是没有递归的题解诶！！！

题意

给定 n 行 m 列的矩阵，若干次操作：删一整行或整列，问能否使矩阵的和为 s，要输出方案。

思路

数据范围是 1\le n,m\le 15，考虑搜索，时间复杂度是 O(2^{n^2})，于是可以用 meet in the middle，折半搜索，优化为 O(2^{\frac{3}{2}n}n)。具体实现是先枚举行的删除情况，然后枚举一半的列的删除情况，再枚举另一半列的删除情况，用 map 来找匹配的一半即可。

Talk is cheap, show me the code.

代码有点丑，但还是比较清晰。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;

typedef long long LL;

const int N = 20;

int n, m;
LL s;
int a[N][N];
LL l[N];

unordered_map<LL, int> Map;

int main() {
    scanf("%d%d", &n, &m);

    LL sum = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            scanf("%d", &a[i][j]);
            sum += a[i][j];
        }
    }
    scanf("%lld", &s);

    if(sum == s) {
        puts("YES");
        printf("0");
        return 0;
    }

    int t1 = 0, t2 = 0, t3 = 0, res = 0;
    for(int i = 0; i < (1 << n); i++) { // 行的删除情况
        int re = n;
        for(int j = 1; j <= n; j++) {
            if((i >> j - 1) & 1) {
                re--;
            }
        }
        for(int j = 1; j <= m; j++) {
            l[j] = 0;
            for(int k = 1; k <= n; k++) {
                if((i >> k - 1) & 1) {
                    l[j] += a[k][j];
                }
            }
        }
        Map.clear();
        for(int j = 0; j < (1 << (m >> 1)); j++) { // 前一半列的删除情况
            LL t = 0;
            for(register int k = 1; k <= (m >> 1); k++) {
                if((j >> k - 1) & 1) {
                    t += l[k];
                }
            }
            Map[t] = j;
        }
        for(int j = 0; j < (1 << m - (m >> 1)); j++) { // 后一半列的删除情况
            LL t = 0;
            for(int k = 1; k <= m - (m >> 1); k++) {
                if((j >> k - 1) & 1) {
                    t += l[m / 2 + k];
                }
            }
            if(Map.count(s - t)) {
                t1 = Map[s - t];
                t2 = j;
                t3 = i;
                goto end; // 不用找最优解啦，随便一个就可以
            }
        }
    }

    puts("NO");
    return 0;

    end:;
    puts("YES");
    int cnt = 0; // 删除的数量
    for(int i = 1; i <= n; i++) {
        if(!((t3 >> i - 1) & 1)) {
            cnt++;
        }
    }
    for(int i = 1; i <= (m >> 1); i++) {
        if(!((t1 >> i - 1) & 1)) {
            cnt++;
        }
    }
    for(int i = 1; i <= m - (m >> 1); i++) {
        if(!((t2 >> i - 1) & 1)) {
            cnt++;
        }
    }
    printf("%d\n", cnt);
    for(int i = 1; i <= n; i++) {
        if(!((t3 >> i - 1) & 1)) {
            printf("1 %d\n", i);
        }
    }
    for(int i = 1; i <= (m >> 1); i++) {
        if(!((t1 >> i - 1) & 1)) {
            printf("2 %d\n", i);
        }
    }
    for(int i = 1; i <= m - (m >> 1); i++) {
        if(!((t2 >> i - 1) & 1)) {
            printf("2 %d\n", m / 2 + i);
        }
    }

    return 0;
}