竞赛讨论区 > 【题解】2021牛客暑期多校训练营5
头像
王清楚
发布于 2022-07-26 16:16
+ 关注

【题解】2021牛客暑期多校训练营5

B

首先，如果要花费 的代价知道黑球数量，那么只会在最开始的时候使用且仅使用一次。所以策略有以下两种情况：

不花费 的代价，把所有的球打开代价是 。

花费 的代价知道所有黑球数量。无论怎么开球，球的颜色都相当于事随机的。那么不妨将 从小到大排序挨着开，知道有一个后缀是同一个颜色就不需要开了。代价是 。因为一个球不开当且仅当后面颜色都和它相等。

然后两者取最小值输出。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
int n;
double C, w[N], sum, f = 1;
int main() {
    scanf("%d%lf", &n, &C);

    for (int i = 1; i <= n; i++) {
        scanf("%lf", &w[i]);
        sum += w[i];
    }

    sort(w + 1, w + 1 + n);

    for (int i = n; i; i--)
        C += (1 - f) * w[i], f /= 2;

    printf("%f\n", min(C, sum));
    return 0;
}

C

对于 球赛制，最多进行 场球局。因为有 ，所以如果快速求出一局游戏的胜负，就可以解决这个问题了。

记录一个前缀和 表示前 个有多少 。记录 表示第 个 在哪里。

当从位置 开始一场 球赛制的游戏时，先找到 个 以后的位置，并取 。接下来有两种情况：

，游戏直接结束。

否则，如果差值为 , 看下一局是否能分出胜负，如果不能差值将会变成 。此时可以预处理一个 表示从 开始，第一次 的位置在哪里。转移有 。总时间复杂度 。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1000010;
const int p = 998244353;
char s[N];
int sumw[N], suml[N];
int posw[N * 2], posl[N * 2], B[N];
int n;
signed main() {
    cin >> n;
    scanf("%s", s + 1);
    int k1 = 1, k2 = 1;

    for (int i = 1; i <= n * 2; i++)
        posw[i] = posl[i] = n + 1;

    for (int i = 1; i <= n; i++) {
        sumw[i] = sumw[i - 1] + (s[i] == 'W');
        suml[i] = suml[i - 1] + (s[i] == 'L');

        if (s[i] == 'W')
            posw[k1++] = i;
        else
            posl[k2++] = i;
    }

    B[n + 1] = n + 1;
    B[n] = n + 1;

    for (int i = n - 1; i >= 1; i--) {
        if (s[i] == s[i + 1])
            B[i] = i + 1;
        else
            B[i] = B[i + 2];
    }

    int ans = 0;

    for (int k = 1, a = 1; k <= n; k++, a = a * (n + 1) % p) {
        int cnt = 0;

        for (int i = 1; i <= n; i++) {
            int a = posw[sumw[i - 1] + k];
            int b = posl[suml[i - 1] + k];
            int t = min(a, b);
            int sw = sumw[t] - sumw[i - 1];
            int sl = suml[t] - suml[i - 1];

            if (abs(sw - sl) == 1)
                t = B[t];

            if (t <= n && sumw[t] - sumw[i - 1] > suml[t] - suml[i - 1])
                cnt++;

            i = t;
        }

        ans = (cnt * a + ans) % p;
    }

    cout << ans << endl;
    return 0;
}

D

枚举 的位置满足 ，前面的方案数即公共子序列的方案数，可以设 表示 前 个和 前 个中公共子序列的个数，在 的时间复杂度内解决。 后面可以任选，枚举长度 方案数为：
$nAmB$ 剩下可选位置数。

考虑组合意义，把 替换为 ，整个式子等价于在 个球里选 个球。因为对于一种 的方案，若前 个球中选择了 个，就对应于 里的一种方案。所以是一一对应的。

当然也可以当 满足 的时候贡献到 上， 就可以任意匹配，最后答案直接输出

时间复杂度都是 。

#include <bits/stdc++.h>
using namespace std;
const int p = 1e9 + 7;
const int N = 5e3 + 9;
char a[N], b[N];
int f[N][N], g[N][N];
signed main() {
    cin >> a >> b;
    int n = strlen(a), m = strlen(b);

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (a[i - 1] == b[j - 1])
                f[i][j] = (f[i - 1][j] + f[i][j - 1] + 1) % p;
            else
                f[i][j] = (1ll * f[i - 1][j] + f[i][j - 1] + p - f[i - 1][j - 1]) % p;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (a[i - 1] < b[j - 1])
                g[i][j] = (1ll * g[i - 1][j] + g[i][j - 1] + f[i - 1][j - 1] + 1) % p;
            else
                g[i][j] = (g[i - 1][j] + g[i][j - 1]) % p;

    printf("%d\n", g[n][m]);
    return 0;
}

