A. Two Squares

只用判断是否有点同时在两个正方形内部即可。

水平放的正方形很好搞，斜着放的转一下坐标也可以搞。

B. Open Communication

模拟题。不知道数据范围为什么搞这么小。

枚举每两对，如果只有一个两对有恰好一个相同的那么答案就是它。否则还要看参赛者是否知道答案。每个参赛者比自己仅多知道他手中的那一对使什么，再枚举对方的每一对同样操作即可。

C. Careful Maneuvering

看到这个题先想如果只有一个小飞船怎么求答案。有以下两种方式：

• 观察发现把飞船放到 0.5 的整数倍的位置才会对答案有贡献。枚举这些位置分别计算答案，取最大的。复杂度 O(20000nm) 。

• 枚举左右两边的一对大飞船，计算它们对 x=0 这条线上的一点的贡献。显然被贡献最多的那一点上放飞船使最优的。复杂度 O(nm) 。

然后用第一种方法处理第一个飞船，第二种方法处理第二个飞船就可以做到 O(20000nm) 。实际上这个地方我想蠢了，其实两次都用第二种方法处理可以做到 O\left((nm)^2\right)。但因为我先想了第一种方法并且数据范围没卡我的做法，所以它还是过了。

D. Compute Power

官方题解给的做法是 O(n^3\log10^{11}) 的，实际上这个题可以做到 O(n^2\log10^{11})。

先把这 n 个任务按 a_i 从大到小排序，a_i 相等的合并成一个元素，内部再按 b_i 从大到小排序。下面设共有 m 个 a_i 不同的元素。

然后二分答案，check(k) 表示答案是否不大于 k。那么每个要在第二次执行的任务都要匹配到一个 a_i 严格大于它的在第一次执行的任务，并且对于选中的在第一次执行的任务要有 \sum a_i-kb_i\leq 0。我们不妨求出这个和式满足约束条件时的最小值。由 Hall 定理可知，对于处理过程中的每一个前缀 i(i\leq m) ，都要满足 i-1 前选了的元素个数大于等于 i 前没选的元素个数。然后 DP ，设 f(i,j) 表示前 i 个中选了 j 个的最小值。那么问题就变成了一个多重背包，因为 a_i 相同的任务肯定会优先选 b_i 大的。物品的总数为 O(n) ，所以复杂度是 O(n^2)。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int MAXN=55;
const ll INF=1E18;
struct Task
{
    int a, b;
    bool operator < (const Task& rhs) const
    {
        return a>rhs.a||a==rhs.a&&b>rhs.b;
    }
} t[MAXN];
int n, m;
vector<int> v[MAXN];
ll f[MAXN][MAXN];
bool check(ll r)
{
    memset(f, 0X3F, sizeof f);
    f[0][0]=0;
    for (int i=1, c=0; i<=m; i++)
    {
        c+=v[i].size();
        for (int j=0; j<=c; j++)
        {
            ll s=0;
            for (int k=0; k<=v[i].size()&&k<=j&&j-k>=c-j; k++)
            {
                if (k) s+=1000ll*t[v[i][k-1]].a-r*t[v[i][k-1]].b;
                f[i][j]=min(f[i][j], f[i-1][j-k]+s);
            }
        }
    }
    for (int i=0; i<=n; i++)
        if (f[m][i]<=0) return 1;
    return 0;
}
int main()
{
//  freopen("D.in", "r", stdin);
//  freopen("D.out", "w", stdout);
    scanf("%d", &n);
    for (int i=1; i<=n; i++) scanf("%d", &t[i].a);
    for (int i=1; i<=n; i++) scanf("%d", &t[i].b);
    sort(t+1, t+n+1);
    for (int i=1; i<=n; i++)
    {
        if (t[i].a!=t[i-1].a) m++;
        v[m].push_back(i);
    }
    ll l=0, r=1E11;
    while (l<r)
    {
        ll mid=l+r>>1;
        if (check(mid)) r=mid;
        else l=mid+1;
    }
    printf("%lld\n", l);
    return 0;
}

E. Nikita and Order Statistics

开始想枚举右端点然后考虑贡献，但怎么想都感觉不能做。。看了眼标签 FFT 后直接明白。

把小于 x 的数视为 1 ，大于等于 x 的数视为 0 ，那么问题就是对于每个 k\in [0,n] 求 sum=k 的区间个数。那么考虑一下这个 01 序列的前缀和 s_i，记 f_i 表示 s_p=i 的个数，答案就是 \sum_{i-j=k}f(i)f(j)。设 g(i)=f(n-i) ，那么式子就变成了 f 和 g 的卷积。NTT 卷一下就可以了。