2023ICPC网络赛第二场

· · 个人记录

I Impatient Patient

题意：

从0到n，有两种操作

1.什么都不做，花费一天，从i到i+1

2.尝试做事，花费一天，成功概率pi，成功后直接到 n ,失败回到a[i]

思路：如果存在一个可以挑战成功的最优状态，我们挑战失败后也会恢复到这一个点继续挑战，直至挑战成功，那么我们枚举哪个状态最优即可，那么我们就是先第一个操作走到i点，然后当前的期望就是i为基础，然后一直挑战，第一次挑战是p * 1 ,失败会多i-a[i]+1天（当前操作用一天，回到i点用i-a[i]天），记作d，

E(i)=i+\sum_{k=0}^{+\infty}(1+kd)*p[i]*(1-p[i])^k

E(i)=i+p[i]*d*\sum_{k=0}^{+\infty}k*(1-p[i])^k+p[i]*\sum_{k=0}^{+\infty}(1-p[i])^k

令q=1-p；

E(i)=i+p[i]*d*\sum_{k=0}^{+\infty}k*q[i]^k+p[i]*\sum_{k=0}^{+\infty}q[i]^k

：\sum_{k=0}^{+\infty}k*q[i]^k=q[i]/(1-q[i])^2

: \sum_{k=0}^{+\infty}q[i]^k=1

E(i)=i+p[i]*d*q[i]/(1-q[i])^2+1

diamond：

#include<bits/stdc++.h>
using namespace std;
#define double long double
void  solve(){
    int n;
    cin>>n;
    vector< double >a(n),q(n),p(n);
    for (int i = 0; i <n ; ++i) {
        cin>>a[i];
    }
    for (int i = 0; i <n ; ++i) {
        cin>>p[i];
        p[i]/=100000;
        q[i]=1-p[i];
    }
    double ans=n;
    for (int i = 0; i <n ; ++i) {
        if(p[i]==0)continue;
        double res=i+(p[i]*(i-a[i]+1)*q[i])/((1-q[i])*(1-q[i]))+1;
        ans=min(res,ans);
    }
    ::printf("%.13Lf\n",ans);

}
signed main() {
    int t;
    cin>>t;
    while (t--){
        solve();
    }
}

E.Another Bus Route Problem

题意：有大小为n的一棵树，树上有m条路，路只能从起点或者终点进入，但可以在任意一处出去，求到1到 结点2-n 最少需要走几条路?

思路：我们考虑到要想从1到其他节点，那么我们首先要到达1，才能到达其他节点，所以我们现要求每一个可上车和下车的车站到达1的最短路径，然后我们就是要确定每个可到达的可上下车的车站的最短路径，这个是怎么确定的呢，其实我们可以这样想，从1到x若是可以到达，那么1到x的路径上的所有点，都可以先到x然后到1，我们是这样进行更新的，我们对第二张图进行BFS的遍历，BFS就是最短的，先遍历到的节点，往上搜索，搜索到没被更新的点就更新，搜到了被更新到的点那么就break，这样就可以保证最短的答案被记录到了可到达的点，若没被更新过的点，那么表示无法到达

diamond：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int fa[N];
vector<int>g[N];
int ans[N];
const int INF=INT_MAX;
void  solve(){
    int n,m;
    cin>>n>>m;
    fill(ans+1,ans+n+1,INF);
    for (int i = 2; i <=n ; ++i) {
        cin>>fa[i];
    }
    for (int i = 0; i <m ; ++i) {
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    queue<int>q;
    q.push(1);
    ans[1]=0;
    while (!q.empty()){
        auto t=q.front();
        q.pop();
        for (auto i:g[t]) {
            int f=i;
            while (ans[f]==INF){
                ans[f]=ans[t]+1;
                if(g[f].size()){
                    q.push(f);
                }
                f=fa[f];
            }
        }
    }
    for (int i = 2; i <=n ; ++i) {
        if(ans[i]!=INF)
        cout<<ans[i]<<' ';
        else cout<<"-1 ";
    }
}
signed main() {
    int t=1;
//    cin>>t;
    while (t--){
        solve();
    }
}