E

因为 很小，考虑对于所有 在 的复杂度内求出每个点的答案。

考虑一个点 从儿子 继承过来。对于 与 的边的操作类型进行分类讨论。

设 表示点 的 的答案

  • 边的操作是

    • 求 的答案：设 表示 子树内第 个点（具体是哪个点不重要）到 的权值。那么点 的答案就是 ，点 的答案就是

    • 求 的答案： ，点 的答案为 。

    • 求 的答案：。点 的答案就是 。不妨按位考虑，把 二进制下为 的分成一部分，为 的分成一部分。

      若 第 位是 ，那么贡献就是 。其中 表示 二进制下第 位是 还是 .。

      若 第 位是 ，那么贡献是 ，这个和子树大小奇偶性有关。把这些加起来就是

最后把每个子树的答案合并起来即可。 其他的操作类比可得。转移复杂度 ，总时间复杂度就是 。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 9;
int n, q;
int v[N], dp[N][102][3];
signed sz[N];
vector<pair<signed, signed>>e[N];
void dfs(int x, int fa, int d) {
    sz[x] = 1;
    int num = v[x] + x * d;
    dp[x][d][1] = ~0ll;

    for (int i = 0; i < e[x].size(); i++) {
        int to = e[x][i].first, op = e[x][i].second;
        int w = v[to] + to * d;
        dfs(to, x, d);
        sz[x] += sz[to];

        if (op == 0) {
            dp[x][d][0] |= dp[to][d][0] | w | num;
            dp[x][d][1] &= dp[to][d][1] & w | num;
            dp[x][d][2] ^= (sz[to] % 2) ? ((dp[to][d][2] ^ w) | num) : ((dp[to][d][2])^w) & (~num);
        }

        if (op == 1) {
            dp[x][d][0] |= (dp[to][d][0] | w)&num;
            dp[x][d][1] &= dp[to][d][1] & w & num;
            dp[x][d][2] ^= (dp[to][d][2] ^ w)&num;
        }

        if (op == 2) {
            dp[x][d][0] |= ((dp[to][d][0] | w) & (~num) | ((~(dp[to][d][1] & w))&num));
            dp[x][d][1] &= ((~(dp[to][d][0] | w))&num | ((dp[to][d][1] & w) & (~num)));
            dp[x][d][2] ^= (sz[to] % 2) ? (dp[to][d][2] ^ w ^ num) : (dp[to][d][2] ^ w);
        }
    }
}
signed main() {
    scanf("%d%d", &n, &q);

    for (int i = 1; i <= n; i++)
        scanf("%lld", &v[i]);

    for (int i = 2; i <= n; i++) {
        int fa, op;
        scanf("%d%d", &fa, &op);
        e[fa].push_back(make_pair(i, op));
    }

    for (int i = 0; i <= 100; i++)
        dfs(1, 0, i);

    while (q--) {
        int d, x;
        scanf("%d%d", &d, &x);
        printf("%lld %lld %lld\n", dp[x][d][0], dp[x][d][1], dp[x][d][2]);
    }
}

G

首先 枚举 的某种因数由 贡献还是由 贡献。但是最终得到的满足条件的 可能小于 ，考虑暴力搜索答案，若搜出来的数大于 就可以贡献进去。 同理。但是发现若存在一种状态 不能大于 ，乘上其他质因子大于 了，但是质因数集合变成了 ，这样就无法贡献到 。所以最后要贡献到子集去，这部分时间复杂度是 。

