2020-2021:teams:mian:hdu_training:2016_multi-university_training_contest_1
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:mian:hdu_training:2016_multi-university_training_contest_1 [2020/05/26 23:15] gary |
2020-2021:teams:mian:hdu_training:2016_multi-university_training_contest_1 [2020/07/05 11:33] (当前版本) grapelemonade ↷ 页面2020-2021:teams:mian:hdutraining:2016_multi-university_training_contest_1被移动至2020-2021:teams:mian:hdu_training:2016_multi-university_training_contest_1 |
||
|---|---|---|---|
| 行 169: | 行 169: | ||
| ===== C: Game ===== | ===== C: Game ===== | ||
| + | * Idea by **//Gary//** | ||
| + | * Debug by **//Gary,Pantw//** | ||
| + | * Code by **//Gary//** | ||
| ==== 题意 ==== | ==== 题意 ==== | ||
| + | |||
| + | $n\times m$方格中有一些守卫，保证一个守卫同行同列以及以它为中心的九宫格内没有其他守卫，任意选方格中没有守卫的两点，求两点最短距离的期望 | ||
| + | |||
| + | $1\le n,m\le1000$ | ||
| ==== 解法 ==== | ==== 解法 ==== | ||
| + | 简单画图可以发现没有守卫时的最短距离即为曼哈顿距离，当被守卫隔开时最短距离即为曼哈顿距离+2 | ||
| + | |||
| + | 因而考虑将两种情况分开求解，先求的所有点对的曼哈顿距离，再求出隔开的点对额外的贡献，$\rm Ans=\frac{\sum dis}{\sum_{x,y\in没有守卫的点}1}$ | ||
| + | |||
| + | 曼哈顿距离可以通过遍历每行和每列来求解，如对于第i列，经过第i列的点对为$sum_{i左侧}\times sum_{i右侧}$，每一个点对都会对曼哈顿距离贡献1，求前缀和后扫描每行每列即可 | ||
| + | |||
| + | 对于守卫隔开的贡献，发现只有连续单调的守卫两边的点对会造成贡献，因为守卫个数极少，对每个守卫$O(n)$扫描来维护最长的连续单调守卫造成的贡献即可 | ||
| + | |||
| + | {{:2020-2021:teams:mian:hdutraining:4.png?400|}} | ||
| ===== D: GCD ===== | ===== D: GCD ===== | ||
2020-2021/teams/mian/hdu_training/2016_multi-university_training_contest_1.1590506102.txt.gz · 最后更改: 2020/05/26 23:15 由 gary
