【题解】D-飞行棋(7612. 2020牛客NOIP赛前集训营-普及组(第五场))

T4 飞行棋

https://ac.nowcoder.com/acm/contest/7612/D

D-飞行棋

思路

为从 走到 的 步数。

  • 时,
  • 时, 期望为

来源:2020牛客NOIP赛前集训营-普及组(第五场)题解 【链接】

代码

#include<bits/stdc++.h>

using namespace std;

int main() {
    int t;
    cin >> t;
    while(t--) {
        int n, d;
        cin >> n >> d;
        if(d == 1) {
            cout << "1.00" << endl;
        }
        else if(n < d) {
            cout << fixed << setprecision(2) << d-1.00 << endl;
        }
        else {
            double f[100005], sum[100005];
            memset(f, 0x00, sizeof(f));
            memset(sum, 0x00, sizeof(sum));
            f[0] = sum[0] = 1;
            for(int i = 1 ; i < d, i <= n ; i++) {
                f[i] = d - 1.00;
                sum[i] = sum[i-1] + f[i];
            }
            for(int i = d ; i <= n ; i++) {
                    f[i]   = (sum[i-1] + f[i] - f[i-d-1])/d;
                    sum[i] = sum[i-1] + f[i] - f[i-d-1];
            }
            cout << fixed << setprecision(2) << f[n] << endl;
        }
    }
    return 0;
}
全部评论

相关推荐

03-13 20:28
已编辑
门头沟学院 Java
已经一年没发牛客了,为什么呢,因为没脸发...&nbsp;一年前的我自认为在25届中技术一流,八股无敌,项目出色,但是一年校招的蹉跎让我差点转行。24年春招收割了十几个实习&nbsp;offer&nbsp;之后我去了某家大厂实习到9月份转正失败,那时候的我还没有意识到噩梦将来,7月因为投秋招提前批没反馈,于是开始投了几个实习转正岗位练手又拿了3个中大厂&nbsp;offer,这时的我沉浸在我自以为是的骄傲里。9月秋招正式批开始后我几乎把我能找到的所有的岗位都投了一遍,只收获了大厂海笔,0面试。10月份第一家给我面试的公司是数字马力(蚂蚁的内包),诚恳的说,当时收到这家面试是嚣张的,觉得我拿这个&nbsp;offer&nbsp;如探囊取物,就当个保底吧。...
中街牛奶提子:是啊,不应该在秋招的时候继续投实习岗。也劝26届的,八月末后,实习岗就不应该投,给人错误的行情认知。佬是学院本,觉得约面难,双非何尝不是一样呢,秋招战场的激烈和实习完全不同。当时我秋招的时候也是边面实习,当时面实习面一个过一个觉得自己很优越,觉得能收获一堆实习offer那秋招肯定也行。为什么要在秋招拿一堆实习offer增强自己所谓的虚荣心,当时就是贱,为了所谓的攀比虚荣心
点赞 评论 收藏
分享
02-26 13:46
湖南大学 Java
Java抽象小篮子:要用外卖就必须得额外包装下,你这没包装好啊,可以看看我的精品贴子汇总,里面有额外扩展了很多技术亮点的魔改外卖话术,和7000字轮子项目话术
点赞 评论 收藏
分享
牛客976315581号:这是hr“不合适”的便捷语句
点赞 评论 收藏
分享
评论
4
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务