1946(div2)

A. Median of an Array

给你一个由 $n$ 个整数组成的数组 $a$ 。

中位数

数组 $q_{1}, q_{2}, \dots, q_{k}$ 的中位数是数字 $p_{⌈ \frac{k}{2} ⌉}$ ，其中 $p$ 是按非递减顺序排序的数组 $q$ 。例如，数组 $[9, 5, 1, 2, 6]$ 的中位数是 $5$ ，在排序后的数组 $[1, 2, 5, 6, 9]$ 中，索引 $⌈ \frac{5}{2} ⌉ = 3$ 处的数字是 $5$ ；数组 $[9, 2, 8, 3]$ 的中位数是 $3$ ，在排序后的数组 $[2, 3, 8, 9]$ 中，索引 $⌈ \frac{4}{2} ⌉ = 2$ 处的数字是 $3$ 。

您可以选择一个整数 $i$ ( $1 \leq i \leq n$ )，并将 $a_{i}$ 增加 $1$ 。

你的任务是找出增加数组中位数所需的最少操作次数。

注意数组 $a$ 不一定包含不同的数。

void solve() {
    int n;cin >> n;vector<int>a(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    sort(a.begin() + 1, a.begin() + 1 + n);
    int x = count(a.begin() + (n + 1) / 2, a.begin() + 1 + n, a[(n + 1) / 2]);
    cout << x << '\n';
}

B. Maximum Sum

你有一个由 $n$ 个整数组成的数组 $a$ 。

你要对它进行 $k$ 次操作。其中一个操作是选择数组 $a$ 的任意连续子数组（可能为空），并在数组的任意位置插入该子数组的和。

你的任务是找出 $k$ 次这样的操作后数组可能的最大和。

由于这个数字可能非常大，请输出取模为 $10^{9} + 7$ 的答案。

一眼看出答案是 $2^{k} \times r e s - r e s + s u n$ ，但是对于如何找到子数组的最大和( $r e s$ ) P1115 最大子段和 - 洛谷。

for (int i = 1;i <= n;i++)cin >> a[i];
int s = 0, cur = 0, ans = 0;
for (int i = 1;i <= n;i++) {
	s += a[i];cur += a[i];
	cur = max(0, cur);
	ans = max(ans, cur);
}
if (!ans)ans = *(max_element(a.begin() + 1, a.end()));
cout << ans << '\n';

只要之前的累加和大于 0，那么加上后面的值就始终是增加的，否则将该值重置为 0，这样可以求最大字段和。

#define int long long
const int mod = 1e9 + 7;
void solve() {
    int n, k;cin >> n >> k;;
    int s = 0, res = 0, cur = 0;
    for (int i = 1;i <= n;i++) {
        int x;cin >> x;
        s += x;
        cur += x;
        cur = max(0ll, cur);
        res = max(res, cur);
    }
    res %= mod;s %= mod;
    int ans = (qpow(2, k) * res - res + s + mod) % mod;
    cout << ans << '\n';
}

C. Tree Cutting

给出一个有 $n$ 个顶点 $n - 1$ 条边的二叉树，求删去 $k$ 条边后被分成的连通块中最小的连通块的最大大小是多少。

Solution

二分

很典的题目：二分模型：最小值最大化
(待更 $\dots$ )

求树每个点对应的的深度：(BFS)

queue< int >q;vector< int > dis(n + 1), vis(n + 1);
q.push(1);vis[1] = 1;
while (q.size()) {
	int now = q.front();q.pop();
	for (auto i : g[now]) {
		if (vis[i])continue;
		vis[i] = 1;
		dis[i] = dis[now] + 1;
		q.push(i);
	}
}
for (int i = 1;i <= n;i++)cout << dis[i] + 1 << " ";

void solve() {
    int n, k;cin >> n >> k;
    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);
    }
    auto check = [&](int x) {
        int res = 0;
        auto dfs = [&](auto self, int u, int p = 0) ->int {
            int ans = 1;
            for (auto i : g[u]) {
                if (i == p)continue;
                ans += self(self, i, u);
            }
            if (ans >= x) {
                res++;return 0;
            }
            return ans;
            };
        dfs(dfs, 1);
        return res > k;
        };
    int l = 1, r = n + 1;
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (check(mid))l = mid;
        else r = mid - 1;
    }
    cout << l << "\n";
}

D. Birthday Gift

给定一个长度为 $n$ 的数组 $a$ 和一个数字 $x$ ，将数组分为 $k$ 段，要求每一段的异或或 $\leq x$ ，即 $(a_{l_{1}} \oplus a_{l_{1} + 1} \oplus \dots \oplus a_{r_{1}}) | (a_{l_{2}} \oplus a_{l_{2} + 1} \oplus \dots \oplus a_{r_{2}}) | \dots | (a_{l_{k}} \oplus a_{l_{k} + 1} \oplus \dots \oplus a_{r_{k}}) \leq x$

求出最大的 $k$ ,若不存在则输出 $- 1$ 。

Solution

位运算+思维

Codeforces Round 936(A-E讲解)_哔哩哔哩_bilibili

从高位到低位进行枚举

如果 $x$ 该位为 1

若得出答案该位为 0，(在 $a_{i}$ 数组中该位为 1 的个数为偶数)，在 $[i, j)$ $(b i t (a_{i} = 1, a_{j} = 1))$ 之间不能分割，其他位置则都可以分割(因为无论怎样分割都比 $x$ 小了)，遍历完更新答案
若得出答案该位为 1，则无论怎样分割都不影响答案了，

如果 $x$ 该位为 0

若得出答案该位为 0，在 $[i, j)$ 之间一定不能分割(这里不能分割指的是后面的位也不能取 $[i, j)$ )，一旦分割就会使得该位变成 1。
若得出答案该位为 1，这时得出的答案比 $x$ 还大，不满足要求。将当前已经存储的答案输出

void solve() {
    int n, x;cin >> n >> x;
    vector<int> a(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    vector<int> flag(n + 1, 1);
    int ans = -1;
    for (int i = 30;i >= 0;i--) {
        int cnt = 0;//能分割成几组
        if (x & (1 << i)) {//x当前位是1
            int ok = 1;
            for (int j = 1;j <= n;j++) {
                if (a[j] & (1 << i))ok ^= 1;//如果当前位置是1，那后面就不能分割了，直到再次遇到1
                if (ok && flag[j])cnt++;
            }
            if (ok) {//若1的个数是偶数个，则可以修改答案
                ans = max(ans, cnt);
            }
        } else {//x当前位是0
            int ok = 1;
            for (int j = 1;j <= n;j++) {
                if (a[j] & (1 << i))ok ^= 1;
                if (!ok)flag[j] = 0;
            }
            if (!ok) {//如果是奇数个，则直接返回答案
                cout << ans << '\n';return;
            }
        }
    }
    int tmp = 0;
    for (int i = 1;i <= n;i++) {
        if (flag[i]) {
            tmp++;
        }
    }
    cout << max(ans, tmp) << '\n';
}