Codeforces Round 936 (Div. 2) Solution

发表于 2024-03-23 更新于 2024-04-19 分类于 contest 阅读次数：本文字数： 3.6k 阅读时长 ≈ 13 分钟

目前进度：

A	B	C	D	E	F
solved contest	solved contest	solved contest	solved contest	solved later	solved later

A. Median of an Array

简要翻译

给定一个数列 \(a\)，每次操作可以将某个数 \(+1\)，求使中位数变大的最少操作数。

思路解析

排序后考虑中位数及其右侧，让中位数 \(+1\) 必须让与中位数相等的数都 \(+1\)。

代码

Code

#include <algorithm>
#include <cstdio>
#include <vector>
namespace Input{
    const int BUFFLEN = 1 << 20;
    char buf[BUFFLEN | 2], *p1 = buf, *p2 = buf;
    inline char getc(){
        if(p1 == p2)
            p1 = buf,
            p2 = buf + fread(buf, 1, BUFFLEN, stdin);
        return p1 == p2? EOF: *p1++;
    }
    inline bool isdgt(const char op){return op >= '0' && op <= '9';}
    inline bool ischr(const char op){return op >= 'a' && op <= 'z';}
    long long read(){
        static long long res; static char op, f;
        for(f = 0, op = getc(); !isdgt(op); op = getc()) f |= (op == '-');
        for(res = 0; isdgt(op); op = getc()) res = res * 10 + (op ^ '0');
        return f? -res: res;
    }
}
using namespace std;
using Input::read;
typedef long long ll;
const int N = 300010;
int a[N], n;
void solve(){
    n = read();
    for(int i = 1; i <= n; ++i)
        a[i] = read();
    sort(a + 1, a + n + 1);
    int p = (n - 1) / 2 + 1;
    if(n == 1)
        printf("1\n");
    else{
        int ans = 0;
        for(int i = p; i <= n; ++i)
            if(a[i] == a[p])
                ans++;
        printf("%d\n", ans);
    }
}
signed main(int argc,char **argv){
    int T = read();
    while(T--) solve();
    return 0;
}

B. Maximum Sum

简要翻译

给定一个序列 \(a\)，每次可以将一个子段的和（可以为空，此时和为 \(0\)）插入 \(a\) 中，求恰好 \(k\) 次操作后序列和的最大值。

思路解析

设 \(a\) 的最大子段和为 \(x\)，那每一步可以将 \(x\) 插入到最大子段的旁边，新的最大字段和变为 \(2x\)。

这样操作 \(k\) 次，获得的增量为 \(x \times (2^k - 1)\)。\(k\) 不大，所以可以不用快速幂。

代码

Code

#include <algorithm>
#include <cstdio>
#include <vector>
namespace Input{
    const int BUFFLEN = 1 << 20;
    char buf[BUFFLEN | 2], *p1 = buf, *p2 = buf;
    inline char getc(){
        if(p1 == p2)
            p1 = buf,
            p2 = buf + fread(buf, 1, BUFFLEN, stdin);
        return p1 == p2? EOF: *p1++;
    }
    inline bool isdgt(const char op){return op >= '0' && op <= '9';}
    inline bool ischr(const char op){return op >= 'a' && op <= 'z';}
    long long read(){
        static long long res; static char op, f;
        for(f = 0, op = getc(); !isdgt(op); op = getc()) f |= (op == '-');
        for(res = 0; isdgt(op); op = getc()) res = res * 10 + (op ^ '0');
        return f? -res: res;
    }
}
using namespace std;
using Input::read;
typedef long long ll;
const int N = 300010;
const ll mod = 1000000007;
ll a[N], n, k;
void solve(){
    n = read(); k = read();
    ll sum = 0, ans = 0, asum = 0;
    for(int i = 1; i <= n; ++i){
        a[i] = read();
        sum += a[i];
        asum += a[i];
        if(sum < 0)
            sum = 0;
        ans = max(ans, sum);
    }
    asum %= mod;
    asum = (asum + mod) % mod;
    ans %= mod;
    for(int i = 1; i <= k; ++i){
        asum = (asum + ans) % mod;
        ans = (ans << 1ll) % mod;
    }
    printf("%lld\n", asum);
}
signed main(int argc, char **argv){
    int T = read();
    while(T--) solve();
    return 0;
}

C. Tree Cutting

简要翻译

给定一棵树，要求切掉 \(k\) 条边，求剩下的连通块最小值的最大值。

思路解析

最小连通块的最大值，听着就很像二分。那么考虑二分答案，转化为能不能凑出 \(k + 1\) 块大小为 \(lim\) 的连通块。

