竞赛讨论区 > 【题解】"蔚来杯"2022牛客暑期多校训练营9
头像
王清楚
发布于 2022-10-19 15:29 北京
+ 关注

【题解】"蔚来杯"2022牛客暑期多校训练营9 精

A

令 表示以 为左端点，最小的合法右端点。那么有 。考虑反证法，若 ，那么区间 包含 。所以 也合法，那么不满足 是最小的合法右端点。

于是双指针扫描，用 数组记录每个数字出现次数。时间复杂度 。

#include <bits/stdc++.h>
using namespace std;
long long n, m, s[100100], v[100100], cnt, ans;
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> s[i];
    for (int l = 1, r = 1; r <= n; r++) {
        if (v[s[r]] == 0)
            cnt++;
        v[s[r]]++;
        while (v[s[l]] > 1) v[s[l++]]--;
        if (cnt == m)
            ans += l;
    }
    cout << ans << endl; return 0;
}

B

表示花费 步跳到 的概率。转移有 ，其中 。发现可转移到的点是一个区间，那么用差分后用前缀和优化。最后答案是 。时间复杂度 。

#include <stdio.h>
const int N = 8005;
int a[N], n;
const long long mod = 998244353;
long long f[N], g[N], inv[N], ans;
int main() {
    scanf("%d", &n);
    inv[1] = 1;
    for (int i = 2; i <= n; ++i) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    for (int i = 1; i < n; ++i) scanf("%d", &a[i]);
    g[1] = 1;
    for (int t = 1, i; t < n; ++t) {
        for (i = t; i < n; ++i) {
            f[i + 1] += g[i] * inv[a[i]] % mod;
            f[i + a[i] + 1] -= g[i] * inv[a[i]] % mod;
        }
        g[t] = 0;
        for (i = t + 1; i <= n; ++i) {
            g[i] = (g[i - 1] + f[i]) % mod;
            f[i] = 0;
        }
        ans = (ans + g[n] * g[n]) % mod;
    }
    printf("%lld\n", ans);
}

C

把题中给的关系看成边权建图。那么不合法当且仅当存在一个回路的矢量和不为 。此时需要改的边就是所有这样的回路的交。

否则，能改的边就是图中割边的个数。（因为其他的边肯定在一个回路里，改了就会破坏原有的合法关系）

建立 树后，所有的回路都可以表示为非树边构成的简单环的线性组合。于是枚举非树边，如果构成的简单环矢量和不为 ，那么给这条非树边覆盖的树边打标记（树上差分）。如果为 ，那这些被覆盖的树边不能更改，打上另一个标记。由于题目保证有解，所以直接这么做即可。时间复杂度 。

#include <bits/stdc++.h>
#define int long long
#define N 500010
using namespace std;
struct node {
    int to, id, a, b, c;
} dep[N];
vector<node> e[N];
int fa[N], vis[N], ans[N], s[N];
void dfs(int x, int f) {
    vis[x] = 1;
    for (auto p : e[x])
        if (!vis[p.to]) {
            fa[p.to] = p.id;
            dep[p.to].id = dep[x].id + 1;
            dep[p.to].a = dep[x].a + p.a;
            dep[p.to].b = dep[x].b + p.b;
            dep[p.to].c = dep[x].c + p.c;
            dfs(p.to, x);
            s[x] += s[p.to];
        }
}
int u[N], v[N], a[N], b[N], c[N];
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m, i;
    cin >> n >> m;
    for (i = 1; i <= m; i++) {
        cin >> u[i] >> v[i] >> a[i] >> b[i] >> c[i];
        e[u[i]].push_back({ v[i], i, a[i], b[i], c[i] });
        e[v[i]].push_back({ u[i], i, -a[i], -b[i], -c[i] });
    }
    dfs(1, 0);
    for (i = 1; i <= m; i++)
        if (abs(dep[u[i]].id - dep[v[i]].id) != 1) {
            if (dep[u[i]].id < dep[v[i]].id)
                swap(u[i], v[i]);
            else
                a[i] = -a[i], b[i] = -b[i], c[i] = -c[i];
            if (dep[u[i]].a - dep[v[i]].a != a[i] || dep[u[i]].b - dep[v[i]].b != b[i] ||
                dep[u[i]].c - dep[v[i]].c != c[i]) {
                ans[i] = 1;
                s[u[i]]++;
                s[v[i]]--;
            } else
                ans[i] = -1e9, s[u[i]] -= 1e9, s[v[i]] += 1e9;
        }
    memset(vis, 0, sizeof(vis));
    dfs(1, 0);
    for (i = 1; i <= n; i++) ans[fa[i]] = s[i];
    int res = 0, mx = 0;
    for (i = 1; i <= m; i++) mx = max(mx, ans[i]);
    for (i = 1; i <= m; i++)
        if (ans[i] == mx)
            res++;
    cout << res << endl;
    for (i = 1; i <= m; i++)
        if (ans[i] == mx)
            cout << i << ' ';
}

