小白月赛 Round 132 题解

A 出题需要 rating

知识点：模拟

模拟一下分数变化即可。

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

void solve() {
    int n, c = 1000;
    cin >> n;
    vector<int> s(7);
    for (int i = 0, x; i < n; ++i) {
        cin >> x;
        c += x;
        if (c < 700)
            s[0]++;
        else if (c < 1100)
            s[1]++;
        else if (c < 1500)
            s[2]++;
        else if (c < 2000)
            s[3]++;
        else if (c < 2400)
            s[4]++;
        else if (c < 2800)
            s[5]++;
        else
            s[6]++;
    }
    for (int i = 0; i < 7; ++i) cout << s[i] << " \n"[i == 6];
}

B 出题需要语文

知识点：贪心、模拟

每套题必须包含 $\texttt{A}$ 到 $\texttt{F}$ 各一道，因此每个难度之间互不影响。为了让平均质量尽可能高，对于每个难度，只需要选择质量分不低于 $60$ 的题中质量最高的一道。

设最终选出的 $6$ 道题质量和为 $sum$ ，平均质量不低于 $70$ 等价于 $sum \ge 420$ 。如果某个难度没有可选题，或者每个难度都选最优后仍然 $sum < 420$ ，则无解；否则输出这 $6$ 道题的编号即可。

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

void solve() {
    int n;
    cin >> n;
    vector<PII> a(6);
    for (int i = 1; i <= n; ++i) {
        char c;
        int x;
        cin >> c >> x;
        if (x >= 60 && x > a[c - 'A'].fi) a[c - 'A'] = {x, i};
    }
    int sum = 0;
    for (auto [u, v] : a) {
        if (!u) {
            cout << -1 << endl;
            return;
        }
        sum += u;
    }
    if (sum < 420) {
        cout << -1 << endl;
        return;
    }
    for (auto [u, v] : a) cout << v << " ";
    cout << endl;
}

C 出题需要加法

知识点：二进制、前缀计数

可合数形如 $2^x+2^y$ 。由于二进制表示唯一，当 $x \ne y$ 时结果的二进制中恰好有两个 $1$ ；当 $x=y$ 时结果为 $2^{x+1}$ ，也对应唯一的一种合成方式。因此只需枚举所有 $x,y$ ，统计不超过某个上界的可合数个数。

记 $f(n)$ 表示 $[0,n]$ 中可合数的数量，则答案为：

f(R)−f(L−1)

枚举时令 $y \le x$ ，避免重复统计同一个数，枚举到 $62$ 即可。

时间复杂度 $\mathcal{O}(T \log^2 R)$

void solve() {
    int l, r;
    cin >> l >> r;
    auto calc = [&](int n) {
        int res = 0;
        for (int i = 0; i <= 62; ++i) {
            for (int j = 0; j <= i; ++j) {
                int x = (1LL << i) + (1LL << j);
                if (x <= n) ++res;
            }
        }
        return res;
    };
    cout << calc(r) - calc(l - 1) << endl;
}

当然也可以预处理所有可合数，然后二分查找。

时间复杂度 $\mathcal O(62^2+Tlog(2000))$

vector<int> vals;
 
void init() {
    for (int i = 0; i <= 62; ++i) {
        for (int j = 0; j <= i; ++j) {
            int val = (1LL << i) + (1LL << j);
            vals.pb(val);
        }
    }
    sort(vals);
}
 
void solve() {
    int l, r;
    cin >> l >> r;
    auto calc = [&](int n) { return upper_bound(all(vals), n) - vals.begin(); };
    cout << calc(r) - calc(l - 1) << endl;
}

D 出题需要构造

知识点：构造、循环移位

一次操作选出 $k$ 个格子的值，实际会把这些值在矩阵中出现的所有位置都放入小球。因此我们只需要构造一个矩阵，使得选定的若干个数字出现的位置在每行、每列中都恰好有 $2$ 个。

若 $n \ne m$ ，总小球数从行看为 $2n$ ，从列看为 $2m$ ，必须相等，因此无解。若 $n=m=1$ ，一行一列不可能都有 $2$ 个小球，也无解。

当 $n=m=2$ 时，直接全填 $1$ ，选择数字 $1$ ，每行每列都有 $2$ 个。

当 $n=m\ge 3$ 时，构造循环矩阵：

a_{i,j}=(i+j)\pmod{n+1}

每个数字在每行、每列中都恰好出现一次，因此选择任意两个不同数字即可让每行、每列恰好有 $2$ 个小球。

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

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

    if (n != m || n < 2) {
        cout << "NO" << endl;
        return;
    }

    cout << "YES" << endl;
    cout << 2 << endl;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << (i + j) % n + 1 << " \n"[j == n - 1];
        }
    }
}

E 出题需要魔法

知识点：单调栈、补集计数

考虑固定位置 $i$ 。在一个包含 $i$ 的子区间 $[l,r]$ 中， $p_i$ 可见当且仅当：

左侧 $[l,i-1]$ 中没有比 $p_i$ 大的数；
或右侧 $[i+1,r]$ 中没有比 $p_i$ 大的数。

反过来， $p_i$ 不可见，当且仅当左右两边都存在比 $p_i$ 大的数。

