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

Claire0918 · 2025-09-28 14:58:58 · 题解

首先很自然的将剩下的数的和转为删去的数的和。看到 h, w \leq 15 首先想到 \mathcal{O}(2^h) 枚举第 i 行删或不删的状态，此时删除每一列的贡献就确定了，我们需要在 w 个数中选出一些数使得和为一个常数。直接考虑每个数删或不删的复杂度是 \mathcal{O}(2^w) 的，总复杂度达到了 \mathcal{O}(2^{h + w})，不能通过。

考虑将这 w 个数分成两个大小为 \frac{w}{2} 的部分，两个部分分别可以用 \mathcal{O}(2^\frac{w}{2}) 的复杂度计算出 2^\frac{w}{2} 个和。设我们要求的和的常数为 s，我们在第一组和中枚举到了 x，那么我们仅需检验第二组和中是否有 s - x 即可。使用 unordered_map 等恰当的实现即可做到单次检验 \mathcal{O}(1)，总时间复杂度 \mathcal{O}(2^{h + \frac{w}{2}}) \approx 2^{23}，可以通过。

Code：

#include<bits/stdc++.h>
#define mem(a, v) memset(a, v, sizeof(a))

using namespace std;

const int maxn = 15 + 10;

int n, m;
long long k;
int a[maxn][maxn];
long long b[maxn];
unordered_map<long long, int> f;

int main(){
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            scanf("%d", &a[i][j]);
        }
    }
    scanf("%lld", &k), k = -k;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; k += a[i][j++]);
    }
    for (int sta = 0; sta < 1 << n; sta++){
        long long now = k;
        for (int i = 1; i <= n; i++){
            if (sta >> i - 1 & 1){
                for (int j = 1; j <= m; now -= a[i][j++]);
            }
        }
        for (int i = 1; i <= m; i++){
            b[i] = 0;
            for (int j = 1; j <= n; j++){
                !(sta >> j - 1 & 1) && (b[i] += a[j][i]);
            }
        }
        f.clear();
        for (int st = 0; st < 1 << (m >> 1); st++){
            long long sum = 0;
            for (int i = 1; i <= m >> 1; i++){
                st >> i - 1 & 1 && (sum += b[i]);
            }
            f[sum] = st;
        }
        for (int st = 0; st < 1 << m - (m >> 1); st++){
            long long sum = 0;
            for (int i = m; i > m >> 1; i--){
                st >> m - i & 1 && (sum += b[i]);
            }
            if (f.count(now - sum)){
                printf("YES\n%d\n", __builtin_popcount(sta) + __builtin_popcount(f[now - sum]) + __builtin_popcount(st));
                for (int i = 1; i <= n; i++){
                    sta >> i - 1 & 1 && printf("1 %d\n", i);
                }
                for (int i = 1; i <= m >> 1; i++){
                    f[now - sum] >> i - 1 & 1 && printf("2 %d\n", i);
                }
                for (int i = m; i > m >> 1; i--){
                    st >> m - i & 1 && printf("2 %d\n", i);
                }
                return 0;
            }
        }
    }
    printf("NO");

return 0;
}