cf Round 763(Div. 2)(cf Round 763(Div. 2))

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
  • 中序遍历这棵树,只要重复会更优且重复节点总数
  • 当一个点重复不会更优且这个点不会因为左子树重复时,右子树必不需要重复。
  • 当找到一个新的需要重复的节点时,可以通过在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;
}
————————

B

Description
The initial interval set is \ (\ {[1, n] \} \), and an interval \ ([l, R] \) will be taken out each time. The number \ (D \) in an interval will be randomly selected to segment the interval, and the segmented result \ (\ {L, D-1 \}, \ {D + 1, R \} \) will be put back into the interval set. Repeat until the interval is empty.
Given all \ ([l, R] \), find the corresponding \ (D \).
Solution
Restore the order of \ ([l, R] \).
Sort by \ (L \) of \ ([l, R] \). If \ (L \) is the same, sort by interval length in descending order.
(obviously, the short interval is segmented from the long interval, and the result after segmentation must be in the form of \ ([l, R ‘], [l’, R] \) or \ ([l, R-1] \) or \ ([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 \) stones. Each pile \ (I \) can take out \ (3D \) stones, divide \ (2D \) stones into \ (I-2 \), \ (D \) stones into \ (i-1 \) (\ (I \ GEQ 3,3d \ Leq \) the initial number of stones owned by the \ (I \) pile), and calculate the maximum value of the minimum pile.
Solution
Two points + greed.

#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
Given a tree of size n, each node has characters, and the string of the tree is a string spliced in the middle traversal order.
The character of each point can be repeated at most once if and only if all nodes on the path from this point to the root are repeated. Repeat at most k nodes.
Find the string with the smallest dictionary order.
Solution
Just be greedy.

  • It is better to preprocess whether each point is repeated: if and only if this point \ (c_i \) is in the middle order traversal, the next character \ (c_j \) different from \ (c_i \) satisfies \ (c_i < c_j \).
  • If the tree is traversed in medium order, it can be repeated as long as the repetition is better and the total number of repeated nodes is less than k.
  • When the repetition of a point is not better and the point is not repeated because of the left subtree, the right subtree does not need to be repeated.
  • When a new node needs to be repeated is found, the contribution to K can be calculated by passing the depth \ (O (1) \) of the last repeated ancestor in DFS.
#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;
}