Educational Codeforces Round 158 (Rated for Div. 2) - VP记录

A. Line Trip

油量必须支持车子通过所有加油站间的空间，还要注意开回来的时候终点不能加油。

#include<cstdio>
#include<algorithm>
using namespace std;

const int N=55;
int n,x,a[N];

int main()
{
	int T; scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&x);
		int ans=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			ans=max(ans,a[i]-a[i-1]);
		}
		ans=max(ans,(x-a[n])<<1);
		printf("%d\n",ans);
	}
	return 0;
}

B. Chip and Ribbon

每一对 \(a_{i-1}<a_i\) 都需要传送到 \(a_i\) 至少 \((a_i-a_{i-1})\) 次，注意开头不需要传送。

#include<cstdio>
#include<algorithm>
using namespace std;

const int N=2e5+5;
int n,a[N];

int main()
{
	int T; scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		long long ans=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			ans+=max(a[i]-a[i-1],0);
		}
		printf("%lld\n",ans-1);
	}
	return 0;
}

C. Add, Divide and Floor

我的洛谷题解

D. Yet Another Monster Fight

我的洛谷题解

E. Compressed Tree

树上 DP，但是统计答案的时候是每一个点都可以是根的。

参考题解

#include<cstdio>
#include<vector>
#include<algorithm>
#include<functional>
using namespace std;

const int N=5e5+5;
const long long INF=1e18;
int n,a[N];

struct Allan{
	int to,nxt;
}edge[N<<1];
int head[N],idx;
inline void add(int x,int y)
{
	edge[++idx]={y,head[x]};
	head[x]=idx;
	return;
}

long long f[N],ans;
void DFS(int x,int fa=0)
{
	vector<long long> son;
	f[x]=a[x];
	ans=max(ans,(long long)a[x]);
	for(int i=head[x];i;i=edge[i].nxt)
	{
		int y=edge[i].to;
		if(y==fa) continue;
		DFS(y,x);
		son.push_back(f[y]);
		ans=max(ans,a[x]+f[y]);
		f[x]=max(f[x],f[y]);
	}
	sort(son.begin(),son.end(),greater<long long>());
	if(son.size()>1)
	{
		long long sum=son[0]+son[1];
		ans=max(ans,sum);
		for(int i=2;i<(int)son.size();i++)
			if(son[i]>0) sum+=son[i];
		f[x]=max(f[x],a[x]+sum);
	}
	if(son.size()>2)
	{
		long long sum=son[0]+son[1]+son[2];
		for(int i=3;i<(int)son.size();i++)
			if(son[i]>0) sum+=son[i];
		ans=max(ans,a[x]+sum);
	}
	return;
}

int main()
{
	int T; scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
			scanf("%d",&a[i]);
		for(int i=1;i<n;i++)
		{
			int x,y; scanf("%d%d",&x,&y);
			add(x,y),add(y,x);
		}
		DFS(1);
		printf("%lld\n",ans);
		
		for(int i=1;i<=n;i++)
			head[i]=f[i]=a[i]=0;
		idx=ans=0;
	}
	return 0;
}