锐客网

  1. 首页 > it技术 > >

hdu|2016 Multi-University Training Contest 1 C Game(hdu 5725)

多校训练HDU

【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 */

    推荐阅读


    上一篇：纯CSS实现小圆点和三角形图案

    下一篇：饮一杯世茶，品味穿越千年的风味