date: 2020-07-18 12:00~17:00

2020-2021 BUAA ICPC Team Supplementary Training 01

2015-2016 Petrozavodsk Winter Training Camp, Saratov SU Contest

题目大意：

题解：

题目大意：

题解：

题目大意：

题解：

题目大意：

现有 $n$ 个质量均匀分布的棒子，头在 (0, 0) 点挂着，尾在 (L, 0) 点挂着，然后让整条链自然下垂，求每个点自然下垂稳定之后的位置。

题解：

不会奇奇怪怪的东西，我只知道自然下垂时，必然总体的重力势能是最小的。

记长度单位为米，棒子每米的质量为 $m_0$，重力势能为 $g$。

记 $\alpha_i \in [0, \pi]$ 为第 $i$ 个棒子和重力方向的夹角。写出来每个点的坐标，写一下重力势能，限制一下最后一个点的坐标为 $(L, 0)$，用拉格朗日乘数法，我们需要最小化： $$ P\left(\vec{\alpha}, \lambda'_1, \lambda'_2\right) = \left(\sum_{i=1}^n{-m_0 l_i g \left(\frac{1}{2} l_i \cos{\alpha_i} + \sum_{j<i}{l_j \cos{\alpha_j}} \right)}\right) + \lambda'_1 \left(\left(\sum_{i=1}^n{l_i \sin{\alpha_i}}\right) - L\right) + \lambda'_2 \left(\sum_{i=1}^n{l_i \cos{\alpha_i}}\right) $$ 相当于最小化： $$ F\left(\vec{\alpha}, \lambda_1, \lambda_2\right) = \left(\sum_{i=1}^n{-l_i \left(\frac{1}{2} l_i \cos{\alpha_i} + \sum_{j<i}{l_j \cos{\alpha_j}} \right)}\right) + \lambda_1 \left(\left(\sum_{i=1}^n{l_i \sin{\alpha_i}}\right) - L\right) + \lambda_2 \left(\sum_{i=1}^n{l_i \cos{\alpha_i}}\right) $$ 偏导： $$ \begin{array}{rcl} \frac{\partial F}{\partial \alpha_i} &=& \frac{1}{2} l_i^2 \sin{\alpha_i} + \sum_{j > i}{l_j l_i \sin{\alpha_i}} + \lambda_1 l_i \cos{\alpha_i} - \lambda_2 l_i \sin{\alpha_i} \\ &=& l_i \sin{\alpha_i} \left(\frac{1}{2} l_i + \sum_{j > i}{l_j}\right) + \lambda_1 l_i \cos{\alpha_i} - \lambda_2 l_i \sin{\alpha_i} \end{array} $$ $$ \frac{\partial F}{\partial \lambda_1} = \left(\sum_{i=1}^n{l_i \sin{\alpha_i}}\right) - L \\ \frac{\partial F}{\partial \lambda_2} = \sum_{i=1}^n{l_i \cos{\alpha_i}} $$

目标是让偏导都为 $0$，但容易想到实际上偏导均为 $0$ 应该是有两个解。另外一个是取最大值，那种情况下必然 $\alpha_1 > \frac{\pi}{2}$。所以我们限制一下 $\alpha_1 \in [0, \frac{\pi}{2}]$。

我们先令 $\frac{\partial F}{\partial \alpha_i} = 0$，容易发现只要前两个角度不同，就可以直接解出 $\lambda_1$ 和 $\lambda_2$。

考虑一下 $\alpha_{i} > \alpha_{i+1}$，容易发现如果我们将第 $i$ 个棒子的起点和第 $i+1$ 个棒子的终点用线段连起来，会发现两个棒子都在这个线段的上方，但是我们如果让两个棒子根据这个线段对称一下，就能得到重力势能最小的解。因此在最小化重力势能的情况下 $\alpha_{i} \le \alpha_{i+1}$。

假设 $\alpha_1 < \alpha_2$ （即 $\alpha_1 \ne \alpha_2$），有： $$ \lambda_1 = \frac{\left|\begin{array}{ccc} -\sin{\alpha_1} \left(\frac{1}{2} l_1 + \sum_{j > 1}{l_j}\right) & -\sin{\alpha_1} \\ -\sin{\alpha_2} \left(\frac{1}{2} l_2 + \sum_{j > 2}{l_j}\right) & -\sin{\alpha_2} \\ \end{array}\right|} {\left|\begin{array}{ccc} \cos{\alpha_1} & -\sin{\alpha_1} \\ \cos{\alpha_2} & -\sin{\alpha_2} \\ \end{array}\right|} $$ $$ \lambda_2 = \frac{\left|\begin{array}{ccc} \cos{\alpha_1} & -\sin{\alpha_1} \left(\frac{1}{2} l_1 + \sum_{j > 1}{l_j}\right) \\ \cos{\alpha_2} & -\sin{\alpha_2} \left(\frac{1}{2} l_2 + \sum_{j > 2}{l_j}\right) \\ \end{array}\right|} {\left|\begin{array}{ccc} \cos{\alpha_1} & -\sin{\alpha_1} \\ \cos{\alpha_2} & -\sin{\alpha_2} \\ \end{array}\right|} $$

题目大意：

题解：

题目大意：

题解：

题目大意：

题解：

题目大意：

题解：

题目大意：

题解：

题目大意：

题解：

题目大意：

题解：