竞赛讨论区 > 2021牛客OI赛前集训营-提高组题解(第四场)

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

头像
emofunx
编辑于 2021-10-12 13:47:54 APP内打开
赞 8 | 收藏 0 | 回复7 | 浏览781

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<

7条回帖

回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