设 \(size_x\) 为 \(x\) 子树内大小为 \(x\) 的连通块个数，\(rest_x\) 表示 \(x\) 所在的连通块的大小。

对于一个待确定的连通块，如果它大小已经到达 \(lim\)，那么再合并其他的散点对于凑出答案不会更优。

所以在 \(rest_x \ge lim\) 时就断开即可。

首先有 \(size_x = \sum_{y} size_y\)，\(rest_x = \sum_{y} rest_x\)。

如果 \(rest_x \ge lim\)，则连通块在 \(x\) 处就可以断开，将 \(size_x + 1\)，并将 \(rest_x\) 清零。

赛时写法略有不同，但效果相同。

时间复杂度 \(\Theta(N \lg N)\)。

代码

Code

#include <algorithm>
#include <cstdio>
#include <vector>
namespace Input{
    const int BUFFLEN = 1 << 20;
    char buf[BUFFLEN | 2], *p1 = buf, *p2 = buf;
    inline char getc(){
        if(p1 == p2)
            p1 = buf,
            p2 = buf + fread(buf, 1, BUFFLEN, stdin);
        return p1 == p2? EOF: *p1++;
    }
    inline bool isdgt(const char op){return op >= '0' && op <= '9';}
    inline bool ischr(const char op){return op >= 'a' && op <= 'z';}
    long long read(){
        static long long res; static char op, f;
        for(f = 0, op = getc(); !isdgt(op); op = getc()) f |= (op == '-');
        for(res = 0; isdgt(op); op = getc()) res = res * 10 + (op ^ '0');
        return f? -res: res;
    }
}
using namespace std;
using Input::read;
typedef long long ll;
const int N = 300010;
vector<int> ver[N];
int res[N], siz[N];
int n, m;
void dfs(int x, int fa, int lim){
    siz[x] = 0; res[x] = 1;
    for(int y : ver[x]){
        if(y == fa) continue;
        dfs(y, x, lim);
        siz[x] += siz[y];
        if(res[y] >= lim){
            siz[x]++;
            res[y] = 0;
        }
        res[x] += res[y];
    }
}
bool chk(int lim){
    dfs(1, 0, lim);
    if(res[1] >= lim)
        siz[1]++;
    return siz[1] > m;
}
void solve(){
    n = read(); m = read();
    for(int i = 1; i <= n; ++i)
        ver[i].clear();
    for(int i = 1, x, y; i < n; ++i){
        x = read(); y = read();
        ver[x].emplace_back(y);
        ver[y].emplace_back(x);
    }
    int l = 0, r = n, mid, ans;
    while(l <= r){
        mid = (l + r) >> 1;
        if(chk(mid))
            l = mid + 1, ans = mid;
        else
            r = mid - 1;
    }
    printf("%d\n",ans);
}
signed main(int argc, char **argv){
    int T = read();
    while(T--) solve();
    return 0;
}

D. Birthday Gift

简要翻译

有一个数列 \(a\)，现在将其分为 \(k\) 个不相交区间，同时 \(k\) 个区间的并为 \([1, n]\)。

需要满足：\((a_{l_1} \oplus a_{l_1 + 1} \oplus \ldots \oplus a_{r_1}) | (a_{l_2} \oplus a_{l_2 + 1} \oplus \ldots \oplus a_{r_2}) | \ldots | (a_{l_k} \oplus a_{l_k + 1} \oplus \ldots \oplus a_{r_k}) \le x\)。

求 \(k\) 的最大值。

思路解析

先分析一下不等式的性质。设 \(S_i = a_1 \oplus a_2 \oplus \ldots \oplus a_i\)。

同时考虑到 \(r_i + 1 = l_{i + 1}, l_1 - 1 = 0, r_k = n\)。

则不等式左侧变为 \(A = (S_{r_1}) | (S_{r_1} \oplus S_{r_2}) | \ldots | (S_{r_{k-1}} \oplus S_{n})\)。

再来看单独的一位上如何限制。

如果 \(A = 0\)，那么 \(S_{r_1} = 0, (S_{r_1} \oplus S_{r_2}) = 0 \Rightarrow S_{r_2} = 0\)。稍加分析，这一关系可以推至任意 \(S_{r_i}\)。

所以 \(A = 0\) 时一定有 \(S_{r_1} = S_{r_2} = \ldots = S_{n} = 0\)。

考虑其逆否命题，若 \(S_{r_1}, S_{r_2}, \ldots, S_{n}\) 中有至少一个值为 \(1\)，则有 \(A = 1\)。

