「题解 P7099」yLOI2020 灼

贴一下原题

好久没做过非传统高斯消元的期望类问题了,由于终点只会被经过一次,因此我们可以考虑从两个终点开始定义状态,令靠近位置$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;
}



Enjoy Reading This Article?

Here are some more articles you might like to read next:

  • 「题解 P2282」HNOI2003 历史年份
  • OI 退役日记 (fake)
  • 「题解 P7098」yLOI2020 凉凉
  • 「题解 P5072」Ynoi2015 盼君勿忘
  • 「题解 P6830」IOI2020 连接擎天树