D

按照出题人所给方法构造（）：

  • ，前 列构造 次拐弯，后 列构造两次。
  • ，对于每 行，前两行构造 次 ,后两行构造 次。
  • 在前 行和 一致，后面特殊构造。
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 1000 + 5

int n, m, Ans[N][N];
bool flip;

int main() {
    scanf("%d%d", &n, &m);
    if (n > m)
        swap(n, m), flip = true;
    if (n == 2) {
        Ans[1][1] = 2, Ans[1][2] = 1;
        Ans[2][1] = 3, Ans[2][2] = 4;
        int a = 2, b = 1;
        for (int j = 3; j * 2 <= m; j++) {
            Ans[a][j] = j * 2 - 1;
            Ans[b][j] = j * 2;
            swap(a, b);
        }
        if (m >= 4) {
            for (int j = m / 2 + 1; j <= m; j++) Ans[a][j] = m / 2 + j;
            for (int j = m; j > m / 2; j--) Ans[b][j] = 2 * m + m / 2 + 1 - j;
        }
    } else {
        bool flag = false;
        if (n % 4 != 0)
            n -= 2, flag = true;
        int id = 0;
        for (int i = n; i; i--) Ans[i][1] = ++id;
        for (int i = 1; i <= n; i += 4) {
            for (int j = 2; j <= m; j++) Ans[i][j] = ++id;
            for (int j = m; j >= 2; j--) Ans[i + 1][j] = ++id;
            int a = 2, b = 3;
            for (int j = 2; j <= m; j++) {
                Ans[i + a][j] = ++id;
                Ans[i + b][j] = ++id;
                swap(a, b);
            }
            if (i % 8 == 5) {
                reverse(Ans[i] + 2, Ans[i] + m + 1);
                reverse(Ans[i + 1] + 2, Ans[i + 1] + m + 1);
                reverse(Ans[i + 2] + 2, Ans[i + 2] + m + 1);
                reverse(Ans[i + 3] + 2, Ans[i + 3] + m + 1);
            }
        }
        if (flag) {
            n += 2;
            if (n % 8 == 6) {
                for (int i = 1; i <= n - 2; i++)
                    for (int j = 1; j <= m; j++) Ans[i][j] += 4;
                Ans[n - 1][1] = 4, Ans[n - 1][2] = 3;
                Ans[n][1] = 1, Ans[n][2] = 2;
                int a = n - 1, b = n, id = (n - 2) * m + 4, j = m;
                for (int ret = m - 3; ret > 2; j--) {
                    Ans[a][j] = ++id;
                    Ans[b][j] = ++id;
                    swap(a, b);
                    ret -= (j == m ? 1 : 2);
                }
                for (int _j = j; _j >= 3; _j--) Ans[a][_j] = ++id;
                for (int _j = 3; _j <= j; _j++) Ans[b][_j] = ++id;
            } else {
                for (int i = 1; i <= n - 2; i++)
                    for (int j = 1; j <= m; j++) Ans[i][j] += 3;
                int id = (n - 2) * m + 3;
                Ans[n - 1][1] = 3, Ans[n - 1][2] = ++id;
                Ans[n][1] = 2, Ans[n][2] = 1;
                int a = n - 1, b = n, j = 3;
                for (int ret = m - 2; ret > 2; j++) {
                    Ans[a][j] = ++id;
                    Ans[b][j] = ++id;
                    swap(a, b);
                    ret -= 2;
                }
                for (int _j = j; _j <= m; _j++) Ans[a][_j] = ++id;
                for (int _j = m; _j >= j; _j--) Ans[b][_j] = ++id;
            }
        }
    }
    if (flip) {
        for (int i = 1; i <= m; i++)
            for (int j = 1; j < i; j++) swap(Ans[i][j], Ans[j][i]);
        swap(n, m);
    }
    puts("Yes");
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) printf("%d%c", Ans[i][j], j == m ? '\n' : ' ');
    return 0;
}

