【bzoj5085】最大(二分+乱搞)
2024-08-26 18:09:16
题目传送门:https://www.lydsy.com/JudgeOnline/problem.php?id=5085
这道题我们可以先二分答案,然后转化为判定是否有四角权值>=mid的矩形。
我们可以发现,若4个点可以构成矩形,那么这四个点一定两两在同一行,同一列。
于是我们可以把每一行的合法点处理出来,在里面枚举点对。若有一个点对出现了两次,那么就说明在上面的某一行的相同列有两个合法点,即能构成矩形。
因为找到两对相同的合法点对就可以反回结果,而合法点对的规模是$ O(m^2) $的,因此总时间复杂度$ O(m^2\log(n)) $。
· (然而我因为读入写错tle了好几发。。。qwq)
代码:
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#define ll long long
#define ull unsigned long long
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define lowbit(x) (x& -x)
#define mod 10000007
#define inf 0x3f3f3f3f
#define eps 1e-10
#define maxn 1010
inline char nc(){
static char buf[],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,,,stdin),p1==p2)?EOF:*p1++;
}
inline ll read(){ll tmp=; char c=nc(),f=; for(;c<''||''<c;c=nc())if(c=='-')f=-; for(;''<=c&&c<='';c=nc())tmp=(tmp<<)+(tmp<<)+c-''; return tmp*f;}
inline ll power(ll a,ll b){ll ans=; for(;b;b>>=){if(b&)ans=ans*a%mod; a=a*a%mod;} return ans;}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline void swap(int &a,int &b){int tmp=a; a=b; b=tmp;}
using namespace std;
int a[maxn][maxn],vis[maxn][maxn];
int x[maxn];
int n,m;
int check(int mid)
{
memset(vis,,sizeof(vis));
for(int i=;i<=n;i++){
int tot=;
for(int j=;j<=m;j++)
if(a[i][j]>=mid)x[++tot]=j;
for(int j=;j<tot;j++)
for(int k=j+;k<=tot;k++)
if(vis[x[j]][x[k]])return ;
else vis[x[j]][x[k]]=;
}
return ;
}
int main()
{
n=read(); m=read();
int l=inf,r=-inf;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
a[i][j]=read(),l=min(l,a[i][j]),r=max(r,a[i][j]);
while(l<r){
int mid=(l+r+)>>;
if(check(mid))l=mid;
else r=mid-;
}
printf("%d\n",l);
}
bzoj5085
Tips:听说找到权值最大的前4n个点直接爆枚就行了?然而我不会证。
最新文章
- Django博客功能实现—文章评论功能
- NAT概述
- jQuery晦涩的底层工具方法们
- Independence独立
- Sharepoint的网页(Page),网页解析(Parsing)与解析安全处理(Security)
- MFC框架中消失的WinMain()
- linux http请求监控工具httpry---官方文档
- HDU 2066 最短路floyd算法+优化
- VS2010创建和调用动态链接库
- Linux IPC - Shared memory
- zuul进阶学习(二)
- Yii2的Gridview应用技巧补充
- FCC JS基础算法题(0):Reverse a String(翻转字符串)
- JS高级-虚拟DOM
- Linq(高级查询)
- windows如何查看电脑开关机记录
- Django ORM OneToOneField
- Thread中join()方法进行介绍
- IIS配置中出现HRESULT:0X80070020错误
- Http请求中Content-Type和Accept讲解以及在Spring MVC中的应用