牛客周赛 Round 143 题解

已向 #define int long long 屈服

A 小红的区间构造

知识点：构造

直接输出区间 $[1,x]$ 即可。这个区间里所有数都是正整数，且数量恰好为 $x$ 。

时间复杂度 $\mathcal{O}(1)$ 。

void solve() {
    int x;
    cin >> x;
    cout << 1 << " " << x << '\n';
}

B 小红的冷门副本

知识点：计数、哈希表

统计每个出现过的副本被选择的次数。没有出现过的副本次数为 $0$ ，一定会参与统计。

设出现次数大于 $x$ 的副本有 $cnt$ 个，它们不是冷门副本，因此答案为 $m-cnt$ 。

时间复杂度 $\mathcal{O}(n)$ 。

void solve() {
    int n, m, x;
    cin >> n >> m >> x;
    unordered_map<int, int> cnt;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        cnt[a]++;
    }

    int hot = 0;
    for (auto [id, c] : cnt) {
        if (c > x) hot++;
    }
    cout << m - hot << '\n';
}

C 小红的因子幂和

知识点：质因数分解、约数枚举、快速幂

先对 $x$ 和 $y$ 分别质因数分解，把同一个质因子的指数相加，即可得到 $v=xy$ 的质因数分解。

接着 DFS 枚举 $v$ 的所有正因子 $d$ ，对每个因子计算 $d^d$ 并累加。

时间复杂度 $\mathcal{O}(\sqrt{x}+\sqrt{y}+\tau(xy)\log(xy))$ 。

void solve() {
    int x, y;
    cin >> x >> y;
    map<int, int> mp;
    auto fac = [&](int n) {
        for (int i = 2; i * i <= n; ++i) {
            while (n % i == 0) {
                mp[i]++;
                n /= i;
            }
        }
        if (n > 1) mp[n]++;
    };
    fac(x), fac(y);
    vector<int> d{1};
    for (auto [p, c] : mp) {
        int s = d.sz, cur = 1;
        for (int i = 1; i <= c; ++i) {
            cur *= p;
            for (int j = 0; j < s; ++j) d.pb(d[j] * cur);
        }
    }
    Z ans = 0;
    for (auto v : d) ans += mypow(Z(v), v);
    cout << ans << endl;
}

D 小红的最佳区间

知识点：区间转化、扫描线

给定区间 $[l_i,r_i]$ 与选择的 $[L,L+k]$ 相交，当且仅当：

L \le r_i,\quad L+k \ge l_i

也就是 $L \in [l_i-k,r_i]$ 。于是每个原区间都会转化成一个可选 $L$ 的区间，问题变成求若干区间覆盖同一个点的最大数量。

对所有 $[l_i-k,r_i]$ 做扫描线即可。因为是闭区间，所以在左端点加 $1$ ，在右端点 $+1$ 的位置减 $1$ 。

时间复杂度 $\mathcal{O}(n\log n)$ 。

void solve() {
    int n, k;
    cin >> n >> k;

    vector<PII> e;

    FOR(i, 1, n) {
        int l, r;
        cin >> l >> r;
        e.pb({l - k, 1}), e.pb({r + 1, -1});
    }

    sort(all(e));

    int ans = 0, cur = 0;
    for (int i = 0; i < e.sz;) {
        int x = e[i].fi;
        while (i < e.sz && e[i].fi == x) cur += e[i].se, i++;
        ans = max(ans, cur);
    }

    cout << ans << endl;
}

E 小红的好矩阵

法 $\texttt{1}$ ： 知识点：构造、分类讨论、分块

每个连通块大小都必须恰好为 $3$ ，所以总格子数 $2n$ 必须能被 $3$ 整除，即 $n$ 必须是 $3$ 的倍数，否则无解。

把矩阵按每 $3$ 列分成一块。一个 $2\times 3$ 块内要被分成两个大小为 $3$ 的连通块，典型形态只有横条形和两种 L 形。

L 形块之间不会跨块连通，因此每个块可以独立取两种翻转方向的较小代价；横条形会沿相邻块横向连通，所以必须按块交替颜色，只需枚举第一块是 000/111 还是 111/000。四类方案取最小值即可。

时间复杂度 $\mathcal{O}(n)$ 。

void solve() {
    int n;
    cin >> n;
    string s1, s2;
    cin >> s1 >> s2;

    if (n % 3 != 0) {
        cout << -1 << endl;
        return;
    }

    int m = n / 3;

    int costA = 0, costB = 0, costC0 = 0, costC1 = 0;

    auto calc = [&](int l, string top, string bot) -> int {
        int c = 0;
        for (int k = 0; k < 3; k++) {
            if (s1[l + k] != top[k]) c++;
            if (s2[l + k] != bot[k]) c++;
        }
        return c;
    };

    for (int i = 0; i < m; i++) {
        int l = i * 3;

        int a1 = calc(l, "001", "011");
        int a2 = calc(l, "011", "001");

        int b1 = calc(l, "100", "110");
        int b2 = calc(l, "110", "100");

        int c1 = calc(l, "000", "111");
        int c2 = calc(l, "111", "000");

        costA += min(a1, a2);
        costB += min(b1, b2);

        if (i % 2 == 0)
            costC0 += c1, costC1 += c2;
        else
            costC0 += c2, costC1 += c1;
    }

    cout << min({costA, costB, costC0, costC1}) << endl;
}

