JZSIM 2.23

Author Avatar
空気浮遊 2019年02月23日
  • 在其它设备中阅读本文章
  • 分享到 Facebook
  • 分享到 Telegram
  • 分享到 Twitter
  • 分享到微博

T1 飞行棋

https://jzoj.net/senior/#contest/show/2635/0

令 $f_{i,j}$ 为恰好 $i$ 局以初始位置从 $j$ 到 $n$ 的概率。

$$f_{i,j}=\frac{1}{6}\sum \limits_{k=1}^{6} f_{i-1, a[min(j+k, n)]}$$

则对于第 $T$ 局 $i$ 的获胜概率为(假设 $b_i=i$,但如果不是的话你们也懂我意思⑧):$$\frac{f_{T,i}}{(1-\sum \limits_{j=1}^{T-1} f_{j, i})}$$

即目前情况下,总的到达终点的概率 $1$ 减去不大于 $i-1$ 局到达终点的概率,其中能在第 $i$ 局到达终点的概率。

然后暴力模拟直到符合精度要求(题目的条件给暴力提供了方便),由于 $m=1$ 时需要很多轮所以需要特判一下。

#include<bits/stdc++.h>
using namespace std;

const int N=152;
double f[2][N], *nf=f[0], *lf=f[1], ans[N], tot[N];
int a[N], b[N];

int main() {
    #ifndef LOCAL
    freopen("feixingqi.in","r",stdin);
    freopen("feixingqi.out","w",stdout);
    #endif
    ios::sync_with_stdio(false), cin.tie(0), cout.setf(ios::fixed), cout<<setprecision(6);
    int n, m;
    cin>>n>>m;
    if(m==1) cout<<1.0<<endl, exit(0);
    for(int i=1; i<=n; i++) cin>>a[i];
    for(int i=1; i<=m; i++) cin>>b[i];
    double rem=1;
    nf[n]=1;
    while(rem>1e-7) {
        swap(nf, lf);
        for(int i=1; i<=n; i++) {
            nf[i]=0;
            if(i<n)
            for(int j=1; j<=6; j++)
                nf[i]+=lf[a[min(i+j, n)]];
            nf[i]/=6.0;
        }
        for(int i=1; i<=m; i++)
            ans[i]+=rem*nf[b[i]]/(1-tot[b[i]]),
            rem*=(1.0-nf[b[i]]/(1-tot[b[i]]));
        for(int i=1; i<=n; i++) tot[i]+=nf[i];
    }
    for(int i=1; i<=m; i++) cout<<ans[i]<<endl;
    return 0;
}

T2

min_25 筛,暂时还不会...

T3

动态树维护 parent tree....
离线处理的的区间本质不同子串询问...

本文链接:https://pst.iorinn.moe/archives/jzsim-2-23.html
许可: https://pst.iorinn.moe/license.html
若无特别说明,博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆

      新篇
旧篇      
    • fingerprint Login
  • home 主页
  • inbox 归档
    • December 2024 1
    • August 2024 1
    • June 2024 1
    • April 2024 3
    • March 2024 1
    • February 2024 2
    • January 2024 1
    • November 2023 1
    • August 2023 1
    • May 2023 1
    • February 2023 2
    • January 2023 2
    • July 2022 1
    • June 2022 1
    • April 2022 1
    • March 2022 1
    • February 2022 2
    • December 2021 1
    • November 2021 1
    • August 2021 3
    • July 2021 3
    • April 2021 2
    • March 2021 1
    • February 2021 4
    • January 2021 2
    • December 2020 1
    • November 2020 1
    • October 2020 3
    • September 2020 1
    • August 2020 1
    • July 2020 1
    • March 2020 1
    • December 2019 1
    • September 2019 1
    • July 2019 1
    • April 2019 2
    • March 2019 13
    • February 2019 15
    • January 2019 11
    • December 2018 3
    • November 2018 6
    • October 2018 28
    • September 2018 32
    • August 2018 19
    • July 2018 13
    • June 2018 27
    • May 2018 11
    • April 2018 12
    • March 2018 19
    • February 2018 8
    • January 2018 7
    • December 2017 2
    • November 2017 2
  • apps 分类
    • 笔记
    • 题解
    • 杂文
    • 技术
    • 游戏
    • 小说
  • 留言板
  • 关于
  • 友链
  • 文章总数 282
主题 - Material i
expand_less
Copyright © 2025 雪屋
Float in air.
Powered by Typecho
Theme - Material