Codeforces/Round936Div2

本场摘要

毕业前抱着玩玩的心态打了若干场正式赛，没有训练也没有补题，结果分掉得很严重，都一路俯冲到蓝名去了。。。

后面就没太敢报正式赛了，倒是陪老同学 vp 几场找了找手感。

这一场的Div2是今年的第一场正式赛，最后的 rank 为 第 172 名，rating 从 1733 涨到了 1873，比赛时通过了 ABCDE 五个题目。

下来补完 F 后，综合来看，这场感觉算是中等偏下的难度，也没有让人眼前一亮的题目。期待后续遇到这种偏简单的场次能 AK 一回吧。

传送门：

题目

C.

题目大意：

给定一颗大小为 n 的树，去除其中刚好 k 条边，要使得每个联通块的大小都要至少为 x 个点，求 x 的最大值是多少。

题解：

十分典的一个贪心题目，先二分 x 的值，然后进行深度优先搜索。一旦当前的子树大小大于了 x，则切掉这个子树与其父亲相连的边，并更新其父节点的大小。如果最后能切掉大约等于 k 条边，则说明当前 x 是可行的。

这个策略可以用反证法证明其正确性。如果遇到这个子树大小大于 x 不切，并且存在另一种合乎要求的切法的话，我们可以在这个新切法的基础上，切掉当前子树与其父相连的边，会得到一个新的小联通块，然后把这个小联通块附着在其他已有的大于 x 的联通块上。

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll, int> pli;
typedef std::pair<ll, ll> pll;
typedef double db;
typedef long double ldb;
const int maxN = 2e5 + 5;
std::vector<int> edge[maxN];
int n, k, size[maxN];
int tot;
int tryCut(int u, int p, int x) {
    int res = 0;
    size[u] = 1;
    for (auto v : edge[u]) {
        if (v == p) continue;
        res += tryCut(v, u, x);
        if (size[v] >= x &&  tot - size[v] >= x){
            res++;
            tot -= size[v];
        } else {
            size[u] += size[v];
        }
    }
    return res;
}
bool check(int x) {
    tot = n;
    return tryCut(1, 0, x) >= k;
}
int main() {
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);

    int T = 1;
    std::cin >> T;
    while (T--) {
        std::cin >> n >> k;
        for (int i = 1; i < n; ++i) {
            int u, v;
            std::cin >> u >> v;
            edge[u].push_back(v);
            edge[v].push_back(u);
        }
        int l = 1, r = n, ans = 0;
        while(l <= r) {
            int mid = (l + r) >> 1;
            if (check(mid)){
                l = mid + 1, ans = std::max(ans, mid);
            } else {
                r = mid - 1;
            }
        }
        std::cout << ans << '\n';
        for (int i = 1; i <= n; ++i) edge[i].clear();
    }

    return 0;
}

D.

题目大意：

将一个大小为 n 的正整数序列划分成若干段，设为 k。给定 x，求满足如下式子的 k 的最大值：

$\left(a_{l_1} \oplus a_{l_1+1} \oplus \ldots \oplus a_{r_1}\right)\left|\left(a_{l_2} \oplus a_{l_2+1} \oplus \ldots \oplus a_{r_2}\right)\right| \ldots \mid\left(a_{l_k} \oplus a_{l_k+1} \oplus \ldots \oplus a_{r_k}\right) \leq x$

题解：

这道题给人的第一感觉就是非常的诡异，求解的模型非常陌生，让人一时之间很摸不着头脑。其实 CodeForces 网站上还挺多这种调调的题目的，虽然模型陌生，但是难度倒并不一定很高，比赛的时候需要集中精力，分析问题的切入点。

把 x 按照位拆分，如果自己需要小于 x，只需要在某一位中，x 为 1， 且自己为 0 即可（当然，这里需要保证高位与 x 相同，低位随意）。这样一来，问题就变成了，对于给定的数字 y（这样的 y 有 30 种），如何尽可能多得划分子段，且满足式子最终结果 y’ 满足 $y' | y = y$。

