Preface

补题，妈的现在Edu E都做不来这搞毛啊

A. Line Trip

签到

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=55;
int t,n,x,a[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d%d",&n,&x),i=1;i<=n;++i) scanf("%d",&a[i]);
		int ans=2*(x-a[n]); for (i=1;i<=n;++i) ans=max(ans,a[i]-a[i-1]);
		printf("%d\n",ans);
	}
	return 0;
}

B. Chip and Ribbon

不难发现这题转化一下就是每次可以给一段区间内的数都减\(1\)，问最少要几步可以把所有数变成\(0\)，经典差分求解即可

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
int t,n,a[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
		LL ans=0; for (i=1;i<=n;++i) ans+=max(0,a[i]-a[i-1]);
		printf("%lld\n",ans-1);
	}
	return 0;
}

C. Add, Divide and Floor

不难发现我们只要把序列的最大最小值找出来，只要把它们变成相同的，那么整个序列中所有数一定都相同

同时稍作分析会发现所有操作可以归为\(x=0\)或\(x=1\)，并且手玩一下会发现最优策略就是看最小值的奇偶性

如果最小值为奇数就用\(x=1\)，为偶数就用\(x=0\)，这样可以尽量减小两个数的差值

操作次数是\(\log\)级别的，可以直接模拟

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
int t,n,a[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
		int mn=*min_element(a+1,a+n+1),mx=*max_element(a+1,a+n+1);
		vector <int> ans; while (mn!=mx)
		{
			if (mn%2==1) ans.push_back(1),mn=(mn+1)/2,mx=(mx+1)/2;
			else ans.push_back(0),mn/=2,mx/=2;
		}
		printf("%d\n",ans.size());
		if (ans.size()>0&&ans.size()<=n)
		{
			for (auto x:ans) printf("%d ",x); putchar('\n');
		}
	}
	return 0;
}

D. Yet Another Monster Fight

枚举第一次操作的位置\(i\)，分别考虑此时向两边传递的最坏次数

对于\(j<i\)，其最坏需要的初始伤害为\(a_j+n-j\)；对于\(j>i\)，其最坏需要的初始伤害为\(a_j+j-1\)

做一个前缀/后缀max后直接枚举即可

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define int long long
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=300005;
int n,a[N],pre[N],suf[N];
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%lld",&n),i=1;i<=n;++i) scanf("%lld",&a[i]);
	for (pre[0]=0,i=1;i<=n;++i) pre[i]=max(pre[i-1],a[i]+n-i);
	for (suf[n+1]=0,i=n;i>=1;--i) suf[i]=max(suf[i+1],a[i]+i-1);
	int ans=1e18; for (i=1;i<=n;++i) ans=min(ans,max({a[i],pre[i-1],suf[i+1]}));
	printf("%lld\n",ans);
	return 0;
}

E. Compressed Tree

我承认我大物课最后几分钟想这题有点急，但这不是做不出的理由

考虑最后压缩时一个点被删去当且仅当其度数为\(2\)，考虑直接用树形DP求解

当我们把这棵树强制转化成有根树后，一个点的度数的贡献就有两种类型，来自儿子的和来自父亲的

但由于这题的删除操作有着很好的性质：如果要将某个点父亲方向的连边断开，则需要把这个点子树外的所有点都删去

因此我们还是只要像一般的树形DP那样只关系子树状态即可，最后枚举要不要删这个点父亲方向的边即可

令\(f_x\)表示在点\(x\)的子树中，当\(x\)向父亲方向的边保留时能得到的最大权值，转移的话根据\(x\)点的度数讨论下即可，注意当\(x\)只有一个孩子时不能算\(a_x\)的贡献

最后考虑如果要断开\(x\)向父亲方向的边时也是类似的情况，注意当\(x\)有两个孩子时不能算\(a_x\)的贡献

因为当一个点的孩子数量\(\ge 3\)时就不再有区别了，因此开一个\([0,3]\)的辅助数组即可

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define int long long
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=500005,INF=1e18;
int t,n,a[N],x,y,f[N],ans; vector <int> v[N];
inline void DFS(CI now=1,CI fa=0)
{
	int g[4]={0,-INF,-INF,-INF}; RI i;
	for (auto to:v[now]) if (to!=fa)
	{
		DFS(to,now); for (i=3;i>=0;--i)
		g[min(i+1,3LL)]=max(g[min(i+1,3LL)],g[i]+f[to]);
	}
	for (f[now]=-INF,i=0;i<4;++i)
	{
		f[now]=max(f[now],g[i]+(i==1?0:a[now]));
		ans=max(ans,g[i]+(i==2?0:a[now]));
	}
}
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%lld",&t);t;--t)
	{
		RI i; for (scanf("%lld",&n),i=1;i<=n;++i) scanf("%lld",&a[i]),v[i].clear();
		for (i=1;i<n;++i) scanf("%lld%lld",&x,&y),v[x].push_back(y),v[y].push_back(x);
		ans=0; DFS(); printf("%lld\n",ans);
	}
	return 0;
}