2018 Petrozavodsk Winter Camp, Yandex Cup G. Piecewise Linearity 数学

题目分析

题目大意：给定 n + 1 n + 1 n+1个二维平面上的点 P 0 , P 1 , . . , P n P_0, P_1,..,P_n P0​,P1​,..,Pn​表示一个分段一次函数 f ( x ) f(x) f(x)，第一段和最后一段分别是射线 P 1 P 0 P_1P_0 P1​P0​和射线 P n − 1 P n P_{n - 1}P_n Pn−1​Pn​，中间第 i i i段是线段 P i P i + 1 P_iP_i + 1 Pi​Pi​+1。求是否存在实数 λ 1 、 λ 2 、 . . . 、 λ m , a 1 , a 2 , . . . , a m \lambda_1、\lambda_2、...、\lambda_m,a_1, a_2,...,a_m λ1​、λ2​、...、λm​,a1​,a2​,...,am​，使得 f ( x ) = ∑ i = 1 m λ i ∣ x − a i ∣ f(x) = \sum^{m}_{i = 1} \lambda_i|x - a_i| f(x)=∑i=1m​λi​∣x−ai​∣。

思路分析：

题目要求我们将分段函数写成 f ( x ) = ∑ i = 1 m λ i ∣ x − a i ∣ f(x) = \sum^{m}_{i = 1} \lambda_i|x - a_i| f(x)=∑i=1m​λi​∣x−ai​∣。我们首先来寻找该函数的规律：

令 m = 3 , a 3 = − 1 , − 2 , − 3 m = 3, a_3 = {-1, -2, -3} m=3,a3​=−1,−2,−3，则有 f ( x ) = ∣ x + 1 ∣ + ∣ x + 2 ∣ + ∣ x + 3 ∣ f(x) = |x + 1| + |x + 2| + |x + 3| f(x)=∣x+1∣+∣x+2∣+∣x+3∣。作该函数的图像：