E

首先有个数最多的方案为 ，这样能有 种。那么不妨先构造一个长度为 的这样的序列，能有 种。接下来把 二进制拆分，考虑构造 。一种方法是在第 个数后面插入比 大的数 ，在这个数前面选择的方案有 种。但是长度不够，接下来只需要补全位数满足长度为 即可。但是如果每个 都去补的话，需要的数是 了。而在这里，由于后面也会做类似的操作，我们只需要保证所有插入的 满足递增且都大于 即可。这样前面的就可以利用后面插入的数从而满足长度要求。具体地，对于两个为 的 位 ，满足 中间没有其他为 的 。那么在 第 个数后面需要插入 个，也就是第 位往上数 的 个数加上 。

#include <bits/stdc++.h>

using namespace std;
int add[100];

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int len = 30;
        while (!(n >> len)) len--;
        int cnt = 0;
        for (int i = len - 1; i >= 0; i--) {
            if (n >> i & 1) {
                add[i] = len - i - cnt;
                cnt += add[i];
            }
        }

        printf("%d\n", 2 * len + cnt + 1);
        int bas = len * 2;
        for (int i = 0; i < len; i++) {
            while (add[i] && add[i]--) printf("%d ", ++bas);
            printf("%d %d ", i * 2 + 2, i * 2 + 1);
        }
        printf("%d\n", ++bas);
    }
}

F

枚举 计算 是 的倍数的子矩阵方案数。然后用莫比乌斯反演求得 恰好为 的方案数。

由于 每个数都有，所以所有的因子总和为 。而求解一个矩阵的全 子矩阵个数，用单调栈即可解决。时间复杂度能做到只遍历为 位置的数。最终复杂度 

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1010;
int n, m;
pair<int, int> f[N * N];
int a[N][N], g[N][N], l[N];
ll s[N][N], d[N][N], ans[N * N];
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            scanf("%d", &a[i][j]);
            f[a[i][j]] = make_pair(i, j);
        }
    for (int i = 1; i <= n * m; i++) {
        vector<pair<int, int>> w;
        for (int j = 1; j * i <= n * m; j++) {
            w.push_back(f[i * j]);
        }
        sort(w.begin(), w.end());
        for (int j = 0; j < w.size(); j++) {
            int x = w[j].first, y = w[j].second;
            g[x][y] = g[x][y - 1] + 1;
            if (g[x - 1][y] == 0) {
                l[y] = 0;
                d[y][0] = x - 1;
            }
            ++l[y];
            d[y][l[y]] = x;
            while (l[y] > 1 && g[x][y] <= g[d[y][l[y] - 1]][y]) {
                l[y]--;
                d[y][l[y]] = d[y][l[y] + 1];
            }
            s[y][l[y]] = s[y][l[y] - 1] + 1ll * (x - d[y][l[y] - 1]) * g[x][y];
            ans[i] += s[y][l[y]];
        }
        for (int j = 0; j < w.size(); j++) {
            l[w[j].second] = 0;
            g[w[j].first][w[j].second] = 0;
        }
    }
    for (int i = n * m; i >= 1; i--) {
        for (int j = 2; j * i <= n * m; j++) ans[i] -= ans[i * j];
    }
    ll s = 0;
    for (int i = 1; i <= n * m; i++) {
        s += 1ll * i * ans[i];
    }
    printf("%lld\n", s);
}

