【CF659F】Polycarp and Hay(并查集,bfs)
2024-08-28 04:06:57
题意:
构造一个矩阵,使得:
矩阵所有格子中数字都小于等于原矩阵,并且至少有一个元素和原矩阵相等,
构造的矩阵除了0以外的数字必须联通并且相等,矩阵中元素之和为K。
n,m<=1e3,1<=K<=1e18
思路:
From https://blog.csdn.net/morejarphone/article/details/51037918
对每个格子的数字进行排序,那么一个格子的数字最多能够填的格子数就是他上下左右格子能够填的格子
数的和,这个可以用并查集来维护
然后枚举每个格子,如果这个格子的数字能够整除k并且这个格子能够填的个数足够,就可以从这个格子出发
bfs一遍找到需要的格子
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef vector<int> VI;
#define fi first
#define se second s
#define MP make_pair
#define N 1100
#define M 1100000
#define MOD 1000000007
#define eps 1e-8
#define pi acos(-1)
#define oo 2e9+1 int dx[]={,-,,},
dy[]={,,-,}; struct node
{
int x,y;
ll z;
}b[M],q[M]; ll a[N][N],K;
int vis[N][N],num[N][N],f[M],size[M],n,m; int read()
{
int v=,f=;
char c=getchar();
while(c<||<c) {if(c=='-') f=-; c=getchar();}
while(<=c&&c<=) v=(v<<)+v+v+c-,c=getchar();
return v*f;
} bool cmp(node a,node b)
{
return a.z>b.z;
} int find(int k)
{
if(f[k]!=k) f[k]=find(f[k]);
return f[k];
} void bfs(int x,int y,ll cnt)
{
int t=;
int w=;
q[].x=x; q[].y=y;
memset(vis,,sizeof(vis));
vis[x][y]=;
cnt--;
while(t<=w&&cnt)
{
t++;
int nowx=q[t].x;
int nowy=q[t].y;
vis[nowx][nowy]=;
for(int i=;i<;i++)
{
int tx=nowx+dx[i];
int ty=nowy+dy[i];
if(!tx||tx>n||!ty||ty>m||vis[tx][ty]) continue;
if(a[tx][ty]>=a[x][y])
{
vis[tx][ty]=;
q[++w].x=tx;
q[w].y=ty;
cnt--;
if(cnt<=) break;
}
}
}
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
if(vis[i][j]) printf("%lld",a[x][y]);
else printf("");
if(j<m) printf(" ");
}
printf("\n");
}
} int main()
{
//freopen("cf659f.in","r",stdin);
//freopen("cf659f.out","w",stdout);
scanf("%d%d%lld",&n,&m,&K);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++) scanf("%lld",&a[i][j]);
int tot=;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
num[i][j]=(i-)*m+j;
size[num[i][j]]=;
f[num[i][j]]=num[i][j];
b[++tot].x=i;
b[tot].y=j;
b[tot].z=a[i][j];
}
sort(b+,b+tot+,cmp); memset(vis,,sizeof(vis));
for(int i=;i<=tot;i++)
{
vis[b[i].x][b[i].y]=;
for(int j=;j<;j++)
{
int x=b[i].x+dx[j];
int y=b[i].y+dy[j];
if(x&&x<=n&&y&&y<=m&&vis[x][y])
{
int p=find(num[b[i].x][b[i].y]);
int q=find(num[x][y]);
if(p!=q)
{
f[q]=p;
size[p]+=size[q];
}
}
}
} // for(int i=1;i<=n;i++)
// for(int j=1;j<=m;j++) printf("%d\n",size[num[i][j]]); int ans=;
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
if(K%a[i][j]==&&size[num[i][j]]>=K/a[i][j])
{
printf("YES\n");
bfs(i,j,K/a[i][j]);
ans=; break;
}
if(ans) break;
}
if(!ans) printf("NO"); }
最新文章
- [.net 面向对象程序设计进阶] (13) 序列化(Serialization)(五) Json 序列化利器 Newtonsoft.Json 及 通用Json类
- struct结构体(剽窃别人的)
- MyBatis传入参数与parameterType
- poj1222 EXTENDED LIGHTS OUT 高斯消元||枚举
- Python3基础 in 列表名 判断一个元素是否在列表中
- 8.0 Qweb 报表编写步骤
- hdu 4163 Stock Prices 水
- 怎样创建TWaver 3D的轮廓选中效果
- Oracle 10g AND Oracle 11g手工建库案例--Oracle 11g
- MySQL replace 的简介
- java也可以做黑客?
- BZOJ5465 APIO2018选圆圈(KD-Tree+堆)
- TCP系列55—拥塞控制—18、其他拥塞控制算法及相关内容概述
- [转]Spring 之 Log4j 的配置
- 声音处理(Cool Edit)
- 【小M的作物】
- java基础-关键词super与this
- VS2013 The Debugger Resource DLL is out of date
- java反射抄的例子
- 第二篇 Python运算符