NOIP2024模拟11:忠于自我

T1

• 一句话题意:有若干个容量为 \(L\) 的包,从左往右装物品,当前包还能装则装,否则必须重开一个包装进去,对于\(\forall i \in [1,n]\), 问想要以此装入第 \(i \sim n\) 个物品需要开多少个包?
• 结论题:倒着装和正着装所需要的包数是一样的.
  • 感性理解:在"正着装"的基础上把物品尽量往后面的包里放,就变成了"倒着装"的情况,相当于全是内部流动,总包数不变.

#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)
#define int long long
using ll = long long;
using namespace std;
const int N=2e5+5;
const ll inf=1e18;
int n,L;
int a[N],ans[N];
signed main(){
	//freopen("pack.in","r",stdin);
	//freopen("pack.out","w",stdout);
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>L; F(i,1,n) cin>>a[i];
	int sum=0; ans[n+1]=1;
	G(i,n,1){
		ans[i]=ans[i+1];
		if(sum+a[i]>L) ++ans[i],sum=0;
		sum+=a[i];
	}
	F(i,1,n) cout<<ans[i]<<" ";
	return 0;
}

T2

• 给定一个元素 \(n\) 和一个可重集 \(B\), 每次从 \(B\) 中选一个数 \(x\), 将 \(n\) 变成 \(\lfloor \frac{n}{x} \rfloor\), 问可以将 \(n\) 变成多少个不同的数
• 开个\(set\)或者 \(unorderedmap\),一个一个元素地暴力试除即可,显然这样的复杂度是 log级别的(想到这个log很关键).假设 \(B\) 刚好包含前\(10\)个质数,答案的最大值为 \(458123\).
• 设答案大小为 \(A\), 则时间复杂度不超过为 \(O(A \times \sum log_x^A)\).

#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)
#define int long long
using ll = long long;
using namespace std;
const ll inf=1e18;
set<int> s,t;
int a[100];
int n,m,ans=0,cnt=0;
signed main(){
	freopen("set.in","r",stdin);
	freopen("set.out","w",stdout);
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>m; 
	s.emplace(n);
	F(i,1,m){
		cin>>a[i];	
		cnt=0;
		for(auto x:s){
			t.clear(); int y=x;
			while(y/=a[i]){
				if(s.count(y)) break;
				t.emplace(y);
			}
			for(auto v:t) s.emplace(v);
		}
	}
	cout<<s.size()+1;
	return 0;
}

T3

• 对于每个 \(i\), 预 处理 \(1 \sim i-1\) 的 \(max,cmax\) 和 \(i+1 \sim n\) 的 \(min,cmin\) 所在的位置.

  • 每轮boruvka都需要重新求,是动态的
  • 注意要保证最大值和次大值对应的集合不是同一个

• Boruvka求最小生成树

  • 用每个点可以连出的最小边更新Best
    • \((pre_i, i)\)
    • \((i,suf_i)\)
    • \(dis(u,v)\)求任意两点距离
  • Merge

• 数组梳理:

  fa[i]

  best[i]:集合i的最佳边的终点,每轮都重置

  val[i]:集合i的最佳边的权值,每轮都重置

  cmin[i],cmax[i]

#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)
#define int long long
using ll = long long;
using namespace std;
const int N=1e6+5;
const ll inf=1e18;
int n;
int x[N],pre[N][2],suf[N][2],fa[N],best[N],val[N];
int get(int x){
	return (fa[x]!=x) ? fa[x]=get(fa[x]) : fa[x];
}
void update(int *A,int i,const auto &cmp){
	if(!i) return ;
	int fA0=get(A[0]),
		fA1=get(A[1]),
		fi=get(i);
	assert(A[0] == 0 || A[1] == 0 || fA0 != fA1);
	if(A[0]==0 || cmp(x[A[0]],x[i])){
		if(fA0==fi){
			A[0]=i;
		}
		else{
			A[1]=A[0];
			A[0]=i;
		}
	}
	else if(A[1]==0|| cmp(x[A[1]],x[i])){
		if(fA0!=fi){
			A[1]=i;
		}
	}
}
void update_max(int *A,int i){
	update(A,i,less<int>());
}
void update_min(int *A,int i){
	update(A,i,greater<int>());
}
int ask(int *A,int i){
	if(get(A[0])!=get(i))
		return A[0];
	return A[1];
}
int dis(int p,int q){
	if(p>q) swap(p,q);
	return x[q]-x[p];
}
int solve(){
	cin>>n; F(i,1,n) cin>>x[i],fa[i]=i;
	int update=n-1,sum=0;
	while(update){
//		cout<<update<<"\n";
		F(i,0,n+1) pre[i][0]=pre[i][1]=suf[i][0]=suf[i][1]=0;
		F(i,1,n){
			if(i!=1){
				update_max(pre[i],pre[i-1][0]);
				update_max(pre[i],pre[i-1][1]);
			}
			update_max(pre[i],i);
		}
		G(i,n,1){
			if(i!=n){
				update_min(suf[i],suf[i+1][0]);
				update_min(suf[i],suf[i+1][1]);
			}
			update_min(suf[i],i);
		}
		F(i,1,n) best[i]=0,val[i]=2e9 + 50;
		F(i,1,n){
			int premax=ask(pre[i],i),pv=dis(premax,i);
			int sufmin=ask(suf[i],i),sv=dis(sufmin,i);
			int o=get(i);
			if(premax && pv<val[o]) best[o]=premax,val[o]=pv;
			if(sufmin && sv<val[o]) best[o]=sufmin,val[o]=sv;
		}
		F(i,1,n){
			if(i==get(i) && get(i)  != get(best[i])){
				update--;
				sum+=val[i];
				fa[get(i)]=get(best[i]);
			}
		}
	}
	return sum;
}
signed main(){
	freopen("mst.in","r",stdin);
	freopen("mst.out","w",stdout);
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cout<<solve();
	return 0;
}