1. 白银莲花池
LUOGU 2411
第一种思路: 当然我们可以写三个 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=0,f=1;
- char ch=getchar();
- while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
- while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
- return x*f;
- }
- int dx[9]={-2,-1,1,2,2,1,-1,-2};
- int dy[9]={1,2,2,1,-1,-2,-2,-1};
- 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];
- queue<pii>q;
- int main()
- {
- //freopen("silvlily.in","r",stdin);
- //freopen("silvlily.out","w",stdout);
- m=read();n=read();
- for(int i=1;i<=m;i++)
- for(int j=1;j<=n;j++)
- {
- w[i][j]=read();
- if(w[i][j]==4) tx=i,ty=j;
- if(w[i][j]==3)
- {
- q.push(make_pair(i,j));
- vis[i][j]=1;
- hl[i][j]=1;
- //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]=0;
- a=add[x][y],b=bs[x][y],c=hl[x][y];
- for(int i=0;i<8;i++)
- {
- int xx=x+dx[i],yy=y+dy[i],flag=0;
- if(xx<1||xx>m||yy<1||yy>n||w[xx][yy]==2||a>add[xx][yy]) continue;
- if(w[xx][yy])
- {
- if(a<add[xx][yy]||b+1<bs[xx][yy])
- add[xx][yy]=a,bs[xx][yy]=b+1,hl[xx][yy]=c,flag=1;
- else if(b+1==bs[xx][yy]) hl[xx][yy]+=c,flag=1;
- }
- else if(a+1<add[xx][yy]||(a+1==add[xx][yy]&&b+1<bs[xx][yy]))
- add[xx][yy]=a+1,bs[xx][yy]=b+1,hl[xx][yy]=c,flag=1;
- else if(a+1==add[xx][yy]&&b+1==bs[xx][yy])
- hl[xx][yy]+=c,flag=1;
- if(flag&&!vis[xx][yy]&&(xx!=tx||yy!=ty))
- q.push(make_pair(xx,yy)),vis[xx][yy]=1;
- }
- }
- //cout<<hl[tx][ty]<<endl;
- if(add[tx][ty]==1e9)
- {
- cout<<"-1"<<endl;
- return 0;
- }
- else cout<<add[tx][ty]<<endl<<bs[tx][ty]<<endl<<hl[tx][ty]<<endl;
- return 0;
- }
- View Code
2. 跳楼机
LUOGU 3403
写这个题有点难受, 读错题了然后考虑只有 x,y 是以为是组合数, 想成有年数学自招题了, 我哭辽...
又有点像背包 1e18 呵呵, 放弃, 但再仔细想想, 这个题和墨墨的等式有点像啊, 墨墨的题解;
在老师的指引下, 我们可以列出公式 ans+=(h-i*x)/y;;
表示通过 y,z 两个操作可以到达的 mod x=i 最小的楼层.
可以得知: f[i+y]=f[i]+y,f[i+z]=f[i]+z.
洛谷这个题解感觉很棒: https://fengzi8615.blog.luogu.org/solution-p3403
令
f(i)
表示表示仅通过操作
2 和操作
3
能到达的
mod
x
=
=
i
的最小楼层
很容易得出状态转移方程
- f(i+y)=f(i)+y
- f
- (
- i
- +
- y
- )
- =
- f
- (i)+y;
- f(i+z)=f(i)+z
- 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 数组的存在, 是不可能出现刚好被整除的, 这一点请自己思考;
来源: http://www.bubuko.com/infodetail-2999164.html