求解这个问题，同样需要贪心的策略。假如目前的子段 i 的异或和已经满足 $y^{'}_i = y$, 那么这个子段 i 就可以单独成段：

首先。假设 $i = 1$，则不存在一种分段方法，能在当前位置之前进行分段。如果不在这里分段，而是在后面分段，显然最终能在这里分一个新段，且原来的第一段依然满足 $y^{'}_i = y$。所以第一段一定会在满足 $y^{'}_1 = y$ 处进行分割。接下来，去除第一段，问题又成了新的子问题，以此类推，划分方式依然不变。

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll, int> pli;
typedef std::pair<ll, ll> pll;
typedef double db;
typedef long double ldb;
const int maxn = 2e5 + 5;
int n, x;
int a[maxn];
int check(int x, int mask) {
    int xorSum = 0, count = 0;
    for (int i = 1; i <= n; ++i) {
        xorSum ^= a[i] & mask;
        if ((xorSum | x) == x) count++;
    }
    if ((xorSum | x) == x) return count;
    else return -1;
}
int main() {
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);

    int T = 1;
    std::cin >> T;
    while (T--) {
        std::cin >> n >> x;
        for (int i = 1; i <= n; ++i) {
            std::cin >> a[i];
        }
        int mask = 0;
        int ans = -1;
        for (int i = 30; i >= 0; --i) {
            mask |= 1 << i;
            if ((1 << i) & x) {
                ans = std::max(ans, check((x & mask) ^ (1 << i), mask));
            }
        }
        ans = std::max(ans, check(x & mask, mask));
        std::cout << ans << '\n';
    }

    return 0;
}

E.

题目大意：

给定长度为 n 的一个排列 a。基于这个排列，题目会给出两个序列：

• 序列一中的每个元素 $p_i$ 满足，如果对于任意 $j < p_i$，则 $a_j > a_{p_i}$
• 序列一中的每个元素 $s_i$ 满足，如果对于任意 $j > s_i$，则 $a_j < a_{s_i}$
  这两个序列的元素都是按照单调递增的顺序给出的。

求满足这两个序列所描述的情况的所有的排列 a 的数量。

题解：

很简单的计数题，难度应该是小于 D 题的，不太理解出题人题目放置顺序的考量是怎样的。。。

显然，序列一的最后一个元素和序列二的第一个元素是相等的。设这个元素的值是 x，则 $a_x = n$。否则一定无解。在比较大小时，我们只在意元素间的大小关系，而不在乎具体的值，所以直接随意选出 $x - 1$ 个元素放在左边，$n - x$ 个元素放在右边即可。

左右两边的策略是对称的，所以仅讨论其中一侧的放法即可，这里以左侧为例。

序列一中倒数第二个元素（设为y）一定是左侧这 $x - 1$ 个元素中最大的，然后这个数字将左侧分成了两个部分。第二个部分夹在 y 与 x 中间，总共 $y - x - 1$ 个数字，从$x - 2$ 个数字中随机选取即可。这样问题变成了仅考虑第一部分的新的子问题。这样不停地继续做下去即可。

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll, int> pli;
typedef std::pair<ll, ll> pll;
typedef double db;
typedef long double ldb;
const ll mod = 1e9 + 7;
const int maxn = 2e5 + 5;
ll fac[maxn];
ll quickPow(ll x, ll y) {
    ll res = 1;
    while (y) {
        if (y & 1)
            res *= x, res %= mod;
        x *= x, x %= mod;
        y /= 2;
    }
    return res;
}
ll inv(ll x) {
    return quickPow(x, mod - 2);
}
ll C(ll up, ll down) {
    return fac[down] * inv(fac[up]) % mod * inv(fac[down - up]) % mod;
}
int m1, m2, n;
int p[maxn], s[maxn];
void solve() {
    if (p[m1] != s[1]) {
        std::cout << "0\n";
        return; 
    } 
    if (p[1] != 1 || s[m2] != n) {
        std::cout << "0\n";
        return; 
    }

    ll ans = C(p[m1] - 1, n - 1);
    for (int i = m1; i > 1; --i) {
        ans *= C(p[i] - p[i - 1] - 1, p[i] - 2) * fac[p[i] - p[i - 1] - 1] % mod;
        ans %= mod;
    }

    for (int i = 1; i < m2; ++i) {
        ans *= C(s[i + 1] - s[i] - 1, n - s[i] - 1) * fac[s[i + 1] - s[i] - 1] % mod;
        ans %= mod;
    }
    std::cout << ans << '\n';
}
int main() {
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);

    int T = 1;
    std::cin >> T;
    fac[0] = 1;
    for (int i = 1; i < maxn; ++i)
        fac[i] = fac[i - 1] * i, fac[i] %= mod;
    while (T--) {
        std::cin >> n >> m1 >> m2;
        for (int i = 1; i <= m1; ++i) std::cin >> p[i];
        for (int i = 1; i <= m2; ++i) std::cin >> s[i];
        solve();
    }

    return 0;
}

