Codeforces Round 926 (Div. 2)#

A - Sasha and the Beautiful Array #

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

1
int n;
2

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

B - Sasha and the Drawing #

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

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

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

C - Sasha and the Casino #

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

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

1
ll k,x,a;
2

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

D - Sasha and a Walk in the City #

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

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

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

那直接取模就可以了。

1
int n;
2
vector<int> G[maxn+5];
3

4
ll dp[maxn+5];
5

6
void dfs(int u,int fa){
7
    for (int v: G[u])
8
        if (v!=fa){
9
            dfs(v,u);
10
            dp[u]*=(dp[v]+1);
11
            dp[u]%=mod;
12
        }
13
}
14

15
void prepare(){
16
    for (int i=0;i<=n;i++){
17
        dp[i]=1;
18
        G[i].clear();
19
    }
20
}
21

22
void solve(void){
23
    cin>>n;
24
    prepare();
25
    vector<int> in(n+1,0);
26
    for (int i=1,u,v;i<n;i++){
27
        cin>>u>>v;
28
        G[u].push_back(v);
29
        G[v].push_back(u);
30
    }
31
    dfs(1,0);
32
    ll ans=0;
33
    for (int i=0;i<=n;i++)
34
        ans+=dp[i],ans%=mod;
35
    cout<<ans<<endl;
36
}

Codeforces Round 926 (Div. 2)#

A - Sasha and the Beautiful Array#

B - Sasha and the Drawing#

C - Sasha and the Casino#

D - Sasha and a Walk in the City#

A - Sasha and the Beautiful Array #

B - Sasha and the Drawing #

C - Sasha and the Casino #

D - Sasha and a Walk in the City #