20231110题解

发表于 分类于 ， 阅读次数：

AFO 前最后一篇。

以后这里也许就更信息论和机器学习了。

sequence

这个东西比较像 DP。可以方便地设计一个状态空间为 \(\mathcal{O}(nW)\) 的状态：用 \(f_{i, j}\) 表示到第 \(i\) 个序列为止，结尾的值是 \(j\) 的最大收益。则我们枚举 \(i+1\) 的结尾，可以知道 \(a_{i+1, k}\) 作为结尾时，开头是 \(a_{i+1,k+1}\)，则 \(\max_j (f_{i,j} + i|a_{i+1,k+1}-j|) \to f_{i+1,a_{i+1,k}}\)。时间复杂度 \(\mathcal{O}(W\sum m)\)。应该有三十分。

实际上刚才那个思路第二维不需要基于值域，可以直接枚举之前是第几个，这样是 \(\mathcal{O}(m^2)\) 的。但是接下来要用值域，所以仍用此法。

显然要考虑优化。DP 优化的关键是把与转移变量无关的项提出来，但是这里 \(a_{i+1,k+1}\) 被缠在了绝对值里。怎么办呢？

对于 \(j\) 分讨，把绝对值拆掉，则转移变成这样：

\[ \begin{aligned} \max_{j=0}^{a_{i+1,k+1}} (f_{i,j} + ia_{i+1,k+1}-ij) &\to f_{i+1,a_{i+1,k}} \\ \max_{j=a_{i+1,k+1}}^{W} (f_{i,j} + ij - ia_{i+1,k+1}) &\to f_{i+1,a_{i+1,k}} \end{aligned} \]

现在就可以把 \(a_{i+1,k+1}\) 提出来了。我们可以用两个辅助状态优化转移：用 \(g_{i,j}\) 表示 \(f_{i,j}-ij\)，\(h_{i,j}\) 表示 \(f_{i,j} + ij\)，则转移方程为：

