2018 TCO Final 解题记录

### Easy BalancingTrees
题意：给你一棵树，有$N$个点，称一棵树为平衡的当对于一棵树的每一个节点来说它的儿子的子树权值和都一样。现在每个点有个权值$w_i$，每次可以把一个点的权值$+x/-x$，代价为$x$。问最少花多少代价让这棵树平衡。$x\in R,N\le 250,w_i\le 10^9$。答案精确到$10^{-9}$

题解：自然的折线题。考虑怎么合并折线的问题，不好做。但是至少能知道答案应该是个关于整棵树大小$T$的下凸包。
题解给的方法是发现一个性质：所有的操作都可以只通过修改叶子而成，因为一个非叶子的操作可以平均分到每一个叶子上并且不会更劣。
发现确定整棵树的大小$T$就可以把所有点的需求推到叶子上，而因为答案的凸性，可以直接三分$T$。用折线来$check$，是$O(n\ log\ n)$的

### Medium BuildTheRoads
题意：平面上有$N$个点，生成一棵树使得它的直径最小。$N\le 200$
题解：想了很久，猜了很多结论都不对，看完题解发现真的好牛逼啊！
无敌的结论：直径最多三条边。
感性理解如下：
![title](https://leanote.com/api/file/getImage?fileId=5c7ce92cab6441439400653c)
四条边无论如何都可以舍去某一条边，因为三角形两边长大于第三边。
因此枚举中间的一条边。
现在我们计算每个点连哪个端点直径最小，直接比较一下就完了。时间复杂度$O(n^3)$
还是找不到性质啊(叹气)

### Hard Worms

题意：一条虫子定义为从一个格子只向左向下走出的路径成为的图形。现在用很多虫子拼成了一个$N\times M$矩形，有个人用相同字符表示一条虫子把整个图形从左到右从上到下输出，但是打印机中途坏了，剩下的一半状态未知。问剩下的一半有几种可能。$N\le 50, M\le 50$

题解：发现左上-右下对角线的每一个格子一定是不同的虫子。那么就可以用第$i$根对角线作为状态来$dp$，每一层的转移再用一个$dp$来实现。具体来说内部的$f(i,0/1)$表示现在在从左到右第$i$个格子，正上方的虫子有没有爬到左边去，对于上面的确定部分来说直接强制转移。这样可以解决坏掉部分是规则矩形的情况。
但是有这种蛋疼的情况：
```
abccd
eff??
?????
```
此时的'f'可以无限向右延伸。
我们直接暴力枚举$f$的延伸步数。

Rockdu's Blog

导航

最近发表

大佬们的友链