Bzoj4899 记忆的轮廓

Stella981
• 阅读 495

B. 记忆的轮廓

题目描述

通往贤者之塔的路上,有许多的危机。
我们可以把这个地形看做是一颗树,根节点编号为1,目标节点编号为n,其中1-n的简单路径上,编号依次递增,在[1,n]中,一共有n个节点。我们把编号在[1,n]的叫做正确节点,[n+1,m]的叫做错误节点。一个叶子,如果是正确节点则为正确叶子,否则称为错误叶子。莎缇拉要帮助昴到达贤者之塔,因此现在面临着存档位置设定的问题。
为了让昴成长为英雄,因此一共只有p次存档的机会,其中1和n必须存档。被莎缇拉设置为要存档的节点称为存档位置。当然不能让昴陷入死循环,所以存档只能在正确节点上进行,而且同一个节点不能存多次档。因为通往贤者之塔的路上有影响的瘴气,因此莎缇拉假设昴每次位于树上一个节点时,都会等概率选择一个儿子走下去。每当走到一个错误叶子时,再走一步就会读档。具体的,每次昴到达一个新的存档位置,存档点便会更新为这个位置(假如现在的存档点是i,现在走到了一个存档位置j>i,那么存档点便会更新为j)。读档的意思就是回到当前存档点。初始昴位于1,当昴走到正确节点n时,便结束了路程。莎缇拉想知道,最优情况下,昴结束路程的期望步数是多少?

输入格式

第一行一个正整数T表示数据组数。
接下来每组数据,首先读入三个正整数n,m,p。
接下来m-n行,描述树上所有的非正确边(正确边即连接两个正确节点的边)
用两个正整数j,k表示j与k之间有一条连边,j和k可以均为错误节点,也可以一个为正确节点另一个为错误节点。
数据保证j是k的父亲。
50<=p<=n<=700,m<=1500,T<=5。
数据保证每个正确节点均有至少2个儿子,至多3个儿子。

输出格式

T行每行一个实数表示每组数据的答案。请保留四位小数。

样例

样例输入

1
3 7 2
1 4
2 5
3 6
3 7

样例输出

9.0000

orz大佬题解:https://blog.csdn.net/WerKeyTom_FTD/article/details/53026266

我这里只是梳理一下自己的思路。

50算法

对于n==p的情况,就是在每一个点都存档,设d[i]表示节点i的儿子数,对于错误节点i,设g[i]为读档的期望步数,则g[i]=1+∑(1/d[i]*g[j]).对于正确节点i,设s[i]=∑g[j](j为i的错误儿子)。设f[i]为从i到n的期望步数,f[n]=0,f[i]=1+f[i+1]/d[i]+∑(g[j]+f[i])/d[i],得f[i]=d[i]+f[i+1]+s[i];

Bzoj4899 记忆的轮廓 Bzoj4899 记忆的轮廓

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
struct edge
{
    int u,v,next;
    #define u(x) ed[x].u
    #define v(x) ed[x].v
    #define n(x) ed[x].next
}ed[200010];
int first[100010],num_e;
#define f(x) first[x]
int T;
int n,m,p;
double d[100000],g[100000],s[100000],f[100000];

void dfs(int x,int fa)
{
    //cout<<x<<" "<<fa<<endl;
    if(x>n)g[x]=1;
        
    for(int i=f(x);i;i=n(i))
    if(v(i)!=fa)
        d[x]++;
        
    for(int i=f(x);i;i=n(i))
    if(v(i)!=fa)
    {
        dfs(v(i),x);
        if(x>n)g[x]+=1/d[x]*g[v(i)];
        else   s[x]+=g[v(i)];
    }
    if(x<n)    f[x]=d[x]+s[x]+f[x+1];
}
inline void add(int u,int v);
signed main()
{
    cin>>T;
    while(T--)
    {
        cin>>n>>m>>p;
        for(int i=1;i<n;i++)
            add(i,i+1),add(i+1,i);
        int u,v;
        for(int i=1;i<=m-n;i++)
        {
            cin>>u>>v;
            add(u,v),add(v,u);
        }
        if(n==p)
        {
            dfs(1,0);
            printf("%0.4lf\n",f[1]);
        }
    }
    
}
inline void add(int u,int v)
{
    ++num_e;
    u(num_e)=u;
    v(num_e)=v;
    n(num_e)=f(u);
    f(u)=num_e;
}

View Code

70算法

