CF1946

A - Median of an Array

题意：加多少次1可以改变中位数大小。

显然比中位数位置大的与中位数相同的数有多少个就加多少次

#include <bits/stdc++.h>
using namespace std;

int a[100000];
int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        sort(a + 1, a + n + 1);
        int k = (n + 1) / 2, ans = 0;
        for (int i = k; i <= n; i++) {
            if (a[i] == a[k])
                ans++;
        }
        cout << ans << endl;
    }
    return 0;
}

B - Maximum Sum

题意：一个长度为$n$的数组$a$，你可以进行k次操作，每一次操作选一个子段和添加到数组的任意位置，最大化数组总和。

当最大子段和小于$0$时显然不进行操作，当最大子段和大于$0$时不断加入$k$次目前最大子段和。

#include <bits/stdc++.h>
using namespace std;
const long long mod = 1000000007ll;

long long T, a[200010], SUM;
void work() {
    int n, k;
    SUM = 0;
    cin >> n >> k;
    for (int i = 1; i <= n; ++i)
        cin >> a[i], SUM += a[i], SUM %= mod;
    long long ans = 0, sum = 0;
    for (int i = 1; i <= n; ++i) {
        sum += a[i];
        if (sum > ans) {
            ans = sum;
        } else if (sum < 0) {
            sum = 0;
        }
    }
    sum = 0;
    for (int i = 1; i <= k; ++i) {
        sum = (sum + ans) % mod;
        ans = (ans + ans) % mod;
    }
    cout << (SUM + sum + 2ll * mod) % mod << endl;
}

int main() {
    cin >> T;
    while (T--)
        work();
    return 0;
}

C - Tree Cutting

题意：一棵$n$个点的树，找出最大的$x$，使得在这棵树删掉$k$条边时，每个剩余的联通块大小至少为$x$

对于每一个$x$，我们可以考虑在剩余联通块大小至少为$x$时，可以删掉几条边。不难发现，$x$变大时，$k$变小，$x$变小时，$k$变大。所以可以考虑二分$x$，进行检验是否能删到至少k条边。

#include <bits/stdc++.h>
using namespace std;

int n, k;
vector<int> e[100010];

void add(int x, int y) {
    e[x].emplace_back(y);
    e[y].emplace_back(x);
}

int cnt[100010], siz[100010];
// cnt: 可删边的个数
// siz: 不包含已经割掉的子树大小的大小
void dfs(int fa, int u, int x) {
    cnt[u] = 0;
    siz[u] = 1;
    for (auto v: e[u]) {
        if (v == fa) continue;
        dfs(u, v, x);
        cnt[u] += cnt[v];
        if (siz[v] >= x) {
            cnt[u]++;
            siz[v] = 0;
        }
        siz[u] += siz[v];
    }
}

bool check(int num) {
    dfs(-1, 1, num);
    if (siz[1] >= num) cnt[1]++;
    if (cnt[1] >= k + 1) return true;
    return false; 
}

void work() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        e[i].clear();
    for (int i = 1, x, y; i < n; i++) {
        cin >> x >> y;
        add(x, y);
    }
    int l = 0, r = n, ans = 0;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid)) {
            l = mid + 1;
            ans = mid;
        } else r = mid - 1;
    }
    cout << ans << endl;
}

int main() {
    int T;
    cin >> T;
    while (T--)
        work();
    return 0;
}

D - Birthday Gift

题意：有一个长度为$n$的数组$a$，还有一个数字$x$，找到最大的$k$，使得可以将$a$划分成$k$组，同时满足:

$$(a_{l_1} \oplus\ a_{l_1 +1} \oplus\ …\ \oplus\ a_{r_1}) |(a_{l_2} \oplus\ a_{l_2 +1} \oplus\ …\ \oplus\ a_{r_2})|…|(a_{l_k} \oplus\ a_{l_k +1} \oplus\ …\ \oplus\ a_{r_k}) \le x$$

首先对$a$进行异或前缀和，然后从二进制高位到低位逐位进行判断。异或前缀和为$S_i$。

则以上式子转化为：

$$(S_{r_1}\ \oplus\ S_{r_2})|(S_{r_2}\ \oplus\ S_{r_3})|…|(S_{r_{n-1}}\ \oplus\ S_{r_{n}}) \le x$$

对于每一个二进制位，x只有两种情况。

x = 1时，如果能在$S_{r_i}$取到k个0，那么显然合法，若不行则比较下一位

x = 0时，如果凑不到k个0，那么则说明这一位会取1则不合法。如果能凑到，就与上一位合并，继续比较下一位。

设$S_1$是这一轮之前的使得结果与x相等的$r_i$集合，$S_2$为当前位为0的集合，$S_3$是这一轮与上一轮同时合法的集合，即$S_3 = S_1 \ \And \ S_2$。那么通过统计$S_3$为1的数量，即可统计出这一位能划分出多少组。

