hiho一下第222周《Big Plus》题目分析

7
0

《Big Plus》题目分析

解决本题需要使用一个经典的优化技巧：前缀和。

对于矩阵中每一个位置(i, j)，我们可以计算up[i][j]， down[i][j], left[i][j], right[i][j]，一次是从(i, j)开始，向上下左右四个方向最多能延伸出多少连续的1。

如果A[i][j]=0，则up[i][j]=down[i][j]=left[i][j]=right[i][j]=0利用类似前缀和的技巧，否则有递推式：

up[i][j] = up[i - 1][j] + 1
down[i][j] = down[i + 1][j] + 1
left[i][j] = left[i][j -  1] + 1
right[i][j] = right[i][j + 1] + 1

我们可以先从上到下，从左到右计算出up[i][j]和left[i][j]，再反向计算出down[i][j]和right[i][j]。时间复杂度是O(N^2)。

最后对于每个(i, j)，up[i][j], down[i][j], left[i][j], right[i][j]的最小值就是以(i, j)为中心的Plus的size。所有(i, j)的最大值就是答案。

2 answer(s)

0

include

define ll long long

using namespace std;

ll p2,p1,q2,q1; ll a,b,c,d,x,y,ret,ans=1e18;

int main(){ cin>>a>>b>>c>>p1>>p2>>q1>>q2; d=__gcd(a,b); if(a==0&&b==0&&c==0) puts("0"); else if(((a==0)&&(b==0)&&c!=0)||c%d!=0) puts("Kuon"); else if(b==0&&a!=0){ if(c%a!=0) puts("Kuon"); else x=c/a,cout<

0

include

using namespace std;

int main() { int matrix_length; cin >> matrix_length; cin.ignore(); int*matrix = new int[matrix_length]; for (int i = 0; i < matrix_length; i++) { matrix[i] = new int[matrix_length]; } for (int i = 0; i < matrix_length; i++) { for (int j = 0; j < matrix_length; j++) matrix[i][j] = cin.get() -'0'; cin.ignore(); } int max = 0; for (int i = 1; i < matrix_length - 1; i++) { for (int j = 1; j < matrix_length - 1; j++) { if (matrix[i][j] == 1) { int u, d, l, r; for (u = 0; u < j&&matrix[i][j - u - 1] == 1; u++); for (d = 0; d < matrix_length - j-1 && matrix[i][j + d + 1] == 1; d++); for (l = 0; l < i&&matrix[i - l - 1][j] == 1; l++); for (r= 0; r < matrix_length - i-1 && matrix[i + r + 1][j] == 1; r++); int min = 0; if (u > d) min = d; else min = u; if (min > l) min = l; else if (min > r) min = r; if (max < min) max = min; } }

}
cout << max;
delete []matrix;
system("pause");
return 0;

}

write answer 切换为英文 切换为中文

转发分享

▲