赛后四题
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题
首先考虑固定一个根
\[f[x]=\sum_{v\in son(x)} f[v]+[a[x] \neq a[v]]*(a[v] \oplus a[x])*size[v]
\]
那么做一个换根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;
}