竞赛讨论区 > 牛客练习赛152出题人题解
头像
grape_king
编辑于 昨天 21:49 上海
+ 关注

牛客练习赛152出题人题解

A

题解:

行为偶数可以这样输出:

行为奇数可以这样输出:

按照以上格式输出即可,还有别的输出格式,打表可观察出。

时间复杂度:

代码:

正解:

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int op[2][4][4] = {{{1, 1, 0, 0}, {0, 0, 1, 1}, {1, 1, 0, 0}, {0, 0, 1, 1}}, {{1, 0, 1, 0}, {1, 0, 1, 0}, {0, 1, 0, 1}, {0, 1, 0, 1}}};
void solve() {
    int n, m; cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << op[n % 2][i % 4][j % 4];
        }
        cout << '\n';
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int _ = 1;
    // std::cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

c++代码(暴力打表找规律代码):

#include <bits/stdc++.h>
using namespace std;
int a[10][10];
bool check(int n, int m) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            sum += a[i][j];
        }
    }
    if (abs(sum - (n * m - sum)) > 1) return false;
    for (int i = 2; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (a[i][j] == a[i - 1][j] && a[i - 1][j] == a[i - 2][j]) return false;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 2; j < m; j++) {
            if (a[i][j] == a[i][j - 1] && a[i][j - 1] == a[i][j - 2]) return false;
        }
    }
    for (int i = 2; i < n; i++) {
        for (int j = 2; j < m; j++) {
            if (a[i][j] == a[i - 1][j - 1] && a[i - 1][j - 1] == a[i - 2][j - 2]) return false;
        }
    }
    for (int i = 2; i < n; i++) {
        for (int j = m - 3; j >= 0; j--) {
            if (a[i][j] == a[i - 1][j + 1] && a[i - 1][j + 1] == a[i - 2][j + 2]) return false;
        }
    }
    return true;
}

void prf(int n, int m) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << a[i][j];
        }
        cout << '\n';
    }
}

void solve() {
    int n, m; cin >> n >> m;
    int s = n * m;
    int op = 1;
    for (int i = 0; i < 1 << s; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < m; k++) {
                a[j][k] = (i >> (j * m + k) & 1);
            }
        }
        if (check(n, m)) {
            cout << "ans: " << i << '\n';
            prf(n, m);
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int _ = 1;
    // std::cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

/*
1010101
1010101
0101010
0101010
1010101
*/

B

题解:

操作一每次都是奇数变偶数、偶数变奇数,所以最终的奇数次数和偶数次数会一直保持不变

现在考虑操作二是找值互质的两个下标数对,已知 ,故我们可以使得值相邻的数形成一个奇数集合或者偶数集合

例如:

这样我们通过操作一拉进两个奇偶不同的数值之间的距离,当距离之差为 时,我们再通过操作二化为一个集合,最后化为全一样的形式。

先特判一开始一样的情况;再特判只有偶数的情况;再特判只有奇数的情况,如果有某对下标满足 ,那么就能凑出至少一个奇数和偶数,这样就一定满足,如果没有满足的,就无法做到。

所以这题只要即有奇数又有偶数即可完成全一样。

时间复杂度:

代码:

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve() {
    int n; cin >> n;
    vector<int> a(n + 1);
    int d = 0, sum = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i]; sum += (a[i] & 1);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            if (std::gcd(a[i], a[j]) == 1) d = 1;
        }
    }
    sort(a.begin() + 1, a.end());
    if (a[1] == a[n]) {
        cout << "YES\n";
        return;
    }
    if (sum == 0 || (sum == n && !d)) {
        cout << "NO\n";
        return;
    }
    cout << "YES\n";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int _ = 1;
    std::cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

C

题解:

特判一种特殊情况,就是形如数组 这种形式,那么说明数组

现在假设数组 里面有出现重复数字,令其为 ,那么这个 一定是原数组 中所有数的 ,所以:

  • ,说明 ,且这个数 只能恰好出现一次,因为删除这个数后,导致整体的 变小了;
  • ,说明 这个数要么 且出现了多次,要么是 的数,然后在这里我们肯定要先贪心 的情况,先将没有出现的 出现多次,这里多次我们可以选择先让 出现两次,假设最后贪心完所有的 的数,其他数我们就直接用大于 的数替代即可,若还有数没贪心完或者贪心的那个数只出现了一次,那么我们就直接输出 -1 即可。

时间复杂度:

