专栏文章

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

CClaire0918
P11122题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minrodpa
此快照首次捕获于
2025/12/02 07:15
3 个月前
此快照最后确认于
2025/12/02 07:15
3 个月前
查看原文
首先很自然的将剩下的数的和转为删去的数的和。看到 h,w≤15h, w \leq 15 首先想到 O(2h)\mathcal{O}(2^h) 枚举第 ii 行删或不删的状态，此时删除每一列的贡献就确定了，我们需要在 ww 个数中选出一些数使得和为一个常数。直接考虑每个数删或不删的复杂度是 O(2w)\mathcal{O}(2^w) 的，总复杂度达到了 O(2h+w)\mathcal{O}(2^{h + w})，不能通过。
考虑将这 ww 个数分成两个大小为 w2\frac{w}{2} 的部分，两个部分分别可以用 O(2w2)\mathcal{O}(2^\frac{w}{2}) 的复杂度计算出 2w22^\frac{w}{2} 个和。设我们要求的和的常数为 ss，我们在第一组和中枚举到了 xx，那么我们仅需检验第二组和中是否有 s−xs - x 即可。使用 unordered_map 等恰当的实现即可做到单次检验 O(1)\mathcal{O}(1)，总时间复杂度 O(2h+w2)≈223\mathcal{O}(2^{h + \frac{w}{2}}) \approx 2^{23}，可以通过。
Code：
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...