D9 图论综合题

1.白银莲花池

第一种思路：当然我们可以写三个bfs a掉这个题，这写下来一二百行要有了吧；

第二种：我们可以在一个bfs中维护所有的信息，一个方向数组，从起点开始，向八个方向扩展，如果添加的莲花需要少，就更新当前的值，如果添加莲花一样多但所需步数更少，也更新，目标点方案数等于当前点方案数。特别地，如果添加莲花和步数一样多，目标点方案数加上当前点方案数。以上三种情况目标点皆需入队；

int add[50][50],bs[50][50],vis[50][50],sx,sy,tx,ty,n,m,w[500][500];
long long ans,c,hl[500][500];//add数组表示需要添加莲花的最小值，bs表示需要的最小步数，hl表示方案数；

#include<bits/stdc++.h>

using namespace std;

#define pii pair<int,int>

inline int read()

{

    int x=,f=;

    char ch=getchar();

    while(!isdigit(ch)) {if(ch=='-') f=-;ch=getchar();}

    while(isdigit(ch)) {x=(x<<)+(x<<)+(ch^);ch=getchar();}

    return x*f;

}

int dx[]={-,-,,,,,-,-};

int dy[]={,,,,-,-,-,-};

int add[][],bs[][],vis[][],sx,sy,tx,ty,n,m,w[][];

long long ans,c,hl[][];

queue<pii>q;

int main()

{

    //freopen("silvlily.in","r",stdin);

    //freopen("silvlily.out","w",stdout);

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

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

        for(int j=;j<=n;j++)

        {

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

            if(w[i][j]==)  tx=i,ty=j;

            if(w[i][j]==)

            {

                q.push(make_pair(i,j));

                vis[i][j]=;

                hl[i][j]=;

                //sx=i,sy=j;

            }

            else add[i][j]=1e9,bs[i][j]=1e9;

        }

    int a,b,x,y,flag;

    while(q.size())

    {

        x=q.front().first,y=q.front().second;

        q.pop();

        vis[x][y]=;

        a=add[x][y],b=bs[x][y],c=hl[x][y];

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

        {

            int xx=x+dx[i],yy=y+dy[i],flag=;

            if(xx<||xx>m||yy<||yy>n||w[xx][yy]==||a>add[xx][yy]) continue;

            if(w[xx][yy])

            {

                if(a<add[xx][yy]||b+<bs[xx][yy])

                    add[xx][yy]=a,bs[xx][yy]=b+,hl[xx][yy]=c,flag=;

                else if(b+==bs[xx][yy]) hl[xx][yy]+=c,flag=;

            }

            else if(a+<add[xx][yy]||(a+==add[xx][yy]&&b+<bs[xx][yy]))

                add[xx][yy]=a+,bs[xx][yy]=b+,hl[xx][yy]=c,flag=;

            else if(a+==add[xx][yy]&&b+==bs[xx][yy])

                hl[xx][yy]+=c,flag=;

            if(flag&&!vis[xx][yy]&&(xx!=tx||yy!=ty))

                q.push(make_pair(xx,yy)),vis[xx][yy]=;

        }

    }

    //cout<<hl[tx][ty]<<endl;

    if(add[tx][ty]==1e9)

    {

        cout<<"-1"<<endl;

        return ;

    }

    else cout<<add[tx][ty]<<endl<<bs[tx][ty]<<endl<<hl[tx][ty]<<endl;

    return ;

}

2.跳楼机

LUOGU 3403

写这个题有点难受，读错题了然后考虑当只有x，y是以为是组合数，我哭辽...

又有点像背包 1e18 呵呵，放弃，但再仔细想想，这个题和墨墨的等式有点像啊，墨墨的题解；

在老师的指引下，我们可以列出公式ans+=（h-i*x）/y;；

我们将x作为最后的拓展，我们相当于分成modx成x种情况进行分类，同余建图对于每一个同余类，我们只需要找到在当前情况下的最低点，那么每次累加x便能再次向上跳，(h-d[i])/x便会得到最后的结果，+1是因为在执行除法时我们讲最低点的情况舍去了；

表示通过y,z两个操作可以到达的 mod x=i最小的楼层；

可以得知：d[i+y]=d[i]+y，d[i+z]=d[i]+z.

洛谷这个题解感觉很棒：https://fengzi8615.blog.luogu.org/solution-p3403

令f(i)表示表示仅通过操作2和操作3能到达的 modx == i 的最小楼层

很容易得出状态转移方程

f(i+y)=f(i)+y f(i+z)=f(i)+z

能到达mod x=i+y的最小楼层
即在能到达mod x=i的最小楼层的基础上,再执行一遍操作2

我们来看看最短路的求法 f(y)=f(x)+edge(i)

y是子结点,x是父节点,edge表示权值
这个写法跟我们上面的转移方程很像诶
于是考虑让(i+y)和(i+z)成为点;
让y,z成为权值从而算出f(i)；

ans+=(h-f[i])/x +1

由于f(i)是在不适用操作1的情况下
所以h和f(i)之间的差值由操作1来完成
而每进行操一次作1,我们就可以到达一个新的楼层
所以答案就要累加上进行操作1的次数

即 (h-f[i])/x +1 为什么要+1呢因为除法是向下取整,注意由于f数组的存在,是不可能出现刚好被整除的,这一点请自己思考；

3.中山市选【生成树】

LUOGU 4821

画图，原图4n个点，5n条边，对于生成树n个点n-1条边，但本题还有每个五边形都有中间n边形重叠一条边；

去掉n边形中的任意一条边，有n种做法，此时肯定有一个五边形和残余的n边形形成一个新环；

我们需要在新环上再去掉一条边，然后按照思考过程对剩下的n-1个五边形去边，有5^（n-1）种方案，所以乘起来就得到ans=4 n 5^（n-1）；

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int mod=;

template<typename T>inline void read(T &x)

{

    x=;T f=,ch=getchar();

    while(!isdigit(ch)) ch=getchar();

    if(ch=='-') f=-, ch=getchar();

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

    x*=f;

}

inline ll Quick_mul(ll x,ll y)

{

    return((x*y-(ll)(((long double)x*y+0.5)/mod)*mod)%mod+mod)%mod;

}

inline ll Quick_power(ll a,ll b)

{

    ll ans=;

    while(b)

    {

        if(b&) ans=Quick_mul(ans,a);

        a=Quick_mul(a,a);

        b>>=;

    }

    return ans;

}

int main()

{

    //freopen("data.in","r",stdin);

    //freopen("data.out","w",stdout);

    int t;

    read(t);

    while(t--)

    {

        int n;

        read(n);

        if(n==) puts("");

        else

        {

            ll ans=Quick_power(,n-);

            printf("%lld\n",ans*n*%mod);

        }

    }

    return ;

}

巴特西

D9 图论综合题

令f(i)表示表示仅通过操作2和操作3能到达的 modx == i 的最小楼层

很容易得出状态转移方程

f(i+y)=f(i)+y f(i+z)=f(i)+z

最新文章

热门文章