专栏首页数据结构与算法agc007C - Pushing Balls(期望 等差数列)

agc007C - Pushing Balls(期望 等差数列)

题意

题目链接

翻译来自神仙yyb

Sol

又是一道神仙题。。

我开始的思路是枚举空位,但是还是不能做,GG

标算过于神仙,其中一些细节我也理解不了

题目给出的实际是一个首项为$d$,公差为$x$的等差数列

$sum = 2dn + \frac{2n(2n - 1)x}{2}$

此时的期望为$\frac{sum}{2n}$

考虑修改之后会有那些值发生改变

$d' = \frac{(2n - 2)d + d + 2x + 3d + 3x)}{2n}$(考虑第一个位置怎么变)

$sum' = \frac{d + (d + x) + (2n - 2)x + d + (2n - 1) x + d}{2n}$

$x' = \frac{sum -2nd}{n(2n - 1)}$

不断推下去即可

#include<bits/stdc++.h>
using namespace std;
long double N, d1, x, ans;
int main() {
    cin >> N >> d1 >> x;
    for(int i = N; i >= 1; i--) {
        long double s = d1 * 2 * N + N * (2 * N - 1) * x;
        ans += s / 2 / N;
        s = s - (4 * d1 + 4 * N * x - 2 * x)  / 2 / N;
        d1 = ((2 * N - 2) * d1 + d1 + 2 * x + 3 * d1 + 3 * x) / 2 / N;
        N--;
        x = (s - 2 * N * d1) / N / (2 * N - 1);
    //    if(i > 990) printf("%.10lf\n", (double)x);
    }
    printf("%.15lf", (double)ans);
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 3038 3n+1问题

    3038 3n+1问题  时间限制: 1 s  空间限制: 32000 KB  题目等级 : 白银 Silver 题解 题目描述 Description 3n+...

    attack
  • 杜教筛入门

    假设我们现在要求$S(n) = \sum_{i = 1}^n f(i)$,$f(i)$为积性函数,$n \leqslant 10^{12}$

    attack
  • 数学水题

    由于阶乘的数量增长非常迅速,而\(k\)又非常小,那么显然最后的序列只有最后几位会发生改变。

    attack
  • EMQ X | 百万级的开源MQTT消息服务器(搭建一个私有MQTT服务器)

    EMQ X 全称 Erlang/Enterprise/Elastic MQTT Broker,它是基于 Erlang/OTP 语言平台开发,支持大规模连接和分布...

    Mculover666
  • 又到公司年会时,给公司写的年会抽奖程序!

    用户5997198
  • ThreadLocal 原理

    从上面可以看出,Thread 类中有一个 threadLocals 和 inheritableThreadLocals 变量,它们都是 ThreadLocalM...

    happyJared
  • Kubernetes Scheduler的Predicates和Priorities Policies解读

    本文是对Kubernetes V1.5 Scheduler 的预选策略Predicates Policies和优选策略Priorities Policies的含...

    Walton
  • python自定义函数基础

    当今统计软件里,通共有五位,stata,R、python、SAS和SPSS,看了多少遍,都是大轮子,一个轮子又另一个,难啊,烦啊,看看这五个软件吧,哪一个不是优...

    用户7760819
  • Scala当中什么是Transformation和 Action,以及它们俩的区别是什么?

    一个完整的RDD任务由两部分组成:Transformation和 Action。Transformation用于对RDD的创建,还可以把老的RDD通过Trans...

    马克java社区
  • 腾讯云语音识别python-sdk使用笔记

    官方文档说明:https://cloud.tencent.com/document/product/1093/35726

    算法发

扫码关注云+社区

领取腾讯云代金券