题目链接：https://nanti.jisuanke.com/t/16445
题意：
给你一个n*n大小的01矩阵，和一个k*k大小的锤子，锤子只能斜着砸，问只砸一次最多能砸到多少个1。
题解：
将原矩阵顺时针旋转45°，二维前缀和预处理，然后枚举每一个可能砸到的正方形之和并取最大。
注：枚举的正方形的四个顶点必须是从原矩阵旋转过来的点，否则会出现砸到下面的这种情况：
（*代表不是原矩阵旋转过来的点，阴影代表砸到的部分）
代码中用vis数组判断是否为原矩阵中旋转过来的点。
AC Code：
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 4005 using namespace std; int n,k,t;
int ans;
int a[MAX_N][MAX_N];
int sum[MAX_N][MAX_N];
bool vis[MAX_N][MAX_N]; void read()
{
memset(a,,sizeof(a));
memset(vis,false,sizeof(vis));
scanf("%d%d",&n,&k);
t=n;
int temp;
for(int i=;i<n;i++)
{
for(int j=;j<n;j++)
{
scanf("%d",&temp);
a[i+j][n--i+j]=temp;
vis[i+j][n--i+j]=true;
}
}
n=n*-;
k=k*-;
} bool is_legal(int x,int y)
{
return x+y>=t- && n--x+y>=t- && n--y+x>=t- && *n--x-y>=t- && vis[x][y];
} void cal_sum()
{
for(int i=;i<n;i++)
{
for(int j=;j<n;j++)
{
if(i->=) sum[i][j]+=sum[i-][j];
if(j->=) sum[i][j]+=sum[i][j-];
if(i->= && j->=) sum[i][j]-=sum[i-][j-];
sum[i][j]+=a[i][j];
}
}
} int cal_max()
{
int maxn=;
for(int i=;i<n && i+k-<n;i++)
{
for(int j=;j<n && j+k-<n;j++)
{
if(!is_legal(i,j) || !is_legal(i,j+k-) || !is_legal(i+k-,j) || !is_legal(i+k-,j+k-)) continue;
int now=sum[i+k-][j+k-];
if(i->=) now-=sum[i-][j+k-];
if(j->=) now-=sum[i+k-][j-];
if(i->= && j->=) now+=sum[i-][j-];
maxn=max(maxn,now);
}
}
return maxn;
} void solve()
{
cal_sum();
ans=cal_max();
} void print()
{
printf("%d\n",ans);
} int main()
{
read();
solve();
print();
}