P7099 [yLOI2020] 灼 题解

题意

题目链接

数轴上有 $n$ 个虫洞,有 $q$ 个按坐标升序给出的飞船,保证飞船一定在不会在第一个虫洞左边或最后一个虫洞右边。每个飞船每秒会等概率左移一格或右移一格,对于每个飞船,求到达任意一个虫洞的期望时间。

解析

记 $f_i$ 为位置在 $i$ 的飞船的期望时间,只要 $i$ 位置没有虫洞(有虫洞期望时间显然为 $0$),就有 $f_i=1+\frac{1}{2}(f_{i-1}+f_{i+1})$,化简得 $(f_{i+1}-f_i)-(f_i-f_{i-1})=-2$,即其二阶差分为一定值,由此可知 $f_i$ 为一个二次函数。将 $f_x=ax^2+bx+c$ 代入上式,可得其二次项系数为 $-1$。

由于飞船一定在两个虫洞之间,记这两个虫洞的位置分别为 $x_1$ 和 $x_2$,我们得到了这个二次函数的两个零点,结合求出的二次项系数可以写出零点式:$f_x=-(x-x_1)(x-x_2)$。

由于飞船坐标升序给出,每个飞船在哪两个虫洞之间是易于维护的,本题解决。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
const int M=5e6+5;
const int mod=998244353;
int T,n,q,x[N],y[M];
int ANS,ansji,ansmx=-1,ansmn=1e9;
signed main(){
    scanf("%lld",&T);scanf("%lld%lld",&n,&q);
    for(int i=1;i<=n;i++) scanf("%lld",&x[i]);
    sort(x+1,x+1+n);int now=2;//对 x 进行排序
    if(n==1) x[2]=x[1];//特判 n=1
    for(int i=1,y;i<=q;i++){
        scanf("%lld",&y);
        while(y>x[now]) now++;//更新现在在哪两个虫洞之间
        int ans=-(y-x[now-1])*(y-x[now])%mod;//带入公式
        ANS^=ans;if(ans&1) ansji++;
        ansmx=max(ansmx,ans);ansmn=min(ansmn,ans);
    }
    printf("%lld\n%lld\n%lld\n%lld",ANS,ansji,ansmx,ansmn);
    return 0;
}
本文作者:water_tomato
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