所以如果 \(x\) 的第 \(k\) 位为 \(0\)，我们只能选则 \(S_p\) 第 \(k\) 位为 \(0\) 的 \(p\) 构成序列 \(r\)。

在推导过程中，可以发现 \(S_n\) 是必选项，所以如果 \(S_n\) 第 \(k\) 位为 \(1\) 时 \(A = 1\)，有 \(A \ge S_n\)。

直接的写法不会，想了一个二分答案，看我们能不能选出 \(lim\) 个右端点构成 \(r\)。

设当前在考虑第 \(k\) 位，当前位为 \(0\) 的 \(S\) 构成的集合为 \(\mathrm{now}\), 高位符合要求的集合为 \(\mathrm{bit}\)。

统计 \(\mathrm{bit}_i\ \&\ \mathrm{now}_i = 1\) 的位置个数 \(t\)。

如果 \(x\) 第 \(k\) 位为 \(1\) 而 \(t \ge lim\)，说明此位选 \(0\) 就可以满足要求，而低位选出的值无论是 \(0\) 是 \(1\) 都不影响 \(A < x\)；

如果 \(t < lim\)，则考虑不应用 \(\mathrm{now}\) 的限制，这一位在低位的计算中会取 \(1\)。

如果 \(x\) 第 \(k\) 位为 \(0\)，因为已经构造的 \(A\) 的高位和 \(x\) 相等，所以此位只能选 \(0\)。将 \(\mathrm{bit}\) 与 \(\mathrm{now}\) 求交集即可。

什么时候无解呢？上面有 \(A \ge S_n\)，所以 \(S_n > x\) 时无解；反之，选取区间 \([1, n]\) 一定成立，答案至少为 \(1\)。

时间复杂度 \(O(N\lg N \lg X)\)。

代码

Code

#include <algorithm>
#include <bitset>
#include <cstdio>
#include <vector>
namespace Input{
    const int BUFFLEN = 1 << 20;
    char buf[BUFFLEN | 2], *p1 = buf, *p2 = buf;
    inline char getc(){
        if(p1 == p2)
            p1 = buf,
            p2 = buf + fread(buf, 1, BUFFLEN, stdin);
        return p1 == p2? EOF: *p1++;
    }
    inline bool isdgt(const char op){return op >= '0' && op <= '9';}
    inline bool ischr(const char op){return op >= 'a' && op <= 'z';}
    long long read(){
        static long long res; static char op, f;
        for(f = 0, op = getc(); !isdgt(op); op = getc()) f |= (op == '-');
        for(res = 0; isdgt(op); op = getc()) res = res * 10 + (op ^ '0');
        return f? -res: res;
    }
}
using namespace std;
using Input::read;
typedef long long ll;
const int N = 100010;
int n,x;
int sum[N];
bitset<N> bit,now;
bool chk(int lim){
    for(int i = 1; i <= n; ++i)
        bit.set(i, 1);
    for(int k = 30, cnt = 0; ~k; cnt = 0, --k){
        for(int i = 1; i <= n; ++i)
            now.set(i, !((sum[i] >> k) & 1));
        for(int i = 1; i <= n; ++i)
            cnt += bit[i] & now[i];
        if((x >> k) & 1){
            if(cnt >= lim && (bit[n] & now[n]))//sn = 0, 可以选出 lim 个
                return true;
        }
        else{
            if(cnt < lim || !(bit[n] & now[n]))//sn = 1 或者选不出 lim 个了
                return false;
            bit = bit & now;//应用此位为 0 的集合约束
        }
    }
    return true;
}
void solve(){
    n = read(); x = read();
    for(int i = 1; i <= n; ++i)
        sum[i] = sum[i - 1] ^ read();
    if(sum[n] > x){
        puts("-1");
        return;
    }
    int l = 0, r = n, mid, ans;
    while(l <= r){
        mid = (l + r) >> 1;
        if(chk(mid))
            l = mid + 1, ans = mid;
        else
            r = mid - 1;
    }
    printf("%d\n", ans);
}
signed main(int argc, char **argv){
    int T = read();
    while(T--) solve();
    return 0;
}

E. Girl Permutation

简要翻译

对于一个排列，给定它的前缀最大值的位置序列、后缀最大值的位置序列，求可能的排列的数量。

前缀最大值的位置序列 \(p\)，指的是序列中的一个值 \(p_i\) 对应 \(v_{p_i}\) 是 \(v_1, v_2, \ldots, v_{p_i}\) 中的最大值。

后缀最大值类似。

思路解析

纯纯数学题。赛场上没想完，亏了。