法 $\texttt{2}$ ： 知识点：状态压缩 DP、轮廓线、并查集

仍然先判 $n$ 是否为 $3$ 的倍数。按列做轮廓线 DP。每一列只有 $4$ 种颜色状态，状态记录最后一列颜色，以及最后一列上、下两个格子所在连通块当前大小。转移到下一列时，用并查集合并两列共 $4$ 个格子中同色且共边的位置；若某个连通块已经离开轮廓线，它之后不可能再扩展，大小必须立刻等于 $3$ ，仍留在轮廓线上的连通块大小不能超过 $3$ 。最后检查轮廓线上剩余连通块是否都为 $3$ 。

时间复杂度 $\mathcal{O}(n)$ 。

struct DSU {
    vector<int> f, siz;
    DSU() {}
    DSU(int n) {
        init(n);
    }
    void init(int n) {
        f.resize(n + 1);
        iota(f.begin(), f.end(), 0);
        siz.assign(n + 1, 1);
    }
    int find(int x) {
        return f[x] == x ? x : f[x] = find(f[x]);
    }
    void merge(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return;
        f[y] = x;
        siz[x] += siz[y];
    }
};

void solve() {
    int n;
    cin >> n;
    vector<string> s(2);
    cin >> s[0] >> s[1];
    if (n % 3) {
        cout << -1 << endl;
        return;
    }
    auto id = [&](int m, int a, int b) { return m * 16 + a * 4 + b; };
    auto cost = [&](int i, int m) {
        int res = 0;
        res += (s[0][i] - '0' != (m & 1));
        res += (s[1][i] - '0' != ((m >> 1) & 1));
        return res;
    };
    auto go = [&](int pm, int a, int b, int nm) {
        DSU d(3);
        int c[4] = {pm & 1, (pm >> 1) & 1, nm & 1, (nm >> 1) & 1};
        if (c[0] == c[1]) d.merge(0, 1);
        if (c[0] == c[2]) d.merge(0, 2);
        if (c[1] == c[3]) d.merge(1, 3);
        if (c[2] == c[3]) d.merge(2, 3);
        int siz[4] = {};
        if (c[0] == c[1]) {
            siz[d.find(0)] += a;
        } else {
            siz[d.find(0)] += a;
            siz[d.find(1)] += b;
        }
        siz[d.find(2)]++;
        siz[d.find(3)]++;
        FOR(i, 0, 3) if (siz[i] > 3) return array<int, 3>{-1, -1, -1};
        int r0 = d.find(2), r1 = d.find(3);
        FOR(i, 0, 3) {
            if (d.find(i) == i && siz[i] && i != r0 && i != r1 && siz[i] != 3) {
                return array<int, 3>{-1, -1, -1};
            }
        }
        return array<int, 3>{1, siz[r0], siz[r1]};
    };
    vector<int> dp(64, INF), ndp(64, INF);
    FOR(m, 0, 3) {
        int a = ((m & 1) == ((m >> 1) & 1) ? 2 : 1);
        int b = a;
        dp[id(m, a, b)] = cost(0, m);
    }
    FOR(i, 1, n - 1) {
        fill(all(ndp), INF);
        FOR(st, 0, 63) {
            if (dp[st] == INF) continue;
            int pm = st / 16, a = st % 16 / 4, b = st % 4;
            FOR(nm, 0, 3) {
                auto t = go(pm, a, b, nm);
                if (t[0] == -1) continue;
                cmin(ndp[id(nm, t[1], t[2])], dp[st] + cost(i, nm));
            }
        }
        dp.swap(ndp);
    }
    int ans = INF;
    FOR(st, 0, 63) {
        if (dp[st] == INF) continue;
        int m = st / 16, a = st % 16 / 4, b = st % 4;
        if ((m & 1) == ((m >> 1) & 1)) {
            if (a == 3) cmin(ans, dp[st]);
        } else {
            if (a == 3 && b == 3) cmin(ans, dp[st]);
        }
    }
    cout << (ans == INF ? -1 : ans) << endl;
}

F 小红的网格路径 II

法 $\texttt{1}$ ： 知识点：动态规划、分段贡献、快速幂

只维护当前最近一个障碍行 $px$ 上方和下方的单位贡献，记为 up、down。遇到下一列障碍 $(nx,ny)$ 时：

若中间隔着空列，先把当前总方案数扩散到所有行，再乘上空列数量对应的 $n$ 的幂；
若两个障碍在相邻列，则直接按 $nx$ 与 $px$ 的相对位置，把上方、下方贡献重新拆分。

