2020/05/16：\\
第三场团队赛：\\
==== 比赛过题情况: ====
当场过题情况：\\
A:思路&代码：Famer 查错：Yuki\\
B:思路&代码：Wzy\\
C:思路&代码：Yuki\\
D:思路&代码：Wzy\\
E:思路&代码：Yuki\\
F:\\
G:未通过（思路&代码：Yuki）\\
H:思路&代码：Yuki\\
I:思路：Famer&Wzy&Yuki 代码：Yuki\\
J:思路&代码：Wzy\\
K:思路&代码：Yuki\\

==== 题解： ====
**A：**\\
**题意：**给定n*m的矩形，'.'表示空地，其他的表示一个建筑模块，让你求出不是空地的那些地方，组成的一个图形的重心，与最后一行横坐标相比，如果重心的横坐标比最后一行的最左面的横坐标小，输出"left"，比最右面的大，输出"right"，否则输出"balanced"。\\
**题解：**本来是个水题但是有个大坑，算中心的时候坐标取的是格子的中电而判断是否超出地基的时候边缘坐标算的是格子的边缘。\\
所以重心坐标应该与L-0.5和R+0.5比较。

**B：**
dfs签到题\\

**C：**\\
**题意：**第一行给定n个点和m条绳子，第二行是点的位置（从小到大排列），第三行是绳子的长度。问能不能把所有的绳子都连进去（绳子的长度>=点之间的距离才可以连，且相同的两个点之间不能连两条绳子）。\\
**题解：**贪心，n个点共可以连n*(n-1)/2条边，越短的绳子肯定要对应距离越小的边，找到最短的m条边从小到大与m根绳子比较。\\
找到最短的m条边的方法：二分第m短的边长度L，将点排序后枚举起点就能算出从这个点向后可以链多少长度小于L的边。最后求出L后用同样的方法求出这m条边的具体长度。

**D：**
给定N个数，求出使两边数的和差最小的位置，带单点修改\\
树状数组维护前缀和，二分查找使两边差最接近0的两个位置，比一比就好了\\

**E：**\\
**题意：**给出一个DAG每个点都可以从0到达。在第i次吃到第j个点的贡献是$\frac{val[j]}{2^{i-1}}$，走到的点可以不吃。求最多吃多少。\\
**题解：**这个题正着想会觉得很迷惑但是如果我们倒过来（从最后一个点往前走），就会变成一个特别显然的dp。\\
f[u]=max(f[v],$\frac{f[v]}{2}$+val[u])

**F：**一个有点麻烦是计算几何题。

**G：**\\
**题意：**有一个红绿灯，你知道绿、黄、红持续时间分别为Tg，Ty，Tr，但是不知道初始绿灯亮的时间T，接下来有n次观察，观察到第t秒的时候红绿灯的颜色，最后一行是一次询问，询问在第t秒颜色为c的概率。\\
**题解：**对于每次观察，合法的初始时间T的范围是一系列连续的区间，在第一次观察时，选择一段区间保存，之后拿每一段区间与当前的区间集合求交集，最终询问的值即为： 最终区间总长度/进行最后一次合并前的区间总长度。\\
考场上的最后一道题，虽然思路正确但是时间太紧实现时出了一些细节问题。

**H:**水题

**I:**\\
**题意：**给一串数字串，求问最多能分成多少个区域使得区域回文。\\
**题解：**贪心，从当前字母，最少分多少字母才能回文匹配。（本来很简单的题，一开始贪心被否决，再贪心又否决，最后就是贪心）

**J：**
最小生成树模板题\\

**K：**虽然题意特别绕，但就是一个简单的背包问题