G

由于一个字符串的所有本质不同回文子串只有 。用 或者回文树求出来，然后用哈希统计出现次数。 需要挂一只 。

#include <iostream>
#define maxn 300005
using namespace std;
string s, s1;
int len[maxn], fail[maxn], tr[maxn][30], cnt[maxn], idex = 1, cur;
int get_fail(int x, int i) {
    while (i - len[x] - 1 < 0 || s[i] != s[i - len[x] - 1]) {
        x = fail[x];
    }
    return x;
}
void build(int k) {
    int llen = s.size();
    len[1] = -1, fail[0] = 1, len[0] = 0, fail[1] = 1;
    for (int i = 0; i < llen; i++) {
        int u = get_fail(cur, i);
        if (!tr[u][s[i] - 'a']) {
            fail[++idex] = tr[get_fail(fail[u], i)][s[i] - 'a'];
            tr[u][s[i] - 'a'] = idex;
            len[idex] = len[u] + 2;
        }
        cur = tr[u][s[i] - 'a'];
        if (cnt[cur] == k - 1) {
            cnt[cur]++;
        }
    }
}
int main() {
    int k;
    cin >> k;
    for (int i = 1; i <= k; i++) {
        cin >> s;
        build(i);
    }
    long long ans = 0;
    for (int i = idex; i > 0; i--) {
        if (cnt[i] == k) {
            ans++;
        }
    }
    cout << ans << endl;
}

I

令 表示前 个数划分成 段从左到右枚举 ，考虑单调栈来把以 为右端点的， 相同的左端点 合并成一段区间。

然后一段的由于代价相同，可以直接用 表示第 个区间内的，所有的 （ 属于第 个区间）的最小值加上左端点在这里面对应的 值 。

每次弹栈的时候，设这个区间原来的 为 ，新的 为 。需要令 加上 ，然后再把所有弹出的区间合并成一个区间。并且再维护一个前缀数组 表示 。弹栈的时候更新这个数组。更新 的时候直接取 的值。时间复杂度 。

#include <bits/stdc++.h>
using namespace std;
const int N = 8e3 + 5;
int f[2][N], g[N], mi[N], stk[N], n, a[N], top;
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i], f[0][i] = 0x3f3f3f3f;
    for (int k = 1; k <= n; k++) {
        int id = k & 1;
        f[id][top = 0] = 0x3f3f3f3f;
        for (int i = k; i <= n; i++) {
            mi[i] = f[id ^ 1][i - 1];
            while (top && a[stk[top]] <= a[i]) {
                mi[i] = min(mi[i], mi[stk[top]]);
                top--;
            }
            f[id][i] = min(f[id][stk[top]], mi[i] + a[i]);
            stk[++top] = i;
        }
        cout << f[id][n] << '\n';
    }
}

J

如果一条边颜色数量大于 ，那么总能选到一个和前后两条边颜色不同的颜色。

剩下的边，每条颜色数小于等于 。于是合并两条路径时候，枚举四条边的颜色得到新的答案。那么对于树上的问题就可以用倍增或者树剖维护了。

考虑基环数，如果路径要经过环，需要枚举从哪边走。一种方法是，把环拎出来，在环上正反做两次倍增维护。时间复杂度 ，常数稍大。

#include <bits/stdc++.h>
#define maxn 200086

using namespace std;

struct Node {
    int c[2][2], f[2][2];
};

Node merge(const Node &l, const Node &r) {
    Node x;
    x.c[0][0] = l.c[0][0], x.c[0][1] = l.c[0][1];
    x.c[1][0] = r.c[1][0], x.c[1][1] = r.c[1][1];
    memset(x.f, -0x3f, sizeof(x.f));
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            for (int k = 0; k < 2; k++)
                for (int o = 0; o < 2; o++) {
                    x.f[i][o] = max(x.f[i][o], l.f[i][j] + r.f[k][o] - (l.c[1][j] == r.c[0][k]));
                }
    return x;
}

int n, q;
int a[maxn][2];
bool flag[maxn];
vector<pair<int, int> > v[maxn];

