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$ 取最小即可。