设a[i][j]为当前存档点为i,从i出发到j的期望步数,用n2的复杂度预处理出a,a[i][i]=0,对于i<j,a[i][j]=a[i][j-1]+1+1/d[j-1]*0+∑(g[k]+a[i][j])/d[j-1];(k为j-1的错误儿子),得a[i][j]=a[i][j-1]*d[j-1]+d[j-1]+s[j-1];这里理解了好长时间,我本来写的是a[i][j]=a[i][j-1]+1/d[j-1]+∑(g[k]+a[i][j])/d[j-1];因为从j-1无论如何都要再走一步到他的儿子节点,我是忘了这个……设f[i][j]表示当前存档点为i,还剩j次存档机会,到n的期望步数,

那么f[i][j]=min(f[k][j-1]+a[i][k]),i<k<=n;最后答案为f[1][p-1];复杂度O(n2p);

Bzoj4899 记忆的轮廓 Bzoj4899 记忆的轮廓

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#define ma(x) memset(x,0,sizeof(x))
using namespace std;
struct edge
{
    int u,v,next;
    #define u(x) ed[x].u
    #define v(x) ed[x].v
    #define n(x) ed[x].next
}ed[20010];
int first[1510],num_e;
#define f(x) first[x]
int T;
int n,m,p;
double d[1510],g[1510],s[1510],f[1510];

double a[710][710],f2[710][710];

void dfs(int x,int fa);
inline void add(int u,int v);
signed main()
{
    //freopen("5.in","r",stdin);
    
    cin>>T;
    while(T--)
    {
        num_e=0;ma(d);ma(g);ma(s);ma(f);ma(f2);ma(a);ma(first);
        cin>>n>>m>>p;
        for(int i=1;i<n;i++)
            add(i,i+1),add(i+1,i);
        int u,v;
        for(int i=1;i<=m-n;i++)
        {
            scanf("%d%d",&u,&v);
            add(u,v),add(v,u);
        }
        dfs(1,0);
        if(n==p)
        {
            printf("%0.4lf\n",f[1]);
            continue;
        }
        for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            a[i][j]=a[i][j-1]*d[j-1]+d[j-1]+s[j-1];
        for(int i=n-1;i;i--)
            for(int j=0;j<=p;j++)
                f2[i][j]=0x7fffffff;
        for(int i=n;i>=1;i--)
            for(int j=1;j<p;j++)
                for(int k=i+1;k<=n;k++)
                    f2[i][j]=min(f2[i][j] , f2[k][j-1]+a[i][k] );
        printf("%0.4lf\n",f2[1][p-1]);
    }
    
}
inline void add(int u,int v)
{
    ++num_e;
    u(num_e)=u;
    v(num_e)=v;
    n(num_e)=f(u);
    f(u)=num_e;
}
void dfs(int x,int fa)
{
    if(x>n)g[x]=1;
    for(int i=f(x);i;i=n(i))
    if(v(i)!=fa)
    {
        d[x]++;
        //cout<<i<<" "<<v(i)<<endl;
    }
    //cout<<x<<endl;
    for(int i=f(x);i;i=n(i))
    if(v(i)!=fa)
    {
        dfs(v(i),x);
        if(x>n)g[x]+=1/d[x]*g[v(i)];
        else   s[x]+=g[v(i)];
    }
    if(x<n)    f[x]=d[x]+s[x]+f[x+1];
}

View Code

 70算法+玄学优化AC

题解的分析没有看懂,就是证明了一下a数组不会爆炸的问题,a的增长是非常快的,但答案并不会有那么大,所以可以假定一个常数step,每次转移最多从距离step转移过来,step取40就差不多了,因为a的下界是2^40了,而答案的上界远远没有达到。题解说复杂度是O(np log ans),没有搞懂,O(40np)更容易理解吧,其实也差不多。

Bzoj4899 记忆的轮廓 Bzoj4899 记忆的轮廓

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#define ma(x) memset(x,0,sizeof(x))
using namespace std;
struct edge
{
    int u,v,next;
    #define u(x) ed[x].u
    #define v(x) ed[x].v
    #define n(x) ed[x].next
}ed[20010];
int first[1510],num_e;
#define f(x) first[x]
int T;
int n,m,p;
double d[1510],g[1510],s[1510],f[1510];

double a[710][710],f2[710][710];
const int step=40;

