E - Bomber
题目大意
给出一个 $H \times W$ 的矩阵，上面有 $M$ 个点，选出一行一列使得覆盖到的点最多。问最多是多少。
其中 $H,W,M <= 3 \times 10^5$
简要题解
注意到一定会贪心的选某个数量最多的行和列。设其行列数量分别 $mx$，$my$，则答案只可能是 $mx + my$ 或 $mx + my - 1$。则只需验证所有数量为 $mx$ 的行和所有数量为 $my$ 的列是否有点，这里注意到最多只会有 $M$ 个点，因此如果行和列交点特别多的情况，必然在前 $M+1$ 次 $check$ 会有一次是不存在点的，算法就会终止。
复杂度
$T$：$O(H+W+MlogM)$ 这里可以使用 hash 进一步降低复杂度，不过 set 已经足够快了
$S$：$O(H+W+M)$
代码实现
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int M=3e5+5;
int cntx[M],cnty[M];
set<PII> se;
int main()
{
int h,w,m; scanf("%d%d%d",&h,&w,&m);
int x,y;
for(int i=0;i<m;i++)
{
scanf("%d%d",&x,&y);
cntx[x]++;
cnty[y]++;
se.emplace(x,y);
}
int mx=0,my=0;
for(int i=1;i<=h;i++)
mx=max(mx,cntx[i]);
for(int i=1;i<=w;i++)
my=max(my,cnty[i]);
vector<int> vx,vy;
for(int i=1;i<=h;i++)
if(cntx[i]==mx) vx.push_back(i);
for(int i=1;i<=w;i++)
if(cnty[i]==my) vy.push_back(i);
int f=0;
int ans=mx+my-1;
for(int i:vx)
{
for(int j:vy)
{
if(!se.count({i,j}))
{
ans=mx+my;
f=1;
break;
}
}
if(f) break;
}
printf("%d\n",ans);
return 0;
}
Next: 《汇编语言》 笔记 第 1 章 基础知识