设：

$L_i$ 表示 $i$ 左边最近的、满足 $p_{L_i}>p_i$ 的位置，若不存在则为 $0$ ；
$R_i$ 表示 $i$ 右边最近的、满足 $p_{R_i}>p_i$ 的位置，若不存在则为 $n+1$ 。

包含位置 $i$ 的子区间总数为：

i\times (n-i+1)

若 $p_i$ 不可见，则区间必须满足 $l \le L_i$ 且 $r \ge R_i$ ，这样的区间数量为：

L_i\times(n-R_i+1)

因此答案为：

i\times (n-i+1)-L_i\times(n-R_i+1)

$L_i,R_i$ 可以用单调栈分别从左到右、从右到左求出。

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

void solve() {
    int n;
    cin >> n;
    vector<int> p(n + 1), L(n + 1), R(n + 1);
    for (int i = 1; i <= n; ++i) cin >> p[i];
 
    vector<int> st;
 
    for (int i = 1; i <= n; ++i) {
        while (!st.empty() && p[st.back()] < p[i]) st.pob();
        L[i] = st.empty() ? 0 : st.back();
        st.pb(i);
    }
 
    st.clear();
 
    for (int i = n; i >= 1; --i) {
        while (!st.empty() && p[st.back()] < p[i]) st.pob();
        R[i] = st.empty() ? n + 1 : st.back();
        st.pb(i);
    }
 
    for (int i = 1; i <= n; ++i) cout << i * (n - i + 1) - L[i] * (n - R[i] + 1) << " \n"[i == n];
}

F 出题需要树论

知识点：树形 $\texttt{DP}$ 、 $\texttt{DFS}$ 、前后缀最大值

考虑选择以节点 $u$ 为根的子树。对于不在该子树内的叶子，它到根的路径和不变；对于在该子树内的叶子，只有从 $u$ 到该叶子的这一段权值会被异或上 $x$ ，而 $u$ 的父亲到根这一段保持不变。

先以 $1$ 为根遍历整棵树，求出每个叶子原本的根到叶路径和。一个节点子树内的所有叶子在这个顺序中是连续的一段，记为 $[L_u,R_u]$ 。

再自底向上求：

down_{u} = \max_{leaf\ v\in subtree(u)}\sum_{t\in path(u,v)}(a_t\oplus x)

也就是如果选择 $u$ 的子树，子树内部到叶子的最大贡献。

对于每个节点 $u$ ：

子树外叶子的最大原路径和，可以用叶子路径和的前缀最大值、后缀最大值求出；
子树内叶子的最大新路径和为：

pre_{fa_u} + down_u

其中 $pre_{fa_u}$ 是根到 $u$ 父亲的原路径和，若 $u=1$ 则为 $0$ 。

于是选择 $u$ 的答案为两者最大值，对所有 $u$ 取最小即可。

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

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

    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].pb(v), g[v].pb(u);
    }

    vector<int> pa(n + 1), order, pre(n + 1), st;
    st.pb(1);
    pre[1] = a[1];

    while (st.size()) {
        auto u = st.back();
        st.pob();
        order.pb(u);
        for (auto v : g[u]) {
            if (v == pa[u]) continue;
            pa[v] = u;
            pre[v] = pre[u] + a[v];
            st.pb(v);
        }
    }

    vector<bool> leaf(n + 1);
    for (int u = 1; u <= n; ++u) leaf[u] = (n == 1 || (u != 1 && g[u].size() == 1));

    vector<int> id(n + 1, -1), val;
    for (auto u : order) {
        if (leaf[u]) {
            id[u] = val.size() + 1;
            val.pb(pre[u]);
        }
    }

    vector<int> down(n + 1), L(n + 1), R(n + 1);

    for (int i = order.size() - 1; i >= 0; --i) {
        int u = order[i];
        if (leaf[u]) {
            L[u] = R[u] = id[u];
            down[u] = (a[u] ^ x);
        } else {
            int l = n, r = -1;
            int mx = -INF;
            for (int v : g[u]) {
                if (v == pa[u]) continue;
                l = min(l, L[v]);
                r = max(r, R[v]);
                mx = max(mx, down[v]);
            }
            L[u] = l;
            R[u] = r;
            down[u] = (a[u] ^ x) + mx;
        }
    }

    int m = val.size();
    vector<int> premx(m + 1, -INF), sufmx(m + 2, -INF);
    for (int i = 1; i <= m; ++i) premx[i] = premx[i] = max(premx[i - 1], val[i - 1]);
    for (int i = m; i >= 1; --i) sufmx[i] = max(sufmx[i + 1], val[i - 1]);

    int ans = -INF;
    for (int u = 1; u <= n; ++u) {
        int cur = max(max(premx[L[u] - 1], sufmx[R[u] + 1]), (u == 1 ? 0 : pre[pa[u]]) + down[u]);
        ans = (u == 1 ? cur : min(ans, cur));
    }

    cout << ans << endl;
}

题解 | 小白月赛 Round 132

A 出题需要 rating

B 出题需要语文

C 出题需要加法

D 出题需要构造

E 出题需要魔法

F 出题需要树论