代码:

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve() {
    int n; cin >> n;
    vector<int> a(n + 1), vis(n);
    bool fg = false;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] >= n) fg = true;
        else vis[a[i]]++;
    }
    if (fg) {
        cout << "-1\n";
        return;
    }
    int sum = 0;
    for (int i = 0; i < n; i++) sum += (vis[i] > 0);
    if (sum == n) {
        for (int i = 1; i <= n; i++) cout << a[i] << ' ';
        cout << '\n';
        return;
    }
    int m = -1;
    for (int i = n - 1; i >= 0; i--) {
        if (!vis[i]) continue;
        if (m == -1) {
            if (vis[i] == 1) {
                cout << "-1\n";
                return;
            }
            m = i;
        } else {
            if (vis[i] > 1) {
                cout << "-1\n";
                return;
            }
        }
    }
    vector<int> b(n + 1, -1), vis2(n);
    for (int i = 1; i <= n; i++) {
        if (a[i] != m) {
            b[i] = a[i];
            vis2[a[i]] = 2;
        }
    }
    int tot = 0;
    for (int i = 1; i <= n; i++) {
        if (b[i] != -1) continue;
        while (tot < m && vis2[tot] == 2) tot++;
        if (tot != m) {
            b[i] = tot;
            vis2[tot]++;
        } else {
            b[i] = m + 1;
        }
    }
    while (tot < m && vis2[tot] == 2) tot++;
    if (tot != m) {
        cout << "-1\n";
        return;
    }
    for (int i = 1; i <= n; i++) {
        cout << b[i] << ' ';
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int _ = 1;
    std::cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

D和E

题解:

对于D

操作定义为:若父节点为 0 且子节点为 1,则可以交换。这意味着:

  • 单向性:权值为 的棋子只能从子树向根节点方向移动,不能向下移动。

  • 合法性:最终状态下,若节点 的条件 ,则该位置不能放置权值 (即 必须为 )。换言之,所有的 最终必须停留在 的节点上

  • 子树限制:由于 只能向上走,对于任何一棵子树,其最终拥有的 的数量不能超过其初始时拥有的 的数量

本题要求计算不同合法最终状态的数量。

状态

  • :表示在节点 的子树中,最终放置了 个权值为 的棋子的方案数。
  • :节点 子树内初始时权值为 的棋子总数。

转移

树形背包dp:

  • 合并子树:遍历 的每个子节点 ,将 的状态合并到 中:

    在合并过程中,需保证 (子树 分到的 不能超过其初始值)。

  • 处理根节点 : 在合并完所有子树后,考虑节点 本身。 如果 ,说明 可以放置一个 。此时,子树内有 的方案可以转化成子树内有 的方案(即将一个 留在根节点 ):

答案为 ,其中 是整棵树初始时 的总数。

对于E

本题要求所有合法最终状态的 最小操作次数之和

  • 最小操作次数:由于 只能向上移动,从初始状态 到最终状态 的最小步数等于每个 移动的距离之和。
  • 边贡献法:对于树上的每一条边 ,其被跨越的次数等于:初始时子树 的数量 - 最终留在子树 的数量。 设初始数量为 ,最终数量为 ,则该边对总步数的贡献为

状态

  • :方案数(同 D 题)。
  • :在 的子树内,所有合法方案的 内部边贡献总和

转移

在合并子节点 到父节点 时,我们需要维护方案数和步数和:

  • 方案数更新(同背包合并):

  • 步数和更新: 当子树 分配了 时,边 的贡献是

    • :原 子树的步数和乘以新子树的方案数。

    • :新 子树的步数和乘以原子树方案数。

    • :跨越边 产生的额外步数。

  • 处理根节点 : 同 题,若 ,则节点 可以选择接纳一个从下方移动上来的

代码:

D题直接输出即可。

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 mod = 998244353;
inline int add(int a, int b) { a += b; if (a >= mod) a -= mod; return a; }
inline int sub(int a, int b) { a -= b; if (a < 0) a += mod; return a; }
void solve() {
    int n; cin >> n;
    vector<vector<int>> g(n + 1);
    vector<int> a(n + 1), s(n + 1);
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int k = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        k += a[i];
    }
    for (int i = 1; i <= n; i++)
        cin >> s[i];
    vector<int> siz(n + 1);
    vector<vector<int>> dp(n + 1, vector<int>(n + 1)), dpc(n + 1, vector<int>(n + 1));
    function<void(int, int)> dfs = [&](int u, int fa) {
        dp[u][0] = 1;
        for (int &v : g[u]) {
            if (v == fa) continue;
            dfs(v, u);
            for (int i = siz[u] + siz[v]; i >= 0; i--) {
                dpc[u][i] = add(1LL * dpc[u][i] * dp[v][0] % mod, 1LL * dp[u][i] * add(dpc[v][0], 1LL * dp[v][0] * siz[v] % mod) % mod);
                dp[u][i] = 1LL * dp[u][i] * dp[v][0] % mod;
                for (int j = min(i, siz[v]); j >= max(1, i - siz[u]); j--) {
                    dpc[u][i] = add(dpc[u][i], add(1LL * dpc[u][i - j] * dp[v][j] % mod, 1LL * dp[u][i - j] * add(dpc[v][j], 1LL * dp[v][j] * (siz[v] - j) % mod) % mod));
                    dp[u][i] = add(dp[u][i], 1LL * dp[u][i - j] * dp[v][j] % mod);
                }
            }
            siz[u] += siz[v];
        }
        if (s[u]) {
            for (int i = siz[u]; i >= 0; i--) {
                dp[u][i + 1] = add(dp[u][i + 1], dp[u][i]);
                dpc[u][i + 1] = add(dpc[u][i + 1], dpc[u][i]);
            }
        }
        siz[u] += a[u];
    };
    dfs(1, 0);
    cout << dpc[1][k] << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int _ = 1;
    std::cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

F

题解:

我们知道对于任意的 ,都有 ,并且它们之间是互不影响的,所以我们可以把每个位置看成一个多项式,对于位置 ,看成 ,那么将前面 个位置乘积起来就是:

因为 的次幂对应的就是当前前缀所选正序对数,我们需要选取 个数给前面进行正序对排列,后面 个数任意全排列即可,所以对于每组询问 ,对应的方案数便是:

前面那部分可用前缀乘和前缀乘逆元预处理,现在考虑后面部分的求和,由欧拉五边形定理可知:

为:

时,有:

时,由于 ,所以 ,那么可以通过容斥去重得:

然后可以预处理多项式 的前缀和,就可以 的时间复杂度得到多项式 的对应系数。

,是常见的生成函数求逆元,得:

故:

由于已知多项式 和多项式 的对应系数,故我们可以通过 算法来实现多项式之间的乘积,时间复杂度为

然后对询问进行离线处理,按照 从小到大排序,依次求出每个 对应的多项式 ,然后前缀和预处理系数再差分得到每次询问的答案。

最终总时间复杂度为:( 是计算去重后的之和)。

代码:

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int mod = 998244353;
const int D = 21;
const int N = (1 << D) + 1;
const int M = 1e6 + 5;
const int g = 3;
inline int add(int a, int b) {
    a += b;
    if (a >= mod) a -= mod;
    return a;
}

inline int sub(int a, int b) {
    a -= b;
    if (a < 0) a += mod;
    return a;
}

int qp(int a, int b) {
    int res = 1;
    for (; b; b >>= 1LL, a = 1LL * a * a % mod) {
        if (b & 1) res = 1LL * res * a % mod;
    }
    return res;
}

int c[N], pc[N], fac[M], invfac[M], inv[N];
int G[N], H[N], rev[N], GG[2][D][N >> 1];
int C(int n, int m) {
    if (n < m) return 0;
    return 1LL * fac[n] * invfac[n - m] % mod * invfac[m] % mod;
}

const int invg = qp(g, mod - 2);
void init() {
    c[0] = 1;
    for (int k = 1; ; k++) {
        int x = k * (3 * k - 1) / 2;
        int y = k * (3 * k + 1) / 2;
        if (x >= N && y >= N) break;

        int v = (k & 1) ? mod - 1 : 1;
        if (x < N) c[x] = v;
        if (y < N) c[y] = v;
    }
    pc[0] = c[0];
    for (int i = 1; i < N; i++) pc[i] = add(pc[i - 1], c[i]);
    inv[1] = 1;
    for (int i = 2; i < N; i++) {
        inv[i] = 1LL * (mod - mod / i) * inv[mod % i] % mod;
    }
    for (int p = 0; p < D; ++p) {
        int buf0 = qp(g, (mod - 1) / (1 << (p + 1)));
        int buf1 = qp(invg, (mod - 1) / (1 << (p + 1)));
        GG[0][p][0] = GG[1][p][0] = 1;
        for (int i = 1; i < (1 << p); ++i) {
            GG[0][p][i] = 1LL * GG[0][p][i - 1] * buf0 % mod;
            GG[1][p][i] = 1LL * GG[1][p][i - 1] * buf1 % mod;
        }
    }
    fac[0] = invfac[0] = 1;
    for (int i = 1; i < M; i++) fac[i] = 1LL * fac[i - 1] * i % mod;
    invfac[M - 1] = qp(fac[M - 1], mod - 2);
    for (int i = M - 2; i >= 1; i--) {
        invfac[i] = 1LL * invfac[i + 1] * (i + 1) % mod;
    }
}

void NTT_init(int n) {
    for (int i = 0; i < n; ++i) {
        rev[i] = ((rev[i >> 1] >> 1) | ((i & 1) ? n >> 1 : 0));
    }
}

void H_init(int t, int n) {
    H[0] = 1;
    for (int i = 1; i < n; i++) {
        H[i] = 1LL * H[i - 1] * (t + i - 1) % mod * inv[i] % mod;
    }
}

void G_init(int t, int n) {
    for (int i = 0; i < n; i++) {
        G[i] = c[i];
    }
    for (int i = t + 1; i < n; i++) {
        G[i] = add(c[i], pc[i - t - 1]);
    }
}

void NTT(int *a, int n, int op) {
    assert(n < N);
    for (int i = 0; i < n; i++) {
        if (i < rev[i]) swap(a[i], a[rev[i]]);
    }
    for (int d = 1, p = 0; d < n; d <<= 1, p++) {
        for (int i = 0; i < n; i += d << 1) {
            int *wn = GG[op][p];
            for (int k = 0; k < d; k++, ++wn) {
                int x = a[i + k];
                int y = 1LL * (*wn) * a[i + d + k] % mod;
                a[i + k] = add(x, y);
                a[i + d + k] = sub(x, y);
            }
        }
    }
    if (op) {
        int invn = qp(n, mod - 2);
        for (int i = 0; i < n; ++i) {
            a[i] = 1LL * a[i] * invn % mod;
        }
    }
}

void Poly_Mul(int *f, int *h, int n) {
    int m = (n << 1) - 1;
    int lim = 1;
    while (lim < m) lim <<= 1;
    for (int i = n; i < lim; i++) {
        f[i] = h[i] = 0;
    }
    NTT_init(lim);
    NTT(f, lim, 0);
    NTT(h, lim, 0);
    for (int i = 0; i < lim; i++) {
        f[i] = 1LL * f[i] * h[i] % mod;
    }
    NTT(f, lim, 1);
}

void solve() {
    int n, q;
    cin >> n >> q;
    vector<array<int, 4>> Q(q);
    for (int i = 0; i < q; i++) {
        cin >> Q[i][0] >> Q[i][1] >> Q[i][2];
        Q[i][3] = i;
    }
    sort(Q.begin(), Q.end());
    int pre = -1;
    vector<int> ans(q);
    for (int i = 0; i < q; i++) {
        auto [t, l, r, id] = Q[i];
        int m = min(1LL * (t - 1) * t / 2, 2LL * t);
        if (pre != t) {
            pre = t;
            G_init(t, m + 1);
            H_init(t, m + 1);
            Poly_Mul(G, H, m + 1);
            for (int j = 1; j <= m; j++) {
                G[j] = add(G[j], G[j - 1]);
            }
        }
        if (l > m) {
            ans[id] = 0;
            continue;
        }
        r = min(r, m);
        ans[id] = 1LL * sub(G[r], l == 0 ? 0 : G[l - 1]) * fac[n] % mod * invfac[t] % mod;
    }
    for (int i = 0; i < q; i++) {
        cout << ans[i] << ' ';
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int _ = 1;
    // std::cin >> _;
    init();
    while (_--) {
        solve();
    }
    return 0;
}

G

题解:

考虑根号分治。对于长度小于 做法是平凡的。对于长度大于等于 (最多有 个)。对 建后缀自动机,并计算一个长度为 的数组 ,其中 ,这可以简单Z函数得到。考虑后缀自动机上的一个节点 ,令其对应结束下标集合为 。对于任意一个长度 ,如果后缀自动机上存在一个节点 ,使得 ,则长度为 的前缀是美丽的。先对后缀link树做一次dfs求出 ,然后把 放在后缀自动机上匹配。对于一个 ,设其匹配到的节点为 ,则只需要查询其后缀link树上的祖先的上式最大值即可。最终复杂度

代码:

#include <bits/stdc++.h>

using namespace std;

template<int sig = 26>
struct SAM {
    struct node {
        int len, link;
        array<int, sig> next;
        node(int len, int link = -1) : len(len), link(link) {
            next.fill(-1);
        }
    };
    int last;
    vector<node> tr;
    SAM() { init(); }
    void init() {
        tr.emplace_back(0, -1);
        last = 0;
    }
    int extend(int c) {
        int cur = tr.size();
        tr.emplace_back(tr[last].len + 1);
        int p = last;
        while (p != -1 && tr[p].next[c] == -1) {
            tr[p].next[c] = cur;
            p = tr[p].link;
        }
        if (p == -1) {
            tr[cur].link = 0;
        } else {
            int q = tr[p].next[c];
            if (tr[p].len + 1 == tr[q].len) {
                tr[cur].link = q;
            } else {
                int clone = tr.size();
                tr.emplace_back(tr[p].len + 1, tr[q].link);
                tr.back().next = tr[q].next;
                while (p != -1 && tr[p].next[c] == q) {
                    tr[p].next[c] = clone;
                    p = tr[p].link;
                }
                tr[q].link = tr[cur].link = clone;
            }
        }
        last = cur;
        return last;
    }
    int size() {
        return tr.size();
    }
    int len(int u) {
        return tr[u].len;
    }
    int link(int u) {
        return tr[u].link;
    }
    int next(int u, int c) {
        return tr[u].next[c];
    }
};

constexpr int M = 700;

vector<int> get_lcp(string& s, string& t) {
    string p = t + "$" + s;
    int sz = p.size();
    vector<int> z(sz);
    for (int i = 1, l = 0, r = 0; i < sz; i++) {
        if (i <= r && z[i - l] < r - i + 1) {
            z[i] = z[i - l];
        } else {
            z[i] = max(0, r - i + 1);
            while (i + z[i] < sz && p[z[i]] == p[i + z[i]]) z[i]++;
        }
        if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
    }
    vector<int> lcp(s.size() + 1, 0);
    for (int i = 0; i < (int)s.size(); i++) {
        lcp[i] = z[t.size() + 1 + i];
    }
    return lcp;
}

void solve() {
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    SAM<26> sam;
    vector<int> pos(n);
    for (int i = 0; i < n; i++) pos[i] = sam.extend(s[i] - 'a');
    int k = sam.size();
    vector<int> f(k, -1);
    for (int i = 0; i < n; i++) f[pos[i]] = i;
    vector<vector<int>> g(k);
    for (int i = 1; i < k; i++) g[sam.link(i)].push_back(i);
    vector<int> a(k), b(k);
    while (q--) {
        string t;
        cin >> t;
        int m = t.size();
        if (m >= M) {
            auto lcp = get_lcp(s, t);
            auto dfs1 = [&](auto &&self, int u) -> void {
                if (f[u] != -1) a[u] = lcp[f[u] + 1];
                else a[u] = 0;
                for (auto v : g[u]) {
                    self(self, v);
                    a[u] = max(a[u], a[v]);
                }
            };
            dfs1(dfs1, 0);
            b[0] = a[0];
            auto dfs2 = [&](auto &&self, int u) -> void {
                for (auto v : g[u]) {
                    b[v] = max(b[u], a[v] + sam.len(v));
                    self(self, v);
                }
            };
            dfs2(dfs2, 0);
            
            int u = 0;
            int len = 0;
            for (int i = 0; i < m; i++) {
                int c = t[i] - 'a';
                while (u && sam.next(u, c) == -1) {
                    u = sam.link(u);
                    len = sam.len(u);
                }
                if (sam.next(u, c) != -1) {
                    len++;
                    u = sam.next(u, c);
                }
                int mx = len + a[u];
                if (u) mx = max(mx, b[sam.link(u)]);
                if (mx >= i + 1) cout << 1;
                else cout << 0;
            }
            cout << "\n";
        } else {
            for (int j = 1; j <= m; j++) {
                int u = 0, len = 0;
                int f = 0;
                for (int i = 0; i < 2 * j - 1; i++) {
                    int c = t[i >= j ? (i - j) : i] - 'a';
                    while (u && sam.next(u, c) == -1) {
                        u = sam.link(u);
                        len = sam.len(u);
                    }
                    if (sam.next(u, c) != -1) {
                        len++;
                        u = sam.next(u, c);
                    }
                    if (len >= j) {
                        f = 1;
                        break;
                    }
                }
                cout << f;
            }
            cout << "\n";
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--) solve();
}

全部评论

(0) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