题解：P11504 [NordicOI 2018] French Fries

· · 题解

感谢镜像赛工作人员 @沉石鱼惊旋 提供官方题解。

以下设 V 为值域，题目中保证 V \le 10^7。

考虑在 x 处放一根薯条的作用效果。枚举这根薯条向左传了 d 次，那么 x + T - 2d 处的人会获得 \frac{{T \choose d}}{2^T} 根薯条。

预处理 dif_i 表示在某个位置放一根薯条，最终距离它为 i 的人能获得多少根薯条。这一部分我们只需预处理 T 以内的阶乘，阶乘可能很大，可以取以 2 为底的对数，这样方便除 2^T。

观察杨辉三角，我们发现两边的数比起中间是非常小的。我们可以设一个宽度 W，在 x 放薯条时只处理 x 对 [x - W, x + W] 的影响，也就是说我们认为 dif_i(i > W) 约等于 0。事实上 W 取 O(\sqrt T) 即可，代码中 W = 10^5。

直接暴力考虑每个放薯条的位置对两边 W 个数的影响，可以得到一个时间复杂度 O(V + P\sqrt T) 的做法，期望得到 74 分。

进一步观察操作性质。发现 dif 可以按奇偶性分成两个序列，一个全是 0，一个单调递减（因为杨辉三角从中间到两边单调递减），下面只讨论后者。

考虑将 dif 分成若干极长段，每一段的最大值 mx 和最小值 mi 满足 \frac{mx}{mi} 不超过一阈值 D = 1.25，将这一段中所有值都认为是 \sqrt{mi \times mx}。

由于每一段最大值不超过上一段的 \frac{1}{D}，这样做将 O(W) 个单点加变成了 O(\log_D \alpha) 个区间加，其中 \alpha 为代码精度（大概是 10^{18} 级别），以便我们快速用差分维护。

再来分析误差，由于 \frac{mx}{mi} \le D，mx 这个数变成了原来的 \sqrt{\frac{mi}{mx}} \ge D^{-0.5} 倍，而 mi 变成了原来的 \sqrt{\frac{mx}{mi}} \le D^{0.5} 倍。所以误差为 D^{-0.5} \sim D^{0.5}，算一算是 0.91287 \sim 1.09545，而题目中允许的误差是 0.8 \sim 1.2，可以接受。

时间复杂度 O(P \log_{D} \alpha + V + T)，期望获得满分。

#include <iostream>
#include <cmath>

using namespace std;

const int W = 1e5, kW = W + 5; 
const int V = 1e7 + W * 2, kV = V + 5; 
const int kM = 5e7 + 5; 
const int kN = 3e5 + 5; 
const double D = 1.25;
const int L = 1000; 

int n, m, a[kN];
double g, fac[kM], mp[kV], dif[kW]; 
int len, l[L], r[L]; 
double v[L];

double C (int n, int m) {
    return fac[n] - fac[m] - fac[n - m]; 
}

int main () {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> g;
    fac[0] = 0; 
    for (int i = 1; i <= m; ++i) 
        fac[i] = fac[i - 1] + log2(i);
    for (int i = 1; i <= n; ++i)
        cin >> a[i], a[i] += W;
    for (int i = 0; i <= min(m, W); ++i) {
        if ((i ^ m) & 1) continue;
        int c = (i + m) >> 1;
        double p = C(m, c) - m, v = 0; 
        if (p >= -60) v = pow(2, p);
        dif[i] = v; 
    }
    double mx, mi; 
    for (int o = m & 1, tl, tr, i = o; i <= W + 2; i += 2) {
        if (dif[i] * D < mx || i == W + 2 || i == o) {
            if (i != o) {
              ++len, l[len] = tl, r[len] = tr;
              ::v[len] = sqrt(mx * mi);
            }
            tl = tr = i, mx = mi = dif[i];
        }
        else {
            tr = i, mi = dif[i];
        }
    }
    auto add = [&](int l, int r, double x) -> void {
        mp[l] += x, mp[r + 2] -= x; 
    }; 
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= len; ++j) {
            add(a[i] - r[j], a[i] - l[j], v[j]);
            add(a[i] + l[j], a[i] + r[j], v[j]); 
        } 
    }
    for (int i = 2; i < V; ++i)
        mp[i] += mp[i - 2];
    int ans = 0; 
    for (int i = 0; i < V; ++i)
        ans += mp[i] >= g;
    cout << ans << '\n';
    return 0; 
}