The Preliminary Contest for ICPC Asia Nanjing 2019/2019南京网络赛—

（施工中……已更新DF）

比赛传送门：https://www.jisuanke.com/contest/3004

D. Robots（期望dp）

题意

给一个DAG，保证入度为$0$的点只有$1$，出度为$0$的点只有$n$。

现在一个机器人从$1$出发，每天都会以相同的概率前往相邻节点之一或静止不动。

每天机器人消耗的耐久等于经过的天数。

求机器人到点$n$期望消耗的耐久。

划水划的很愉快，唯一一道做出来的题。但是和题解做法不同（感觉我的方法麻烦），因此砸了3h在这题上面（正在试图读懂题解ing）。

设$f[u][j]$表示第$j$天从点$u$出发到$n$期望消耗的耐久，$out[i]$表示$i$的出度$+1$，那么答案就是$f[1][1]$。

初始的方程就不写了很容易。

经过一大顿推导可以求出$f[u][j]=\frac{out[u]}{out[u]-1}\times j+\frac{out[u]}{(out[u]-1)^2}+\sum_v(\frac{f[v][j+1]}{out[u]}+\frac{f[v][j+2]}{out[u]^2}+...)$，其中$v$为$u$相邻节点。

后面那点奇葩的东西很难处理，不妨我们先思考对于$1->2$这样的一个图，$f[1][j]$是多少？

咦为什么这个东西是个等差数列？

于是我们假设$f[v][j]$也是一个等差数列，则原式子可以化为$f[u][j]=\frac{out[u]}{out[u]-1}\times j+\frac{out[u]}{(out[u]-1)^2}+\sum_v \frac{f[v][j+1]*out[u]-f[v][j]}{(out[u]-1)^2}$，总之你能求出$f[u][j]$也是个等差数列就是了。

于是数学归纳法可以求出所有的$f[u][j]$都是等差数列，因此我们$j$只需要求$1$和$2$，然后从后往前求即可，复杂度$O(n+m)$，细节和具体实现看代码。

#include<cmath>

#include<stack>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

typedef long double dl;

const int N=1e5+;

const int M=2e5+;

inline int read(){

    int X=,w=;char ch=;

    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}

    while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();

    return w?-X:X;

}

struct node{

    int to,nxt;

}e[M];

int n,m,cnt,head[N],out[N],dep[N];

dl f[N][];

inline void add(int u,int v){

    e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;out[u]++;

}

void init(){

    for(int i=;i<=n;i++){

        head[i]=;out[i]=;

        f[i][]=f[i][]=;

    }

    cnt=;

}

dl F(int u,int j){

    if(u==n)return ;

    if(f[u][]>&&f[u][]>)return (f[u][]-f[u][])*(j-)+f[u][];

    dl sum=(dl)out[u]/(out[u]-)*j+(dl)out[u]/(out[u]-)/(out[u]-);

    for(int i=head[u];i;i=e[i].nxt){

        int v=e[i].to;

        dl div=(out[u]-)*(out[u]-);

        dl a1=-F(v,j);dl a2=F(v,j+)*out[u];

        sum+=(a1+a2)/div;

    }

    return f[u][j]=sum;

}

int main(){

    int T=read();

    for(int cas=;cas<=T;cas++){

        n=read(),m=read();

        init();

        for(int i=;i<=m;i++){

            int u=read(),v=read();add(u,v);

        }

        printf("%.2Lf\n",F(,));

    }

    return ;

}

F. Greedy Sequence（线段树）

题意

给定一个长度为$n$的排列$a$，对每一个 $i \in [1,n]$，定义一个序列$s_i$，规则如下：

①$s_i[1]=i$;

②对于每一个$j\in [2,n],s_i[j]\le s_i[j−1]$；

③对于每一个$j\in [2,n],s_i[j],s_i[j-1]$ 在 $a$ 中的位置之差的绝对值$\le k$，并且$a$中的每一个元素至多在$s_i$中出现一次；

④填不了时，用 $0$ 填充剩余的数至$s_i$长度为$n$为止；

⑤$s_i[j]$要尽可能的大；

输出$|s_1|,|s_2|,...,|s_n|$，其中$|s_i|$为序列$s_i$中不为$0$的数的个数。

显然我们要取的数是可取区间内最大的，并且容易发现，前一个数取$i$则后一个数一定会取某个数不变。

于是维护$nxt[i]$表示$i$后面取的数，$nxt$数组可用线段树求出。

#include<cmath>

#include<stack>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

const int N=1e5+;

inline int read(){

    int X=,w=;char ch=;

    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}

    while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();

    return w?-X:X;

}

int n,k,w[N],id[N],nxt[N],sum[N];

int tr[N<<];

void build(int a,int l,int r){

    if(l==r){

        tr[a]=w[l];return;

    }

    int mid=(l+r)>>;

    build(a<<,l,mid);build(a<<|,mid+,r);

    tr[a]=max(tr[a<<],tr[a<<|]);

}

void modify(int a,int l,int r,int x,int y){

    if(l==r){

        tr[a]=y;return;

    }

    int mid=(l+r)>>;

    if(x<=mid)modify(a<<,l,mid,x,y);

    else modify(a<<|,mid+,r,x,y);

    tr[a]=max(tr[a<<],tr[a<<|]);

}

int query(int a,int l,int r,int l1,int r1){

    if(r<l1||r1<l)return ;

    if(l1<=l&&r<=r1)return tr[a];

    int mid=(l+r)>>;

    return max(query(a<<,l,mid,l1,r1),query(a<<|,mid+,r,l1,r1));

}

inline void check(int x){

    int where=id[x];

    modify(,,n,where,);

    nxt[x]=query(,,n,max(,where-k),min(n,where+k));

}

int main(){

    int T=read();

    for(int cas=;cas<=T;cas++){

        n=read(),k=read();

        for(int i=;i<=n;i++){

            w[i]=read();id[w[i]]=i;

            sum[i]=;

        }

        build(,,n);

        for(int i=n;i>=;i--)check(i);

        for(int i=;i<=n;i++)sum[i]+=sum[nxt[i]]+;

        for(int i=;i<=n;i++){

            if(i!=)putchar(' ');

            printf("%d",sum[i]);

        }

        putchar('\n');

    }

    return ;

}

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。　　　　　　　　　　　　　　+

+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+

+++++++++++++++++++++++++++++++++++++++++++

巴特西

The Preliminary Contest for ICPC Asia Nanjing 2019/2019南京网络赛——题解

最新文章

热门文章