Educational Codeforces Round 158 Solution

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

目前进度：

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

A. Line Trip

简要翻译

在一维数轴上，有一辆车，刚开始在 \(0\) 且油箱为满，走一个单位消耗一升油，经过 \(a_1,a_2\ldots a_n\) 处可加满油。

现在需要从 \(0\) 走到 \(x\) 再走回 \(0\)，求能完成路径的油箱油量最小值。

思路解析

先不考虑回程，设 \(a_0=0\)，则 \(ans = \underset{1\le i\le n}{max} \lbrace a_{i}-a_{i-1} \rbrace\)。

在 \(x\) 处转弯时不能加油，所以有 \(ans = max(ans,2(x-a_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
#include<algorithm>
#include<iostream>
const int N=100;
int a[N],n,x;
void work(){
    std::cin>>n>>x;
    for(int i=1;i<=n;++i)
        std::cin>>a[i];
    int ans=2*(x-a[n]);
    for(int i=1;i<=n;++i)
        ans=std::max(ans,a[i]-a[i-1]);
    std::cout<<ans<<std::endl;
}
signed main(int argc,char **argv){
//  freopen("order.in","r",stdin);
//  freopen("order.out","w",stdout);
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int T;
    std::cin>>T;
    while(T--)
        work();
    return 0;
}

B. Chip and Ribbon

简要翻译

有一列 \(n\) 个格子和一个指针，一开始格子里的数 \(a_i=0\) 。

第 \(1\) 步，Mococarp 会把指针放在第一个格子上，接下来每一步可以做下列两种移动之一：

  1. 若指针在第 \(i\) 个格子上，且 \(i \neq n\)，则将指针放在 \(i+1\) 上。

  2. 将指针放在任意一个格子上（可以放在同一个格子上）。

每一步之后，若指针在第 \(x\) 个格子上，则 \(a_x\) 加一。

现在，Mococarp 想尽可能少的使用移动 \(2\)，使得 \(\forall i\in [1,n],a_i=c_i\)。

思路解析

只使用移动 \(1\) 时相当于给一个区间加一，问题转化为用多少个区间可以使 \(i\) 被 \(c_i\) 个区间包含。

那么 \(c_i>c_{i-1}\) 时表示有 \(c_i -c_{i-1}\) 个区间要从 \(i\) 开始，\(ans+=c_i-c_{i-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
#include<algorithm>
#include<iostream>
#include<vector>
using std::cin;
using std::cout;
using std::endl;
using std::vector;
typedef long long ll;
const int N = 200010;
ll c[N],n;
void work(){
    cin>>n;
    for(int i=1;i<=n;++i)
        cin>>c[i];
    ll ans=0;
    for(int i=1;i<=n;++i)
        if(c[i]>c[i-1])
            ans+=c[i]-c[i-1];
    cout<<ans-1<<endl;
}
signed main(int argc,char **argv){
//  freopen("order.in","r",stdin);
//  freopen("order.out","w",stdout);
    cin.tie(nullptr)->sync_with_stdio(false);
    int T;
    cin>>T;
    while(T--)
        work();
    return 0;
}

C. Add, Divide and Floor

简要翻译

有一个数组 \(\lbrace a_n \rbrace\)，每次可以选一个 \(x\)，将所有 \(a_i\) 赋值为 \(\lfloor \dfrac{a_i+x}{2} \rfloor\)，求最少次数使 \(a_1=a_2=\cdots=a_n\)。

思路解析

先考虑两个数 \(x,y(x<y)\) 如何化为相等值。

考虑两者的差值，若选的数 \(v \ge 2\) 则总有等效操作。

如果 \(v\ge 2\) 且为偶数，则 \(\lfloor \dfrac{x+v}{2} \rfloor = \lfloor \dfrac{x}{2} \rfloor+\dfrac{v}{2}\)，\(\lfloor \dfrac{y+v}{2} \rfloor = \lfloor \dfrac{y}{2} \rfloor+\dfrac{v}{2}\)，和直接除以二的效果相同。

如果 \(v\ge 2\) 且为奇数，则和加一再除以二的效果相同。

观察样例，在 \(x\) 为奇数 且 \(y\) 为偶数时，加一再除以二相当于除以二后只给 \(x\) 加一。

其他情况下，加一再除以二不如直接除以二。

因为 \(x\le y \Leftrightarrow \lfloor \dfrac{x+v}{2} \rfloor \le \lfloor \dfrac{y+v}{2} \rfloor\)，所以只用考虑数列中的最小值和最大值，其他值经过操作后也一定夹在两数中间。

代码

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
#include<algorithm>
#include<iostream>
#include<vector>
using std::cin;
using std::cout;
using std::endl;
using std::vector;
typedef long long ll;
const int N=200010;
int a[N],n;
int Ans[N],len;
void work(){
    cin>>n;
    len=0;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    std::sort(a+1,a+n+1);
    ll x=a[1],y=a[n];//仅最小值与最大值就可以了
    if(n==1)
        cout<<0<<endl;
    else{
        while(x!=y){
            if((x&1)==1&&(y&1)==0){//x 奇数 && y 偶数, +1 /2
                Ans[++len]=1;
                x=(x+1)>>1;
                y=(y+1)>>1;
            }
            else{//其他, +0 /2
                Ans[++len]=0;
                x>>=1;
                y>>=1;
            }
        }
        cout<<len<<endl;
        if(len<=n){
            for(int i=1;i<=len;++i)
                cout<<Ans[i]<<' ';
            cout<<endl;
        }
    }
}
signed main(int argc,char **argv){
//  freopen("order.in","r",stdin);
//  freopen("order.out","w",stdout);
    cin.tie(nullptr)->sync_with_stdio(false);
    int T;
    cin>>T;
    while(T--)
        work();
    return 0;
}

D. Yet Another Monster Fight

简要翻译

有 \(n\) 个怪兽，第 \(i\) 个的生命值为 \(a_i\)。

Vasya 有闪电法术，他可以选择初始威力 \(x\) 和攻击的第一个怪兽 \(i_1\)。

每次攻击后，闪电会随机攻击一个尚未被攻击且旁边有被攻击过怪兽的怪兽。

第 \(k\) 次攻击的怪兽 \(i_k\) 收到 \((x-k+1)\) 点伤害，这个值大于等于 \(a_i\) 会使怪兽死亡。

现在 Vasya 想确定最小的 \(x\)，使得在适当挑选 \(i_1\) 后，无论闪电的攻击顺序如何，所有怪兽都会死亡。

思路解析

对于 \(a_i\)，考虑 \(i_1<i\) 和 \(i_1>i\) 的情况。

  1. \(i_1<i\)：\(a_i\) 能影响 \(x\) 取值的最坏情况是，把前 \(i-1\) 个数都消灭之后再消灭 \(a_i\)，对应的 \(x\) 至少为 \(a_i+i-1\)。
  2. \(i_1>i\)：最坏情况变为，把后面 \(a_{i+1} \sim a_n\) 都消灭后再消灭 \(a_i\)，对应的 \(x\) 至少为 \(a_i+n-i\)。

第一种情况求后缀，第二种情况求前缀（\(\max\)），然后 \(i_1=i\) 时的答案为 $pre_{i-1}, a_i, nxt_{i+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
#include<algorithm>
#include<iostream>
#include<vector>
using std::cin;
using std::cout;
using std::endl;
using std::max;
typedef long long ll;
const int N=300010;
ll a[N],pre[N],nxt[N],n;
void work(){
    cin>>n;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    for(int i=1;i<=n;++i)
        pre[i]=a[i]+n-i,// i1 > i
        nxt[i]=a[i]+i-1;// i1 < i
    ll ans=0x3f3f3f3f3f3f3f3f;
    for(int i=2;i<=n;++i)
        pre[i]=max(pre[i],pre[i-1]);
    for(int i=n-1;i;--i)
        nxt[i]=max(nxt[i],nxt[i+1]);
    nxt[n+1]=pre[0]=0;
    for(int i=1;i<=n;++i)
        ans=std::min(ans,max(a[i],max(pre[i-1],nxt[i+1])));
    cout<<ans<<endl;
}
signed main(int argc,char **argv){
//  freopen("order.in","r",stdin);
//  freopen("order.out","w",stdout);
    cin.tie(nullptr)->sync_with_stdio(false);
    int T=1;
    while(T--)
        work();
    return 0;
}

E. Compressed Tree

简要翻译

有一棵 \(n\) 个点的树，每个点有权值 \(a_i\)。

在第一阶段，你可以选择任意一个有至多 \(1\) 条边的点，并删除这个点和它所连的边。可以重复任意次。

在第二阶段，所有度为 \(2\) 的点将被删去，原来和它相连的 \(2\) 个点之间生成一条新边。一直重复直到不存在度为 \(2\) 的点。

求压缩后剩下的点的权值和最大值。注意，权值可以是负数。

思路分析

比赛时想到树形 dp，但是想到换根去了，最后浪费一个小时。

官方题解的说法，是按保不保留 \(x\) 与父亲 \(fa_x\) 的边，以及 \(x\) 保留儿子的个数来讨论的。

设 \(f_x\) 为保留边 \((x,fa_x)\) 时，\(x\) 及其子树内压缩后的最大权值和。

则讨论 \(x\) 保留儿子的个数：

  1. 不保留： 只保留 \(x\) 作为叶子，\(f_x =\max(f_x,a_x)\)。

  2. 保留 \(1\) 个：那么 \(x\) 恰好有两条边，压缩后消失，\(f_x=\max(f_x,\underset{y}{\max}f_y)\)。

  3. 保留 \(2\) 个及以上：\(x\) 可以保留，\(f_x=\max(f_x,a_x+\underset{y}{\sum}\max(0,f_y))\)，至少选两个 \(f_y\)。

考虑不保留边 \((x,fa_x)\) 时，\(x\) 子树外的节点全部都被删除了。

再讨论保留儿子的个数：

  1. 不保留：\(ans=\max(ans,a_x)\)。

  2. 保留 \(1\) 个：\(ans=\max(ans,a_x+\underset{y}{max}f_y)\)。

  3. 保留 \(2\) 个：\(x\) 恰好会被压缩，\(ans=\max(ans,\underset{y_1,y_2}{\max}(f_{y_1}+f_{y_2}))\)。

  4. 保留 \(3\) 个及以上：\(ans=\max(ans,\underset{y}{\sum}\max(0,f_y))\)，至少选三个 \(f_y\)。

儿子个数用类似 \(01\) 背包的写法，非常巧妙。

代码

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
#include<algorithm>
#include<iostream>
#include<vector>
using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::max;
typedef long long ll;
const ll inf=0x3f3f3f3f3f3f3f3f;
const int N=500010;

vector<int> ver[N];
ll val[N];
ll f[N],ans;
int n;
void clear(){
    for(int i=1;i<=n;++i)
        ver[i].clear();
    ans=0;
}
void dfs(int x,int fa){
    vector<ll> sum(4, -inf);
    sum[0]=0;
    for(int y : ver[x]){
        if(y==fa)continue;
        dfs(y,x);
        sum[3]=max(sum[3],sum[3]+f[y]);//更新 f[y] 的和
        for(int j=3;j;--j)// 更新选 1/2 个时 f[y] 的最优值
            sum[j]=max(sum[j],sum[j-1]+f[y]);
    }
    f[x]=-inf;
    for(int j=0;j<4;++j)
        f[x]=max(f[x],sum[j]+(j==1?0:val[x])),
        ans=max(ans,sum[j]+(j==2?0:val[x]));
}
void work(){
    cin>>n;
    clear();
    for(int i=1;i<=n;++i)
        cin>>val[i];
    for(int i=1,x,y;i<n;++i){
        cin>>x>>y;
        ver[x].push_back(y);
        ver[y].push_back(x);
    }
    dfs(1,0);
    cout<<ans<<endl;
}
signed main(int argc,char **argv){
//  freopen("order.in","r",stdin);
//  freopen("order.out","w",stdout);
    cin.tie(nullptr)->sync_with_stdio(false);
    int T;
    cin>>T;
    while(T--)
        work();
    return 0;
}

F. Landscaping

简要翻译

没看懂呢

思路分析

没想出来呢

代码

没写呢