$$ \[\begin{aligned} ia_{i+1,k+1}+\max_{j=0}^{a_{i+1,k+1}} g_{i,j ## sequence 这个东西比较像 DP。可以方便地设计一个状态空间为 $\mathcal{O}(nW)$ 的状态：用 $f_{i, j}$ 表示到第 $i$ 个序列为止，结尾的值是 $j$ 的最大收益。则我们枚举 $i+1$ 的结尾，可以知道 $a_{i+1, k}$ 作为结尾时，开头是 $a_{i+1,k+1}$，则 $\max_j (f_{i,j} + i|a_{i+1,k+1}-j|) \to f_{i+1,a_{i+1,k}}$。时间复杂度 $\mathcal{O}(W\sum m)$。应该有三十分。 ~~实际上刚才那个思路第二维不需要基于值域，可以直接枚举之前是第几个，这样是 $\mathcal{O}(m^2)$ 的。但是接下来要用值域，所以仍用此法。~~ 显然要考虑优化。DP 优化的关键是把与转移变量无关的项提出来，但是这里} &\to f_{i+1,a_{i+1,k}} \\ -ia_{i+1,k+1}+\max_{j=a_{i+1,k+1}}^{W} h_{i,j} &\to f_{i+1,a_{i+1,k}} \end{aligned}\]

$$

容易看出，我们只要维护 \(g_i\) 的前缀最值以及 \(h_i\) 的后缀最值即可。使用树状数组维护，时间复杂度 \(\mathcal{O}(\log W \sum m)\)。

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;

template <class T>
void read(T &r) {
    r = 0; int ch = getchar(), f = 0;
    while (!isdigit(ch)) {if (ch == 45) f ^= 1; ch = getchar(); }
    while (isdigit(ch)) (r *= 10) += ch - 48, ch = getchar();
    if (f) r = -r;
}

const int maxn = 1e6 + 5;

int t, n;
vector<long long> a[maxn];
vector<long long> w[maxn];
pair<int, long long> prec[maxn], sufc[maxn];

void update(pair<int, long long> c[], int pos, pair<int, long long> v) {
    while (pos <= 1e6) {
        c[pos] = max(c[pos], v);
        pos += (pos & -pos);
    }
}

pair<int, long long> ask(pair<int, long long> c[], int pos) {
    pair<int, long long> res;
    while (pos) {
        res = max(c[pos], res);
        pos -= (pos & -pos);
    }
    return res;
}

long long nxt(vector<long long> &x, int id) {
    if (++id == x.size()) id = 0;
    return x[id];
}

int main() {
    // freopen("sequence.in", "r", stdin);
    // freopen("sequence.out", "w", stdout);
    read(t);
    while (t--) {
        read(n);
        for (int i = 1; i <= n; i++) {
            a[i].clear(); w[i].clear();
            int m; read(m);
            for (int j = 1; j <= m; j++) {
                int x; read(x);
                a[i].emplace_back(x);
            }
        }
        memset(prec, 0, sizeof prec);
        memset(sufc, 0, sizeof sufc);
        for (int i = 0; i < a[1].size(); i++) {
            update(prec, a[1][i], make_pair(1, -1LL * a[1][i]));
            update(sufc, 1e6 + 1 - a[1][i], make_pair(1, 1LL * a[1][i]));
        }
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j < a[i].size(); j++) {
                long long v = nxt(a[i], j);
                auto r1 = ask(prec, v), r2 = ask(sufc, 1e6 + 1 - v);
                long long w1 = (r1.first == i - 1) ? r1.second : 0xcfcfcfcfcfcfcfcf;
                long long w2 = (r2.first == i - 1) ? r2.second : 0xcfcfcfcfcfcfcfcf;
                w[i].emplace_back(max(w2 - (i - 1) * v, w1 + (i - 1) * v));
            }
            for (int j = 0; j < a[i].size(); j++) {
                update(prec, a[i][j], make_pair(i, w[i][j] - i * a[i][j]));
                update(sufc, 1e6 + 1 - a[i][j], make_pair(i, w[i][j] + i * a[i][j]));
            }
        }
        long long ans = 0xcfcfcfcfcfcfcfcf;
        for (auto x : w[n]) {
            ans = max(ans, x);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

//f_i :以数字i结尾的最大值 + val(i)
//g_i :以数字i结尾的最大值 - val(i)

tree

我们用 \(T_k(d)\) 表示一棵深度为 \(d\) 的满 \(d\) 叉树，再用 \(\operatorname{Sub}(x)\) 表示以 \(x\) 为根的子树，则容易发现题目说的 \(f_{i,k} = \max\{d \mid T_k(d) \subseteq \operatorname{Sub}(i) \}\)。

考虑对 \(k\) 分类讨论：

  • \(k=1\)，此时 \(f_i\) 就是 \(i\) 到叶子节点的最大深度。
  • \(k > 1\) 时，\(|T_k(d)|=\frac{k^d-1}{k-1}\)，由于 \(|T_k(d)| \le |\operatorname{Sub}(i)| \le n\)，所以合法的 \(d= \mathcal{O}(\log_kn)\)。这样就可以从 \(d\) 入手：记 \(g_{i,d}=\max\{k \mid T_k(d) \subseteq \operatorname{Sub}(i) \}\)，我们会发现 \(\sum_i\sum_k{f_{i,k}} = \sum_i\sum_d{g_{i,d}}\)（考虑每一个 \(d\) 的贡献可证），而 \(g_{i,d}\) 可以由儿子直接转移。由于 \(d\) 有上限，所以不会 T。

注意一点，上面所说的两部分其实重复统计了 \(k=1\) 时的贡献。如果我们枚举的 \(d\) 上限是 \(w=\mathcal{O}(\log n)\)，应该把第一条的贡献从最大深度变成最大深度减去 \(w\)。

具体细节见代码：

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
#include <bits/stdc++.h>
using namespace std;

template <class T>
void read(T &r) {
    r = 0; int ch = getchar(), f = 0;
    while (!isdigit(ch)) {if (ch == 45) f ^= 1; ch = getchar(); }
    while (isdigit(ch)) (r *= 10) += ch - 48, ch = getchar();
    if (f) r = -r;
}

const int maxn = 3e5 + 5;
int n;
vector<int> tree[maxn];
int g[maxn][20], md[maxn];
vector<int> tmp;
long long ans;

void dfs(int u, int fa) {
    md[u] = 1;
    for (int v : tree[u]) {
        if (v == fa) continue;
        dfs(v, u);
        md[u] = max(md[u], md[v] + 1);
    }
    if (md[u] > 19) ans += md[u] - 19;
    // for (int i = 1; i <= n; i++) {
    //     f[u][i] = 1; int cnt = 0, mx = 0;
    //     for (int v : tree[u]) {
    //         if (v == fa) continue;
    //         if (f[v][i] > mx) {
    //             mx = f[v][i];
    //             cnt = 1;
    //         } else if (f[v][i] == mx) cnt++;
    //     }
    //     f[u][i] = max(f[u][i], mx + (cnt >= i));
    // }
    g[u][1] = n; ans += n;
    for (int d = 2; d < 20; d++) {
        tmp.clear(); int td = 0;
        for (int v : tree[u]) {
            if (v == fa) continue;
            td = max(td, g[v][d]);
            tmp.emplace_back(g[v][d - 1]);
        }
        sort(tmp.begin(), tmp.end());
        int j = td + 1;
        for (int i = 0; i < tmp.size(); i++) {
            if (tmp.size() - i < j) break;
            while (tmp[i] >= j) {
                if (tmp.size() - i < j) break;
                td = max(j, td);
                j++;
            }
            if (tmp.size() - i < j) break;
        }
        g[u][d] = td, ans += td;
    }
}

int main() {
    // freopen("tree.in", "r", stdin);
    // freopen("tree.out", "w", stdout);
    read(n);
    for (int i = 1; i < n; i++) {
        int u, v; read(u); read(v);
        tree[u].emplace_back(v);
        tree[v].emplace_back(u);
    }
    dfs(1, 0);
    // for (int i = 1; i <= n; i++) {
    //     // for (int j = 1; j <= n; j++) {
    //     //     // ans += f[i][j];
    //     //     printf("%d%c", f[i][j], " \n"[j == n]);
    //     // }
    //     for (int j : g[i]) ans += j;
    // }
    printf("%lld\n", ans);
    return 0;
}

cloud

诈骗题。我居然想了好久。

首先，有这么两个性质：

  1. 时刻 0 的时候所有的云都不相交。
  2. 所有的云只有两种相同的方向，且速度一样。

这样的话，我们立即可以得到：

  1. 方向相同的云永不相交。
  2. 如果两个方向相异的相交了，覆盖层数也最多是 2，因为此时其他的云都不会与相交部分相交。

所以答案只能是 1 和 2。

接下来考虑，什么时候答案会是 2 呢？

两种方向一起运动不好考虑，但是题目说了不限时间地点，所以可以考虑相对运动：让 \(d=0\) 的不动，\(d=1\) 的向左上方 \(45\degree\) 运动。

斜的运动还是不好，我们再把坐标系也旋转 \(45\degree\)，这样原来的正方形就变成了斜着的宝石形。（我的 zsh 告诉我这种斜着的正方形叫做 diamond，我也觉得挺不像的）

在新的坐标系下，\(d=0\) 的不动，\(d=1\) 的上下移动。

既然我们只用考虑两个正方形相交，我们就可以只考察这个正方形最宽的那个对角线。只要运动中这两个对角线会相交，则一定相交。

所以思路就简单了：先处理所有 \(d=0\) 的正方形，找到它们旋转之后在 \(x\) 轴上的投影，将投影区域区间加；再处理 \(d=1\) 的，如果它对应的投影里区间和不为 0，那么就一定会重合，答案就是 2。

由于值域比较大，需要对坐标离散化。

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
#include <bits/stdc++.h>
using namespace std;

template <class T>
void read(T &r) {
    r = 0; int ch = getchar(), f = 0;
    while (!isdigit(ch)) {if (ch == 45) f ^= 1; ch = getchar(); }
    while (isdigit(ch)) (r *= 10) += ch - 48, ch = getchar();
    if (f) r = -r;
}

const int maxn = 1e5 + 5;
int n, t, l[maxn], r[maxn], d[maxn];
long long s[maxn << 1];
vector<int> a;

int main() {
    // freopen("cloud.in", "r", stdin);
    // freopen("cloud.out", "w", stdout);
    read(t);
    while (t--) {
        read(n); a.clear();
        for (int i = 1; i <= n; i++) {
            int x, y, w, h; read(x); read(y); read(w); read(h); read(d[i]);
            l[i] = x + y, r[i] = x + y + w + h - 1;
            a.emplace_back(l[i]);
            a.emplace_back(r[i]);
        }
        sort(a.begin(), a.end());
        auto p = unique(a.begin(), a.end());
        memset(s, 0, sizeof s);
        for (int i = 1; i <= n; i++) {
            l[i] = lower_bound(a.begin(), p, l[i]) - a.begin() + 1;
            r[i] = lower_bound(a.begin(), p, r[i]) - a.begin() + 1;
            if (d[i] == 0) {
                s[l[i]]++;
                s[r[i] + 1]--;
            }
        }
        for (int i = 1; i <= 2 * n + 1; i++) s[i] += s[i - 1];
        for (int i = 1; i <= 2 * n + 1; i++) s[i] += s[i - 1];
        int ans = 1;
        for (int i = 1; i <= n; i++) {
            if (d[i] == 1) {
                if (s[r[i]] > s[l[i] - 1]) {
                    ans = 2;
                    break;   
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}