求hack,数据点太水了
查看原帖
求hack,数据点太水了
137172
xpc2024楼主2024/8/10 13:31

复杂度 O(n5n^5) 按道理是超时的结果也能AC

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

int a[105][105];

int main() {
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= n; ++ i) {
		for(int j = 1; j <= m; ++ j) {
			cin >> a[i][j];
		}
	}
	
	int ans = 0;
	for(int l = 1; l <= min(n, m); ++ l) { // 遍历正方形的边长
		// (i, j) 遍历终点 
		for(int i = l; i <= n; ++ i) {
			for(int j = l; j <= m; ++ j) {
				
				// 矩阵的范围为 (i-l+1, j-l+1) 到 (i, j), 暴力枚举求和 
				int t = 0; 
				for(int i1 = i - l + 1; i1 <= i; ++ i1) {
					for(int j1 = j - l + 1; j1 <= j; ++ j1) {
						t += a[i1][j1];
					}
				}
				// 如果满足 更新答案 
				if(t == l * l) {
					ans = max(ans, l);
				}
				
			}
		}	
	}
	cout << ans;
	return 0;
}
2024/8/10 13:31
加载中...