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

Problem A. 最终测试

做法一

枚举所有可能性，一共 种。对于每种可能性，对选手排序得到他们的排名。
复杂度 。期望通过 10%。

做法二

假设第 位选手的最终总分数为 ，考虑对于第 位选手，他的排名期望为 。由于 ，可以 求 ，因此得到一个复杂度为 的做法。期望通过 40%。

做法三

在做法二的基础上，推导得到：
因此我们可以将所有 进行排序，就可以二分 的得到最里面的求和。总复杂度为 。期望通过 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% 的数据。

做法二

把构造过程反过来，看成从 到 的构造，那么操作2,3可以看成 和 。根据著名的 猜想，对于给定的范围，只要 为偶数就让 的话，正整数的 必然能到达 ，负整数的 必然能落到 。对于负整数或0，让 的绝对值足够小后可以使用操作1使其变为正整数，然后再使用操作2,3让 变为 。经过验证这样构造必然不会超过 步。（实际上大部分仅在 到 步左右）。期望通过 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. 快速访问

做法一

暴力计算 。如果暴力求 ，复杂度为 ，期望通过 10%。
使用倍增、树链剖分、ST表等数据结构求LCA，可以让复杂度降到 或 ，期望通过 40%。

做法二

考虑维护一个集合 到任意点 的距离和，其中对集合 的操作是增/删一个元素，
可以将 拆成 。因此
三项中前两项都可以直接维护，最后一项相当于 里面的每个 对它到根的每个结点都有一个贡献，查询时可以查询 到根每个结点当前收集到的贡献，因此可以使用树链剖分进行维护。

对于维护 ，我们可以使用类似的方法，将平方项拆成六个部分，分别维护每个部分的和即可。时间复杂度 。

代码

#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，复杂度为 ，其中 。期望通过 10%。

做法二

注意到 ，所以不可能出现还没走到沙发又折返回到的门口的情况。如果离开门口再回来，一定是在沙发上休息了一段时间。令 表示时刻 在门口，且接待完所有 的选手的最大开心度，转移考虑上次在门口的最后时刻 ，则有两种可能性，一种是从时刻 开始从门口往沙发走，时间段 在沙发，时刻 开始从沙发往门口走，开心度变化为 。另一种是从时刻 到时刻 一直在门口，变化为 。时刻 接待的选手是所有 的选手。暴力转移复杂度为 ，可以用一些前缀和优化，复杂度为 ，其中 。分别期望通过 30% 和 50%。

做法三

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

做法四

最终得到的DP方程形如：
那么可以使用李超线段树，维护一些 的线段。复杂度为 。考虑到实际上 都是关于 不降的，因此也可以使用一些单调队列等数据结构维护这些线段，复杂度为 或 ，取决于具体的实现。考虑到后面的优化只是一些繁琐而机械的工作，因此上述的三种复杂度均期望通过 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，（据说是他当门童的真实感受），曾经出了一个简单版给校赛，不出意外的并没有人通过（甚至没有提交），于是我们重写了题面并把数据加强到 放到了提高D，造这题数据也很痛苦，因为我发现题目性质太优秀了，导致存在很多奇怪的乱搞都能通过，最后造了40个点防止乱搞AC。
总的来说，作为出题人，我对这场的题目还是比较满意的，希望选手们也能从比赛中感受到快乐，或者学习到一些新知识>v<

全部评论
确实很 CS😣P
4 回复 分享
发布于 2021-10-11 22:32
最后一题为什么我直接斜率优化会 WA 啊，两个指针都是递增的啊！
点赞 回复 分享
发布于 2021-10-12 12:18
请问T1的P,F,G都是什么意思？
点赞 回复 分享
发布于 2021-10-12 18:21
T3的deep[j]*deep[lca(i,j)]怎么维护？？？
点赞 回复 分享
发布于 2021-10-12 22:02
T3的deep[lca(i,j)]^2怎么维护 ?
点赞 回复 分享
发布于 2021-10-13 08:49
我的T1的期望是按照：每个人第kth的排名的概率的加权平均数，感觉这就是按照定义来的，可是他和您的题解中的是等价的吗，求解释
点赞 回复 分享
发布于 2021-10-13 16:36
问个问题，T3有没有数据卡KDT做法啊，虽然这东西最好也是根号的
点赞 回复 分享
发布于 2021-10-14 15:02
请问T4有没有详细的单调队列的做法或题解
点赞 回复 分享
发布于 2022-01-17 23:21

相关推荐

11-20 17:12
西安电子科技大学 Java
面试官：禁用Cookie后Session还能用吗？
作者：Java中文社群原文：***********************************Cookie&nbsp;和&nbsp;Session&nbsp;是&nbsp;Web&nbsp;应用程序中用于保持用户状态的两种常见机制，它们之间既有联系也有区别。Cookie&nbsp;是由服务器在&nbsp;HTTP&nbsp;响应中发送给客户端（通常是浏览器）的一小段数据。客户端将这些信息保存在本地，并在后续的请求中自动将其发送回服务器。而&nbsp;Session&nbsp;是在服务器端创建的一种机制，用于跟踪用户的会话状态。服务器会给每个用户分配一个唯一的会话&nbsp;ID，并将该&nbsp;ID&nbsp;通过&nbsp;Cookie&nbsp;或其他方式传递给客户端。客户端随后在请求时携带会话&nbsp;ID，服务器根据这个&nbsp;ID&nbsp;从内存...
点赞 评论 收藏
分享
11-17 21:13
广西民族大学 APP推广
点赞 评论 收藏
分享
10-07 23:57
已编辑
电子科技大学 Java
说给的多，没说给这么多呀
八街九陌：博士？客户端？开发？啊？
点赞 评论 收藏
分享
11-21 15:10
华南农业大学 运营
点赞 评论 收藏
分享
9 收藏 评论
分享

全站热榜

正在热议
# 25届秋招总结 #
248071次浏览 2013人参与
# 学历or实习经历，哪个更重要 #
41119次浏览 300人参与
# 北方华创开奖 #
22819次浏览 259人参与
# 地方国企笔面经互助 #
2549次浏览 6人参与
# 你最想要的公司福利是？ #
40034次浏览 126人参与
# 选完offer后，你后悔学本专业吗 #
10487次浏览 75人参与
# 面试题刺客退退退 #
137191次浏览 2092人参与
# 国企/银行/研究所公司爆料 #
89741次浏览 412人参与
# 应届生被毁约被毁意向了怎么办 #
27153次浏览 238人参与
# 一觉醒来，我觉醒了超级打工人系统 #
2908次浏览 35人参与
# 机械应届生薪资要多少才合适？ #
12397次浏览 60人参与
# 查收我的offer竞争力报告 #
16831次浏览 228人参与
# 校招入职后的感受 #
156966次浏览 1961人参与
# 你觉得第一学历对求职有影响吗？ #
14894次浏览 121人参与
# 没有实习经历，还有机会进大厂吗 #
805141次浏览 13814人参与
# 我的工作日记 #
21206次浏览 270人参与
# 不给转正的实习，你还去吗 #
1517077次浏览 16968人参与
# 寒假躺平还是提前实习 #
58447次浏览 438人参与
# 总结:哪家公司面试体验感最差 #
25767次浏览 129人参与
# 秋招OC许愿 #
226684次浏览 1872人参与
# 如何写一份好简历 #
602236次浏览 8442人参与
牛客网
牛客企业服务