B

Description
初始区间集为\(\{[1,n]\}\)，每次会从中拿出一个区间\([l,r]\)，随机选一个区间内的数\(d\)对区间进行分割，分割后的结果\(\{l,d-1\},\{d+1,r\}\)放回区间集。重复操作直到区间为空。
现给定所有的\([l,r]\)，求对应的\(d\)。
Solution
还原\([l,r]\)的先后关系即可求解。
按\([l,r]\)的\(l\)升序排序，若\(l\)相同，按区间长度降序排序。
（显而易见，短区间由长区间分割而来；而分割后的结果也一定形如\([l,r'],[l',r]\)或\([l,r-1]\)或\([l+1,r]\)）

#include<bits/stdc++.h>
using namespace std;

const int N=1005;
struct range{
	int l,r;
}a[N];
int n,t;
bool cmp(range a,range b){
	if(a.l!=b.l) return a.l<b.l;
	return a.r>b.r;
} 
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		for(int i=1;i<=n;++i)
			scanf("%d%d",&a[i].l,&a[i].r);
		sort(a+1,a+1+n,cmp);
		for(int i=1,d;i<=n;++i){
			if(a[i].l==a[i].r){
				printf("%d %d %d\n",a[i].l,a[i].r,a[i].l);
			}
			else{
				if(a[i+1].l>a[i].l){
					printf("%d %d %d\n",a[i].l,a[i].r,a[i].l);
				}
				else{
					printf("%d %d %d\n",a[i].l,a[i].r,a[i+1].r+1);
				}
			}
		} 
	}
	return 0;
} 

C

Description
\(n\)堆石子，每个堆\(i\)可以取出\(3d\)个石子分\(2d\)给\(i-2\)，\(d\)个给\(i-1\)（\(i\geq 3,3d\leq\)第\(i\)堆拥有的初始石子数），求最小堆的最大值。
Solution
二分+贪心即可。

#include<bits/stdc++.h>
using namespace std;
 
const int N=200005;
int a[N],h[N],n,t;
bool chk(int ans){
	for(int i=1;i<=n;++i) a[i]=h[i];
	for(int i=n,d;i>=3;--i){
		if(a[i]<ans) return false;
		d=min(h[i],(a[i]-ans))/3;
		a[i-1]+=d;
		a[i-2]+=d*2;
	}
	return a[1]>=ans&&a[2]>=ans;
}
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		int l=1,r=0,mid;
		for(int i=1;i<=n;++i){
			scanf("%d",&h[i]);
			r=max(r,h[i]);
		}
		while(l<r){
			mid=(l+r+1)>>1;
			if(chk(mid)) l=mid;
			else r=mid-1;
		}
		printf("%d\n",l);
	}
	return 0;
}

E

Description
给定一个大小为n的树，每个节点有个字符，树的字符串为按中序遍历顺序拼接的字符串。
每个点的字符可以至多重复一次，当且仅当这个点到根的路径上所有节点都重复。至多重复k个节点。
求字典序最小的字符串。
Solution
贪心即可。

• 预处理出每个点是否重复会更优：当且仅当这个点\(c_i\)在中序遍历中，下一个不同于\(c_i\)的字符\(c_j\)满足\(c_i<c_j\)。
• 中序遍历这棵树，只要重复会更优且重复节点总数<k即可重复。
• 当一个点重复不会更优且这个点不会因为左子树重复时，右子树必不需要重复。
• 当找到一个新的需要重复的节点时，可以通过在dfs时传递上一个重复的祖先的深度\(O(1)\)算对k的贡献。

#include<bits/stdc++.h>
using namespace std;

const int N=200005;
int l[N],r[N],fa[N],dfn[N],n,k,cnt;
bool b[N],d[N];
char c[N],s[N];
void init(int u){
	if(l[u]) init(l[u]);
	dfn[++cnt]=u;
	s[cnt]=c[u];
	if(r[u]) init(r[u]);
}
bool dfs(int u,int dep,int lst_dep){
	if(l[u]){
		d[u]=dfs(l[u],dep+1,lst_dep);
	}
	if(d[u]){
		lst_dep=dep;
	}
	else if(dep-lst_dep<=k&&b[u]){
		d[u]=true;
		k-=(dep-lst_dep);
		lst_dep=dep;
	}
	if(r[u]&&(b[u]||d[u])){
		d[u]|=dfs(r[u],dep+1,lst_dep);
	}
	return d[u];
}
int main(){
	scanf("%d%d",&n,&k);
	scanf("%s",c+1);
	for(int i=1;i<=n;++i){
		scanf("%d%d",&l[i],&r[i]);
		if(l[i]) fa[l[i]]=i;
		if(r[i]) fa[r[i]]=i;
	}
	init(1);
	char ch=0;
	for(int i=n;i;--i){
		if(c[dfn[i]]<ch){
			b[dfn[i]]=true;
		}
		if(c[dfn[i]]!=c[dfn[i-1]])
			ch=c[dfn[i]];
	}
	dfs(1,1,0);
	for(int i=1;i<=n;++i){
		printf("%c",c[dfn[i]]);
		if(d[dfn[i]]) printf("%c",c[dfn[i]]);
	}
	return 0;
}