自动搬运

查看原文

来自洛谷，原作者为

	DHT666 听自己的歌，写自己的故事。​

搬运于2025-08-24 23:04:25，当前版本为作者最后更新于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;
}