「GYM102341」Dedenne

发表于 | 更新于 | 分类于 | 阅读次数：

题意简述

GYM102341D

一堆01串是 dictionary 仅当其中没有一个串为另一个的前缀，且每个串都不含子串00。

一个 dictionary $S$ 的 cost，是所有01串 $s$（不仅包含 $S$ 中的串）的 cost 的和。

对于一个01串 $s$，若其为 $k$ 个 $S$ 中串的前缀，则其 cost 为 $\sum\limits_{j=1}^k\lfloor1+\log_2j\rfloor$。

$t$ 组询问大小为 $n$ 的 dictionary 的 cost 的最小值，$t\le 5\times 10^4, 2\le n\le 10^{15}$。

主要思路

首先 $f(k)=\sum\limits_{j=1}^k\lfloor1+\log_2j\rfloor$ 可以在 $O(\log n)$ 预处理后 $O(1)$ 计算。

设 $D(n)$ 为构造大小为 $n$ 的 dictionary 的最小代价，则 $D(1)=1$。

我们把串扔到 trie 上，那么显然地，$D(n) = f(n)+\min\limits_{i\le k<n}\{f(k)+D(k)+D(n-k)\}$。这里 $k$ 是枚举左子树的叶子个数，$f(k)$ 是因为左边的串（因为不能出现00）要以01开头。（$k=1$ 时则不需要加上 $f(1)$。）

可以证明 $D$ 是下凸函数，同时 $f$ 也是下凸函数，因此 $f(k)+D(k)+D(n-k)$ 也是下凸的。因此可以三分 $k$。于是我们可以 $O(\log^2n)$ 地求出任意一个 $D(n)$。

显然这不够。我们不妨枚举增量 $\delta$，每次求出最大 $n’$ 使 $D(n’)=D(n)+\delta\cdot(n’-n)$，其中 $n$ 是目前确定的最远 $D$ 值。
$n’$ 可以二分，且当 $n$ 足够大时，计算 $D(n’)$ 不会用到未确定的 $D$ 值。
可以证明 $\delta$ 是 $O(\log^2n)$ 级别。（经过尝试，$n\le 10^{15}$ 时，增量 $\delta$ 仅有 $1840$。）

于是可以 $O(\log^5 n)$ 预处理上述所有东西，每次询问再 $O(\log n)$ 二分一下即可。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
typedef vector<i64> VI;
#define pb emplace_back
#define Templ(T) template <typename T>
Templ(_Tp) inline int chkmin(_Tp &x, _Tp y) { return x > y ? x = y, 1 : 0; }
Templ(_Tp) inline int chkmax(_Tp &x, _Tp y) { return x < y ? x = y, 1 : 0; }
constexpr i64 inf = 1'00000'00000'00000;
constexpr i64 B = 1'000; // limit of brute force
i64 fp[55];
i64 f(i64 k) {
    int t = 64 - __builtin_clzll(k);
    return fp[t] + (k + 1 - (1ll << (t - 1))) * t;
}
// #define fk1(k) ((k) == 1 ? 0 : f(k))

VI a, D;
i64 Dsm[1024];
i64 Dbrute(i64 n) {
    // assert(n <= B);
    if (Dsm[n] != 0) return Dsm[n];
    i64 res = 1 + Dsm[n - 1];
    // assert(Dsm[n - 1] != 0);
    for (i64 i = 2; i <= n / 2; ++i) {
        i64 tmp = f(i) + Dsm[i] + Dsm[n - i];
        chkmin(res, tmp);
    }
    return Dsm[n] = res + f(n);
}
i64 Dget(i64 n) {
    if (n <= B) return Dbrute(n);
    int k = upper_bound(a.begin(), a.end(), n) - a.begin();
    return D[k - 1] + k * (n - a[k - 1]);
}
i64 Dcalc(i64 n) {
    if (n <= B) return Dbrute(n);
    i64 l = n / 3, r = n / 2;
    while (l < r) {
        i64 m = (l + r) / 2;
        i64 Dl = f(m) + Dget(m) + Dget(n - m);
        i64 Dr = f(m + 1) + Dget(m + 1) + Dget(n - m - 1);
        if (Dl < Dr) r = m;
        else l = m + 1;
    }
    return f(n) + f(l) + Dget(l) + Dget(n - l);
}

int main() {
    for (int i = 1; i < 54; ++i)
        fp[i + 1] = fp[i] + (1ll << (i - 1)) * i;
    a.pb(1), D.pb(1);
    Dsm[1] = 1;
    int delta = 1;

#define Dexp(i) (D.back() + delta * ((i) - a.back())) // expect
    while (a.back() < inf) {
        i64 n = a.back();
        while (n < B && Dcalc(n + 1) == Dexp(n + 1)) ++n;
        if (n < B) {
            D.pb(Dcalc(n)), a.pb(n), ++delta;
            continue;
        }

        // assert(Dcalc(n / 2 * 3) != Dexp(n / 2 * 3));
        i64 l = n, r = n / 2 * 3 - 1;
        while (l < r) {
            i64 m = (l + r + 1) / 2;
            if (Dcalc(m) == Dexp(m)) l = m;
            else r = m - 1;
        }
        D.pb(Dcalc(l)), a.pb(l), ++delta;
    }

    int Q;
    scanf("%d", &Q);
    while (Q--) {
        i64 n;
        scanf("%lld", &n);
        printf("%lld\n", Dget(n));
    }
    return 0;
}