【hdu|2016 Multi-University Training Contest 1 C Game(hdu 5725)】题目链接
题目大意 棋盘上有一些守卫，每个守卫的攻击范围是他周围的八个格子，以及他所在的行和列。
已知现在棋盘上没有两个守卫可以相互攻击到。
求棋盘上所有可行路径（不经过守卫）的平均长度。
题解 题解说的挺简单的。
这题一点都不简单。
首先要yy出一个结论：
从题目这个奇怪的条件（守卫攻击范围大，却只有经过时才会触发）可以发现，守卫的分布是比较稀疏的。
所以猜想任意一条路径最多只可能被一个守卫影响。
这个模拟几组数据就会有感觉，但具体不知道如何证明。
于是可以先算出所有路径的和，然后在把必须经过一个守卫的路径条数算出来，乘二加入答案。
现在的问题分成了两个：
1.如何求所有一开始的路径和。
2.如何求必须经过一个守卫的路径条数。
第一个还是相对好解决的，可以利用二维前缀和。
可以发现，如果一个方块B在当前方块A的左上方，那么B对答案的贡献是两个负的，A是两个正的，即 dis=xa?xb+ya?yb
如果B在A 的左下方，那么 dis=xa?xb+yb?ya
所有的情况都可以被这两种情况包含，但是要注意同一行的情况，不可以重复算。
然后考虑如何解决第二个问题。
首先可以想到的是如果两个格子在同一行（列），并且它们之间有一个守卫，那么它们一定要经过守卫。
但是这还远远不够。
比如这组数据：
7 7
######G
###G###
#G#####
####G##
##G####
#####G#
G######
（1,4）到（6,3）就要经过一个守卫。
行与列相似，这里只考虑列。
不仅是相邻两列，不同的列之间也有可能。
比如（1,4）到（7,6），也必须要经过一个守卫。
所以可以猜想，如果守卫的位置是单调向下的，那么就可以一直往后面更新，路径条数就是当前列的守卫以上的空格数*对应列的守卫以下的空格数。
比如，第四列可以一直更新到第六列。第六列对答案的贡献是1*5+1*3+1*1=9
单调向上也与单调向下类似，只是左右反一下罢了。
这组数据答案是4.7846。
代码写的很丑，跑得极慢。
#include
#include
using namespace std;
const int M=1005;
typedef long long ll;
char mp[M][M];
ll sum[2][M][M];
int tot[2][M][M],tmp[M],presum[4][M];
void solve(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;
i<=n;
i++)
scanf("%s",mp[i]+1);
for(int i=1;
i<=n;
i++)
presum[3][i]=m+1,presum[1][i]=0;
for(int i=1;
i<=m;
i++)
presum[2][i]=0,presum[0][i]=n+1;
for(int i=1;
i<=n;
i++)
for(int j=1;
j<=m;
j++)
if(mp[i][j]=='G'){
presum[3][i]=min(presum[3][i],j);
presum[1][i]=max(presum[1][i],j);
presum[0][j]=min(presum[0][j],i);
presum[2][j]=max(presum[2][j],i);
}
for(int i=1;
i<=n;
i++){
presum[3][i]--;
presum[1][i]=m-presum[1][i];
}
for(int i=1;
i<=m;
i++){
presum[0][i]--;
presum[2][i]=n-presum[2][i];
}
ll ans=0;
for(int i=1;
i<=n;
i++){
for(int j=i+1;
j<=n;
j++){
if(presum[3][j-1]3][j]&&presum[3][i]!=m&&presum[1][j]!=m){
ans+=2*presum[3][i]*presum[1][j];
}else break;
}
for(int j=i+1;
j<=n;
j++){
if(presum[3][j-1]>presum[3][j]&&presum[3][j]!=m&&presum[1][i]!=m){
ans+=2*presum[1][i]*presum[3][j];
}else break;
}
}
for(int i=1;
i<=m;
i++){
for(int j=i+1;
j<=m;
j++){
if(presum[0][j-1]>presum[0][j]&&presum[0][i]!=n&&presum[2][j]!=n){
ans+=2*presum[2][i]*presum[0][j];
}else break;
}
for(int j=i+1;
j<=m;
j++){
if(presum[0][j-1]0][j]&&presum[2][j]!=n&&presum[0][i]!=n){
ans+=2*presum[0][i]*presum[2][j];
}else break;
}
}
int cnt=0;
for(int i=1;
i<=n;
i++)
for(int j=1;
j<=m;
j++){
tot[0][i][j]=tot[0][i-1][j]+tot[0][i][j-1]-tot[0][i-1][j-1]+(mp[i][j]!='G');
sum[0][i][j]=sum[0][i-1][j]+sum[0][i][j-1]-sum[0][i-1][j-1]-(i+j)*(mp[i][j]!='G');
}
for(int i=n;
i>=1;
i--)
for(int j=1;
j<=m;
j++){
tot[1][i][j]=tot[1][i][j-1]+tot[1][i+1][j]-tot[1][i+1][j-1]+(mp[i][j]!='G');
sum[1][i][j]=sum[1][i][j-1]+sum[1][i+1][j]-sum[1][i+1][j-1]+(i-j)*(mp[i][j]!='G');
}
for(int i=1;
i<=n;
i++)
for(int j=1;
j<=m;
j++){
if(mp[i][j]=='G') continue;
ans+=1LL*(i+j)*tot[0][i][j]+sum[0][i][j];
ans+=1LL*(-i+j)*tot[1][i+1][j-1]+sum[1][i+1][j-1];
}
tmp[m+1]=0;
for(int i=1;
i<=n;
i++){
for(int j=m;
j>=1;
j--)
tmp[j]=tmp[j+1]+(mp[i][j]!='G');
for(int j=1;
j<=m;
j++)
if(mp[i][j]=='G')
ans+=2LL*(tot[0][i][j]-tot[0][i][j-1])*(tot[1][i][j]-tot[1][i][j-1])+2LL*(tot[0][i][j]-tot[0][i-1][j])*tmp[j];
else cnt++;
}
printf("%.4lf\n",(double)ans*2/cnt/cnt);
for(int i=1;
i<=n;
i++)
for(int j=1;
j<=m;
j++)
for(int k=0;
k<2;
k++)
tot[k][i][j]=sum[k][i][j]=0;
}
int main(){
int T;
scanf("%d",&T);
while(T--) solve();
return 0;
}
/*
4
3 3
##G
G##
###
2 2
##
G#
3 3
##G
G##
###
7 7
######G
###G###
#G#####
####G##
##G####
#####G#
G######1.7959
0.8889
1.7959
4.7846
*/
推荐阅读
- HDU|HDU 1576 A/B（拓展欧几里得，模板题）
- 比赛题解|2020 杭电多校9 1007 Game （平衡树）
- hdu|HDU 6133 Army Formations 树状数组 + 启发式合并
- HDU|HDU 5528 狄利克雷卷积
- hdu|【hdu 5354】Bipartite Graph【分治 并查集】
- online|hdu4115Eliminate the Conflict
- online|hdu5955Guessing the Dice Roll
- online|hdu1816Get Luffy Out *
- online|hdu3622Bomb Game