牛客周赛 Round 144 题解

已向 #define int long long 屈服

A 我是谁？

知识点：字符串、计数。

只需要统计 $\texttt{A,B,C,D}$ 四种字符出现次数，判断是否四个计数完全相同（即最大值等于最小值）即可。

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

void solve() {
    int n;
    string s;
    cin >> n >> s;
    vector<int> a(4);
    for (auto v : s) a[v - 'A']++;
    cout << (max(all(a)) == min(all(a)) ? "Yes" : "No") << endl;
}

B 我是清楚姐姐

法 $\texttt{1}$ ：

知识点：构造、贪心、最大公约数。

考虑让第 $i$ 列的最大公约数为 $i$ 。最简单的办法是先把第一行放成 $1,2,\dots,n$ ，这样第 $i$ 列已经包含了 $i$ ，只要之后放进第 $i$ 列的数都能被 $i$ 整除，那么该列的 $\gcd$ 就一定恰好为 $i$ 。

于是问题转化为：把 $n+1\sim n^2$ 这些数填到若干列中，数字 $x$ 只能填入满足 $i\mid x$ 的第 $i$ 列，且每列最终有 $n$ 个数。

从大到小枚举 $x$ ，每次优先放入当前还能容纳它的最大编号列。编号越大的列可用倍数越少，更应该优先满足；若当前数字找不到任何还有空位的因子列，则无法完成构造，输出 $-1$ 。否则所有列被填满后，列 gcd 分别为 $1,2,\dots,n$ ，满足要求。

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

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> a(n, vector<int>(n));
    for (int i = 0; i < n; ++i) a[0][i] = i + 1;
    int now = n * n;
    vector<int> cnt(n, 1);
    while (now > n) {
        bool f = 1;
        for (int i = n; i >= 1; --i)
            if (__gcd(now, i) == i && cnt[i - 1] != n) {
                a[cnt[i - 1]][i - 1] = now, now--, cnt[i - 1]++;
                f = 0;
                break;
            }
        if (f) {
            cout << -1 << endl;
            return;
        }
    }
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j) cout << a[i][j] << " \n"[j == n - 1];
}

法 $\texttt{2}$ ：

知识点：打表

不难发现只有当 $n=1$ 、 $n=2$ 或 $n=3$ 才有解。

如果你需要一个证明的话：

打表发现 $n=1,2,3$ 时有解，接下来证明当 $n\geq 4$ 时无解：

$n=2k,\ k\in Z$ ： $\gcd$ 为偶数的列共有 $m$ 个： $2,4,...,n$ 。这些列里的数全都必须是偶数，所以它们一共要用掉 $m \cdot n = n^2/2$ 个偶数，也就是说，所有偶数都已经被这些列用光了。

但 $\gcd$ 为 $n-1$ 的那一列， $n-1$ 是奇数。在 $1\sim n^2$ 中， $n-1$ 的倍数一共有
$\left\lfloor \frac{n^2}{n-1}\right\rfloor = n+1$
个，其中奇数倍最多只有
$\left\lceil \frac{n+1}{2}\right\rceil = \frac n2+1$
个，所以这一列至少要用
$n-\left(\frac n2+1\right)=\frac n2-1>0$
个偶数，矛盾。
$n=2k+1,\ k\in Z$ ： $\gcd$ 为偶数的列有 $m$ 列： $2,4,\dots,n-1$ 。这 $m$ 列全都只能放偶数，所以一共用掉 $m\cdot n = \frac{n(n-1)}2$ 个偶数。

总偶数个数是
$\frac{n^2-1}{2}=\frac{n(n-1)}2+\frac{n-1}{2}$
所以还剩 $\frac{n-1}{2}$ 个偶数。

而 $\gcd$ 为 $n$ 的那一列，因为 $n$ 是奇数，它的 $n$ 个倍数里，偶数倍正好有 $\frac{n-1}{2}$ 个，所以它会把这剩下的偶数全部用完。但 $n\ge 5$ 时， $n-2$ 这列也存在，而且 $n-2$ 也是奇数。 $n-2$ 的倍数总数至多为

