中国建设电工网站,做网站优化价格,能免费建手机网站吗,网站建设和管理专业好不好链接#xff1a; 文章目录题目描述题解#xff1a;代码#xff1a;时间限制#xff1a;C/C 1秒#xff0c;其他语言2秒
空间限制#xff1a;C/C 262144K#xff0c;其他语言524288K
64bit IO Format: %lld题目描述 帕秋莉掌握了一种土属性魔法 这种魔法可以在一片kk大小…链接
文章目录题目描述题解代码时间限制C/C 1秒其他语言2秒
空间限制C/C 262144K其他语言524288K
64bit IO Format: %lld题目描述 帕秋莉掌握了一种土属性魔法 这种魔法可以在一片k×k大小的一个正方形区域内产生地震 但是如果某片即将产生地震的区域内有建筑物帕秋莉会停止施法 整个地图大小为n×m其中一些地方有建筑 请问有多少种可能的情况使得帕秋莉会停止施法 输入描述: 第一行三个数n, m, k意义见描述 接下来一个n×m的01矩阵表示这篇区域的情况1表示这个地方有建筑 输出描述: 输出一个数表示答案 示例1 输入
4 4 2
1000
0100
0000
0001输出
5备注: 对于30%的数据n, m≤30 对于100%的数据n, m≤1000k≤min(n, m) 题解
关于二维前缀和的题目 我们都知道一维前缀和二维前缀和就是在一维的基础上建立的可以通过二维前缀和求出矩阵内一个任意的子矩阵的数的和。 dp [ i ] [ j ] 表示表示一个矩阵内数的总和 1,1与ij这两个点分别为这个矩阵的左上角和右下角。 状态转移方程为 dp [ i ] [ j ] d p [ i - 1 ] [ j ] dp [ i ] [j - 1 ] - d p [ i - 1 ] [ j -1 ] a [ i ] [ j ]
大致可以理解成整个矩形区域左边区域(1,1)~ (i,j-1)上面区域1,1~i-1,j减去重复区域红色部分再加上蓝色部分 当前点 i j 图片选自
放在本题 当矩阵某点 ( i , j ) 的值为1时dp [ i ] [ j ] 然后求出二维前缀和的值 然后我们可以通过这些值求出 矩阵的大小是固定的 k * k 的情况是否符合要求
我们枚举正方形右下角的点 i , j 对于1,1到ij的矩阵 sumdp [ ik−1 ] [ jk−1 ]− dp [ ik−1 ][ j−1 ]−dp [ i−1 ][ jk−1 ]dp [ i − 1 ] [ j− 1 ] 可以理解成二维前缀和的那个式子倒过来 用ij的二维前缀和也就是图中整个矩形减去上部分再减去左部分加上被多减的红色部分剩下的就是蓝色部分也就是我们所求的k*k大的矩阵 sum0,说明符合条件结果加一
代码
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int maxn1e34;
char a[maxn][maxn];
int dp[maxn][maxn];
int n,m,k;
int main()
{int sum0;cinnmk;for(int i1;in;i)for(int j1;jm;j){cina[i][j];}for(int i1;in;i)for(int j1;jm;j){dp[i][j]dp[i-1][j]dp[i][j-1]-dp[i-1][j-1];if(a[i][j]1)dp[i][j];}for(int ik;in;i)for(int jk;jm;j){if(dp[i][j]-dp[i-k][j]-dp[i][j-k]dp[i-k][j-k])sum;}coutsumendl;return 0;
}
