题解：P14995 [Nordic OI 2020] Apple Delivery

· · 题解

题解：P14995 [Nordic OI 2020] Apple Delivery

诶期末考试咧，啷个还在刷竞赛题捏（HF 音）？

然后做了三天多没做出来，抢首 A 变成了首 WA…

我不行了我一直在找 O(n\log r) 的做法，开始思路有问题。

前置知识

这是一道高斯圆问题（圆内整点问题）。

对于固定的半径 r 的圆，将其分解为 4 个象限上的点和 4 个半轴上的点，以及 1 个原点。

4 个象限的点数相同，4 个半轴上的点数也相同。所以一个圆内的点，可以以一象限和 y 轴正半轴为准，拆分成 1 + 4 \times（一象限的点 + y 轴正半轴上的点）。

枚举 x 坐标，勾股可得最大 y = \left\lfloor \sqrt{r^2 - x^2} \right\rfloor。

由此得到 O(r) 的单个圆内整点的公式：

Poi_r = 1 + \sum_{i = 0}^{r - 1} \left\lfloor \sqrt{r^2 - i^2} \right\rfloor

:::success[暴力做法（仅给暴力思路，看正解的可跳过）] 40pts

对于每个 r，均套用一遍公式得出每个圆内的点数和模 8 意义下的值，然后枚举或状压。

55pts

只需加上记忆化处理，可以去掉一部分 r 重合的情况。 :::

处理模 8 意义下的值

由上述公式可得，Poi_r = 4n + 1，故模 8 意义下只有 1 和 5 这两个值，取决于一象限和 y 轴正半轴点数和的奇偶（若为奇数则为 5，偶数则为 1）。可以从这方面入手。

继续拆分一象限，以 y = x 这一直线将其分为 3 部分，y = x 上面的点、下面的点，以及 y = x 上的点。

由于 y = x 上下的点数对称，故只需要考虑 y = x 上的点数 + y 轴正半轴上的点数和的奇偶。这样就可以 O(1) 预处理出模 8 意义下的值。

删除半径

由上，我们得到了两个可重集合（分别对应模 8 为 1 和模 8 为 5 的半径）。要使送出的苹果数为 8 的倍数，就是在模 8 为 1 的集合中选 a 个数，在模 8 为 5 的集合中选 b 个数，使 a + 5b \equiv 0 \pmod{8}。

未分发的苹果数最少，则已分发的苹果最多。所以选出来的这些半径所包含的整点要尽量多，则半径要尽量大。故可以将半径升序排序，从后向前选。

任意考虑一个集合，如果在选完后，剩余的半径个数 \ge 8，就可以再选 8 个半径加入，加入后条件仍成立。因此，选的要尽量多，那么不选的半径个数只能是 0\~7 个。

于是枚举模 8 为 5 的集合中未选的项数，求出在这种情况下最多可选的能使 a + 5b \equiv 0 \pmod{8} 成立的模 8 为 1 的半径个数，计算未分发的苹果数并比较。最后输出最小值即可。

for(int k5 = 0; k5 < sz5; ++k5) {
  int k1 = ((num5 - k5) * 5 + num1) % 8;
    if(k1 >= sz1) continue;
    ans = min(ans, sum5[k5] + sum1[k1]);
}

为简化时间复杂度，可以预处理前缀和，后续可以 O(1) 调用。

for(int i = 1; i < sz1; ++i) {
    int r = mod1[i - 1], poi = 0;
    for(int j = 0; j < r; ++j)
        poi += (int)floor(sqrt((double)(r * r - j * j)));
    poi = poi * 4 + 1;
    sum1[i] = sum1[i - 1] + poi;
}

for(int i = 1; i < sz5; ++i) {
    int r = mod5[i - 1], poi = 0;
    for(int j = 0; j < r; ++j)
        poi += (int)floor(sqrt((double)(r * r - j * j)));
    poi = poi * 4 + 1;
    sum5[i] = sum5[i - 1] + poi;
}

总结一下做法

记得开 long long

#include<bits/stdc++.h>
#define int long long
using namespace std;

int n, ans = 1e15;
vector<int> mod1, mod5;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for(int i = 1, r; i <= n; ++i) {
        cin >> r;
        if(((int)floor((double)r / sqrt(2)) + r) % 2 == 0) 
            mod1.push_back(r);
        else mod5.push_back(r);
    }
    sort(mod1.begin(), mod1.end());
    sort(mod5.begin(), mod5.end());

    int num1 = (int)mod1.size();
    int num5 = (int)mod5.size();
    int sz1 = min((int)8, num1 + 1);
    int sz5 = min((int)8, num5 + 1);

    vector<int> sum1(static_cast<size_t>(sz1), 0);
    vector<int> sum5(static_cast<size_t>(sz5), 0);

    for(int i = 1; i < sz1; ++i) {
        int r = mod1[i - 1], poi = 0;
        for(int j = 0; j < r; ++j)
            poi += (int)floor(sqrt((double)(r * r - j * j)));
        poi = poi * 4 + 1;
        sum1[i] = sum1[i - 1] + poi;
    }

    for(int i = 1; i < sz5; ++i) {
        int r = mod5[i - 1], poi = 0;
        for(int j = 0; j < r; ++j)
            poi += (int)floor(sqrt((double)(r * r - j * j)));
        poi = poi * 4 + 1;
        sum5[i] = sum5[i - 1] + poi;
    }

    for(int k5 = 0; k5 < sz5; ++k5) {
        int k1 = ((num5 - k5) * 5 + num1) % 8;
        if(k1 >= sz1) continue;
        ans = min(ans, sum5[k5] + sum1[k1]);
    }

    cout << ans;

return 0;
}

呜呜呜审核大大给过吧...