\left\lfloor \frac{n^2}{n-2}\right\rfloor \le n+3

所以奇数倍最多只有 $\frac{n+3}{2}<n$ 个，不够填满一整列，因此它至少也需要一个偶数。可现在偶数已经被用光了，矛盾。

所以 $n\geq 4$ 都无解。

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

void solve() {
    int n;
    cin >> n;
    if (n == 1) cout << 1 << endl;
    else if (n == 2) cout << "1 2\n3 4" << endl;
    else if (n == 3) cout << "1 2 3\n5 4 6\n7 8 9" << endl;
    else cout << -1 << endl;
}

C 其实我是小苯

法 $\texttt{1}$ ：

知识点：数学、分类讨论、大整数输出。

$n$ 位正整数的取值范围是 $[10^{n-1},10^n-1]$ 。不妨令 $n\ge m$ 。

最小值看两个区间是否相交：

若 $n=m$ ，可以取 $a=b$ ，最小值为 $0$ 。
若 $n=m+1$ ，最小值为 $10^m-(10^m-1)=1$ 。
否则最小值为 $10^{n-1}-(10^m-1)$ ，按十进制直接输出即可。

最大值一定由较大的 $n$ 位最大数和较小的 $m$ 位最小数相减得到，即

(10^n-1)-10^{m-1}.

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

void solve() {
    int n, m;
    cin >> n >> m;
    if (n < m) swap(n, m);
    if (n == m) {
        cout << 0;
    } else if (n - 1 == m) {
        cout << 1;
    } else {
        for (int i = m + 1; i < n; ++i) cout << 9;
        for (int i = 1; i < m; ++i) cout << 0;
        cout << 1;
    }
    cout << " ";
    for (int i = m; i < n; ++i) cout << 9;
    cout << 8;
    for (int i = 1; i < m; ++i) cout << 9;
    cout << endl;
}

法 $\texttt{2}$ ：

知识点： $\texttt{Python}$ 。

$\texttt{Python}$ 做这种题目就是很强，推导过程同上。

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

n, m = map(int, input().split())
if n < m:
    n, m = m, n
if n == m:
    print(0, pow(10, n) - 1 - pow(10, m - 1))
else:
    print(pow(10, n - 1) - pow(10, m) + 1, pow(10, n) - 1 - pow(10, m - 1))

D 骗你的，其实我是小红

知识点：位运算、同余计数、组合计数。

因为 $k$ 是 $2$ 的非负整数次幂，设 $k=2^t$ 。一个数能被 $k$ 整除，等价于低 $t$ 位全为 $0$ 。因此

i\oplus j

是 $k$ 的倍数，当且仅当 $i,j$ 的低 $t$ 位完全相同，也就是 $i\equiv j\pmod k$ 。

所以只需要统计区间 $[l,r]$ 中每个模 $k$ 余数出现了多少次。设区间长度为 $n=r-l+1$ ，每个余数出现次数只可能是 $\lfloor n/k\rfloor$ 或 $\lfloor n/k\rfloor+1$ 。令 $b=\lfloor n/k\rfloor,e=n\bmod k$ ，答案为

e\binom{b+1}{2}+(k-e)\binom{b}{2}.

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

void solve() {
    int l, r, k;
    cin >> l >> r >> k;
    int n = r - l + 1, b = n / k, e = n % k;
    auto S = [&](int x) { return x * (x - 1) / 2; };
    cout << e * S(b + 1) + (k - e) * S(b) << endl;
}

E 好吧，我是Bingbong

知识点：树、 $\texttt{DFS}$ 、前缀贡献。

注水过程本质上是一个由管道高度决定的 $\texttt{DFS}$ 顺序：对于同一个瓶子的所有子树，管道位置越低，越先被完全灌满。一个节点 $u$ 的瓶子达到满水时， $u$ 的整棵子树也已经全部注满。

先计算

siz_u=\sum_{x\in subtree(u)}h_x,

表示子树 $u$ 全部灌满需要的水量。

