怎么免费做网站教程,福建省住房和城乡建设厅门户网站,手工制作的意义和作用,莱芜在线论坛莱芜话题凤城高中正题
P5952 题目大意
有一个n*m的网格#xff0c;每个网格之间有一个板#xff0c;给出每个板的高度#xff08;边界有一个高度为 ∞\infty∞ 的墙#xff09;#xff0c;在每个网格中注水#xff08;必须是非负整数#xff09;#xff0c;使得两个高度不等且相邻的网…正题
P5952 题目大意
有一个n*m的网格每个网格之间有一个板给出每个板的高度边界有一个高度为 ∞\infty∞ 的墙在每个网格中注水必须是非负整数使得两个高度不等且相邻的网格之间有一个大于两边高度的板可以理解为水的自由流动如果没有板阻挡会过去若最高高度为H问合法的注水方案数 解题思路
考虑每一个网格网上注水会先越过哪个板与另一个点高度同步
对每个板建一条连接两个点的边然后跑最小生成树那么往上注水然后与别的格子同步一定之和这棵树上的边有关
证明
如果存在一个点y和x相连但是x和y的边不在最小生成树内如果x在注水到x-y的高度之前都没有和y同步那么最小生成树上x到y的路径最大权值就大于x-y的高度不符合最小生成树的定义所以不存在这样的情况
设 hxh_xhx 为当前状态下x 所在连通块的最高的板 ansxans_xansx 为当前状态下x 所在连通块到达最高的板的高度之前的方案数因为超过最高的板后可能注的水后超过后面增加的板
对于每一次连边设 z 为当前板的高度那么有 ans(ansxz−hx)×(ansyz−hy)ans(ans_xz-h_x)\times (ans_yz-h_y)ans(ansxz−hx)×(ansyz−hy)即两边的水可以选择 h1∼zh1\sim zh1∼z 的高度所以方案数加上z-h
最后得到的答案加上全部水覆盖到H的方案数即可 code
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define N 500500
#define mp make_pair
#define fs first
#define sn second
#define mod 1000000007
using namespace std;
ll n,m,w,H,x,y,z,h[N],fa[N],ans[N];
pairint,pairint,int a[N1];
ll g(ll x,ll y)
{return (x-1)*my;
}
ll find(ll x)
{return xfa[x]?x:fa[x]find(fa[x]);
}
int main()
{scanf(%lld%lld%lld,n,m,H);for(ll i1;in;i)for(ll j1;jm;j){scanf(%lld,x);a[w]mp(x,mp(g(i,j),g(i,j1)));}for(ll i1;in;i)for(ll j1;jm;j){scanf(%lld,x);a[w]mp(x,mp(g(i1,j),g(i,j)));}sort(a1,a1w);for(ll i1;in;i)for(ll j1;jm;j){xg(i,j);fa[x]x;ans[x]1;}for(ll i1;iw;i){xfind(a[i].sn.fs);yfind(a[i].sn.sn);za[i].fs;if(xy)continue;fa[x]y;ans[y](ans[x]z-h[x]mod)%mod*((ans[y]z-h[y]mod)%mod)%mod;h[y]z;}xfind(1);printf(%lld,(ans[x]H-h[x])%mod);return 0;
}
