2021-10-12 13:47 已编辑上海温哥华电影学院安全工程师

关注

2021牛客OI赛前集训营-提高组题解（第四场）

Problem A. 最终测试

做法一

枚举所有可能性，一共 $2^{2n}$ 种。对于每种可能性，对选手排序得到他们的排名。
复杂度 $O(2^{2n}n\log(n))$ 。期望通过 10%。

做法二

假设第 $i$ 位选手的最终总分数为 $s_i$ ，考虑对于第 $i$ 位选手，他的排名期望为 $E_{i} = 1 + \sum_{1\leq j\leq n, j\not= i}P(s_j>s_i)$ 。由于 $P(s_j>s_i)=\frac{1}{16}\sum_{0\leq f_1, f_2, g_1, g_2\leq 1} [f_1a_{i,1}+f_2a_{i,2}<g_1a_{j,1}+g_2a_{j,2}]$ ，可以 $O(1)$ 求 $P(s_j>s_i)$ ，因此得到一个复杂度为 $O(n^2)$ 的做法。期望通过 40%。

做法三

在做法二的基础上，推导得到： $E_{i} = 1 + \sum_{1\leq j\leq n, j\not= i}P(s_j>s_i) \\ = 1 + \frac{1}{16} \sum_{0\leq f_1, f_2\leq 1} \sum_{0\leq g_1, g_2 \leq 1, j\not= i} [f_1a_{i,1}+f_2a_{i,2}<g_1a_{j,1}+g_2a_{j,2}]$
因此我们可以将所有 $f_1a_{i,1}+f_2a_{i,2}$ 进行排序，就可以二分 $O(logn)$ 的得到最里面的求和。总复杂度为 $O(nlogn)$ 。期望通过 100%。

代码

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

const int maxn = 100100;
int a[maxn][4], x[4 * maxn], t, ans[maxn];

int main(void) {
    int n; scanf("%d", &n);
    assert(1 <= n && n <= 100000);

    for (int i=1; i<=n; i++) {
        int y[2]; scanf("%d%d", &y[0], &y[1]);
        assert(0 <= y[0] && y[0] <= 10000);
        assert(0 <= y[1] && y[1] <= 10000);

        for (int j=0; j<4; j++) {
            int s = 0;
            for (int k=0; k<2; k++) if ((j>>k) & 1) s += y[k];
            a[i][j] = s;
            x[t++] = s;
        }
    }

    sort(x, x+t, greater<int>());

    for (int i=1; i<=n; i++) {
        for (int j=0; j<4; j++) {
            int pos = lower_bound(x, x+t, a[i][j], greater<int>()) - x;
            for (int k=0; k<4; k++) if (a[i][k] > a[i][j]) pos--;
            ans[i] += pos;
        }
    }

    for (int i=1; i<=n; i++) printf("%f\n", ans[i] / 16.0 + 1);

    return 0;
}

Problem B. 空间跳跃

做法一

DFS，期望能通过至少 40% 的数据。

做法二

把构造过程反过来，看成从 $n$ 到 $1$ 的构造，那么操作2,3可以看成 $n=n/2$ 和 $n=3n+1$ 。根据著名的 $3n+1$ 猜想，对于给定的范围，只要 $n$ 为偶数就让 $n=n/2$ 的话，正整数的 $n$ 必然能到达 $1$ ，负整数的 $n$ 必然能落到 $-1,-5,-17$ 。对于负整数或0，让 $n$ 的绝对值足够小后可以使用操作1使其变为正整数，然后再使用操作2,3让 $n$ 变为 $1$ 。经过验证这样构造必然不会超过 $1500$ 步。（实际上大部分仅在 $200$ 到 $300$ 步左右）。期望通过 100%。

代码

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

using ll = long long;

const int N = 10000000;

int main(void) {
//    freopen("sample.in", "r", stdin);

    int q, d, l; scanf("%d%d%d", &q, &d, &l);
    assert(1 <= q && q <= 20);
    assert(1 <= d && d <= 1000000);
    assert(1000 <= l && l <= 1000000);
    int m = 1500;
    for (int i=0; i<q; i++) {
        ll n; scanf("%lld", &n);
        assert(-N <= n && n <= N);
        vector <ll> x;
        x.push_back(n);
        while (n != 0 && n != 1 && n != -1 && n != -5 && n != -17) {
            if (n % 2 == 0) n /= 2;
            else n = 3 * n + 1;
            x.push_back(n);
        }
        while (n <= 0) {
            n += d;
            x.push_back(n);
        }
        while (n != 1) {
            if (n % 2 == 0) n /= 2;
            else n = 3 * n + 1;
            x.push_back(n);
        }
        assert(x.size() <= m);
        printf("%d", x.size()-1); for (int i=x.size()-1; i>=0; i--) printf(" %lld", x[i]);
        printf("\n");
    }

    return 0;
}

