Lucky Number 题解
June 23, 2022
题意 #
对于序列A，S序列是A序列的相邻两项之和的序列: $S_i = A_i + A_{i+1}$, S序列已知
给定一个X序列，请你确定一个A序列，使得X序列中的数字出现的次数仅可能的多，输出最多的次数。
分析 #
我们可以很容易的写出A序列：
$$ \begin{aligned} A_1 &= A_1 \\ A_2 &= S_1 - A_1 \\ A_3 &= S_2 - A_2 = S_2 - S_1 + A_1 \\ A_4 &= S_3 - A_3 = S_3 - S_2 + S_1 - A_1 \\ A_5 &= S_4 - A_4 = S_4 - S_3 + S_2 - S_1 + A_1 \\ \end{aligned} $$
引入一个B序列，我们可以将上面的式子简写为:
$$ \begin{aligned} B_1 &= 0 \\ A_1 &= B_1 + A_1 \\ A_2 &= B_2 - A_1 \\ A_3 &= B_3 + A_1 \\ A_4 &= B_4 - A_1 \\ A_5 &= B_5 + A_1 \\ \end{aligned} $$
可知B序列是已知序列，可由S序列计算得出。对于一个确定的$A_1$, 则序列A是确定的。
若$A_i = X_j$ 则: $A_i = B_{i} + (-1)^{i+1}A_1 = X_j$, 可知$A_1 = (-1)^{i+1}(X_j - B_i)$。
由此可知，每一对$A_i = X_j$都对应了一个$A_1$, 因此只需要统计哪一种$A_1$出现的次数最多就可以了。