Educational Codeforces Round 158 Solution (Chinese)

Правка en1, от a999999, 2023-11-27 09:59:19

个人博客地址:blog.jerryhzy.top 比赛链接 Educational Codeforces Round 158 (Rated for Div. 2)

目前进度:

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))$。

返程和去程一样,不用再统计。

代码

```cpp
#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 想尽可能少的使用移动

Unable to parse markup [type=CF_MATHJAX]

\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}$。

代码

```cpp
#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$$$ 且为偶数,则

Unable to parse markup [type=CF_MATHJAX]

\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$,所以只用考虑数列中的最小值和最大值,其他值经过操作后也一定夹在两数中间。

代码

```cpp
#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$$$ 时的答案为 $\max \lbrace pre_{i-1}, a_i, nxt_{i+1} \rbrace $,取最小值即可。

代码

```cpp
#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$$$ 背包的写法,非常巧妙。

代码

```cpp
#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

简要翻译

没看懂呢

思路分析

没想出来呢

代码

没写呢

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en11 Английский a999999 2023-11-27 10:18:08 0 (published)
en10 Английский a999999 2023-11-27 10:17:51 5
en9 Английский a999999 2023-11-27 10:14:54 3 (saved to drafts)
en8 Английский a999999 2023-11-27 10:12:39 41 (published)
en7 Английский a999999 2023-11-27 10:09:12 1 Tiny change: '以有 $ans = max(ans,2(' -> '以有 $ans = \max(ans,2(' (saved to drafts)
en6 Английский a999999 2023-11-27 10:07:58 50 (published)
en5 Английский a999999 2023-11-27 10:06:55 210
en4 Английский a999999 2023-11-27 10:04:39 42
en3 Английский a999999 2023-11-27 10:00:34 13
en2 Английский a999999 2023-11-27 10:00:04 6
en1 Английский a999999 2023-11-27 09:59:19 7599 Initial revision (saved to drafts)