再设 $st_u$ 表示开始灌入子树 $u$ 之前，系统中已经存在的水量。对节点 $u$ ，按管道高度从小到大枚举儿子 $v$ 。若当前儿子管道高度为 $w_v$ ，且此前已经灌满的较低儿子子树总量为 pre，则

st_v=st_u+w_v+pre.

于是节点 $v$ 自己达到满水时，总水量为

ans_v=st_v+siz_v.

根节点没有外部前缀， $st_1=0$ ，答案为整棵树容量和。

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

void solve() {
    int n;
    cin >> n;
    vector<int> h(n + 1), siz(n + 1), st(n + 1), ans(n + 1);
    for (int i = 1; i <= n; ++i) cin >> h[i];
    vector<int> fa(n + 1, 0);
    for (int i = 2; i <= n; ++i) cin >> fa[i];
    vector<int> w(n + 1, 0);
    for (int i = 2; i <= n; ++i) cin >> w[i];
    vector<vector<PII>> g(n + 1);
    for (int i = 2; i <= n; ++i) g[fa[i]].push_back({w[i], i});
    for (int i = 1; i <= n; ++i) sort(all(g[i]));
    for (int i = 1; i <= n; ++i) siz[i] = h[i];
    for (int i = n; i >= 2; --i) siz[fa[i]] += siz[i];
    st[1] = 0, ans[1] = siz[1];
    for (int u = 1; u <= n; ++u) {
        int pre = 0;
        for (auto [ww, v] : g[u]) st[v] = st[u] + ww + pre, ans[v] = st[v] + siz[v], pre += siz[v];
    }
    for (int i = 1; i <= n; ++i) cout << ans[i] << " \n"[i == n];
}

F 牛魔！

法 $\texttt{1}$ ：

知识点：树上贪心、异或操作、构造性调整。

把根的深度设为 $0$ 。若选择深度至少为 $2$ 的节点 $u$ 作为操作中的孩子节点，则一次操作会同时翻转 $u,fa_u,fa_{fa_u}$ 。从叶子往根处理时，处理到某个深度 $\ge 2$ 的节点 $u$ 后，之后不会再影响它的子树，因此若 $a_u=0$ ，就直接执行这次操作把它变成 $1$ 。这样可以保证所有深度至少为 $2$ 的节点最终全为 $1$ ，祖先受到的影响留到之后再处理。

这一步结束后，只有根和根的儿子可能不是 $1$ 。如果根已经是 $1$ ，再为了调整根儿子而翻转某条链，至少会让一个已经为 $1$ 的深层节点变成 $0$ ，不会变优。

只有一种情况还能多赚 $1$ ：根为 $0$ ，某个根儿子也为 $0$ ，并且该儿子所在子树中存在一个深度 $\equiv 2\pmod 3$ 的节点。沿这条根到该节点的链组合若干次操作，可以做到只翻转根、这个根儿子和该深层节点。这样两个 $0$ 变成 $1$ ，一个深层 $1$ 变成 $0$ ，总和增加 $1$ 。

因此先用自底向上的贪心统计当前答案，再判断上述额外调整是否存在即可。

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

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    vector<vector<int>> g(n + 1);
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v), g[v].push_back(u);
    }
    vector<int> fa(n + 1), dep(n + 1), bel(n + 1), ord, st;
    st.push_back(1);
    fa[1] = 0;
    while (st.size()) {
        int u = st.back();
        st.pop_back();
        ord.push_back(u);
        for (auto v : g[u]) {
            if (v == fa[u]) continue;
            fa[v] = u, dep[v] = dep[u] + 1, bel[v] = (u == 1 ? v : bel[u]);
            st.push_back(v);
        }
    }
    vector<int> ok(n + 1, 0);
    for (int i = n - 1; i >= 0; --i) {
        int u = ord[i];
        if (dep[u] < 2) continue;
        if (dep[u] % 3 == 2) ok[bel[u]] = 1;
        if (a[u] == 0) a[u] ^= 1, a[fa[u]] ^= 1, a[fa[fa[u]]] ^= 1;
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) ans += a[i];
    if (a[1] == 0) {
        for (auto v : g[1]) {
            if (fa[v] == 1 && a[v] == 0 && ok[v]) {
                ++ans;
                break;
            }
        }
    }
    cout << ans << endl;
}

