Codeforces Round 926 (Div. 2) solutions (A-D)

ACM
2.6k words

Codeforces Round 926 (Div. 2)

A - Sasha and the Beautiful Array

直接找最大和最小的数取差值即可。

1
2
3
4
5
6
7
8
9
10
11
12
int n;
 
void solve(void){
    cin>>n;
    int minn=INT_MAX,maxx=0;
    for (int i=1,x;i<=n;i++){
        cin>>x;
        minn=min(minn,x);
        maxx=max(maxx,x);
    }
    cout<<maxx-minn<<endl;
}

B - Sasha and the Drawing

分类讨论一下，很显然，我们直接第一行逐个取格子，第一行是每个格子都可以提供22的新对角线贡献的。kk小等于于2n2n的时候，直接输出⌈k/2⌉\lceil k/2\rceil即可。如果k≥2nk\geq 2n，也就是说第一行的格子提供的贡献不够了，再来看最后一行，最后一行除了第一个和第二个格子，每个也可以提供2n2n的贡献，因此在k≤2(n+n−2)k\leq 2(n+n-2)的情况下，我们也可以同理输出⌊k/2⌋\lfloor k/2\rfloor。然后剩下就只有两种情况，4n−4<n≤4n−24n-4<n\leq 4n-2，这两种情况，我们把最后一行剩下两个格子取了就行。

（这里我第一次wa了，后面乱改改过了，发现是因为cout输出double类型会出现科学计数法的问题，这里ceil本来是double类型的，要强制转成long long或者其他整型。）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void solve(void){
    ll n,k;
    cin>>n>>k;
    if (k<=2*n){
        cout<<(ll)(ceil((double)k/2))<<endl;
        return ;
    }
    ll ans=n;
    k-=2*n;
    if (k<=2*(n-2)){
        cout<<(ll)(ans+ceil((double)k/2))<<endl;
        return ;
    }
    k-=2*(n-2);
    ans+=n-2;
    cout<<(ll)(ans+k)<<endl;
}

C - Sasha and the Casino

这题有点像那个经典的赌场问题，就是在本金无限大的情况下，不断赌博是必赢的，因为只要每一次下的赌注足够大，大到赢了一次的奖励能大于前面的损失，即使不断输，只要赢一次，就能翻本。比如假设输赢的概率五五开，第一次赌1块，输了，那第二次赌2块，赢了就能赢4块，翻本。如果还输，就赌8块，以此类推。

所以只需要11到xx次，假设一直输，下的赌注每次都使得如果赢的奖金能翻本并且多一点即可。如果没赌到xx次，本金就不够了，那就必输了，前面的11到xx次，因为我们下的赌注是赢一次能翻本的，所以只要能赢一次，就能继续从头开始继续赢。但是这里我们要求最坏情况下，如果赌到xx次都一直输，接下来就是必胜局了，直接赌上所有剩余本金，如果这次赢的能覆盖之前的所有损失，就是必赢的，如果不能，就是必输的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
ll k,x,a;
 
void solve(void){
    cin>>k>>x>>a;
    ll now=a;
    debug(a);
    for (int i=0;i<x;i++){
        ll y=max(1LL,(ll)floor((double)(a-now)/(double)(k-1))+1);
        now-=y;
        debug(i,y,now);
        if (now<=0){
            cout<<"NO"<<endl;
            return ;
        }
    }
    now*=k;
    if (now>a)
        cout<<"YES"<<endl;
    else
        cout<<"NO"<<endl;
}

D - Sasha and a Walk in the City

很显然最终集合的最大的规模，是这棵树的叶子节点数。

既然是树上问题，考虑一下dp，每个节点u的子树中，设dp[u]为节点u及其子树中的满足不存在任何直接祖先关系的集合的大小，同时要注意，单个节点占据路口也是可以的。假设u节点有一堆儿子v1,v2,...,vm，可以得到递推方程：

dp[u]=∏(1+dp[v])dp[u]=\prod(1+dp[v])

那直接取模就可以了。

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
int n;
vector<int> G[maxn+5];

ll dp[maxn+5];

void dfs(int u,int fa){
    for (int v: G[u])
        if (v!=fa){
            dfs(v,u);
            dp[u]*=(dp[v]+1);
            dp[u]%=mod;
        }
}

void prepare(){
    for (int i=0;i<=n;i++){
        dp[i]=1;
        G[i].clear();
    }
}

void solve(void){
    cin>>n;
    prepare();
    vector<int> in(n+1,0);
    for (int i=1,u,v;i<n;i++){
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1,0);
    ll ans=0;
    for (int i=0;i<=n;i++)
        ans+=dp[i],ans%=mod;
    cout<<ans<<endl;
}