这样每个障碍只处理一次。最后若最后一个障碍就在第 $m$ 列，只能从它下方到达终点；否则再经过若干空列扩散到终点列。

时间复杂度 $\mathcal{O}(k\log m)$ 。

void solve() {
    int n, m, k;
    cin >> n >> m >> k;

    vector<PII> a(k);
    for (auto &[y, x] : a) cin >> x >> y;
    sort(all(a));

    if (k == 0) {
        cout << mypow(Z(n), m - 1) << endl;
        return;
    }

    auto step = [&](int px, int py, Z up, Z down, int nx, int ny) {
        int gap = ny - py - 1;
        if (gap >= 1) {
            Z sum = Z(px - 1) * up + Z(n - px) * down;
            Z v = sum * mypow(Z(n), gap - 1);
            return pair<Z, Z>{Z(nx - 1) * v, Z(n - nx) * v};
        } else {
            if (nx < px) {
                Z nu = Z(nx - 1) * up;
                Z nd = Z(px - nx - 1) * up + Z(n - px) * down;
                return pair<Z, Z>{nu, nd};
            } else if (nx == px) {
                Z nu = Z(px - 1) * up;
                Z nd = Z(n - px) * down;
                return pair<Z, Z>{nu, nd};
            } else {
                Z nu = Z(px - 1) * up + Z(nx - px - 1) * down;
                Z nd = Z(n - nx) * down;
                return pair<Z, Z>{nu, nd};
            }
        }
    };

    int x = a[0].se, y = a[0].fi;
    Z up, down;

    if (y == 1) {
        up = 1;
        down = 0;
    } else {
        Z v = mypow(Z(n), y - 2);
        up = Z(x - 1) * v;
        down = Z(n - x) * v;
    }

    int px = x, py = y;

    for (int i = 1; i < k; ++i) {
        int nx = a[i].se, ny = a[i].fi;
        auto [nu, nd] = step(px, py, up, down, nx, ny);
        up = nu;
        down = nd;
        px = nx;
        py = ny;
    }

    Z ans;
    if (py == m) {
        ans = down;
    } else {
        Z sum = Z(px - 1) * up + Z(n - px) * down;
        ans = sum * mypow(Z(n), m - py - 1);
    }

    cout << ans << endl;
}

法 $\texttt{2}$ ： 知识点：动态规划、线段树、坐标压缩

路径不能向左走，因此每一列只会走一段竖直线，再向右进入下一列。设进入某列的行分布为 DP 值，若这一列没有障碍，则所有行的新值都等于上一列所有行的方案和；若这一列障碍在第 $x$ 行，则 $x$ 不能走，障碍上方所有行的新值等于上方方案和，障碍下方所有行的新值等于下方方案和。

由于每列至多一个障碍，DP 值只会在障碍行附近发生分段变化。把所有障碍行和起点行 $1$ 取出做坐标压缩，用线段树维护每个行段的长度和方案和，支持整段赋值与区间求和。连续空列的转移可以一次性用快速幂合并。

时间复杂度 $\mathcal{O}(k(\log k+\log m))$ 。

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<PII> a(k);
    vector<int> xs;
    xs.pb(1);
    for (auto &[y, x] : a) {
        cin >> x >> y;
        xs.pb(x);
    }
    sort(all(a)), sort(all(xs));
    xs.erase(unique(all(xs)), xs.end());
    vector<PII> seg;
    map<int, int> id;
    int lst = 0;
    for (auto x : xs) {
        if (lst + 1 <= x - 1) seg.pb({lst + 1, x - 1});
        id[x] = seg.sz + 1;
        seg.pb({x, x});
        lst = x;
    }
    if (lst + 1 <= n) seg.pb({lst + 1, n});
    int S = seg.sz;
    vector<int> len(S + 1);
    for (int i = 1; i <= S; ++i) {
        len[i] = seg[i - 1].se - seg[i - 1].fi + 1;
    }
    SegTree<Z> tr(S);
    tr.build(len);
    tr.update(id[1], id[1], {1});
    auto full = [&](int d) {
        if (d <= 0) return;
        Z sum = tr.ask(1, S).val;
        tr.update(1, S, {sum * mypow(Z(n), d - 1)});
    };
    auto block = [&](int x) {
        int p = id[x];
        Z l = tr.ask(1, p - 1).val;
        Z r = tr.ask(p + 1, S).val;
        tr.update(1, p - 1, {l});
        tr.update(p, p, {0});
        tr.update(p + 1, S, {r});
    };
    int cur = 1;
    for (auto [y, x] : a) {
        full(y - cur);
        if (y == m) {
            int p = id[x];
            cout << tr.ask(p + 1, S).val << endl;
            return;
        }
        block(x);
        cur = y + 1;
    }
    full(m - cur);
    cout << tr.ask(1, S).val << endl;
}

题解 | 牛客周赛 Round 143

A 小红的区间构造

B 小红的冷门副本

C 小红的因子幂和

D 小红的最佳区间

E 小红的好矩阵

F 小红的网格路径 II