Codeforces Round 926 (Div. 2) Solution

发表于 更新于 分类于 阅读次数： 本文字数： 2.4k 阅读时长 ≈ 9 分钟

目前进度：

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

A. Sasha and the Beautiful Array

简要翻译

给定一个数组 \(a\)，可以随意交换元素，最大化 \(\sum_{i=2}^{n} (a_i - a_{i-1})\)。

思路解析

\(\sum_{i=2}^{n} (a_i - a_{i-1}) = a_n - a_1\)，所以最大值减最小值即可。

代码

Code

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<algorithm>
#include<cstdio>
using namespace std;
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';}
    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 Input::read;
typedef long long ll;
const int N=300010;
ll a[N],n;
void work(){
    n=read();
    ll mina=1000000000,maxa=0;
    for(int i=1;i<=n;++i)
        a[i]=read(),
        mina=min(mina,a[i]),
        maxa=max(maxa,a[i]);
    printf("%lld\n",maxa-mina);
}
signed main(int argc,char **argv){
    freopen("order.in","r",stdin);
    freopen("order.out","w",stdout);
    int T=Input::read();
    while(T--)work();
    return 0;
}

B. Sasha and the Drawing

简要翻译

给定一个 \(n \times n\) 的方格网，求最少的填色块数，使得至少 \(k\) 条对角线上有被染色的格子。

正方向（左上-右下方向）与负方向各有 \(2n - 1\) 条对角线，所以 \(k \leq 4n - 2\)。

思路解析

首先，每多 \(1\) 个填色块，有颜色的对角线个数最多 \(+2\)。

我们可以先给第 \(1\) 行的方格填色，这样每次填色增加的对角线都没有重复。

接下来画个图，发现正方向和负方向的对角线各被统计了 \(n\) 条。

而在第 \(n\) 行，除了 \((n,1)\) 与 \((n,n)\)，其他方格填色仍然能使有颜色的对角线个数 \(+2\)。 对于 \((n,1)\) 和 \((n,n)\)，选它们的贡献只有 \(1\)。

所以 \(k \leq 2(2n - 2)\) 时，答案为 \(\lceil \frac{k}{2} \rceil\)。如果 \(4n - 4 < k \leq 4n - 2\)，则答案为 \(k - 2n + 2\)。

代码

Code

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<algorithm>
#include<cstdio>
using namespace std;
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';}
    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 Input::read;
typedef long long ll;
void work(){
    ll n=read(),k=read();
    if(k<=(n*4-4))
        printf("%lld\n",(k+1)>>1);
    else
        printf("%lld\n",k-2*n+2);
}
signed main(int argc,char **argv){
    freopen("order.in","r",stdin);
    freopen("order.out","w",stdout);
    int T=Input::read();
    while(T--)work();
    return 0;
}

C. Sasha and the Casino

简要翻译

Sasha 去赌场玩，可以下赌若干次。每局赌注的金额为正整数且不超过 Sasha 现有资金。

设赌注金额为 \(y\)，若赢了可以得到 \((k - 1) \cdot y\)，若输了则失去 \(y\)。

赌场有一个特殊机制：连输 \(x\) 局后下一局必赢。当然，赌场里有很多手脚，不违反机制的情况下可以操控任意一局的输赢。

Sasha 的启动资金为 \(a\)，问适当策略下 Sasha 能否赚到无限多的钱。

思路解析

因为前 \(x+1\) 局里一定有一局赢，所以我们只要考虑在这个区间赢一局能否赚到。

如果可以，那么钱就能一直变多；如果不能，那么赌场就可以在适当的时间让你赢一局（中断连败），同时你还亏钱，不可能越赌越多。

设 \(y\) 为本次下注的最小金额，\(z\) 为此次下注之前已经输了的钱。

如果这次赢了，那么必须赚到，所以 \((k - 1) \cdot y > z \Rightarrow y = \lfloor \frac{z}{k-1} \rfloor + 1\)。

本次下注金额不能超过现有资金，有 \(y \leq a - z\)。

输了 \(z\) 变为 \(z + y\)，到下一轮。

如果第 \(x+1\) 轮仍有 \(y \leq a - z\)，说明 Sasha 一定能回本且赚钱。

代码

Code

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<algorithm>
#include<cstdio>
using namespace std;
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';}
    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 Input::read;
typedef long long ll;
bool work(){
    ll k=read(),x=read(),a=read(),z=0;
    for(int i=1;i<=x+1;++i){
        ll y=z/(k-1)+1;
        if(i==1)y=1;
        if(y>a-z)return false;
        z+=y;
    }
    return true;
}
signed main(int argc,char **argv){
//  freopen("order.in","r",stdin);
//  freopen("order.out","w",stdout);
    int T=Input::read();
    while(T--)
        puts(work()?"YES":"NO");
    return 0;
}

D. Sasha and a Walk in the City

简要翻译

给定一棵树，求如下点集的数量：

若将点集中的点染黑，任意一条树上简单路径中黑点不超过两个。

思路解析

类似树上 dp 的做法。

当一个点 \(x\) 不能被选中，一定是以下两种情况之一：

  1. 有至少两个子树，它们中有选中点。这两个黑点的路径上包括了 \(x\)，\(x\) 不能选。

  2. 有一个子树，其中某两个选中点构成父子关系。从 \(x\) 到更深的那个黑点的路径上有两个黑点，\(x\) 不能选。

