Codeforces Round 635 (Div.2) Solution (Problem A ~ Problem D)

打完这场，终于上紫了。我好菜啊。

Problem A

题意：

给定 $a,b,c,d$。要求选取三个正整数 $x,y,z$（$a \leq x \leq b,b \leq y \leq c,c \leq z \leq d$），使得以 $x,y,z$ 为三边长能组成一个三角形。

$1 \leq a \leq b \leq c \leq d \leq 10^9$

做法：

因为三角形任意两边之和大于第三边，很容易想到将两条短边 $x,y$ 取最长，长边 $z$ 取最短。则 $x=b,y=c,z=c$ 一定是一组合法解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# include <bits/stdc++.h>
# define rr register
const int N=100010,INF=0x3f3f3f3f;
inline int read(void){
	int res,f=1;
	char c;
	while((c=getchar())<'0'||c>'9')
		if(c=='-')f=-1;
	res=c-48;
	while((c=getchar())>='0'&&c<='9')
		res=res*10+c-48;
	return res*f;
}
int main(void){
	int T;
	T=read();
	while(T--){
		int a=read(),b=read(),c=read(),d=read();
		printf("%d %d %d\n",b,c,c);
	}

	return 0;
}

Problem B

题意：

给定正整数 $x$ 和两种操作。第一种操作将 $x$ 变为 $\lfloor \dfrac x2\rfloor+10$，第二种操作将 $x$ 减去 $10$。

你可以进行第一种操作最多 $n$ 次，第二种操作最多 $m$ 次。

问能不能将 $x$ 变成非正整数。

$x \leq 10^5,1 \leq n,m \leq 30$

做法：

显然应该先执行所有的第一种操作，然后执行第二种操作。

模拟即可。注意判断执行第一种操作使答案变劣的情况。例如 $x=6$，执行第一种操作会将 $x$ 变为 $13$，这个时候应该选择不执行第一种操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# include <bits/stdc++.h>
# define rr register
const int N=100010,INF=0x3f3f3f3f;
inline int read(void){
	int res,f=1;
	char c;
	while((c=getchar())<'0'||c>'9')
		if(c=='-')f=-1;
	res=c-48;
	while((c=getchar())>='0'&&c<='9')
		res=res*10+c-48;
	return res*f;
}
int main(void){
	int T=read();
	while(T--){
		int x=read(),n=read(),m=read();
		for(rr int i=1;i<=n;++i){
			if((x/2)+10>=x){
				break;
			}
			x=x/2+10;
		}
		if(x<=10*m){
			puts("YES");
		}else{
			puts("NO");
		}
	}

	return 0;
}

Problem C

显然我们应该优先选择深度尽量深的节点。

对于两个深度相同的节点，我们应该选择子树大小比较小的那个。因为选择这个点后，答案的贡献将会减少 该点子树大小 $-1$（这个点没被选择的时候，它所有子树到根的路径都会经过它）。

综上所述，我们可以计算选择每个点对答案的贡献：（深度 $-1$）$-$（子树大小 $-1 $）。排序之后取前 $k$ 大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
# include <bits/stdc++.h>
# define rr register
# define int long long
const int N=200010,INF=0x3f3f3f3f;
struct Edge{
	int to,next;
}edge[N<<1];
int head[N],sum;
int depth[N],size[N];
int v[N];
int n,k;
inline int read(void){
	int res,f=1;
	char c;
	while((c=getchar())<'0'||c>'9')
		if(c=='-')f=-1;
	res=c-48;
	while((c=getchar())>='0'&&c<='9')
		res=res*10+c-48;
	return res*f;
}
inline void add(int x,int y){
	edge[++sum].to=y;
	edge[sum].next=head[x];
	head[x]=sum;
	return;
}
void dfs(int i,int fa){
	depth[i]=depth[fa]+1;
	size[i]=1;
	for(rr int j=head[i];j;j=edge[j].next){
		if(edge[j].to==fa)
			continue;
		dfs(edge[j].to,i);
		size[i]+=size[edge[j].to];	
	}
	return;
}
inline bool cmp(int a,int b){
	return a>b;
}
signed main(void){
	n=read(),k=read();
	for(rr int i=1;i<n;++i){
		int x=read(),y=read();
		add(x,y),add(y,x);
	}
	dfs(1,0);
	for(rr int i=1;i<=n;++i){
		v[i]=(depth[i]-1)-(size[i]-1);
	}
	std::sort(v+1,v+1+n,cmp);
	int ans=0;
	for(rr int i=1;i<=k;++i){
		ans+=v[i];
	}
	printf("%I64d",ans);
	return 0;
}