#include <bits/stdc++.h>
#define ll __int128
using namespace std;
const int N = (1 << 18);
ll A[N], B[N];
ll n, p[19], q[19], a, b;
ll read() {
    ll x = 0, f = 0;
    char ch = getchar();

    while (!isdigit(ch)) {
        f |= (ch == '-');
        ch = getchar();
    }

    while (isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }

    return x;
}
void print(ll x) {
    if (x >= 10)
        print(x / 10);

    putchar(x % 10 + '0');
}
void dfs(ll d, ll S, ll v) {
    if (d >= n) {
        if (v >= a)
            A[S] = min(A[S], v);

        if (v >= b)
            B[S] = min(B[S], v);

        return ;
    }

    dfs(d + 1, S, v);

    for (int i = 1; i <= q[d]; i++) {
        v *= p[d];

        if (i == q[d])
            S |= (1 << d);

        dfs(d + 1, S, v);
    }
}
int main() {
    n = read();

    for (int i = 0; i < n; i++)
        p[i] = read(), q[i] = read();

    a = read();
    b = read();
    ll inf = 1e35;

    for (int i = 0; i < (1 << n); i++)
        A[i] = B[i] = inf;

    dfs(0, 0, 1);

    for (int i = 0; i < n; i++)
        for (int j = (1 << n) - 1; ~j; j--) {
            if ((1 << i)&j)
                continue;

            A[j] = min(A[j], A[j ^ (1 << i)]);
            B[j] = min(B[j], B[j ^ (1 << i)]);
        }

    ll ans = inf;

    for (int i = 0; i < (1 << n); i++)
        ans = min(ans, A[i] + B[((1 << n) - 1)^i]);

    print(ans - a - b);
}

H

考虑构造如下矩阵
$a_{i,j}=(i+\lfloor\frac{j}{2}\rfloor)%20$ 标号）

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++)
            cout << ((j / 2 + i) & 1);

        puts("");
    }

    return 0;
}

I

如果在已有的区间里减去一个数，发现需要维护所有连续段的长度然后取 ，这样需要 的复杂度。但是如果考虑每次加入一个数，只需要把新加的值左右两边的连续段合并起来得到新的长度，和答案取 即可 更新。那么考虑使用不删除莫队。具体的，对于一个块，左端点停留在 上，即左端点在这个块里的最大值。左端点在同一个块的询问按照右端点从小往大排序。每次左右端点增加到需要的位置，然后只用栈还原即可。时间复杂度 。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
const int p = 998244353;
int n, m, S, tmp, res;
int a[N], pre[N], nt[N], vis[N];
long long p2[N];
long long ans[N];
int sta[N], top;
struct node {
    int l, r, k, blo, id;
    bool operator<(const node &a)const {
        return blo == a.blo ? r < a.r : blo < a.blo;
    }
} q[N];
void init() {
    res = tmp = 0;

    for (int i = 1; i <= n; ++i) {
        vis[i] = 0;
        pre[i] = i - 1;
        nt[i] = i + 1;
    }

    pre[n + 1] = n;
    nt[n + 1] = n + 1;
}
void clear() {
    tmp = res;

    while (top) {
        int v = sta[top--];
        --vis[v];

        if (!vis[v]) {
            pre[nt[v]] = v;
            nt[pre[v]] = v;
        }
    }
}
void add(int x, int f) {
    x = a[x];
    ++vis[x];

    if (vis[x] == 1) {
        pre[nt[x]] = pre[x];
        nt[pre[x]] = nt[x];
        tmp = max(tmp, nt[x] - pre[x] - 1);
    }

    if (!f)
        res = tmp;
    else
        sta[++top] = x;
}
int main() {
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);

    S = (int)sqrt(n);
    p2[0] = 1;

    for (int i = 1; i <= n; i++)
        p2[i] = 1ll * p2[i - 1] * (n + 1) % p;

    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &q[i].l, &q[i].r, &q[i].k);
        q[i].blo = (q[i].l - 1) / S + 1;
        q[i].id = i;
    }

    sort(q + 1, q + m + 1);
    int mx, l, r;

    for (int i = 1; i <= m; ++i) {
        if (q[i].blo > q[i - 1].blo) {
            init();
            mx = q[i].blo * S;
            l = mx, r = mx - 1;
        }

        if (q[i].r < mx) {
            for (int j = q[i].l; j <= q[i].r; j++)
                add(j, 1);

            ans[q[i].id] = tmp;

            for (int j = 1; j < q[i].k; j++) {
                add(q[i].l - j, 1);
                add(q[i].r + j, 1);
                ans[q[i].id] = (ans[q[i].id] + p2[j] * tmp % p) % p;
            }

            clear();
        } else {
            while (r < q[i].r)
                add(++r, 0);

            while (l > q[i].l)
                add(--l, 1);

            ans[q[i].id] = tmp;

            for (int j = 1; j < q[i].k; ++j) {
                add(q[i].l - j, 1);
                add(q[i].r + j, 1);
                ans[q[i].id] = (ans[q[i].id] + p2[j] * tmp % p) % p;
            }

            clear();
            l = mx;
        }
    }

    for (int i = 1; i <= m; ++i)
        printf("%lld\n", ans[i]);

    return 0;
}