设 \(f_x\) 为 \(x\) 子树内不存在父子关系的点集方案数， \(g_x\) 为 \(x\) 子树内存在父子关系的点集方案数。

考虑 \(x\) 子树内不存在父子关系。若不选 \(x\)，其儿子 \(y\) 之间的方案相互独立，可以相乘。然后再加上一个只选 \(x\) 的方案。

\[ f_x = \prod_{y \in \mathrm{son}(x)} f_y + 1 \]

再考虑 \(x\) 子树内存在父子关系。若不选 \(x\)，其儿子 \(y\) 的 \(f_y\) 至多选一个；若选 \(x\)，则其儿子的 \(g_y\) 至多选一个。相加即可。

从 \(g_y\) 到 \(f_x\) 时，对于每个儿子 \(y\)，若子树选了空集，那么选了 \(x\) 也不构成父子关系，所以应该加 \(g_y - 1\)。

\[ g_x = \sum_{y \in \mathrm{son}(x)} (f_y + g_y - 1) \]

最后输出 \(f_1 + g_1\) 即可。

代码

Code

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<algorithm>
#include<cstdio>
#include<vector>
using namespace std;
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';}
    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 Input::read;
typedef long long ll;
const int N=300010;
const ll mod=998244353;
vector<int> ver[N];
int fa[N],n;
ll f[N],g[N];
void clear(){
    for(int i=1;i<=n;++i)
        ver[i].clear(),
        fa[i]=0,
        f[i]=g[i]=0;
}
void dfs(int x){
    f[x]=1;
    g[x]=0;
    for(int y:ver[x]){
        if(y==fa[x])continue;
        fa[y]=x;
        dfs(y);
        f[x]=(f[x]*f[y])%mod;
        g[x]=(g[x]+g[y]+f[y]+mod-1ll)%mod;
    }
    f[x]=(f[x]+1ll)%mod;
}
void work(){
    n=read();
    int root=1;
    for(int i=1,x,y;i<n;++i){
        x=read();y=read();
        ver[x].emplace_back(y);
        ver[y].emplace_back(x);
    }
    dfs(1);
    printf("%lld\n",(f[1]+g[1])%mod);
    clear();
}
signed main(int argc,char **argv){
//  freopen("order.in","r",stdin);
//  freopen("order.out","w",stdout);
    int T=Input::read();
    while(T--)work();
    return 0;
}

F. Sasha and the Wedding Binary Search Tree

简要翻译

给定一颗二叉搜索树（BST）和值域 \([1, C]\),其中一些节点的权值未定，权值可以重复，求不同的 BST 方案数。 只要有一个节点的权值不同，就认为是不同的方案。

思路分析

对 BST 中序遍历，应该得到一个非严格递增的序列 \(a\)。

所以对于序列一段未定的权值，它们应该是非严格递增的。

对于一段未定权值，如果两端的确定权值为 \(a_l, a_r\)，则相当于在 \([a_l, a_r]\) 中选 \((r-l-1)\) 个数。

权值可以重复，应用隔板法可以得到方案数应为

\[ \binom{a_r - a_l + 1 + r - l - 1}{r - l - 1} \]

对于序列两端的未定权值，设 \(a_0 = 1, a_{n+1} = C\) 即可。

因为 \(a_r - a_l\) 和 \(C\) 同阶，不能预处理阶乘来计算组合数。

（这里想了好久怎么办）

最后发现由于 \(\sum (r - l) = n + 1\)，所以可以用朴素的 \(\Theta(m)\) 方法求 \(\binom{n}{m}\)，总复杂度为 \(\Theta(n)\)。

至于取模，用 \(x^{-1} \equiv x^{p-2} \bmod p\) 即可。

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

代码

Code

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<algorithm>
#include<cstdio>
using namespace std;
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';}
    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 Input::read;
typedef long long ll;
const int N=500010;
const ll mod=998244353;
int lc[N],rc[N],val[N];
int a[N],num;
int n;ll inf;
void clear(){
    for(int i=1;i<=n;++i)
        lc[i]=rc[i]=-1,
        val[i]=-1,
        a[i]=0;
    num=0;
}
void dfs(int x){
    if(~lc[x])dfs(lc[x]);
    a[++num]=val[x];
    if(~rc[x])dfs(rc[x]);
}
ll qpow(ll x,ll y){
    ll ans=1;
    for(;y;y>>=1ll,x=(x*x)%mod)
        if(y&1ll)
            ans=(ans*x)%mod;
    return ans;
}
ll C(ll n,ll m){//(n(n-1)(n-2)...(n-m+1))/(m!)
    ll p=1,q=1;
    for(ll i=1;i<=m;++i)
        p=(p*(n+1-i))%mod,
        q=(q*i)%mod;
    return p*qpow(q,mod-2)%mod;
}
void work(){
    n=read();inf=read();
    for(int i=1;i<=n;++i)
        lc[i]=read(),
        rc[i]=read(),
        val[i]=read();
    dfs(1);
    ll ans=1;
    a[0]=1;a[n+1]=inf;
    for(int i=1,lst=0;i<=n+1;++i)
        if(~a[i]){
            ans=ans*C(a[i]-a[lst]+i-lst-1ll,i-lst-1ll)%mod;
            lst=i;
        }
    printf("%lld\n",ans);
    clear();
}
signed main(int argc,char **argv){
//  freopen("order.in","r",stdin);
//  freopen("order.out","w",stdout);
    int T=Input::read();
    while(T--)work();
    return 0;
}