#include <bits/stdc++.h>
using namespace std;

long long n, x;
long long a[200010];
vector<bool> s1, s2, s3;

bool check(int mid) {
    for (int i = 1; i <= n; i++)
        s1[i] = true;
    int cnt;
    for (long long b = 32; b >= 0; b--) {
        for (int i = 0; i <= n; i++)
            s2[i] = false;
        for (int i = 1; i <= n; i++) {
            if (!(a[i] & (1ll << b)))
                s2[i] = true;
        }
        cnt = 0;
        for (int i = 1; i <= n; i++) {
            s3[i] = s1[i] & s2[i];
            cnt += s3[i];
        }
        if (x & (1ll << b)) {
            if (cnt >= mid && s3[n])
                return true;
        } else {
            if (cnt < mid || !s3[n])
                return false;
            for (int i = 1; i <= n; i++)
                s1[i] = s3[i];
        }
    }
    return true;
}

void work() {
    cin >> n >> x;
    s1.clear();
    s2.clear();
    s3.clear();
    s1.reserve(n + 10);
    s2.reserve(n + 10);
    s3.reserve(n + 10);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] = a[i] ^ a[i - 1];
    }
    long long l = 0, r = n, ans = 0, mid;
    while (l <= r) {
        mid = (l + r) >> 1ll;
        if (check(mid)) {
            l = mid + 1;
            ans = mid;
        } else r = mid - 1;
    }
    if (ans != 0)
        cout << ans << endl;
    else cout << -1 << endl;
    return ;
}

int main() {
    int T;
    cin >> T;
    while (T--)
        work();
    return 0;
}

E - Girl Permutation

题意：有一个长度为$n$的排列，给定前缀最大值的索引$P_i$和后缀最大值的索引$S_i$，求满足条件的排列数量。

首先，可以发现$P_1 = 1, P_{m_1}=S_1,S_{m_2}=n$，若不满足则不存在这样的排列。

然后对于整个排列的最大值的位置是已知的，即$P_{m_1}=S_1$这个位置。

先考虑最大值位置左边，右边可以通过类似的计算得出结果。

对于这个位置左边，每一个$P_i$和$P_{i+1}$之间存在的空隙影响这排列个数。我们可以从$P_{m_1}$往左看，每个$P_i$和$P_{i+1}$间有$P_{i+1}-P_i-1$个数，同时在$P_{i+1}$左边可取的数为$P_{i+1}-2$个（除去$P_i$和$P_{i+1}$这两个数），所以此时的方案数是

$$\tbinom{P_{i+1}-2}{P_{i+1}-P_{i}-1} \times ({P_{i+1}-P_{i}-1})!$$​

化简得：

$$\frac{(P_{i+1}-2)!}{(P_{i}-1)!}$$

同理可计算出右边方案数为：

$$\frac{(n-S_i-1)!}{(n-S_{i+1})!}$$

最后再乘上$\binom{n-1}{S_1-1}$即可

#include <bits/stdc++.h>
using namespace std;

const long long mod = 1000000007ll;
long long fac[200010], invFac[200010];

long long qpow(long long x, long long p) {
    if (x == 0) return 0;
    if (x == 1 || p == 0) return 1;
    long long ans = 1;
    while (p) {
        if (p & 1)
            ans = ans * x % mod;
        x = x * x % mod;
        p >>= 1ll;
    }
    return ans;
}

void init() {
    fac[0] = 1;
    for (int i = 1; i <= 200000; i++)
        fac[i] = (fac[i - 1] * i) % mod;
    invFac[200000] = qpow(fac[200000], mod - 2);
    for (int i = 199999; i >= 0; i--)
        invFac[i] = invFac[i + 1] * (i + 1) % mod;
}

long long C(int n, int m) {
    return (fac[n] * (invFac[n - m] * invFac[m] % mod) % mod);
}

void work() {
    int n, m1, m2;
    cin >> n >> m1 >> m2;
    vector<int> p(m1 + 1), s(m2 + 1);
    for (int i = 1, x; i <= m1; i++)
        cin >> p[i];
    for (int i = 1, x; i <= m2; i++)
        cin >> s[i];
    if (p[m1] != s[1] || p[1] != 1 || s[m2] != n) {
        cout << "0\n";
        return ;
    }
    long long ans1 = 1, ans2 = 1;
    for (int i = m1 - 1; i >= 1; i--) {
        ans1 = (ans1 * fac[p[i + 1] - 2] % mod) * invFac[p[i] - 1] % mod;
    }
    for (int i = 1; i < m2; i++) {
        ans2 = (ans2 * fac[n - s[i] - 1] % mod) * invFac[n - s[i + 1]] % mod;
    }
    cout << (ans1 * ans2 % mod) * C(n - 1, s[1] - 1) % mod << endl;
}

int main() {
    init();
    int T;
    cin >> T;
    while (T--)
        work();
    return 0;
}