Dream

2015年，全中国实现了户户通电。作为一名电力建设者，小明正在帮助一带一路上的国家通电。
　　这一次，小明要帮助 n 个村庄通电，其中 1 号村庄正好可以建立一个发电站，所发的电足够所有村庄使用。
　　现在，这 n 个村庄之间都没有电线相连，小明主要要做的是架设电线连接这些村庄，使得所有村庄都直接或间接的与发电站相通。
　　小明测量了所有村庄的位置（坐标）和高度，如果要连接两个村庄，小明需要花费两个村庄之间的坐标距离加上高度差的平方，形式化描述为坐标为 $(x_1, y_1)$ 高度为$ h_1$ 的村庄与坐标为 $(x_2, y_2)$ 高度为 $h_2$ 的村庄之间连接的费用为
　　$sqrt((x_1-x_2)* (x_1-x_2)+(y_1-y_2)* (y_1-y_2))+(h_1-h_2)*(h_1-h_2)$。
　　在上式中 sqrt 表示取括号内的平方根。请注意括号的位置，高度的计算方式与横纵坐标的计算方式不同。
　　由于经费有限，请帮助小明计算他至少要花费多少费用才能使这 n 个村庄都通电。

蓝桥模拟2第八题题解

2020-07-08

题解 / 蓝桥

题目描述

如果一个序列的奇数项都比前一项大，偶数项都比前一项小，则称为一个摆动序列。即 a[2i]<a[2i-1], a[2i+1]>a[2i]。
　　小明想知道，长度为 m，每个数都是 1 到 n 之间的正整数的摆动序列一共有多少个。

蓝桥模拟2第九题题解

2020-07-08

题解 / 蓝桥

题目描述

　　小明和朋友们一起去郊外植树，他们带了一些在自己实验室精心研究出的小树苗。
　　小明和朋友们一共有 n 个人，他们经过精心挑选，在一块空地上每个人挑选了一个适合植树的位置，总共 n 个。他们准备把自己带的树苗都植下去。
　　然而，他们遇到了一个困难：有的树苗比较大，而有的位置挨太近，导致两棵树植下去后会撞在一起。
　　他们将树看成一个圆，圆心在他们找的位置上。如果两棵树对应的圆相交，这两棵树就不适合同时植下（相切不受影响），称为两棵树冲突。
　　小明和朋友们决定先合计合计，只将其中的一部分树植下去，保证没有互相冲突的树。他们同时希望这些树所能覆盖的面积和（圆面积和）最大。

线段树

2020-07-08

数据结构

基本介绍

1、线段树是一棵二叉搜索树，它储存的是一个区间的信息。

2、每个节点以结构体的方式存储，结构体包含以下几个信息：

区间左端点、右端点；（这两者必有）

这个区间要维护的信息（事实际情况而定，数目不等）。

3、线段树的基本思想：二分。

4、线段树一般结构如图所示：

5、特殊性质：

由上图可得，

1、每个节点的左孩子区间范围为$[l,mid]$，右孩子为$[mid+1,r]$。

2、对于结点k，左孩子结点为$2\times k$，右孩子为$2\times k+1$，这符合完全二叉树的性质。