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 许可协议 进行许可☆