J

首先，每一时刻肯定都不会闲着。于是在 时刻就可以打捞所有珠宝。但是对于每个珠宝，在不同时刻打捞的代价是会变化的。若在时刻 和物品 之间连一条边，这就变成了二分图最小权完美匹配的问题。用 算法即可在 的时间复杂度内解决。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 6e2 + 50;
const int inf = 1e12;
int n, m;
int e[N][N];
int mb[N], vb[N], ka[N], kb[N], p[N], c[N];
int qf, qb, q[N];
void Bfs(int u) {
    int a, v = 0, vl = 0, d;

    for (int i = 1; i <= n; i++)
        p[i] = 0, c[i] = inf;

    mb[v] = u;

    do {
        a = mb[v], d = inf, vb[v] = 1;

        for (int b = 1; b <= n; b++)
            if (!vb[b]) {
                if (c[b] > ka[a] + kb[b] - e[a][b])
                    c[b] = ka[a] + kb[b] - e[a][b], p[b] = v;

                if (c[b] < d)
                    d = c[b], vl = b;
            }

        for (int b = 0; b <= n; b++)
            if (vb[b])
                ka[mb[b]] -= d, kb[b] += d;
            else
                c[b] -= d;

        v = vl;
    } while (mb[v]);

    while (v)
        mb[v] = mb[p[v]], v = p[v];
}
int KM() {
    for (int i = 1; i <= n; i++)
        mb[i] = ka[i] = kb[i] = 0;

    for (int a = 1; a <= n; a++) {
        for (int b = 1; b <= n; b++)
            vb[b] = 0;

        Bfs(a);
    }

    int res = 0;

    for (int b = 1; b <= n; b++)
        res += e[mb[b]][b];

    return res;
}
int x[N], y[N], z[N], v[N], ans;
signed main() {
    scanf("%d", &n);

    for (int i = 1; i <= n; i++) {
        scanf("%lld%lld%lld%lld", &x[i], &y[i], &z[i], &v[i]);
        ans += x[i] * x[i] + y[i] * y[i] + z[i] * z[i];
    }

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            e[i][j] = -v[i] * v[i] * (j - 1) * (j - 1) - 2 * v[i] * z[i] * (j - 1);

    printf("%lld\n", ans - KM());
}

K

若固定左端点，发现随着右端点的增大， 也会单调不降。于是考虑双指针，每次 往右动一格， 找到最小的合法的位置。现在需要快速计算区间最值，用 st 表即可。时间复杂度 

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 9;
int n, m, k, a[N], mn[N], mx[N];
signed main() {

    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);

    while (m--) {
        scanf("%lld", &k);
        int f = 1, r = 0, ql = 1, qr = 0;
        int ans = 0;

        for (int i = 1, l = 1; i <= n; ++i) {
            while (f <= r && a[i] >= a[mx[r]])
                --r;

            mx[++r] = i;

            while (ql <= qr && a[i] <= a[mn[qr]])
                --qr;

            mn[++qr] = i;

            while (a[mx[f]] - a[mn[ql]] > k) {
                ans += n - i + 1, ++l;

                if (mx[f] < l)
                    ++f;

                if (mn[ql] < l)
                    ++ql;
            }
        }

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

    return 0;
}
2024最新求职资料大礼包领取
真题
历年笔试真题附答案
度小满校招数据库工程师第2批
掌阅科技2023年秋招大数据岗笔试真题
神策数据秋招技术岗3卷
全部 >
面经
面试常考问题整理
0926腾讯音乐笔试题解
管理类双非硕的23秋招记录＆反思
2022考研失败春招选手的群面攻略（适用于菜鸡互啄型）
全部 >
内推
员工内推码获取
拼多多暑期实习
携程内推携程内推码
【美团】校招社招内推，所有岗位，进度可查，消息必回
全部 >
大家都在关注
校招日程表 笔试日历 ai模拟面试 面试宝典 剑指offer 知识点专项练习

全部评论

(0) 回帖
加载中...
话题 回帖
返回全部帖子

本文相关内容

等你来战

查看全部

热门推荐

牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”