Contest Info

date: 2018.11.18 13:05-18:05

practice link

Solutions

A. Ski race

签到题。

C. Triangle

题目大意：给出平面上的一个不退化的整点三角形，坐标范围 \(\pm10^{3}\)。每次可以询问平面上一条直线（这条直线的参数有一定范围限制），交互器返回直线将三角形划分成的两个部分占总面积之比。在 \(1000\) 次询问内找出这个三角形。

题解：首先我们很容易二分出三角形上下左右的边界。

随后我们可以找出三角形中间是否有一个拐点，不妨设下边界为 \(d\)。我们询问 \(y=d,y=d+\frac{1}{2},y=d+1\) 三条直线，即可插值求出下面部分的面积关于长度的二次函数。之后我们二分出第一个不能用该二次函数拟合的整点即可。

之后需要分许多情况讨论，这里就不一一赘述了。（我分了 \(22\) 种）

另外还需要特别注意参数的范围限制，可能需要归一化才能满足。

D. Wires

记不清了，反正维护两个单调不降子序列，令\(dp[i][j]\)为\(i\)是一个序列的最后一项，另一个序列的最后一项为\(j\)，线段树维护一下转移即可，时间复杂度\(O(n\log{n})\)。

H. A system of balance scales

题目大意：

有\(n\le5\times10^4\)个天平组成了树形结构，给出\(n\)个天平的长度（重量忽略不计），\(n+1\)个叶子节点的初始重量。

每个天平任何时刻都处于平衡状态，之后\(K\le10^5\)次操作，每次改变一个叶子的重量，或者询问一个天平的平衡点的位置。

题解：

由力矩平衡，只需要维护子树和即可，时间复杂度\(O(n\log{n})\).

K. Test generation

签到题。