设前缀最大值的位置序列为 \(a_1, a_2, \ldots, a_{m_1}\)，后缀最大值的位置序列为 \(b_1, b_2, \ldots, b_{m_2}\)。

根据定义不难得出 \(a_1 = 1, b_{m_1} = n\)。同时 \(v_p = n\) 的位置应该既是 \(a_{m_1}\) 又是 \(b_1\)。有一条不满足，则答案为 \(0\)。

显然前缀最大值和后缀最大值相交于 \(v_p = n\) 而不会交叉，所以两边可以分开计算。

同时我们可以把任意 \(m_1 - 1\) 个数放在 \(n\) 的左边，然后让它们按规则排列。这样答案就有一个基数 \(\binom{n - 1}{m_1 - 1}\)。

先算左边。设 \(f_i\) 为序列 \(1 \sim i\) 位置上的方案数。不妨先假设值域为 \([1, m_1]\)。

如果 \(i\) 是某个 \(a_j\)，那么 \(v_i\) 在前 \(i\) 个数排序后必须处于末尾，\(f_i = f_{i-1}\)；

否则 \(v_i\) 在前 \(i\) 个数排序后不能处于末尾，有 \(i - 1\) 个位置可供选择，\(f_i = f_{i-1} \times (i - 1)\)。

对后缀最大值的处理类似，不再赘述。

时间复杂度 \(\Theta(N)\)。

代码

Code

#include<algorithm>
#include<cstdio>
#include<vector>
namespace Input{
    const int BUFFLEN = 1 << 20;
    char buf[BUFFLEN | 2], *p1 = buf, *p2 = buf;
    inline char getc(){
        if(p1 == p2)
            p1 = buf,
            p2 = buf + fread(buf, 1, BUFFLEN, stdin);
        return p1 == p2? EOF: *p1++;
    }
    inline bool isdgt(const char op){return op >= '0' && op <= '9';}
    inline bool ischr(const char op){return op >= 'a' && op <= 'z';}
    long long read(){
        static long long res;static char op,f;
        for(f = 0, op = getc(); !isdgt(op); op = getc())f |= (op == '-');
        for(res = 0; isdgt(op); op = getc())res = res * 10 + (op ^ '0');
        return f? -res: res;
    }
    int readstr(char *s){
        static int len;static char op;
        do op = getc(); while(!ischr(op));
        for(len = 0; ischr(op); op = getc())s[len++] = op;
        return len;
    }
}
using namespace std;
using Input::read;
typedef long long ll;
const int N = 200010;
const ll mod = 1000000007;
ll fac[N], inv[N], invfac[N];
int pre[N], suf[N], n, m1, m2;
void init(){
    fac[0] = fac[1] = 1;
    inv[0] = inv[1] = 1;
    invfac[0] = invfac[1] = 1;
    for(int i = 2; i < N; ++i){
        fac[i] = (fac[i - 1] * i) % mod;
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
        invfac[i] = (invfac[i - 1] * inv[i]) % mod;
    }
}
ll binom(int n, int m){
    return fac[n]*invfac[m]%mod*invfac[n-m]%mod;
}
void solve(){
    n = read();
    m1 = read();
    m2 = read();
    for(int i = 1; i <= m1; ++i)
        pre[i] = read();
    for(int i = 1; i <= m2; ++i)
        suf[i] = read();
    if(pre[1] != 1 || pre[m1] != suf[1] || suf[m2] != n){
        printf("0\n");
        return;
    }
    ll ans = 1;
    for(int i = 1, p = 1; i <= pre[m1]; ++i)
    if(i != pre[p])
        ans = ans * (i-1ll) % mod;
    else
        p++;
    for(int i = n, p = m2; i >= suf[1]; --i)
    if(i != suf[p])
        ans = ans * (n - i) % mod;
    else
        p--;
    ans = ans * binom(n - 1, pre[m1] - 1) % mod;
    printf("%lld\n", ans);
}
signed main(int argc, char **argv){
    init();
    int T=read();
    while(T--)solve();
    return 0;
}

F. Title

简要翻译

给定一个序列 \(a\)，每次查询一个区间，询问区间中子序列的数量，要求子序列中前一个数是后一个数的约数。

思路解析

这题 6s 时限，看上去会略超过 \(10^8\) 计算量。

区间用类扫描线的方法转化，在右端点加入集合的时候查询。

设 \(s_i\) 表示从 \(i\) 开始，到目前的右界 \(r\) 中合法子序列的数量。

当右界从 \(r - 1\) 移动到 \(r\) 时，所有新增的子序列必须以 \(r\) 结尾。

那么新增序列去掉 \(r\) 之后的末尾，它的值一定是 \(v_r\) 的约数。