int fa[maxn], id[maxn];
int dep[maxn];
vector<pair<int, int> > w;

void dfs(int i) {
    dep[i] = dep[fa[i]] + 1;
    for (auto it : v[i]) {
        int to = it.first, co = it.second;
        if (flag[co])
            continue;
        flag[co] = true;
        if (!dep[to]) {
            fa[to] = i, id[to] = co;
            dfs(to);
        } else {
            int x = i;
            while (x ^ to) {
                w.push_back({ x, id[x] });
                x = fa[x];
            }
            w.push_back({ to, co });
        }
    }
}

bool vis[maxn];
int rt[maxn], f[maxn][20];
Node g[maxn][20], h[maxn * 2][20];
int lg[maxn];

void init(Node &x, int id) {
    x.c[0][0] = x.c[1][0] = a[id][0];
    x.c[0][1] = x.c[1][1] = a[id][1];
    x.f[0][0] = x.f[1][1] = 1;
    x.f[0][1] = x.f[1][0] = -0x3f3f3f3f;
}

void dfs(int i, int x) {
    dep[i] = dep[f[i][0]] + 1, rt[i] = x;
    for (int j = 1; j < 20; j++) {
        f[i][j] = f[f[i][j - 1]][j - 1];
        g[i][j] = merge(g[i][j - 1], g[f[i][j - 1]][j - 1]);
    }
    for (auto it : v[i]) {
        int to = it.first, id = it.second;
        if (to == f[i][0] || vis[to])
            continue;
        f[to][0] = i;
        init(g[to][0], id);
        dfs(to, x);
    }
}

int lca(int x, int y) {
    if (dep[x] < dep[y])
        swap(x, y);
    while (dep[x] > dep[y]) x = f[x][lg[dep[x] - dep[y]]];
    if (x == y)
        return x;
    for (int i = 19; ~i; i--)
        if (f[x][i] ^ f[y][i])
            x = f[x][i], y = f[y][i];
    return f[x][0];
}

Node G(int x, int d) {
    Node ans;
    bool tag = false;
    for (int i = 0; i < 20; i++)
        if (d & (1 << i)) {
            if (!tag)
                ans = g[x][i], tag = true;
            else
                ans = merge(ans, g[x][i]);
            x = f[x][i];
        }
    return ans;
}

Node H(int x, int d) {
    Node ans;
    bool tag = false;
    for (int i = 0; i < 20; i++)
        if (d & (1 << i)) {
            if (!tag)
                ans = h[x][i], tag = true;
            else
                ans = merge(ans, h[x][i]);
            x += 1 << i;
        }
    return ans;
}

Node rev(Node x) {
    swap(x.c[0][0], x.c[1][0]), swap(x.c[0][1], x.c[1][1]);
    swap(x.f[0][1], x.f[1][0]);
    return x;
}

int cal(Node x) { return max({ x.f[0][0], x.f[0][1], x.f[1][0], x.f[1][1] }); }

int Id[maxn];