Problem C. 快速访问

做法一

暴力计算 $A_i=\sum_{j\in S_i} \operatorname{dis}(i,j)^2$ 。如果暴力求 $\operatorname{dis}(i,j)$ ，复杂度为 $O(n^3)$ ，期望通过 10%。
使用倍增、树链剖分、ST表等数据结构求LCA，可以让复杂度降到 $O(n^2\log(n))$ 或 $O(n^2)$ ，期望通过 40%。

做法二

考虑维护一个集合 $S$ 到任意点 $i$ 的距离和，其中对集合 $S$ 的操作是增/删一个元素，
可以将 $\operatorname{dis}(i,j)$ 拆成 $\operatorname{dis}(i,j) = \operatorname{dep}(i) + \operatorname{dep}(j) - \operatorname{dep}(\operatorname{lca}(i,j))$ 。因此 $\sum_{j\in S} \operatorname{dis}(i,j) = |S|\operatorname{dep}(i)+\sum_{j\in S}\operatorname{dep}(j) - \sum_{j\in S}\operatorname{dep}(\operatorname{lca}(i,j))$
三项中前两项都可以直接维护，最后一项相当于 $S$ 里面的每个 $j$ 对它到根的每个结点都有一个贡献，查询时可以查询 $i$ 到根每个结点当前收集到的贡献，因此可以使用树链剖分进行维护。

对于维护 $\sum_{j\in S}\operatorname{dis}(i,j)^2$ ，我们可以使用类似的方法，将平方项拆成六个部分，分别维护每个部分的和即可。时间复杂度 $O(n\log^2(n))$ 。

代码

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

using ll = long long;

const int maxn = 200200;

vector <int> e[maxn];
int sz[maxn], pa[maxn], dep[maxn], top[maxn], dfn[maxn], tot, id[maxn];

void dfs1(int u, int p) {
    pa[u] = p;
    sz[u] = 1;
    for (auto & v : e[u]) {
        if (v == p) continue;
        dep[v] = dep[u] + 1;
        dfs1(v, u);
        sz[u] += sz[v];
        if (e[u][0] == p || sz[e[u][0]] < sz[v]) {
            swap(e[u][0], v);
        }
    }
}
void dfs2(int u, int p) {
    dfn[++tot] = u;
    id[u] = tot;
    for (auto v : e[u]) {
        if (v == p) continue;
        if (v == e[u][0]) top[v] = top[u];
        else top[v] = v;
        dfs2(v, u);
    }
}

struct seg_tree {
    ll sum[maxn * 4], lazy[maxn * 4];
    void push_down(int l, int r, int rt) {
        if (lazy[rt]) {
            int mid = (l + r) / 2;
            sum[rt<<1] += lazy[rt] * (mid - l + 1);
            lazy[rt<<1] += lazy[rt];
            sum[rt<<1|1] += lazy[rt] * (r - mid);
            lazy[rt<<1|1] += lazy[rt];
            lazy[rt] = 0;
        }
    }
    void add(int L, int R, ll v, int l, int r, int rt) {
        if (L <= l && r <= R) {
            sum[rt] += v * (r - l + 1);
            lazy[rt] += v;
            return ;
        }
        push_down(l, r, rt);
        int mid = (l + r) / 2;
        if (L <= mid) add(L, R, v, l, mid, rt<<1);
        if (mid < R) add(L, R, v, mid+1, r, rt<<1|1);
        sum[rt] = sum[rt<<1] + sum[rt<<1|1];
    }
    ll ask(int L, int R, int l, int r, int rt) {
        if (L <= l && r <= R) return sum[rt];
        push_down(l, r, rt);
        int mid = (l + r) / 2;
        ll ans = 0;
        if (L <= mid) ans += ask(L, R, l, mid, rt<<1);
        if (mid < R) ans += ask(L, R, mid+1, r, rt<<1|1);
        return ans;
    }
} S1, S2;

