Codeforces Round 899 (Div. 2)

赛后四题

B题直接枚举不存在的元素即可
C题的trick有点像之前abc的某道题，对于奇数位置它一定可以贡献，对于偶数位置，如果它有数选了，那么它就能够贡献。

\(f[i]\)表示到前i个且至少选了一个的最大答案。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))

using namespace std;
typedef double db;
typedef long long ll;
const int N = 2e5 + 5;
const ll inf = 1ll << 60;
ll a[N], n, ans, f[N];
void solve() {
	ans = 0;
	scanf("%lld", &n);

	fo(i, 0, n) f[i] = -inf;
	fo(i, 1, n) scanf("%lld", &a[i]);

	fo(i, 1, n) {
		if (i & 1) {
			f[i] = max(a[i], f[i - 1] + max(0ll, a[i]));
		}
		else {
			f[i] = max(0ll, f[i - 1] + max(0ll, a[i]));
		}

		ans = max(ans, f[i]);

	}
	printf("%lld\n", ans);

}
int main()
{

// #ifdef LOCAL
//  		freopen("in.txt", "r", stdin);
//     	freopen("out.txt", "w", stdout);
// #endif
	
	int T;
	scanf("%d", &T);
	while (T--) {
		solve();
	}

	return 0;
}

 

D题
首先考虑固定一个根

那么做一个换根dp即可

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
using namespace std;
typedef double db;
typedef long long ll;
const int N=2e5+5;
const ll mo=998244353;
ll f[N],g[N],s[N],a[N];
int tot,nex[N*2],head[N],to[N*2],n,x,y;

void add(int x,int y){
	to[++tot]=y; nex[tot]=head[x]; head[x]=tot;
}
void dfs(int x,int y){
	s[x]=1; f[x]=g[x]=0;
	for (int i=head[x];i;i=nex[i]){
		int v=to[i];
		if (v==y) continue;
		dfs(v,x);
		s[x]+=s[v];
		
		if (a[v]==a[x]) f[x]+=f[v];
		else f[x]+=f[v]+s[v]*(a[v]^a[x]);
	}
}
void dg(int x,int y){
	for (int i=head[x];i;i=nex[i]){
		int v=to[i];
		if (v==y) continue;
		if (a[x]==a[v]) {
			g[v]=g[x];
		}
		else {
			g[v]=g[x]+((ll)n-2ll*s[v])*(a[x]^a[v]);
		}
		
		dg(v,x);
	}
}
void solve(){
	scanf("%d",&n);
	tot=0;
	fo(i,1,n) head[i]=0;
	
	fo(i,1,n) scanf("%lld",&a[i]);
	fo(i,1,n-1){
		scanf("%d %d",&x,&y);
		add(x,y); add(y,x);
	}
	
	dfs(1,0);
	
	g[1]=f[1];
	dg(1,0);
	
	fo(i,1,n) printf("%lld ",g[i]);
	printf("\n");
}
int main()
{
//	freopen("data.in","r",stdin);

	int T;
	scanf("%d",&T);
	while (T--){
		solve();
	}
	
	return 0;
}