Problem D

容易发现，当确定了取的三个数 $x,y,z$ 中的任意两个时，第三个数就随之确定：例如，当 $x,y$ 确定时，$z$ 一定是 $b$ 数组中 $\dfrac {x+y}{2}$ 的一个不严格前驱 / 后继。

显然，当 $x$ 确定时，$y$ 取 $x$ 在 $g$ 数组中的不严格前驱 / 后继最优。

所以我们得到了一个算法：在 $r$ 数组中枚举 $x$，求出 $x$ 在 $g$ 数组中的不严格前驱 / 后继作为 $y$，并求出 $\dfrac {x+y}{2}$ 在 $b$ 数组中的不严格前驱 / 后继作为 $z$。

但容易发现，不一定是由 $x,y$ 确定推算出 $z$，还有可能是 $x,z$ 确定推算出 $y$。和上面的情况几乎完全一致，不再赘述。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
# include <bits/stdc++.h>
# define rr register
# define int long long
const int N=500010,INF=6e18;
int a[N],b[N],c[N];
int asize,bsize,csize;
int T;
int minx;
inline int read(void){
	int res,f=1;
	char c;
	while((c=getchar())<'0'||c>'9')
		if(c=='-')f=-1;
	res=c-48;
	while((c=getchar())>='0'&&c<='9')
		res=res*10+c-48;
	return res*f;
}
inline int nxt(int *ar,int size,int x){ // 不严格后继是第一个 >= 它的数
	int ans=std::lower_bound(ar+1,ar+1+size,x)-ar;
	if(ans>size) // 小心越界...找不到一定要返回 0
		return 0;
	return ar[ans];
}
inline int pre(int *ar,int size,int x){ // 不严格前驱是最后一个 <= 它的数
	int ans=std::upper_bound(ar+1,ar+1+size,x)-ar-1;
	if(ans>size||ans<1) // 同上
		return 0;
	return ar[ans];	
}
inline int p(int x){
	return x*x;
}
inline void cmin(int x,int y,int z){
	if(x&&y&&z)
		minx=std::min(minx,p(x-y)+p(y-z)+p(z-x));
	return;
}
signed main(void){
	T=read();
	while(T--){
		asize=read(),bsize=read(),csize=read();
		for(rr int i=1;i<=asize;++i){
			a[i]=read();
		}
		for(rr int i=1;i<=bsize;++i){
			b[i]=read();
		}
		for(rr int i=1;i<=csize;++i){
			c[i]=read();
		}
		std::sort(a+1,a+1+asize);
		std::sort(b+1,b+1+bsize);
		std::sort(c+1,c+1+csize);
		minx=INF; // INF 一定要开得极大 样例中已经提示了
		for(rr int i=1;i<=asize;++i){
			int va=nxt(b,bsize,a[i]),vb=pre(b,bsize,a[i]);
			cmin(a[i],va,nxt(c,csize,(a[i]+va)/2));
			cmin(a[i],va,pre(c,csize,(a[i]+va)/2));
			cmin(a[i],vb,nxt(c,csize,(a[i]+vb)/2));
			cmin(a[i],vb,pre(c,csize,(a[i]+vb)/2));
			va=nxt(c,csize,a[i]),vb=pre(c,csize,a[i]);
			cmin(a[i],nxt(b,bsize,(a[i]+va)/2),va);
			cmin(a[i],pre(b,bsize,(a[i]+va)/2),va);
			cmin(a[i],nxt(b,bsize,(a[i]+vb)/2),vb);
			cmin(a[i],pre(b,bsize,(a[i]+vb)/2),vb);
		}
		std::cout<<minx<<std::endl;
	}

	return 0;
}