WA on #8,#9求助,回赠关注
查看原帖
WA on #8,#9求助,回赠关注
461366
封禁用户楼主2022/8/8 15:47

感谢您进来了!

如果您能指出我代码中的错误or给一组HACK,我将会回赠关注(2个号),同时小号会挂上您的友链。

感激不尽。

#include <bits/stdc++.h>
using namespace std;

int n, m, k;
char a[1000][1000];
int pre[1000][1000];
int ans, U, D, L, R;
char C;

void update(char c) { // 尝试填充灰色或者棕色 
	// 做一个纵列的前缀和 
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (a[i][j] == 'B') {
				pre[i][j] = pre[i - 1][j] + (c == 'B' ? 0 : 1);
			} else if (a[i][j] == 'G') {
				pre[i][j] = pre[i - 1][j] + (c == 'G' ? 0 : 1);
			} else {
				pre[i][j] = pre[i - 1][j] + 300000;
				// 写一个永远取不到的数字,这样在左端点更新的时候就能忽略这一行,因为紫名是无敌的,不能改 
			}
		}
	} 
	for (int u = 1; u <= n; u++) {
		for (int d = u; d <= n; d++) {
			// 枚举上下界,总和为0 
			int l = 1, r = 0, cnt = 0;
			while (r < m) {
				do {
					r++;  // r端点必须要往前,不然就没有继续循环的意义了 
					cnt += pre[d][r] - pre[u - 1][r];  // 总和加上右边的和 
				} while (r < m && cnt + pre[d][r + 1] - pre[u - 1][r + 1] <= k);  // 如果cnt在加下一列的情况下还是合法的,那么继续走 
				while (cnt > k) {  // 左端点更新到cnt合法 
					cnt -= pre[d][l] - pre[u - 1][l];
					l++; 
				}
				if (ans < (d - u + 1) * (r - l + 1)) {  // 更新答案 
					ans = (d - u + 1) * (r - l + 1);
					U = u;
					D = d;
					L = l;
					R = r;
					C = c;
				}
			}
		}
	}
}

void updateP() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			pre[i][j] = pre[i - 1][j];
			if (a[i][j] == 'P') {
				pre[i][j]++;
			}
		}
	}
	for (int u = 1; u <= n; u++) {
		for (int d = u; d <= n; d++) {
			int l, r = 0;
			while (r < m && pre[d][r + 1] - pre[u - 1][r + 1] != (d - u + 1)) r++;
			while (r < m && pre[d][r + 1] - pre[u - 1][r + 1] == (d - u + 1)) r++;
			if (pre[d][r] - pre[u - 1][r] != (d - u + 1)) break;
			l = r;
			while (pre[d][l - 1] - pre[u - 1][l - 1] == (d - u + 1)) l--;
			if (ans < (d - u + 1) * (r - l + 1)) {
				ans = (d - u + 1) * (r - l + 1);
				U = u;
				D = d;
				L = l;
				R = r;
				C = 'P';
			}
		}
	}
}

int main() {
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
		}
	}
	update('G');
	update('B');
	updateP();
	cout << ans << endl;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (U <= i && i <= D && L <= j && j <= R) {
				cout << C;
			} else {
				cout << a[i][j];
			}
		}
		cout << endl;
	}
	return 0;
}
2022/8/8 15:47
加载中...