Codeforces Round 977 (Div. 2, based on COMPFEST 16 - Final Round) （A-E3）
写在前面
阳间比赛时间总出不太能做的阴间题
印尼的场，final round质量也还ok，算是学了两个经典trick吧
题目
A. Meaning Mean
排个降序后从小的开始合就好了，直觉上是哈夫曼树的合并方式，
但是只固定了第一个，后面的没有实时维护有序，也过了
代码
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,ll> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
typedef long long ll;
const int N=55;
int t,n;
vector<int>a;
int main(){sci(t);while(t--){sci(n);a.resize(n);rep(i,1,n)sci(a[i-1]);sort(a.begin(),a.end(),greater<int>());while(SZ(a)>1){int x=a.back();a.pop_back();int y=a.back();a.pop_back();a.pb((x+y)/2);}pte(a[0]);}return 0;
}
B. Maximize Mex
这里是写了个O(nlogn)的，当然可以写成O(n)的，增序检查i，i用完了就留给i+x
代码
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,ll> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
typedef long long ll;
const int N=55;
int t,n,x,v;
map<int,int>p,q;
int main(){sci(t);while(t--){sci(n);sci(x);q.clear();p.clear();rep(i,1,n){sci(v);q[v]++;}int mex=0;rep(i,0,n){if(q[i]){q[i]--;p[i%x]+=q[i];continue;}else if(p[i%x]){p[i%x]--;continue;}mex=i;break;}pte(mex);}return 0;
}
C1-C2. Adjust The Presentation（set维护前驱后继）
首先性质是，考虑b序列里的每个首次出现的数，需要和a序列里一一对应，
因为剩下的非首次位置，总能通过你的重新安排，使得它能在想要的时机出现
赛中写了个线段树，维护v当前在b序列的位置减v在a序列的位置，
然后需要让所有值都是0，感觉蠢完了
实际上之前也出过一个lca的题，维护相邻项即可，
EPIC Institute of Technology Round August 2024 D2. DFS Checker (Hard Version)（dfs序性质 lca）_epic institute of technology round august 2024 (di-CSDN博客
只需要关注对于每个a序列里的v，记它的前驱是pre[v]，
v在b序列里的首次出现位置，
也需要满足在pre[v]在b序列里的首次位置的后面，
每次修改最多影响两个位置，对应影响其前驱和后继，
动态维护当前不合法的个数cnt即可
代码
#include<bits/stdc++.h>
using namespace std;
// #define DEBUG
#ifdef DEBUG
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define debug(...) [](auto...a){((cout<<a<<' '),...)<<endl;}(#__VA_ARGS__,":",__VA_ARGS__)
#define debugv(v) do{cout<<#v<<" : {";for(int izxc=0;izxc<v.size();++izxc){cout<<v[izxc];if(izxc+1!=v.size())cout <<", ";}cout<<"}"<<endl;}while(0)
#define debugmp(mp) do{cout<<#mp<<" : { ";for(auto p:mp){cout<<'['<<p.first<<" -> "<<p.second<<"] ";}cout<<"}"<<endl;}while(0)
#define debugset(s) do{cout<<#s<<" : {";for(auto x:s)cout<<x<<' ';cout<<"}"<<endl;}while(0)
#else
#define debug(...)
#define debugv(v)
#define debugmp(mp)
#define debugset(s)
#endif
typedef long long ll;
typedef pair<int, int> pii;const int N = 2e5+5;
int a[N], pre[N], nxt[N], b[N];
set<int> s[N];void solve() {int n, m, q; cin >> n >> m >> q;for(int i = 1; i <= n; i++) cin >> a[i];for(int i = 1; i <= n; i++) {if(i > 1) pre[a[i]] = a[i - 1];else pre[a[i]] = 0;if(i < n) nxt[a[i]] = a[i + 1];else nxt[a[i]] = 0;}for(int i = 1; i <= n; i++) {s[a[i]].clear();s[a[i]].insert(m + i);}for(int i = 1; i <= m; i++) {cin >> b[i];s[b[i]].insert(i);}int cnt = 0;for(int i = 2; i <= n; i++) {if(*s[a[i - 1]].begin() >= *s[a[i]].begin()) cnt++;}if(cnt == 0 ) cout << "YA" << endl;else cout << "TIDAK" << endl;while(q--) {int pos, t; cin >> pos >> t;if(b[pos] != t) {int x = b[pos];int tcnt = 0;if(pre[x] && *s[pre[x]].begin() >= *s[x].begin()) tcnt--;if(nxt[x] && *s[x].begin() >= *s[nxt[x]].begin()) tcnt--;s[x].erase(pos);if(pre[x] && *s[pre[x]].begin() >= *s[x].begin()) tcnt++;if(nxt[x] && *s[x].begin() >= *s[nxt[x]].begin()) tcnt++;cnt += tcnt;tcnt = 0;x = t;if(pre[x] && *s[pre[x]].begin() >= *s[x].begin()) tcnt--;if(nxt[x] && *s[x].begin() >= *s[nxt[x]].begin()) tcnt--;s[x].insert(pos);if(pre[x] && *s[pre[x]].begin() >= *s[x].begin()) tcnt++;if(nxt[x] && *s[x].begin() >= *s[nxt[x]].begin()) tcnt++;cnt += tcnt;b[pos] = t;}if(cnt == 0) cout << "YA" << endl;else cout << "TIDAK" << endl;}
}int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int T; cin >> T;while(T--) solve();return 0;
}D. Boss, Thirsty（dp优化）
单写了一篇博客，这里不再赘述了
Codeforces Round 977 (Div. 2, based on COMPFEST 16 - Final Round) D. Boss, Thirsty（前缀后缀max dp优化）-CSDN博客
代码
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=105,M=1e4+10;
const ll INF=1e15;
int t,n,m;
ll sol(){sci(n),sci(m);vector<vector<int>>a(n+1,vector<int>(m+1,0));vector<vector<ll>>f(n+1,vector<ll>(m+2,-INF));vector<vector<ll>>g(n+1,vector<ll>(m+2,-INF));vector<ll>pre(m+2,-INF),suf(m+2,-INF),sum(m+2,0);ll ans=-INF;rep(i,1,n){pre[0]=suf[m+1]=-INF;rep(j,1,m){sci(a[i][j]);sum[j]=sum[j-1]+a[i][j];}rep(j,1,m){pre[j]=max(pre[j-1],sum[m]-sum[j-1]);}per(j,m,1){suf[j]=max(suf[j+1],sum[j]);}auto premax=[&](int j){if(j<1)return 0ll;return pre[j]-(sum[m]-sum[j]);};auto sufmax=[&](int j){if(j>m)return 0ll;return suf[j]-sum[j-1];};if(i==1){rep(j,1,m){f[i][j]=sufmax(j);g[i][j]=premax(j);}}else{auto f1=[&](int k){return f[i-1][k]+sum[k]+max(0ll,sufmax(k+1));};auto f2=[&](int k){return f[i-1][k]-sum[k-2]+max(0ll,premax(k-2));};auto g1=[&](int k){return g[i-1][k]-sum[k-1]+max(0ll,premax(k-1));};auto g2=[&](int k){return g[i-1][k]+sum[k+1]+max(0ll,sufmax(k+2));};int p1=m,p2=m-1;per(j,m-1,1){if(f1(j+1)>f1(p1))p1=j+1;if(g2(j)>g2(p2))p2=j;f[i][j]=max(f1(p1),g2(p2))-sum[j-1];}int p3=1,p4=2;rep(j,2,m){if(g1(j-1)>g1(p3))p3=j-1;if(f2(j)>f2(p4))p4=j;g[i][j]=max(g1(p3),f2(p4))+sum[j];}}// rep(j,1,m){// printf("i:%d j:%d f:%lld g:%lld\n",i,j,f[i][j],g[i][j]);// }}rep(j,1,m){ans=max(ans,f[n][j]);ans=max(ans,g[n][j]);}return ans;
}
int main(){sci(t);while(t--){ptlle(sol());}return 0;
}
/*
f[i][j]表示i行j列作为左端点必取的最大和
g[i][j]表示i行j列作为右端点必取的最大和
f[i][j]=max(k从j+1到m f[i-1][k]+sum[j,k]+sufmax[k+1:m]) sum[k]-sum[j-1] (f1)
g[i][j]=max(k从1到j-1 g[i-1][k]+sum[k,j]+premax[1:k-1]) sum[j]-sum[k-1] (g1)
f[i][j]=max(k从j到m-1 g[i-1][k]+sum[j,k+1]+sufmax[k+2:m]) sum[k+1]-sum[j-1] (g2)
g[i][j]=max(k从2到j f[i-1][k]+sum[k-1,j]+premax[1:k-2]) sum[j]-sum[k-2] (f2)
*/E1-E3. Digital Village（树形背包 dp优化）
也单写了一篇博客
Codeforces Round 977 (Div. 2) E. Digital Village（树形背包 kruskal重构树 凸函数 闵可夫斯基和(min,+)差分优化）-CSDN博客
代码
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=2e5+10,M=4e5+10;
const ll INF=1e15;
int t,n,m,p,v,c,par[M],sz[M],W[M];
ll ans,dp[M];
vector<ll>f[M];
struct edge{int u,v,w;
}e[N];
int find(int x){return par[x]==x?x:par[x]=find(par[x]);
}
bool operator<(edge a,edge b){return a.w<b.w;
}
void dfs(int u,int fa){dp[u]=0;for(auto &v:f[u]){dfs(v,u);dp[u]=max(dp[u],dp[v]);}for(auto &v:f[u]){if(dp[u]==dp[v]){dp[v]=0;break;}}if(u<c){dp[u]+=1ll*sz[u]*(W[fa]-W[u]);}
}
int main(){sci(t);while(t--){sci(n),sci(m),sci(p);rep(i,1,n){par[i]=i;sz[i]=W[i]=0;}rep(i,1,p){sci(v);sz[v]=1;}rep(i,1,m){scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);}sort(e+1,e+m+1);c=n;rep(i,1,m){int u=find(e[i].u),v=find(e[i].v),w=e[i].w;if(u==v)continue;W[++c]=w;sz[c]=0;par[u]=par[v]=par[c]=c;f[c].pb(u);f[c].pb(v);sz[c]=sz[u]+sz[v];}dfs(c,0);ll ans=1ll*p*W[c];sort(dp+1,dp+c+1,greater<ll>());rep(i,1,n){ans-=dp[i];printf("%lld%c",ans," \n"[i==n]);}rep(i,1,c){f[i].clear();}}return 0;
}
/*
设kruskal重构树上点x有直连儿子y1、y2假设y1内子树所有点都在y1处集结（已经通过y1及子树内的边联通），
如果有一个宽带在y1所在的连通块里，
就能阻止y1子树内所有点通过点x进入兄弟y2子树，
也就是x这条边权实际不需要连，也就是能省去y1->x增量的贡献递归往下考虑，放的这一个宽带，
可以满足既在y1连通块里，也在y1直连儿子z1的连通块里，
这样就能省去z1->y1增量的贡献，取二者更大的那个显然更优，递归到底实际是一个叶子，也就是原图上的点
所以放一个宽带最优影响的是一条权值和最大的重链
那么将kruskal重构树树链剖分后，按权值链降序贪心即可由于实际转移是一个树形背包的形式，函数也都是凸函数，
所以闵可夫斯基和(min,+)卷积可以被拆成差分，即f(i+1)可以由f(i)得到
*/