制作响应式网站,网页文章 在wordpress,wordpress文章评论插件,做网站-信科网络正题
题目链接:https://www.luogu.com.cn/problem/P5952 题目大意 n∗mn*mn∗m个格子#xff0c;最外层有无限高的墙#xff0c;然后每个格子之间有一睹给定高度的墙#xff0c;然后求有多少种不同的水位情况。 解题思路
首先我们如果将墙看成边#xff0c;那么会造成影响…正题
题目链接:https://www.luogu.com.cn/problem/P5952 题目大意
n∗mn*mn∗m个格子最外层有无限高的墙然后每个格子之间有一睹给定高度的墙然后求有多少种不同的水位情况。 解题思路
首先我们如果将墙看成边那么会造成影响的一定是在最小生成树上的边那么考虑一条边的影响假设左边联通块墙最高为h1h1h1右边为h2h2h2左边水位都不高于h1h1h1时有ans1ans1ans1种方案右边水位都不高于h2h2h2时有ans2ans2ans2中方案。该边的高度为hhh那么新联通块的答案为(ans1h−h1)∗(ans2h−h2)(ans1h-h1)*(ans2h-h2)(ans1h−h1)∗(ans2h−h2)计算即可 codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
#define p(x,y) ((x-1)*m(y))
using namespace std;
const ll N1e610,XJQ1e97;
struct node{ll x,y,w;
}a[N*4];
ll n,m,H,tot,fa[N],ans[N],h[N];
bool cmp(node x,node y)
{return x.wy.w;}
ll find(ll x)
{return (fa[x]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)fa[p(i,j)]p(i,j),ans[p(i,j)]1;for(ll i1;in;i)for(ll j1;jm;j){ll x;scanf(%lld,x);a[tot](node){p(i,j),p(i,j1),x};}for(ll i1;in;i)for(ll j1;jm;j){ll x;scanf(%lld,x);a[tot](node){p(i,j),p(i1,j),x};}sort(a1,a1tot,cmp);for(ll i1;itot;i){ll Fafind(a[i].x),Fbfind(a[i].y);if(Fa!Fb){ans[Fa](ans[Fa]a[i].w-h[Fa])%XJQ*((ans[Fb]a[i].w-h[Fb])%XJQ)%XJQ;fa[Fb]Fa;h[Fa]a[i].w; }}printf(%lld,(ans[find(1)]H-h[find(1)])%XJQ);
}
