T1 避雷针 (lightning)
题意:
给定一个序列,对每个i询问使得任意非i的j满足h[j]<=h[i]+p-sqrt(abs(i-j))
解题思路:
好好的场切被ceil精度卡了。
思路是很简单的,考虑sqrt(x)的增长速度是由快变慢的,那么对于一个i,找出使得p最大的一个j。如果i增大,答案一定不在j左。考虑到这一点,整体二分即可。
T3 滑雪 (ski)
题意:
很难形容
解题思路:
因为“#”太难画了,所以用×代替,蓝色×为移动后产生的冰块,S为起点,T为终点
如果你颓多了,结论是显然的——ZYB。首先来证明上下和左右横跳一定最优。
显然一个点要不通过横跳到达相邻的点至少需要三步
而横跳只需要两步
自此,左右横跳更优证毕。我们易知返回同一个节点显然不优。那么只需要考虑每一个节点向上下左右四个相邻点的距离。分为两种情况,当前点是“.”和当前点是“#”。
- 1.当前点是"."
考虑去左边的相邻点(如果不是“#”),其他方向是一样的,有两种情况
第一种显然只需要一次,向左连一条边权为1的边:
第二种则需要两次,向左连一条边权为2的边:
- 2.当前点是"#"
你们的代码一个比一个鬼畜——ZYB
显然我们现在只加了相邻点的边,那要没有一种可能连接不相邻的两个点呢?是有可能的,比如这一个:
#......#
考虑为什么会出现这种情况。本质的原因就是左右两个"#",所以在遇到一个“#”后,如果上下左右相邻格为".",从相邻两格的格子开始拓宽,向相邻格连一条边权为1的边。