【2024.09.27】NOIP2024 赛前集训-刷题训练（3）

「NOIP2018 提高组」铺设道路

算法一：模拟正常人铺路的过程，每次找区间的最小值，最小值就是本次填的高度，由于出现了若干个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];
	

「NOIP2018 提高组」货币系统

结论就是如果货币系统里的一些数可以由其他数表示出来，那么这样的数就可以被删掉。

那么每往新的货币系统里加一个数，就把 能由它的若干倍表示的数 都标记上（值域很小），剪下枝就过了。

#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;
}

「NOIP2018 提高组」赛道修建

\(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;
}