Codeforces Round 936 (Div. 2) Solution

发表于 2024-03-23 更新于 2024-07-23 分类于 contest 阅读次数： 2 本文字数： 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$ 插入到最大子段的旁边，新的最大字段和变为 $2 x$ 。

这样操作 $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$ 块大小为 $l i m$ 的连通块。

设 $s i z e_{x}$ 为 $x$ 子树内大小为 $x$ 的连通块个数， $r e s t_{x}$ 表示 $x$ 所在的连通块的大小。

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

所以在 $r e s t_{x} \geq l i m$ 时就断开即可。

首先有 $s i z e_{x} = \sum_{y} s i z e_{y}$ ， $r e s t_{x} = \sum_{y} r e s t_{x}$ 。

如果 $r e s t_{x} \geq l i m$ ，则连通块在 $x$ 处就可以断开，将 $s i z e_{x} + 1$ ，并将 $r e s t_{x}$ 清零。

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

时间复杂度 $Θ (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 \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$ 的最大值。

思路解析

先分析一下不等式的性质。设 $S_{i} = a_{1} \oplus a_{2} \oplus \dots \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}}) | \dots | (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}} = \dots = S_{n} = 0$ 。

考虑其逆否命题，若 $S_{r_{1}}, S_{r_{2}}, \dots, S_{n}$ 中有至少一个值为 $1$ ，则有 $A = 1$ 。

所以如果 $x$ 的第 $k$ 位为 $0$ ，我们只能选则 $S_{p}$ 第 $k$ 位为 $0$ 的 $p$ 构成序列 $r$ 。

在推导过程中，可以发现 $S_{n}$ 是必选项，所以如果 $S_{n}$ 第 $k$ 位为 $1$ 时 $A = 1$ ，有 $A \geq S_{n}$ 。

直接的写法不会，想了一个二分答案，看我们能不能选出 $l i m$ 个右端点构成 $r$ 。

设当前在考虑第 $k$ 位，当前位为 $0$ 的 $S$ 构成的集合为 $now$ , 高位符合要求的集合为 $bit$ 。

统计 ${bit}_{i} & {now}_{i} = 1$ 的位置个数 $t$ 。

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

如果 $t < l i m$ ，则考虑不应用 $now$ 的限制，这一位在低位的计算中会取 $1$ 。

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

什么时候无解呢？上面有 $A \geq 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}, \dots, v_{p_{i}}$ 中的最大值。

后缀最大值类似。

思路解析

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

设前缀最大值的位置序列为 $a_{1}, a_{2}, \dots, a_{m_{1}}$ ，后缀最大值的位置序列为 $b_{1}, b_{2}, \dots, 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)$ 。

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

时间复杂度 $Θ (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} + \dots + \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 堆了一个又一个，感觉清明之前不完成的话会度过一个很不愉快的假期。

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

加把劲吧。