struct seg_tree2 {
    ll sum[maxn * 4], lazy[maxn * 4], d[maxn * 4];
    void build(int l, int r, int rt) {
        sum[rt] = lazy[rt] = 0;
        if (l == r) {
            d[rt] = 2 * dep[dfn[l]] - 1;
            return ;
        }
        int mid = (l + r) / 2;
        build(l, mid, rt<<1);
        build(mid+1, r, rt<<1|1);
        d[rt] = d[rt<<1] + d[rt<<1|1];
    }
    void push_down(int rt) {
        if (lazy[rt]) {
            sum[rt<<1] += lazy[rt] * d[rt<<1];
            lazy[rt<<1] += lazy[rt];
            sum[rt<<1|1] += lazy[rt] * d[rt<<1|1];
            lazy[rt<<1|1] += lazy[rt];
            lazy[rt] = 0;
        }
    }
    void add(int L, int R, ll v, int l, int r, int rt) {
        if (L <= l && r <= R) {
            sum[rt] += v * d[rt];
            lazy[rt] += v;
            return ;
        }
        push_down(rt);
        int mid = (l + r) / 2;
        if (L <= mid) add(L, R, v, l, mid, rt<<1);
        if (mid < R) add(L, R, v, mid+1, r, rt<<1|1);
        sum[rt] = sum[rt<<1] + sum[rt<<1|1];
    }
    ll ask(int L, int R, int l, int r, int rt) {
        if (L <= l && r <= R) return sum[rt];
        push_down(rt);
        int mid = (l + r) / 2;
        ll ans = 0;
        if (L <= mid) ans += ask(L, R, l, mid, rt<<1);
        if (mid < R) ans += ask(L, R, mid+1, r, rt<<1|1);
        return ans;
    }
} S3;
struct solver {
    int n, num;
    ll sum1, sum2;
    void init(int _n) {
        n = _n + 1;
        for (int i=0; i<=4*n; i++) {
            S1.sum[i] = S1.lazy[i] = S2.sum[i] = S2.lazy[i] = 0;
        }
        S3.build(1, n, 1);
    }
    void add(int u, int val) {
        num += val;
        sum1 += val * dep[u];
        sum2 += val * (ll)dep[u] * dep[u];
        int ou = u;
        for ( ; ~u; ) {
            S1.add(id[top[u]], id[u], val, 1, n, 1);
            S2.add(id[top[u]], id[u], val * dep[ou], 1, n, 1);
            S3.add(id[top[u]], id[u], val, 1, n, 1);
            u = pa[top[u]];
        }
    }

    ll query(int u) {
        ll ans = num * (ll)dep[u] * dep[u] + sum2 + 2ll * dep[u] * sum1;
        int ou = u;
        ll tmp1 = 0, tmp2 = 0, tmp3 = 0;
        for ( ; ~u; ) {
            tmp1 += S1.ask(id[top[u]], id[u], 1, n, 1);
            tmp2 += S2.ask(id[top[u]], id[u], 1, n, 1);
            tmp3 += S3.ask(id[top[u]], id[u], 1, n, 1);
            u = pa[top[u]];
        }
        ans -= 4ll * dep[ou] * tmp1;
        ans -= 4ll * tmp2;
        ans += 4ll * tmp3;
        return ans;
    }
} sol;


int main(void) {
//    freopen("sample.in", "r", stdin);

    int n, k; scanf("%d%d", &n, &k);
    assert(1 <= k && k <= n && n <= 200000);
    for (int i=0; i<n; i++) {
        int u, v; scanf("%d%d", &u, &v);
        assert(0 <= u && u <= n);
        assert(0 <= v && v <= n);
        e[u].push_back(v);
        e[v].push_back(u);
    }

    dep[0] = 1;
    dfs1(0, -1);
    dfs2(0, -1);

    sol.init(n);

    sol.add(0, 1);

    for (int i=1; i<=n; i++) {
        if (i-k-1 >= 1) sol.add(i-k-1, -1);

        ll ans = sol.query(i);
        printf("%lld\n", ans);

        sol.add(i, 1);
    }

    return 0;
}

Problem D. 门童

做法一

$dp(i,j,mask)$ 表示时刻 $i$ 距离门口 $j$ 的最大开心度，接待了的集合为 $mask$ 。大力DP，复杂度为 $O(T\cdot L\cdot 2^n)$ ，其中 $T=\max t_k+p_k$ 。期望通过 10%。

做法二

