CodeForces 659F Polycarp and Hay

并查集,$dfs$。

从大的数字往里加,每加一个数字合并一下连通块,判断连通块内数字个数是否够,以及k能不能被当前加入的数字整除。然后$dfs$一下构造答案。

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<iostream>
using namespace std;
typedef long long LL;
const double pi=acos(-1.0),eps=1e-;
void File()
{
freopen("D:\\in.txt","r",stdin);
freopen("D:\\out.txt","w",stdout);
}
template <class T>
inline void read(T &x)
{
char c=getchar(); x=;
while(!isdigit(c)) c=getchar();
while(isdigit(c)) {x=x*+c-''; c=getchar();}
} const int maxn=;
int n,m,sz,c; LL k;
struct X { int r,c; LL v; }s[maxn*maxn];
int fa[maxn*maxn],a[maxn][maxn],cnt[maxn*maxn]; LL ans[maxn][maxn];
bool f[maxn][maxn],q;
int dir[][]={{-,},{,},{,-},{,}}; int Find(int x)
{
if(x!=fa[x]) fa[x]=Find(fa[x]);
return fa[x];
} bool cmp(X a,X b) { return a.v<b.v; } void work(int a,int b)
{
if(b<||b>=n*m) return; int fx=Find(a),fy=Find(b); if(f[b/m][b%m]==) return; if(fx==fy) return;
fa[fy]=fx;
cnt[fx]=cnt[fx]+cnt[fy]; cnt[fy]=;
} bool check(int a,int b)
{
if(a>=&&a<n&&b>=&&b<m) return ;
return ;
} void dfs(int x,int y,LL v,int f)
{
c++; ans[x][y]=v; if(c>=f) return;
for(int i=;i<;i++)
{
int tx=x+dir[i][],ty=y+dir[i][];
if(!check(tx,ty)) continue;
if(a[tx][ty]<v) continue;
if(ans[tx][ty]!=) continue;
dfs(tx,ty,v,f); if(c>=f) return;
}
} int main()
{
scanf("%d%d%lld",&n,&m,&k);
for(int i=;i<n*m;i++) fa[i]=i,cnt[i]=;
for(int i=;i<n;i++)
{
for(int j=;j<m;j++)
{
scanf("%lld",&a[i][j]);
s[sz].r=i; s[sz].c=j; s[sz].v=a[i][j]; sz++;
}
}
sort(s,s+sz,cmp); for(int j=sz-; j>=; j--)
{
int id1=s[j].r*m+s[j].c,id2;
if(check(s[j].r-,s[j].c))
{
id2=(s[j].r-)*m+s[j].c;
work(id1,id2);
}
if(check(s[j].r+,s[j].c))
{
id2=(s[j].r+)*m+s[j].c;
work(id1,id2);
}
if(check(s[j].r,s[j].c-))
{
id2=s[j].r*m+s[j].c-;
work(id1,id2);
}
if(check(s[j].r,s[j].c+))
{
id2=s[j].r*m+s[j].c+;
work(id1,id2);
}
f[s[j].r][s[j].c]=; int d=Find(id1);
if(k%s[j].v==&&(LL)cnt[d]>=k/s[j].v)
{
dfs(s[j].r,s[j].c,s[j].v,(int)(k/s[j].v));
q=; break;
}
if(q) break;
} if(!q) { printf("NO\n"); return ;}
printf("YES\n");
for(int i=;i<n;i++)
{
for(int j=;j<m;j++)
{
printf("%lld",ans[i][j]);
printf(" ");
}
printf("\n");
}
return ;
}
上一篇:如何用Pr完成作业~


下一篇:webstorm实用快捷键