本文共 1887 字，大约阅读时间需要 6 分钟。
并查集，$dfs$。
从大的数字往里加，每加一个数字合并一下连通块，判断连通块内数字个数是否够，以及k能不能被当前加入的数字整除。然后$dfs$一下构造答案。
#pragma comment(linker, "/STACK:1024000000,1024000000")#include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long LL;const double pi=acos(-1.0),eps=1e-6;void File(){ freopen("D:\\in.txt","r",stdin); freopen("D:\\out.txt","w",stdout);}template inline void read(T &x){ char c=getchar(); x=0; while(!isdigit(c)) c=getchar(); while(isdigit(c)) {x=x*10+c-'0'; c=getchar();}}const int maxn=1010;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[4][2]={ {-1,0},{ 1,0},{ 0,-1},{ 0,1}};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 =n*m) return; int fx=Find(a),fy=Find(b); if(f[b/m][b%m]==0) return; if(fx==fy) return; fa[fy]=fx; cnt[fx]=cnt[fx]+cnt[fy]; cnt[fy]=0;}bool check(int a,int b){ if(a>=0&&a =0&&b =f) return; for(int i=0;i<4;i++) { int tx=x+dir[i][0],ty=y+dir[i][1]; if(!check(tx,ty)) continue; if(a[tx][ty] =f) return; }}int main(){ scanf("%d%d%lld",&n,&m,&k); for(int i=0;i =0; j--) { int id1=s[j].r*m+s[j].c,id2; if(check(s[j].r-1,s[j].c)) { id2=(s[j].r-1)*m+s[j].c; work(id1,id2); } if(check(s[j].r+1,s[j].c)) { id2=(s[j].r+1)*m+s[j].c; work(id1,id2); } if(check(s[j].r,s[j].c-1)) { id2=s[j].r*m+s[j].c-1; work(id1,id2); } if(check(s[j].r,s[j].c+1)) { id2=s[j].r*m+s[j].c+1; work(id1,id2); } f[s[j].r][s[j].c]=1; int d=Find(id1); if(k%s[j].v==0&&(LL)cnt[d]>=k/s[j].v) { dfs(s[j].r,s[j].c,s[j].v,(int)(k/s[j].v)); q=1; break; } if(q) break; } if(!q) { printf("NO\n"); return 0;} printf("YES\n"); for(int i=0;i
转载于:https://www.cnblogs.com/zufezzt/p/5884426.html