AtCoder Beginner Contest 215

https://atcoder.jp/contests/abc215

F - Dist Max 2

题意

给定 $n$ 个点 $(x,y)$。定义点 $i$ 与点 $j$ 的距离为 $\min(|x_i-x_j|,|y_i-y_j|)$。求两点间的最大距离。

数据范围：$2\leq n\leq 2\times10^5$。

题解

考虑二分答案，对于固定的 $m$，即需要检验是否存在一对 $i,j$，满足

$$|x_i-x_j|\geq m,|y_i-y_j|\geq m$$

可以将所有点按 $x$ 排序，然后双指针：对于每个 $i$，将所有 $x_i-x_j\geq m$ 的 $j$ 加入，并维护 $y$ 的最值，判断是否有 $|y-y_i|\geq m$ 即可。

代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N=2e5+5;
int n;
pii a[N];
bool check(int m)
{
    int mx=0,mn=1e9;
    for(int i=1,j=1;i<=n;i++)
    {
        while(j<i&&a[i].first-a[j].first>=m)
        {
            mx=max(mx,a[j].second);
            mn=min(mn,a[j].second);
            j++;
        }
        if(mx>=a[i].second+m) return 1;
        if(mn<=a[i].second-m) return 1;
    }
    return 0;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i].first>>a[i].second;
    sort(a+1,a+n+1);
    int l=0,r=1e9;
    while(l<r)
    {
        int m=(l+r+1)/2;
        if(check(m)) l=m;
        else r=m-1;
    }
    cout<<l<<'\n';
    return 0;
}

G - Colorful Candies 2

题意

有 $n$ 颗糖果，每颗糖果有一种颜色。对于 $k=1,2,\cdots,n$，求在这 $n$ 颗糖果中取 $k$ 颗，颜色数的期望。

数据范围：$1\leq n\leq5\times10^4$。

题解

考虑每种颜色的贡献，假设有 $a_i$ 个。那么取 $k$ 个糖果的答案就是

$$\sum\frac{\binom{n}{k}-\binom{n-a_i}{k}}{\binom{n}{k}}$$

而不同的 $a_i$ 的个数是 $O(\sqrt{n})$ 级别的，所以直接计算就可以了。