F.

题目大意：

给定一个大小为 n 的排列，然后给出 q 个询问，每个询问输入两个值，分别是 l 与 r。求出满足如下要求的子序列数量：

• 子序列中的元素的下标均在 $[l, r]$ 内。
• 子序列中相邻元素中，后一个是前一个的整数倍。

题解：

估算一次查询的结果大小，以某个元素为起点，则最长的序列长度为 $\log{n}$，则答案最大为 $n * \log{n} * \log{n}$。果能确定序列的第一个元素，则很容易求以这个元素为起点的所有序列的数量，使用一个复杂度为 $n * \log{n} * \log{n}$ 简单 DP 即可（详见代码）。

对于一个查询 $[l, r]$，本质上就是对所有起点在 l 之后，且终点在 r 之前的序列进行求和。我们记录下每一次查询，按照左端点从大到小排列所有询问，然后离线进行求解。我们把从 n 到 1 的每个元素依次作为左端点，计算以此为起点的序列的所有可能终点对应的方案数量，然后使用树状数组加速求和过程。

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll, int> pli;
typedef std::pair<ll, ll> pll;
typedef double db;
typedef long double ldb;
const int maxn = 1e6 + 5;
int n, q, a[maxn];
std::vector<pii> seg[maxn];
ll dp[maxn];
int pos[maxn];
ll res[maxn];
struct Fenwick {
    ll tree[maxn];
    int size;
    void reset(int n) {
        for (int i = 0; i <= n; ++i) tree[i] = 0;
        size = n;
    }
    void add(int x, ll val) {
        while(x <= size) {
            tree[x] += val;
            x += lowbit(x);
        }
    }
    ll query(int l, int r) {
        return sum(r) - sum(l - 1);
    }
    ll sum(int x) {
        ll res = 0;
        while(x) {
            res += tree[x];
            x -= lowbit(x);
        }
        return res;
    }
    int lowbit(int x) {
        return x & (-x);
    }
}spike;
void initializeDP(int l) {
    dp[l] = 1;
    for (int x = a[l]; x <= spike.size; x += a[l]) {
        if (pos[x] < l) continue;
        spike.add(pos[x], dp[pos[x]]);
        for (int y = x * 2; y <= spike.size; y += x) {
            if (pos[y] < pos[x]) continue;
            dp[pos[y]] += dp[pos[x]];
        }
    }
    for (int x = a[l]; x <= spike.size; x += a[l]) {
        dp[pos[x]] = 0;
    }
}
int main() {
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);

    int T = 1;
    std::cin >> T;
    while (T--) {
        std::cin >> n >> q;
        for (int i = 1; i <= n; ++i) {
            std::cin >> a[i];
            pos[a[i]] = i;
        }
        spike.reset(n);
        for(int i = 1; i <= q; ++i) {
            int l, r;
            std::cin >> l >> r;
            seg[l].push_back({r, i});
        }
        for (int l = n; l >= 1; --l) {
            initializeDP(l);
            for (auto [r, i] : seg[l]) {
                res[i] = spike.query(l, r);
            }
        }
        for (int i = 1; i <= q; ++i) {
            std::cout << res[i] << " ";
        }
        std::cout << '\n';
        for (int i = 1; i <= n; ++i) pos[i] = 0;
        for (int i = 1; i <= n; ++i) seg[i].clear();
    }

    return 0;
}