将函数转写为分段函数表达式： f ( x ) = { − 3 x + 6 ,   x ∈ ( − ∞ , − 3 ] − x ,   x ∈ [ − 3 , − 2 ] x + 4 ,   x ∈ [ − 2 , − 1 ] 3 x + 6 ,   x ∈ [ − 1 , + ∞ ) f(x) = \begin{aligned} \begin{cases} -3x + 6,\ x \in (-\infty, -3] \\ -x,\ x \in [-3, -2] \\ x + 4,\ x \in [-2, -1] \\ 3x + 6, \ x \in [-1, +\infty) \end{cases} \end{aligned} f(x)=⎩⎪⎪⎪⎨⎪⎪⎪⎧​−3x+6, x∈(−∞,−3]−x, x∈[−3,−2]x+4, x∈[−2,−1]3x+6, x∈[−1,+∞)​​ 再:

• 令 m = 3 , a 3 = 1 , a 2 = 2 , a 1 = − 1 m = 3, a_3 = 1, a_2 = 2, a_1 = -1 m=3,a3​=1,a2​=2,a1​=−1，则有 f ( x ) = ∣ x + 1 ∣ + ∣ x + 2 ∣ + ∣ x − 3 ∣ f(x) = |x + 1| + |x + 2| + |x - 3| f(x)=∣x+1∣+∣x+2∣+∣x−3∣；
• 令 m = 3 , a 3 = 1 , a 2 = − 2 , a 1 = 1 m = 3, a_3 = 1, a_2 = -2, a_1 = 1 m=3,a3​=1,a2​=−2,a1​=1，则有 f ( x ) = ∣ x + 1 ∣ + ∣ x − 2 ∣ + ∣ x + 3 ∣ f(x) = |x + 1| + |x - 2| + |x + 3| f(x)=∣x+1∣+∣x−2∣+∣x+3∣；
• 令 m = − 3 , a 3 = 1 , a 2 = 2 , a 1 = 1 m = -3, a_3 = 1, a_2 = 2, a_1 = 1 m=−3,a3​=1,a2​=2,a1​=1，则有 f ( x ) = ∣ x − 1 ∣ + ∣ x + 2 ∣ + ∣ x + 3 ∣ f(x) = |x - 1| + |x + 2| + |x + 3| f(x)=∣x−1∣+∣x+2∣+∣x+3∣;

分别做上述函数的图像：

继续写分段函数表达式，并观察各个直线斜率的变化情况： f 1 ( x ) = { − 3 x ,   x ∈ ( − ∞ , − 2 ] − x + 4 ,   x ∈ [ − 2 , − 1 ] x + 6 ,   x ∈ [ − 1 , 3 ] 3 x ,   x ∈ [ 3 , + ∞ ) ,    f 2 ( x ) = { − 3 x − 2 ,   x ∈ ( − ∞ , − 3 ] − x + 4 ,   x ∈ [ − 3 , − 1 ] x + 6 ,   x ∈ [ − 1 , 2 ] 3 x ,   x ∈ [ 2 , + ∞ ) ,    f 3 ( x ) = { − 3 x − 4 ,   x ∈ ( − ∞ , − 3 ] − x ,   x ∈ [ − 3 , − 2 ] x + 6 ,   x ∈ [ − 2 , 1 ] 3 x + 4 ,   x ∈ [ 1 , + ∞ ) f_1(x) = \begin{aligned} \begin{cases} -3x,\ x \in (-\infty, -2] \\ -x + 4,\ x \in [-2, -1] \\ x + 6,\ x \in [-1, 3] \\ 3x, \ x \in [3, +\infty) \end{cases} \end{aligned} ,\ \ f_2(x) = \begin{aligned} \begin{cases} -3x - 2,\ x \in (-\infty, -3] \\ -x + 4,\ x \in [-3, -1] \\ x + 6,\ x \in [-1, 2] \\ 3x, \ x \in [2, +\infty) \end{cases} \end{aligned} ,\ \ f_3(x) = \begin{aligned} \begin{cases} -3x - 4,\ x \in (-\infty, -3] \\ -x,\ x \in [-3, -2] \\ x + 6,\ x \in [-2, 1] \\ 3x + 4, \ x \in [1, +\infty) \end{cases} \end{aligned} f1​(x)=⎩⎪⎪⎪⎨⎪⎪⎪⎧​−3x, x∈(−∞,−2]−x+4, x∈[−2,−1]x+6, x∈[−1,3]3x, x∈[3,+∞)​​,  f2​(x)=⎩⎪⎪⎪⎨⎪⎪⎪⎧​−3x−2, x∈(−∞,−3]−x+4, x∈[−3,−1]x+6, x∈[−1,2]3x, x∈[2,+∞)​​,  f3​(x)=⎩⎪⎪⎪⎨⎪⎪⎪⎧​−3x−4, x∈(−∞,−3]−x, x∈[−3,−2]x+6, x∈[−2,1]3x+4, x∈[1,+∞)​​ 不难发现， a i a_i ai​的值影响直线的拐点，且 a i a_i ai​就是函数的拐点，且 m = n − 1 m = n - 1 m=n−1。

我们继续寻找规律：对于 f ( x ) = λ 3 ∣ x + 1 ∣ + λ 2 ∣ x + 2 ∣ + λ 1 ∣ x + 3 ∣ f(x) = \lambda_3|x + 1| + \lambda_2|x + 2| + \lambda_1|x + 3| f(x)=λ3​∣x+1∣+λ2​∣x+2∣+λ1​∣x+3∣，分别取 { λ 1 = 1 , λ 2 = 1 , λ 3 = 1 } , { λ 1 = 2 , λ 2 = 1 , λ 3 = 1 } , { λ 1 = 1 , λ 2 = 2 , λ 3 = 1 } , { λ 1 = 1 , λ 2 = 1 , λ 3 = 2 } \{\lambda_1 = 1, \lambda_2 = 1, \lambda_3 = 1\}, \{\lambda_1 = 2, \lambda_2 = 1, \lambda_3 = 1\}, \{\lambda_1 = 1, \lambda_2 = 2, \lambda_3 = 1\}, \{\lambda_1 = 1, \lambda_2 = 1, \lambda_3 = 2\} {λ1​=1,λ2​=1,λ3​=1},{λ1​=2,λ2​=1,λ3​=1},{λ1​=1,λ2​=2,λ3​=1},{λ1​=1,λ2​=1,λ3​=2}

不难发现， λ i \lambda_i λi​的取值只会影响第 i i i个拐点处的一个函数。注意： λ \lambda λ值按照位置顺序从左向右排序。

继续对上面三个函数列分段函数解析式，不难发现，对于每个拐点 a i a_i ai​而言， λ i = k r − k l 2 \lambda_i = \frac{k_r - k_l}{2} λi​=2kr​−kl​​，其中 k l , k r k_l, k_r kl​,kr​为拐点两侧斜率。

对 λ \lambda λ取累加和可得：每段直线的斜率 k k k值实际上是 λ \lambda λ序列的求和表达式： { k 1 = − λ 1 − λ 2 − ⋯ − λ n − 1 k 2 = λ 1 − λ 2 − ⋯ − λ n − 1 k 3 = λ 1 + λ 2 − ⋯ − λ n − 1 ⋯ k n = λ 1 + λ 2 + ⋯ + λ n − 1 \begin{aligned} \begin{cases} k_1=-\lambda_1-\lambda_2-\cdots-\lambda_{n-1}\\ k_2=\lambda_1-\lambda_2-\cdots-\lambda_{n-1}\\ k_3=\lambda_1+\lambda_2-\cdots-\lambda_{n-1}\\ \cdots\\ k_n=\lambda_1+\lambda_2+\cdots+\lambda_{n-1}\\ \end{cases} \end{aligned} ⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧​k1​=−λ1​−λ2​−⋯−λn−1​k2​=λ1​−λ2​−⋯−λn−1​k3​=λ1​+λ2​−⋯−λn−1​⋯kn​=λ1​+λ2​+⋯+λn−1​​​ 此时是否能够化为解析式的问题转化为线性方程组是否有解。可以使用高斯消元法进行化简后验证线性方程组是否有解。但是高斯消元法复杂度较高，显然无法用于求解本题目。我们继续推导：由于一共有 n n n个方程，如果我们不考虑最后一个方程，那么前 n − 1 n - 1 n−1个方程构成的方阵一定可以得到一组解。我们只需要将其带入到最后一个方程中判断是否成立即可。即：我们只需要判断 − 1 × k 1 -1 \times k_1 −1×k1​是否等于 k n k_n kn​即可。

至此，我们可以在 O ( 1 ) O(1) O(1)复杂度内验证所给函数的斜率 k k k是否满足条件。我们还需要继续对斜截式方程的截距进行讨论：

考虑 f ( x ) = ∑ i = 1 m λ i ∣ x − a i ∣ f(x) = \sum^{m}_{i = 1} \lambda_i|x - a_i| f(x)=∑i=1m​λi​∣x−ai​∣的展开式，容易发现对于 b x b_x bx​，其值可以由定义式展开为 ∑ i = 1 j λ i a i − ∑ i = j + 1 n − 1 λ i a i \sum_{i = 1}^{j} \lambda_ia_i - \sum^{n - 1}_{i = j + 1} \lambda_i a_i ∑i=1j​λi​ai​−∑i=j+1n−1​λi​ai​，很容易发现其不带有常数项 C C C。因此我们可以认为不存在常数项，那么我们可以利用斜率推到的结论 λ i = k r − k l 2 \lambda_i = \frac{k_r - k_l}{2} λi​=2kr​−kl​​继续推导截距限制： y x = f ( x ) ,   k 1 = − k n ∵ y 0 = ∑ i = 1 n − 1 λ i ( x i − x 0 ) = ∑ i = 1 n − 1 k i + 1 − k i 2 ( x i − x 0 ) ,    y n = ∑ i = 1 n − 1 λ i ( x n − x i ) = ∑ i = 1 n − 1 k i + 1 − k i 2 ( x n − x i ) ∴ y 0 + y n = ∑ i = 1 n − 1 k i + 1 − k i 2 ( x n − x 0 ) = k n − k 1 2 ( x n − x 0 ) = k n − ( − k n ) 2 ( x n − x n ) = y n − y n − 1 x n − x n − 1 ( x n − x 0 ) ∴ y 0 + y n = y n − y n − 1 x n − x n − 1 ( x n − x 0 ) ∴ ( y 0 + y n ) ( x n − x n − 1 ) = ( y n − y n − 1 ) ( x n − x 0 ) y_x= f(x),\ k_1 = -k_n\\ \because y_0=\sum^{n - 1}_{i = 1}\lambda_i(x_i-x_0)=\sum_{i = 1}^{n - 1}\frac{k_{i+1}-k_i}2(x_i-x_0),\ \ y_n=\sum^{n - 1}_{i = 1}\lambda_i(x_n-x_i)=\sum_{i = 1}^{n - 1}\frac{k_{i+1}-k_i}2(x_n-x_i)\\ \therefore y_0+y_n=\sum^{n - 1}_{i = 1}\frac{k_{i+1}-k_i}2(x_n-x_0)=\frac{k_n-k_1}2(x_n-x_0) = \frac{k_n - (-k_n)}{2}(x_n - x_n) = \frac{y_n - y_{n - 1}}{x_n - x_{n - 1}}(x_n - x_0)\\ \therefore y_0+y_n=\frac{y_n - y_{n - 1}}{x_n - x_{n - 1}}(x_n - x_0)\\ \therefore (y_0 + y_n)(x_n - x_{n - 1}) = (y_n - y_{n - 1})(x_n - x_0)\\ yx​=f(x), k1​=−kn​∵y0​=i=1∑n−1​λi​(xi​−x0​)=i=1∑n−1​2ki+1​−ki​​(xi​−x0​),  yn​=i=1∑n−1​λi​(xn​−xi​)=i=1∑n−1​2ki+1​−ki​​(xn​−xi​)∴y0​+yn​=i=1∑n−1​2ki+1​−ki​​(xn​−x0​)=2kn​−k1​​(xn​−x0​)=2kn​−(−kn​)​(xn​−xn​)=xn​−xn−1​yn​−yn−1​​(xn​−x0​)∴y0​+yn​=xn​−xn−1​yn​−yn−1​​(xn​−x0​)∴(y0​+yn​)(xn​−xn−1​)=(yn​−yn−1​)(xn​−x0​) 利用反证法证明，如果存在常数项 C C C，上式一定不成立：

设 y 0 = k 1 x 0 + b 1 ,   y n = k n x n + b n y_0 = k_1x_0 + b_1,\ y_n = k_nx_n + b_n y0​=k1​x0​+b1​, yn​=kn​xn​+bn​，假设存在不可提取的常数项 C C C，那么我们可以将两个解析式拆公共常数项并合并因子，表示为： y 0 = k 1 ( x 0 + b ′ ) + C 1 y n = k n ( x n + b ′ ) + C n C 1 + C n ≠ 0 y_0 = k_1(x_0 + b') + C_1\\ y_n = k_n(x_n + b') + C_n \\ C_1 + C_n \neq 0 y0​=k1​(x0​+b′)+C1​yn​=kn​(xn​+b′)+Cn​C1​+Cn​​=0 那么加和表示为： y 0 + y n = k 1 ( x 0 + b 1 ′ ) + k n ( x n + b n ′ ) + C 1 + C n ∵ k 1 = − k n ∴ y 0 + y n = k 1 ( x 0 + b 1 ′ ) + k n ( x n + b n ′ ) + C 1 + C n = − k n ( x 0 + b 1 ′ ) + k n ( x n + b n ′ ) + C 1 + C n = k n ( x n − x 0 ) + k n ( b n ′ − b 1 ′ ) + C 1 + C n = k n ( x n − x 0 ) + C 1 + C n y_0 + y_n = k_1(x_0 + b_1') + k_n(x_n + b_n') + C_1 + C_n\\ \because k_1 = -k_n\\ \begin{aligned} \therefore y_0 + y_n &= k_1(x_0 + b_1') + k_n(x_n + b_n') + C_1 + C_n\\ &= -k_n(x_0 + b_1') + k_n(x_n + b_n') + C_1 + C_n\\ &= k_n(x_n - x_0) + k_n(b_n' - b_1') + C_1 + C_n\\ &= k_n(x_n - x_0) + C_1 + C_n \end{aligned} y0​+yn​=k1​(x0​+b1′​)+kn​(xn​+bn′​)+C1​+Cn​∵k1​=−kn​∴y0​+yn​​=k1​(x0​+b1′​)+kn​(xn​+bn′​)+C1​+Cn​=−kn​(x0​+b1′​)+kn​(xn​+bn′​)+C1​+Cn​=kn​(xn​−x0​)+kn​(bn′​−b1′​)+C1​+Cn​=kn​(xn​−x0​)+C1​+Cn​​ 由于上式必须满足假设 C 1 + C n ≠ 0 C_1 +C_n \neq 0 C1​+Cn​​=0，因此与 y 0 + y n = k n ( x n − x 0 ) y_0+y_n=k_n(x_n - x_0) y0​+yn​=kn​(xn​−x0​)矛盾，故存在不可消除的常数项时， ( y 0 + y n ) ( x n − x n − 1 ) = ( y n − y n − 1 ) ( x n − x 0 ) (y_0 + y_n)(x_n - x_{n - 1}) = (y_n - y_{n - 1})(x_n - x_0) (y0​+yn​)(xn​−xn−1​)=(yn​−yn−1​)(xn​−x0​)一定不成立。

至此，充要条件全部具备了，我们可以上述两个条件根据输入在 O ( 1 ) O(1) O(1)判断能否构成求和序列。

#include 
#define int long long
using namespace std;

const int N = 1e5 + 10;
int x[N], y[N];

inline int read() {
    int f = 1, x = 0; char s = getchar(); 
    while(s  '9'){ if(s =='-') f = -1; s = getchar(); } 
    while(s >= '0' && s > n;
    for(int i = 0; i