我们可以将标记打在 \(\{p | (v_p | v_r)\}\) 上，这时候 \(p\) 就是新增序列的等效末尾，再用它来向前更新。

更新 \(s_i\) 之后就可以查询了。这里因为复杂度比较高，使用了树状数组来降低常数。

计算所有的 \(r\) 一共更新了多少个值，可以反过来算每个 \(v_i\) 的倍数出现的次数和。

因为 \(v\) 构成排列，这个数应当等于 \((\frac{N}{1} + \frac{N}{2} + \ldots + \frac{N}{N})\)，即 \(N\ln N\)。

所以总复杂度为 \(O(N\ln N \lg^2 N)\)，能卡过也是神奇。

代码

Code

#include <algorithm>
#include <cstdio>
#include <queue>
#include <vector>
namespace Input{
    const int BUFFLEN = 1 << 20;
    char buf[BUFFLEN | 2], *p1 = buf, *p2 = buf;
    inline char getc(){
        if(p1 == p2)
            p1 = buf,
            p2 = buf + fread(buf, 1, BUFFLEN, stdin);
        return p1 == p2? EOF: *p1++;
    }
    inline bool isdgt(const char op){return op >= '0' && op <= '9';}
    inline bool ischr(const char op){return op >= 'a' && op <= 'z';}
    long long read(){
        static long long res;static char op,f;
        for(f = 0, op = getc(); !isdgt(op); op = getc()) f |= (op == '-');
        for(res = 0; isdgt(op); op = getc()) res = res * 10 + (op ^ '0');
        return f? -res: res;
    }
    int readstr(char *s){
        static int len;static char op;
        do op = getc(); while(!ischr(op));
        for(len = 0; ischr(op); op = getc()) s[len++] = op;
        return len;
    }
}
using namespace std;
using Input::read;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1000010;
template<typename Tp, int LEN>
class BIT{
public:
    void resize(int len);
    void clear();
    void add(int x, Tp v);
    Tp ask(int x);
private:
    Tp c[LEN];
    int c_len;
};
template<typename Tp, int LEN>
void BIT<Tp, LEN>::clear(){
    for(int x = 0; x <= c_len; x++) c[x] = 0;
}
template<typename Tp, int LEN>
void BIT<Tp, LEN>::resize(int len){
    c_len = len;
    clear();
}
template<typename Tp, int LEN>
void BIT<Tp, LEN>::add(int x, Tp v){
    for(; x <= c_len; x += x & -x) c[x] += v;
}
template<typename Tp, int LEN>
Tp BIT<Tp, LEN>::ask(int x){
    Tp ans(0);
    for(; x; x -= x & -x) ans += c[x];
    return ans;
}
BIT<ll, N> B;
vector<int> divend[N];
vector<pii> query[N];
priority_queue<int> Q;
int per[N], pos[N], n, m;
ll tag[N], ans[N];
void init(){
    for(int x = 1; x < N; x++)
    for(int y = x << 1; y < N; y += x)
        divend[y].emplace_back(x);
}
void solve(){
    n = read();
    m = read();
    B.resize(n);
    for(int i = 1; i <= n; ++i)
        query[i].clear();
    for(int i = 1; i <= n; ++i)
        pos[per[i] = read()] = i;
    for(int i = 1, l, r; i <= m; ++i){
        l = read();
        r = read();
        query[r].emplace_back(make_pair(l, i));
    }
    for(int i = 1; i <= n; ++i){
        Q.push(i);
        tag[i] = 1;
        while(!Q.empty()){
            int x = Q.top(); Q.pop();
            for(int y : divend[per[x]])
            if(pos[y] < x){
                if(!tag[pos[y]])
                    Q.push(pos[y]);
                tag[pos[y]] += tag[x];
            }
            B.add(x, tag[x]);
            tag[x] = 0;
        }
        for(auto [l, id] : query[i])
            ans[id] = B.ask(i) - B.ask(l - 1);
    }
    for(int i = 1; i <= m; ++i)
        printf("%lld ", ans[i]);
    putchar('\n');
}
signed main(int argc,char **argv){
    init();
    int T = read();
    while(T--) solve();
    return 0;
}

后记

这把 D 题做完还有 30min，以为自己不能拿下很数学的 E 题，遂开摆。最后发现自己离 1900 只有一步之遥，感觉很后悔。

最近作业压力太大，Lab 和 Proj 堆了一个又一个，感觉清明之前不完成的话会度过一个很不愉快的假期。

转念一想，清明可以和烧烤群的各位面基，还是很期待的。

加把劲吧。