心血来潮看了看18年的联赛，感觉自己进步很大= =
T1
对于一个“波”来说，显然需要的次数为最大的数（波峰），对于多个“波”，就每次记录一下从波底到波峰的高度差即可，这可以用差分简单实现
// by SkyRainWind
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mpr make_pair
#define debug() cerr<<"Madoka"<<endl
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define pii pair<int,int>
using namespace std;
typedef long long LL;
const int inf = 1e9, INF = 0x3f3f3f3f, maxn=100005;
int a[maxn], n;
signed main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
int ans = a[1];
for(int i=2;i<=n;i++){
if(a[i] > a[i-1]){
ans += a[i] - a[i-1];
}
}
printf("%d\n",ans);
return 0;
}
T2
显然两种系统\(a,b\)等价当且仅当\(a\)中的数字都能被\(b\)中的数字通过线性组合得到，对1~25000的数跑一个类似于完全背包的dp即可
// by SkyRainWind
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mpr make_pair
#define debug() cerr<<"Madoka"<<endl
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define pii pair<int,int>
using namespace std;
typedef long long LL;
const int inf = 1e9, INF = 0x3f3f3f3f;
int n;
int dp[25005],a[105];
void solve(){
memset(dp,0,sizeof dp);
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
sort(a+1,a+n+1);
int ans = 0;
for(int i=1;i<=n;i++){
if(dp[a[i]])continue;
++ ans;
dp[a[i]] = 1;
for(int j=1;a[i]+j<=25000;j++)dp[a[i] + j] |= dp[j];
}
printf("%d\n",ans);
}
signed main(){
int te;scanf("%d",&te);
while(te --)solve();
return 0;
}
T3
给一个带边权的树，要划分出\(m\)个边不相交的路径，使得路径权值的最小值最大
首先二分答案mid，考虑树形dp，需要维护一个当前结点为根的子树的答案，以及在这种情况下能够向上传的路径权值的最大值
设\(dp[i]\)表示以 i 为根的答案，\(mx[i]\)表示 i 结点的子树能向上传的路径权值的最大值（dfs时顺便加上(i,fa[i])的权值）
\(dp[i] = \sum dp[u] + C\)，其中 C 需要我们将每个儿子向上传的权值两两配对，使权值达到mid，以及在答案最优时向上传的权值要最大
首先想到的是暴力枚举向上传的边，这里有一个精妙的实现：for(int i=-1;i<(int)mp.size();i++)，这样就涵盖了恰好两两匹配的情况。注意(int)必加！！因为\(vector<>.size()\)是unsigned，不能判断负数，时间复杂度是非常不满的O(n^2logn)，结合树的直径可以拿到90pts的好成绩
发现枚举向上传的边这一步是有单调性的，很明显如果上传了边权为w的边，则比w小的边也一定可以上传，于是可以二分上传的边，时间复杂度大概是两个log，可以过
注意vector
// by SkyRainWind
#include <cstdio>
#include <vector>
#include <set>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mpr make_pair
#define debug() cerr<<"Yoshino"<<endl
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define pii pair<int,int>
using namespace std;
typedef long long LL;
const int inf = 1e9, INF = 0x3f3f3f3f,maxn=50005;
int n,m;
vector<pii>g[maxn];
int dp[maxn], mx[maxn];
void dfs(int x,int lim,int fat = -1){
if(~fat && g[x].size() == 1)return ;
vector<int> mp;
for(pii now : g[x]){
int u = now.first, w = now.second;
if(u == fat)continue;
dfs(u, lim, x);
mx[u] += w;
if(mx[u] >= lim)++ dp[x]; // 自成一派
else mp.push_back(mx[u]);
dp[x] += dp[u];
}
sort(mp.begin(),mp.end());
int mpc = mp.size();
int curid = -2, curmx = -inf;
int le = 0, ri = mpc-1, rans;
// 单独考虑全配对情况
int l=0;
int r=mpc-1;
int curres = 0;
while(l < r){
if(mp[l] + mp[r] >= lim)++l, -- r,++ curres;
else ++ l;
}
if(curres > curmx)curmx = curres, curid = -1;
else if(curres == curmx)curid = -1;
// 二分上传哪条边
while(le <= ri){
int mid = le + ri >> 1;
int l = mid == 0 ? 1 : 0;
int r = mid == mpc-1 ? mpc-2 : mpc-1;
int curres = 0;
while(l < r){
if(l == mid){
++l;continue;
}
if(r == mid){
-- r;continue;
}
if(mp[l] + mp[r] >= lim)++l, -- r,++ curres;
else ++ l;
}
if(curres > curmx)curmx = curres, curid = mid, le=mid+1;
else if(curres == curmx)curid = mid, le=mid+1;
else ri = mid-1;
}
if(curid == -2){ // 没有配对，直接取最大
mx[x] = mp[mp.size() - 1];
return ;
}
if(curid == -1){ // 全配对
mx[x] = 0;
dp[x] += curmx;
return ;
}
mx[x] = mp[curid]; // 部分配对
dp[x] += curmx;
}
int check(int lim){
for(int i=1;i<=n;i++)dp[i] = mx[i] = 0;
dfs(1, lim);
if(dp[1] >= m)return 1;
return 0;
}
signed main(){
// freopen("P5021_5.in","r",stdin);
scanf("%d%d",&n,&m);
for(int i=1;i<=n-1;i++){
int x,y,z;scanf("%d%d%d",&x,&y,&z);
g[x].push_back(mpr(y,z)), g[y].push_back(mpr(x, z));
}
int l = 1, r = 1e9, ans;
while(l <= r){
int mid=l+r>>1;
if(check(mid))l = mid+1, ans = mid;
else r = mid-1;
}
printf("%d\n",ans);
return 0;
}