注意到 $x_{01}+x_{10} \ge 2x_{00}$ ，所以不可能出现还没走到沙发又折返回到的门口的情况。如果离开门口再回来，一定是在沙发上休息了一段时间。令 $dp(i)$ 表示时刻 $i$ 在门口，且接待完所有 $t_k\leq i$ 的选手的最大开心度，转移考虑上次在门口的最后时刻 $j$ ，则有两种可能性，一种是从时刻 $j$ 开始从门口往沙发走，时间段 $[j+L,i-L]$ 在沙发，时刻 $i-L$ 开始从沙发往门口走，开心度变化为 $-(x_{01}+x_{10})L+x_{11}(i-j-2L)$ 。另一种是从时刻 $j$ 到时刻 $i$ 一直在门口，变化为 $-x_{00}(i-j)$ 。时刻 $i$ 接待的选手是所有 $j<t_k\leq i$ 的选手。暴力转移复杂度为 $O(T^2n)$ ，可以用一些前缀和优化，复杂度为 $O(T^2)$ ，其中 $T=\max t_k+p_k$ 。分别期望通过 30% 和 50%。

做法三

注意到，离开门口的时刻只会在时刻 $0$ 、 $t_k$ 或 $t_k+p_k\ (1\leq k\leq n)$ ，因为如果在时刻 $T$ 离开门口，那么让 $T$ 前移到上一个为 $0$ 、 $t_k$ 或 $t_k+p_k\ (1\leq k\leq n)$ 的时刻，并不会影响选手的接待，且到沙发上休息的时间会更长，得到的开心度只会更多。因此将时间离散化成 $O(n)$ 个关键时刻，得到 $O(n^2)$ 的做法。期望通过 70%。

做法四

最终得到的DP方程形如： $dp(i) = \max\left\{ \max_{L_i\leq j\leq R_i} \left( dp(j) + A_i+B_j+t_iC_j \right), dp(i-1)+...\right\}$
那么可以使用李超线段树，维护一些 $y=C_jx+B_j+dp(j)$ 的线段。复杂度为 $O(n\log^2(n))$ 。考虑到实际上 $L_i,R_i,C_i$ 都是关于 $i$ 不降的，因此也可以使用一些单调队列等数据结构维护这些线段，复杂度为 $O(n\log(n))$ 或 $O(n)$ ，取决于具体的实现。考虑到后面的优化只是一些繁琐而机械的工作，因此上述的三种复杂度均期望通过 100%。

代码

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

using ll = long long;

const ll inf = 0x3f3f3f3f3f3f3f3fll;
const int maxn = 202020;

int t[maxn], a[maxn], b[maxn], c[maxn], L[maxn];
ll N[maxn], K[maxn], B[maxn], dp[maxn];

int left_i[maxn], right_i[maxn];

struct lichao_tree {
    struct line {
        ll k, b;
    } tr[maxn * 4];

    void init(int n) {
        for (int i=0; i<=4*n; i++) tr[i].k = 0, tr[i].b = -inf;
    }

    void add(int L, int R, ll k, ll b, int l, int r, int rt) {
        if (L <= l && r <= R) {
            int mid = (l + r) / 2;
            bool bl = (k * t[l] + b) <= (tr[rt].k * t[l] + tr[rt].b);
            bool br = (k * t[r] + b) <= (tr[rt].k * t[r] + tr[rt].b);
            if (bl && br) return ;
            else if (!bl && !br) { tr[rt] = (line){k, b}; return ; }
            else {
                bool bm = (k * t[mid] + b) <= (tr[rt].k * t[mid] + tr[rt].b);
                line li = (line){k, b};
                if (!bm) li = tr[rt], tr[rt] = (line){k, b};

                if ((!bm && bl) || (bm && !bl)) add(L, R, li.k, li.b, l, mid, rt<<1);
                else add(L, R, li.k, li.b, mid+1, r, rt<<1|1);
            }
            return ;
        }
        int mid = (l + r) / 2;
        if (L <= mid) add(L, R, k, b, l, mid, rt<<1);
        if (mid < R) add(L, R, k, b, mid+1, r, rt<<1|1);
    }

    ll ask(int p, int l, int r, int rt) {
        if (l == r) return tr[rt].k * t[p] + tr[rt].b;
        int mid = (l + r) / 2;
        ll ans = tr[rt].k * t[p] + tr[rt].b;
        if (p <= mid) ans = max(ans, ask(p, l, mid, rt<<1));
        else ans = max(ans, ask(p, mid+1, r, rt<<1|1));
        return ans;
    }
} S1;