法 $\texttt{2}$ ：

知识点：树、操作等价性、子树 $\texttt{DP}$

一次操作会同时翻转 $fa(i)、i、son(i)$ 三个点，把树按深度 $\mod 3$ 分层后，这三个点一定分别落在三层里，所以操作本质上只是在改三层里 $1$ 的奇偶性。

于是对每个子树，只需要关心三层分别有多少个点，以及三层 $1$ 的奇偶关系。

设三层奇偶为 $P0,P1,P2$ ，那么 $P1\oplus P2$ 是子树内部不变量， $P0\oplus P2$ 只和这个子树向外接出去的状态有关，所以每个根儿子子树最后只需要算出一个二进制状态 $q = P0\oplus P2$ ，以及在这个状态下最多能放多少个 $1$ 。

对子树里某一层:

如果这一层有 $cnt$ 个点，要求最终 $1$ 的奇偶性为 $p$ ，那这一层最多能取 $cnt$ 个 $1$ 。
若奇偶不对就少留一个变成 $cnt-1$ 。
如果 $cnt=0$ 还要求奇数那就是非法。

所以对每个根儿子子树 $\texttt{DFS}$ 一遍，统计三层点数 $cnt[0/1/2]$ ，再枚举 $P2$ ，由 $P1 = P2\oplus Ic$ 推出 $P1$ ，由 $P0 = q \oplus P2$ 推出 $P0$ ，就能得到这棵子树在状态 $q$ 下的最优贡献 $M[q]$ 。不同儿子子树之间只需要按异或合并这些 $q$ ，设 $dp[s]$ 表示处理完若干棵子树后，它们的 $q$ 异或和为 $s$ 时最多能得到多少个 $1$ ，那么有

dp[s\oplus q] = max(dp[s\oplus q], dp[s] + M[q])

最后根节点自身也由全局异或状态决定，直接把它补上后取最大值就是答案。

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

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    vector<vector<int>> g(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        g[u].pb(v), g[v].pb(u);
    }
    int I = a[1], dp[2] = {0, -INF};
    auto get = [](int count, int req) {
        if (count == 0) return req == 0 ? 0 : -INF;
        return count - (count % 2 != req);
    };
    for (auto fc : g[1]) {
        int cnt[3] = {0, 0, 0}, Ic = 0;
        auto dfs = [&](auto &self, int u, int p, int d) -> void {
            cnt[d % 3]++;
            if (d % 3 != 1) I ^= a[u];
            if (d % 3 != 0) Ic ^= a[u];
            for (int v : g[u])
                if (v != p) self(self, v, u, d + 1);
        };
        dfs(dfs, fc, 1, 1);
        int M[2] = {-INF, -INF};
        for (int P2 = 0; P2 <= 1; P2++) {
            int P1 = P2 ^ Ic;
            for (int P0 = 0; P0 <= 1; P0++) {
                int q = P0 ^ P2, ones = get(cnt[0], P0) + get(cnt[1], P1) + get(cnt[2], P2);
                M[q] = max(M[q], ones);
            }
        }
        int ndp[2] = {-INF, -INF};
        for (int S = 0; S <= 1; S++)
            for (int q = 0; q <= 1; q++) ndp[S ^ q] = max(ndp[S ^ q], dp[S] + M[q]);
        dp[0] = ndp[0], dp[1] = ndp[1];
    }

    int ans = max(dp[0] + (I ^ 0), dp[1] + (I ^ 1));
    cout << ans << endl;
}

备注

#define int long long
constexpr int INF = 1e9 + 7;
int __INIT__ = []() {
    ios::sync_with_stdio(0), cin.tie(0);
    cout << fixed << setprecision(15);
    return 0;
}();

题解 | 牛客周赛 Round 144

A 我是谁？

B 我是清楚姐姐

C 其实我是小苯

D 骗你的，其实我是小红

E 好吧，我是Bingbong

F 牛魔！

备注