void dfs(int x,int fa);
inline void add(int u,int v);
signed main()
{
    //freopen("5.in","r",stdin);
    
    cin>>T;
    while(T--)
    {
        num_e=0;ma(d);ma(g);ma(s);ma(f);ma(f2);ma(a);ma(first);
        cin>>n>>m>>p;
        for(int i=1;i<n;i++)
            add(i,i+1),add(i+1,i);
        int u,v;
        for(int i=1;i<=m-n;i++)
        {
            scanf("%d%d",&u,&v);
            add(u,v),add(v,u);
        }
        dfs(1,0);
        if(n==p)
        {
            printf("%0.4lf\n",f[1]);
            continue;
        }
        for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            a[i][j]=a[i][j-1]*d[j-1]+d[j-1]+s[j-1];
        for(int i=n-1;i;i--)
            for(int j=0;j<=p;j++)
                f2[i][j]=0x7fffffff;
        for(int i=n;i>=1;i--)
            for(int j=1;j<p;j++)
                for(int k=i+1;k<=min(i+step,n);k++)
                    f2[i][j]=min(f2[i][j] , f2[k][j-1]+a[i][k] );
        printf("%0.4lf\n",f2[1][p-1]);
    }
    
}
inline void add(int u,int v)
{
    ++num_e;
    u(num_e)=u;
    v(num_e)=v;
    n(num_e)=f(u);
    f(u)=num_e;
}
void dfs(int x,int fa)
{
    if(x>n)g[x]=1;
    for(int i=f(x);i;i=n(i))
    if(v(i)!=fa)
        d[x]++;
    for(int i=f(x);i;i=n(i))
    if(v(i)!=fa)
    {
        dfs(v(i),x);
        if(x>n)g[x]+=1/d[x]*g[v(i)];
        else   s[x]+=g[v(i)];
    }
    if(x<n)    f[x]=d[x]+s[x]+f[x+1];
}

View Code

100算法

  居然是个单队。首先证明a[i][j+1]-a[i][j]>=a[i+1][j+1]-a[i+1][j],把a[i][j+1]展开,得左边=(d[j]-1)*a[i][j]+…,右边=(d[j]-1)*a[i+1][j]+…。得证。则可以用单队优化,复杂度O(np log n)。

另外还有一种做法,目前还没有看懂……

点赞
收藏
评论区
推荐文章
blmius blmius
2年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
待兔 待兔
2星期前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Wesley13 Wesley13
2年前
GoJS API学习
varnode{};node"key""节点Key";node"loc""00";//节点坐标node"text""节点名称";//添加节点通过按钮点击,添加新的节点到画布myDiagram.model.addNodeData(nod
Wesley13 Wesley13
2年前
PHP数据结构与算法:树
一、概念树(Tree)是一种抽象数据类型(ADT)或是实作这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合。它是由n(n1)个有限节点组成一个具有层次关系的集合。看起来向一颗根朝上叶朝下的的倒挂树。每个节点有零个或多个子节点没有父节点的节点称为根节点每一个非根节点有且只有一个父节点除根
Wesley13 Wesley13
2年前
PHP创建多级树型结构
<!lang:php<?php$areaarray(array('id'1,'pid'0,'name''中国'),array('id'5,'pid'0,'name''美国'),array('id'2,'pid'1,'name''吉林'),array('id'4,'pid'2,'n
Stella981 Stella981
2年前
LeetCode 5561. 获取生成数组中的最大值
文章目录1\.题目2\.解题1\.题目给你一个整数n。按下述规则生成一个长度为n1的数组nums:nums00nums11当2<2i<n时,nums2inumsi
Wesley13 Wesley13
2年前
C语言递归之二叉树的最小深度
https://www.cnblogs.com/shichampion/p/12262678.html题目描述给定一个二叉树,找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。说明: 叶子节点是指没有子节点的节点。示例输入:3,9,20,null,null,15,7
Wesley13 Wesley13
2年前
B
BTreeBTree又叫做B树,和平衡二叉树不同的地方在于B树是多叉树(平衡多路查找树),Oracle和MongoDB的索引技术就是基于B树的数据结构,B树也可以看作是对23查找树的一种扩展。一个m阶的BTree有以下性质1.每个节点最多有m个子节点;2.每个非叶子节点(根节点除外)至少含有m/2个子节点;3.
Stella981 Stella981
2年前
LeetCode112
非商业,LeetCode链接附上:https://leetcodecn.com/problems/pathsum/进入正题。题目:给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。说明: 叶子节点是指没有子节点的节点。示例:给定如下二叉树,以及目标和
Python进阶者 Python进阶者
6个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这