题解 P7099 【[yLOI2020] 灼】

· · 题解

F

Algorithm 1

对于虫洞间距离不超过 2 的情况，显然答案只有 0 和 1 两种可能。期望得分 20 分。

Algorithm 2

考虑推一推式子。设 f_i 表示在坐标 i 时的期望步数，那么转移显然：

f_{i} = \frac 1 2(f_{i - 1} + f_{i + 1}) + 1

这个式子的意思是分别有 \frac 1 2 的概率向左走向右走，然后变为对应坐标的期望步数。同时因为走了一步，所以最后要 +1。

边界条件是在虫洞结点上 f_i = 0。

对于子任务 3，可以通过手算发现这时候不在虫洞上的 f 的值为 2。结合算法一，期望得分 30 分。

Algorithm 3

用高斯消元求解算法二中的式子，时间复杂度 O(qn^3)，期望得分 50 分。

Algorithm 4

验题人拉瓦手算带入消元得到了一个递推式，可以矩阵加速，时间复杂度 O(q \log n) 带 8 倍常数。期望得分 70 分。

Algorithm 5

考虑把算法二中的式子乘二然后整理，可以得到

(f_{i + 1} - f_{i}) - (f_{i} - f_{i - 1}) = -2

这就是说，f 的二阶差分是一个非零常数。因此 f 的通项公式一定是一个二次多项式。

我们考虑正着推式子：对于 g(x) = ax^2 + bx + c，有 g(x - 1) = a(x^2 - 2x + 1) +b(x - 1) + c，g(x + 1) = a(x^2 + 2x + 1) +b(x + 1) + c。

因此 g(x) - g(x - 1) = 2ax - a + b；g(x + 1) - g(x) = 2ax + a + b。

因此 [g(x + 1) - g(x)] - [g(x) - g(x - 1)] = 2a。这就是说，二次函数的二阶差分值是其二次项系数的两倍。因此可以得到 f 的通项公式的二次项系数是 -1。同时我们还知道 f 的两个零点，因此可以直接以零点式写出 f 的通项公式，带入 x 即可 O(1) 计算。时间复杂度 O(n \log n + q)。这里的 \log n 需要对 x 数组进行排序。然后用指针指向第一个大于询问值的元素。因为询问是单调不降的，所以指针移动是均摊 O(1) 的。期望得分 100 分。

#include <cstdio>
#include <cctype>
#include <iostream>
#include <algorithm>

template <typename T>
inline void qr(T &x) {
  char ch = getchar(); x = 0;
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
}

const int maxn = 100005;
const int mod = 998244353;

int n, q;
int ans, answ, answe = -1, answer = mod + 1; 
int a[maxn];

int main() {
  qr(n); qr(n); qr(q);
  for (int i = 1; i <= n; ++i) {
    qr(a[i]);
  }
  std::sort(a + 1, a + 1 + n);
  for (int x, p = 1; q; --q) {
    qr(x);
    while ((p < n) && (a[p] <= x)) ++p;
    int y = 1ll * (x - a[p - 1]) * (a[p] - x) % mod;
    ans ^= y;
    if (y & 1) ++answ;
    answe = std::max(answe, y);
    answer = std::min(answer, y);
  }
  std::cout << ans << std::endl << answ << std::endl << answe << std::endl << answer << std::endl;
}