int main() {
    for (int i = 2; i < maxn; i++) lg[i] = lg[i >> 1] + 1;
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        v[x].push_back({ y, i }), v[y].push_back({ x, i });
        int k;
        scanf("%d", &k);
        if (k >= 3) {
            a[i][0] = a[i][1] = 5e5 + i;
            while (k--) scanf("%d", &x);
        } else if (k == 2)
            scanf("%d%d", &a[i][0], &a[i][1]);
        else
            scanf("%d", &a[i][0]), a[i][1] = a[i][0];
    }
    dfs(1);
    for (int i = 0; i < w.size(); i++) Id[w[i].first] = i, vis[w[i].first] = true;
    for (int i = 0; i < w.size(); i++) dfs(w[i].first, w[i].first);
    for (int i = 0; i < w.size(); i++) {
        init(h[i][0], w[i].second);
        h[i + w.size()][0] = h[i][0];
    }
    for (int j = 1; j < 20; j++) {
        for (int i = 0; i + (1 << (j - 1)) < w.size() * 2; i++) {
            h[i][j] = merge(h[i][j - 1], h[i + (1 << (j - 1))][j - 1]);
        }
    }
    while (q--) {
        int x, y;
        scanf("%d%d", &x, &y);
        if (rt[x] == rt[y]) {
            Node ans;
            if (dep[x] < dep[y])
                swap(x, y);
            int z = lca(x, y);
            if (z == y) {
                ans = G(x, dep[x] - dep[y]);
            } else {
                Node l = G(x, dep[x] - dep[z]), r = rev(G(y, dep[y] - dep[z]));
                ans = merge(l, r);
            }
            printf("%d\n", cal(ans));
        } else {
            if (Id[rt[x]] > Id[rt[y]])
                swap(x, y);
            Node l = G(x, dep[x] - dep[rt[x]]), r = rev(G(y, dep[y] - dep[rt[y]]));
            Node i = H(Id[rt[x]], Id[rt[y]] - Id[rt[x]]),
                 j = rev(H(Id[rt[y]], w.size() - (Id[rt[y]] - Id[rt[x]])));
            if (x == rt[x] && y == rt[y])
                printf("%d\n", max(cal(i), cal(j)));
            else if (x == rt[x])
                printf("%d\n", max(cal(merge(i, r)), cal(merge(j, r))));
            else if (y == rt[y])
                printf("%d\n", max(cal(merge(l, i)), cal(merge(l, j))));
            else
                printf("%d\n", max(cal(merge(l, merge(i, r))), cal(merge(l, merge(j, r)))));
        }
    }
}

K

定义全集 定义集合幂级数 。若存在给定集合 那么 为 。

定义卷积为并卷积，可以用 计算。那么只需要求出 ，对于一个 找到最小的 使得 ，就是 的度数。

得到这些答案后，再做一次高为后缀 即可。时间复杂度 。

#include <cstdio>
using namespace std;
int n, K, ans[100];
int A[1100000], B[1100000];
void FWT_or(int *f, int type) {
    for (int mid = 1; mid < (1 << K); mid <<= 1)
        for (int block = mid << 1, j = 0; j < (1 << K); j += block)
            for (int i = j; i < j + mid; i++) f[i + mid] = (f[i + mid] + f[i] * type);
}
int main() {
    scanf("%d%d", &n, &K);
    for (int x, y, z, i = 1; i <= n; i++) {
        scanf("%d", &x);
        z = 0;
        for (int i = 1; i <= x; i++) {
            scanf("%d", &y);
            z |= 1 << y - 1;
        }
        A[z] = 1;
    }

    for (int i = (1 << K) - 1; i > 0; i--)
        for (int k = i, j = k & -k; k; k -= j, j = k & -k) A[i ^ j] |= A[i];
    FWT_or(A, 1);

    B[0] = ans[0] = 1;
    for (int j = 1; j <= K; j++) {
        FWT_or(B, 1);
        for (int i = 0; i < (1 << K); i++) B[i] *= A[i];
        FWT_or(B, -1);

        for (int i = 0; i < (1 << K); i++)
            if (B[i])
                B[i] = 1, ans[j]++;
    }
    for (int i = K; i; i--) ans[i] -= ans[i - 1];
    for (int i = 1; i <= K; i++) printf("%d ", ans[i]);
}
2026最新求职资料大礼包领取
真题
历年笔试真题附答案
中国系统2023校园招聘-前端笔试
2024年秋招-Shopee-SRE-提前批笔试
欢聚时代2018校招笔试题-交互设计
全部 >
面经
面试常考问题整理
Springboot全套注解解析《看不懂算我输》
23届联想面经分享： 秋招上岸
腾讯三面已上岸
全部 >
内推
员工内推码获取
2026届拼多多校招内推内推内推码
阿里云智能-弹性计算高级研发工程师/高级技术专家-北京/杭州
国科微电子最新社招/校招，岗位多多
全部 >
大家都在关注
校招日程表 笔试日历 ai模拟面试 面试宝典 剑指offer 知识点专项练习

全部评论

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

本文相关内容

等你来战

查看全部

热门推荐

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

扫描二维码，进入QQ群

扫码关注“比赛自动姬”