「题解 P7099」yLOI2020 灼

November 22, 2020

2020   ·   OI   Chinese     ·   pre-university  

贴一下原题

好久没做过非传统高斯消元的期望类问题了, 由于终点只会被经过一次, 因此我们可以考虑从两个终点开始定义状态, 令靠近位置$pos$的两个端点为$l$和$r$, 到达任意终点的期望步数为$f_i$, 则有:

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

特殊的, $f_l=f_r=0$

$\because 2f_i = f_{i+1}+f_{i-1}+2$

$\therefore f_{i+1}-f{i}=f_{i}-f_{i-1}+2$

于是问题就转化为一道低于全国卷难度的数学题了

$\therefore 令g_i=f_{i+1}-f_i$

$\therefore g_i=g_{i-1}-2$, ${g_i}$为等差数列

$\therefore 设g_i=g_1-2(i-1)$

$\because \Sigma_{i=l}^{r-1} g_i=f_r-f_l=0$

$\therefore [g_1-2(l-1)+g_1-2(r-2)]*(r-1)/2=0$

$\therefore g_1=l+r-3$

$\therefore f_{pos}=f_{pos}-f_l=\Sigma_{i=l}^{pos-1}g_i=(r-pos)(pos-l)$

注意到输入中$y_i$单调不降, 那么我们一遍扫过去更新$l,r$即可

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

using namespace std;

const int MAXN = 100005;
const int MOD = 998244353;

int T, n, q;
int pos[MAXN];
long long ans, ans1, ans2, ans3, ans4;

int main()
{
    scanf("%d%d%d", &T, &n, &q);
    for (int i = 1; i <= n; i++)
        scanf("%d", &pos[i]);
    sort(pos + 1, pos + n + 1);
    int nex = 1;
    ans4 = 1e18;
    for (int i = 1; i <= q; i++)
    {
        int npos;
        scanf("%d", &npos);
        while (npos > pos[nex]) nex++;
        ans = 1LL * (npos - pos[nex - 1]) * (pos[nex] - npos) % MOD;
        ans1 ^= ans;
        ans2 += ans & 1;
        ans3 = max(ans3, ans);
        ans4 = min(ans4, ans);
    }
    printf("%lld\n%lld\n%lld\n%lld", ans1, ans2, ans3, ans4);
    return 0;
}