int main(void) {
    int tot = 0;
    int n, l; scanf("%d%d", &n, &l);
    assert(1 <= n && n <= 100000);
    assert(1 <= l && l <= (int)1e9);
    int x[4];
    for (int i=0; i<4; i++) {
        scanf("%d", &x[i]);
        assert(1 <= x[i] && x[i] <= 200);
    }
    assert(x[1] + x[2] >= 2 * x[0]);

    t[tot++] = 0;
    for (int i=1; i<=n; i++) {
        scanf("%d%d%d", &a[i], &b[i], &c[i]);
        assert(1 <= a[i] && a[i] <= (int)1e9);
        assert(1 <= b[i] && b[i] <= (int)1e9);
        assert(1 <= c[i] && c[i] <= 200);
        t[tot++] = a[i];
        t[tot++] = a[i] + b[i];
    }
    sort(t, t+tot);
    tot = unique(t, t+tot) - t;

    for (int i=1; i<=n; i++) {
        int l = lower_bound(t, t+tot, a[i]) - t;
        int r = lower_bound(t, t+tot, a[i] + b[i]) - t;
        L[r] = max(L[r], l);
        N[l]++;
        K[l] += c[i];
        B[l] += c[i] * ((ll)a[i] + b[i]);
    }

    for (int i=1; i<tot; i++) {
        L[i] = max(L[i], L[i-1]);
        N[i] += N[i-1];
        K[i] += K[i-1];
        B[i] += B[i-1];
    }

    int las = tot-1; for ( ; N[las] == n; las--) ;

    ll ans = -inf;
    int left_t = 0, right_t = -1;

    memset(left_i, 0x3f, sizeof(left_i));

    for (int i=1; i<tot; i++) {
        while (right_t+1 < i && right_t+1 <= las) {
            right_t++;
            left_i[right_t] = i;
        }

        while (left_t < L[i-1]) {
            right_i[left_t] = i - 1;
            left_t++;
        }

    }

    while (left_t <= right_t) right_i[left_t] = tot - 1, left_t++;

    S1.init(tot);

    if (left_i[0] <= right_i[0]) {
        S1.add(left_i[0], right_i[0], K[0], dp[0]-B[0]-x[3]*(ll)t[0], 0, tot-1, 1);
    }

    for (int i=1; i<tot; i++) {

        dp[i] = max(S1.ask(i, 0, tot-1, 1) + B[i] - K[i]*t[i] + x[3]*(ll)t[i] - (x[1]+x[2]+2*x[3])*(ll)l,
                    dp[i-1] + B[i] - B[i-1] - (K[i] - K[i-1]) * t[i] - x[0] * (ll)(t[i] - t[i-1]));

        if (left_i[i] <= right_i[i])
            S1.add(left_i[i], right_i[i], K[i], dp[i]-B[i]-x[3]*(ll)t[i], 0, tot-1, 1);

        if (N[i] == n) ans = max(ans, dp[i]);
    }

    printf("%lld\n", ans);

    return 0;
}

写在最后

最后还是讲讲出题的故事。这四道题让我感到最满意的一点是都有一定的现实背景，而不是对着某个OI知识点生造出来的。其中A题的灵感来自于codeforces的FST，是一道小清新的概率期望题。一开始考虑过题目数更大的做法，但是只会指数级别的做法，于是就把题目数定为2而放到了第一题。
B题的灵感自然是来自于3x+1问题，当时朦胧的产生了用这个造构造题的想法，但是没想好怎么把它隐藏得更好，之后尝试了多种条件，增加了题目里面的操作1，本来操作1里面是没有关于min(|n|,|n-d|)<=l的限制的，但发现没有限制根本卡不了暴力dfs，加上没太多时间了（之前咕了太久），所以就只能增加上这个限制来卡dfs。
C题的灵感是windows 10的文件夹系统的快速访问功能，一开始想求min(dis)，然而感觉太点分板子了说不定有原题，于是改成了求sum(dis^2)（虽然好像并没有改变这题的板子本质，于是这题算是给数据结构选手送福利了）。
D题是 playf(playf)当志愿者时候迸发的idea，（据说是他当门童的真实感受），曾经出了一个简单版给校赛，不出意外的并没有人通过（甚至没有提交），于是我们重写了题面并把数据加强到 $10^5$ 放到了提高D，造这题数据也很痛苦，因为我发现题目性质太优秀了，导致存在很多奇怪的乱搞都能通过，最后造了40个点防止乱搞AC。
总的来说，作为出题人，我对这场的题目还是比较满意的，希望选手们也能从比赛中感受到快乐，或者学习到一些新知识>v<