[校内互测]最大（二分+线段树||bitset）

2019-11-11 05:27:34

字体：大中小

来源：转载

供稿：网友

题目描述

这里写图片描述

题解

最小值最大很容易想到二分答案二分mid之后，将所有大于等于mid的点留下，判断是否能组成一个矩形判断的时候可以将满足条件的置1，其余置0，然后将每两行做与运算，判断结果中是否有大于2个1 用bitset比较方便，但是非常慢，不过这题的时限比较宽，大概是可以卡时的也可以30或60压位然后利用lowbit查询，只需查询2个lowbit就可以了不过我用了一个比较傻但是比较稳定的方法，就是类似于线段树的合并，用动态开点搞出来n棵线段树，然后两两合并时判断，时间大概是logn的时间复杂度O(log231nmlogn) $O(log2^{31}nmlogn)$

代码

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;#define N 1005int n,m,Max,sz,cnt,ans;int squ[N][N];int root[N],sum[N*N*20],ls[N*N*20],rs[N*N*20];void insert(int &now,int l,int r,int x){ int mid=(l+r)>>1; if (!now) now=++sz; ++sum[now]; if (l==r) return; if (x<=mid) insert(ls[now],l,mid,x); else insert(rs[now],mid+1,r,x);}void merge(int x,int y,int l,int r){ int mid=(l+r)>>1; if (!x||!y) return; if (l==r) { if (sum[x]+sum[y]==2) ++cnt; return; } merge(ls[x],ls[y],l,mid); merge(rs[x],rs[y],mid+1,r);}bool check(int mid){ sz=0; memset(root,0,sizeof(root)); memset(sum,0,sizeof(sum)); memset(ls,0,sizeof(ls)); memset(rs,0,sizeof(rs)); for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) if (squ[i][j]>=mid) insert(root[i],1,m,j); for (int i=1;i<=n;++i) for (int j=i+1;j<=n;++j) { cnt=0; merge(root[i],root[j],1,m); if (cnt>=2) return 1; } return 0;}int find(){ int l=0,r=Max,mid,ans=0; while (l<=r) { mid=(l+r)>>1; if (check(mid)) ans=mid,l=mid+1; else r=mid-1; } return ans;}int main(){ freopen("max.in","r",stdin); freopen("max.out","w",stdout); scanf("%d%d",&n,&m); for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) { scanf("%d",&squ[i][j]); Max=max(Max,squ[i][j]); } ans=find(); PRintf("%d/n",ans);}

上一篇：HashSet、LinkedHashSet、TreeSet使用区别

下一篇：简单算法———堆排序

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注