题目连接：hdu_5110_Alexandra and COS
题意：
给你一个图，X代表宝藏，然后有一个船，它的声纳的频率为D，定船到宝藏的距离为Dis=max(abs(x1-x2),abs(y1-y2)),如果D是Dis的约数并且宝藏在船的上方开角45°，那么这个船就能探测到这个宝藏，现在给你q个询问，每一个询问有一个位置x,y和一个声纳的频率D，问这个船能探测到多少宝藏
题解：
因为是45°角，所以Dis实际就是abs(y1-y2)，然后我们可以对每一个D，DP它45°开角满足条件的前缀和，不过对每一个D都这样做，那肯定超时，仔细想想，D越大，直接暴力搜肯定会比DP来的快，因为直接暴力我们可以每次跳D格来找，所以这里我们就要分块，一般分为sqr=sqrt(n)，不过这里我亲测出数据好像当sqr=3时，跑的速度更快，然后我就直接分为D>3和D<=3来做
这里DP的方程为：设dp[i][j][k]为第i行，第j列，声纳频率为k的开角45°满足条件的前缀和，状态转移方程为dp[i][j][k]=dp[i-k][j-k][k]+dp[i-k][j+k][k]-dp[i-2*k][j][k]+第(i-k)行中[j-k,j+k]满足条件的点
（没装画图软件，画的有点丑，将就看）下面以D为2时举例，假设我们要查询x=5，y=3这个点，红色的代表满足条件的点，蓝色的线代表范围，我们可以看到粉圈内的点加了两次，所以要减掉，对应的范围就是dp[i-2*k][j][k]
#include<cstdio>
#include<cstring>
#include<algorithm>
#define F(i,a,b) for(int i=a;i<=b;++i)
using namespace std; const int N=;
int dp[N][N][],g[N][N],n,m,q;
char in[N][N]; int main(){
while(~scanf("%d%d%d",&n,&m,&q)){
F(i,,n)scanf("%s",in[i]+);
F(i,,n)F(j,,m)g[i][j]=g[i][j-]+(in[i][j]=='X');
for(int i=,*p,kk;i<=n;++i)F(j,,m)F(k,,){
p=&dp[i][j][k],*p=(in[i][j]=='X'),kk=k<<;
if(i>k){
if(j>k)*p+=dp[i-k][j-k][k]+g[i-k][j]-g[i-k][j-k];
else{
*p+=g[i-k][j];
if(i>kk)*p+=dp[i-kk][j][k]+g[i-kk][j-];
}
if(j+k<=m)*p+=dp[i-k][j+k][k]+g[i-k][j+k-]-g[i-k][j];
else{
*p+=g[i-k][m]-g[i-k][j];
if(i>kk)*p+=dp[i-kk][j][k]+g[i-kk][m]-g[i-kk][j];
}
if(i>kk)*p-=dp[i-kk][j][k];
}
}
for(int i=,c,r,w,ret;i<=q;i++){
scanf("%d%d%d",&r,&c,&w);
if(w>){
ret=;
for(int j=r,lf=c,rt=c;j>;j-=w,lf=max(lf-w,),rt=min(m,rt+w))
ret+=g[j][rt]-g[j][lf-];
printf("%d\n",ret);
}else printf("%d\n",dp[r][c][w]);
}
}
return ;
}