【2024.09.27】NOIP2024 赛前集训-刷题训练（3）
算法一：模拟正常人铺路的过程，每次找区间的最小值，最小值就是本次填的高度，由于出现了若干个0位置，就分裂成若干个子区间去重复上述过程，直到全部变成0。时间复杂度 \(O(nlogn)\)， 瓶颈在预处理 st表。
算法二：若 \(a[i - 1] < a[i]\), 则 \(ans += a[i] - a[i - 1], i \in [0,n]\)。 感性理解一下： \(\forall i, a[i] <= a[i - 1]\) 的情况都会被顺便删掉。
所以其实以下两种写法都是对的：
//写法一
F(i, 2, n + 1) if(a[i] < a[i - 1]) ans += a[i - 1] - a[i];
//写法二
F(i, 1, n) if(a[i] > a[i - 1]) ans += a[i] - a[i - 1];
结论就是如果货币系统里的一些数可以由其他数表示出来，那么这样的数就可以被删掉。
那么每往新的货币系统里加一个数，就把 能由它的若干倍表示的数 都标记上（值域很小），剪下枝就过了。
#include<bits/stdc++.h>
#define F(i,l,r) for (int i(l); i<=(r); ++i)
#define G(i,r,l) for (int i(r); i>=(l); --i)
using namespace std;
using ll = long long;
const int N = 1e5 + 5,mx = 25000;
int t[N], a[N];
int n, T;
signed main(){
// freopen("money.in","r",stdin);
// freopen("money.out","w",stdout);
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> T;
while(T --){
cin >> n;
F(i, 1, n) cin >> a[i];
sort(a + 1, a + n + 1);
if(a[1] == 1){
cout << "1\n";
continue;
}
memset(t, 0, sizeof(t));
t[0] = 1;
int ans = 0;
F(i, 1, n){
if(t[a[i]]) continue;
++ans;
F(j, 0, mx) if(t[j] && !t[j + a[i]]) for(int k = a[i];j + k <= mx; k += a[i]) t[j + k] = 1;
}cout << ans << '\n';
}
return fflush(0),0;
}
\(m = 1\)：自底向上dp就行。
\(a_i = 1\)：菊花图，做法显然。
\(b_i = a_i + 1\)：链，在序列上二分即可。
分支不超过3：根最多三叉，别的点最多二叉，观察一下发现一个儿子的贡献要么向另一个儿子拐，要么穿过父节点继续向上，由此想到自底向上贪心。（提示正解）
综上有80pts。
正解就是扩展一下，记 \(T(u)\) 表示 \(u\) 的子树。记 \(d[u]\) 为 \(T(u)\) 能向上传的最大权值的链。（抛开能计算贡献的链）
\(d[u]\) 和 贡献 靠 \(multiset\) 维护即可。按权值从小到大枚举链，找最小的能和它匹配的链， 匹配后把他们从集合里删掉。
细节是如果 单链权值 就 \(\ge lim\) 就不要放进集合了直接算贡献。
反思一下，对 \(multiset\) 操作太不熟了，有点儿难调。。。代码能力还能提升！
#include<bits/stdc++.h>
#define F(i,l,r) for (int i(l); i<=(r); ++i)
#define G(i,r,l) for (int i(r); i>=(l); --i)
using namespace std;
using ll = long long;
const int N = 1e6 + 5;
bool vis[N];
struct node{
int v,w,ne;
}e[N << 1];
int n, m, idx = 0, num = 0;
int mx[N], first[N], d[N];
void add(int x, int y, int z){
e[++idx] = (node){y, z, first[x]};
first[x] = idx;
}
void go(int u, int f, int lim){
multiset<int> p;
for(int i = first[u]; i; i = e[i].ne){
int v = e[i].v, w = e[i].w;
if(v == f) continue;
go(v, u, lim);
if(d[v] + w>=lim) ++num;
else p.insert(d[v] + w);
}
while(p.size()){
int x = *p.begin();
p.erase(p.begin());
auto it = p.lower_bound(lim - x);
if(it != p.end()){
++ num;
p.erase(it);
}
else d[u] = max(x, d[u]);
}
}
inline bool chk(int lim){
memset(d, 0, sizeof(d));
num = 0;
go(1, 0, lim);
return num >= m;
}
signed main(){
// freopen("track.in","r",stdin);
// freopen("track.out","w",stdout);
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
F(i, 1, n - 1){
int u, v, w;
cin >> u >> v >> w;
add(u, v, w);
add(v, u, w);
}
int l = 0, r = 5e8 + 1, mid;
while(l + 1 < r){
mid = (l + r) >> 1;
if(chk(mid)) l = mid;
else r = mid;
}
cout << l << '\n';
return fflush(0),0;
}