【牛客_2020.10.27】飞行棋

本文主要是介绍【牛客_2020.10.27】飞行棋，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

飞行棋

---

嫅朑磃淥_{（解题思路）}

我们来进行分类讨论：

当 $i<d$ 时
设期望 $s$ 次扔到点 $1$ ，那么有：
$$s=\frac{d-2}{d-1}(s+1)+\frac{1}{d-1}$$
解得：
$$s=d-1$$
所以 $f[1$~$d-1]$ 的值就为 $d-1$

当 $i\ge d$ 时
我们有 $\frac{1}{d}$ 的概率走到 $i-d$~$i-1$ 的所有点，且走到 $i-d$ 不需要回合，那么有：
$$f[i]=\frac{{\sum }_{j=i-d+1}^{i-1}f[j]+1}{d}+\frac{f[i-d]}{d}$$
但是呢，如果这样的话时间复杂度是 $O(Tnd)$ ，而 $2\le d,n\le 100000$ ，所以这样肯定会爆。我们就用前缀和 $s$ 来优化，表达式就变成了这样：
$$f[i]=\frac{s[i-1]-s[i-d]+d-1}{d}+\frac{f[i-d]}{d}$$
于是时间复杂度就很优秀的达到了 $O(Tn)$

code

#include<iostream>
#include<cstdio>
using namespace std;int T;
int n,d;
double f[100010],s[100010];int main()
{cin>>T;while(T--){scanf("%d%d",&n,&d);f[0]=s[0]=1;for(int i=1;i<d;i++)f[i]=d-1,s[i]=s[i-1]+f[i];for(int i=d;i<=n;i++){f[i]=(s[i-1]-s[i-d]+d-1)/d+f[i-d]/d;s[i]=s[i-1]+f[i];}printf("%.2lf\n",f[n]);}
}

这篇关于【牛客_2020.10.27】飞行棋的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---