题目名称 | 2692. 天才魔法少女琪露诺爱计数 |
---|---|
输入输出 | cirnoisclever.in/out |
难度等级 | ★★★ |
时间限制 | 666 ms (0.666 s) |
内存限制 | 256 MiB |
测试数据 | 10 |
题目来源 | sxysxy 于2017-05-10加入 |
开放分组 | 全部用户 |
提交状态 | |
分类标签 | |
分享题解 |
通过:42, 提交:101, 通过率:41.58% | ||||
三玖是我老婆 | 100 | 0.002 s | 3.44 MiB | C++ |
┭┮﹏┭┮ | 100 | 0.004 s | 3.44 MiB | C++ |
小金 | 100 | 0.018 s | 1.60 MiB | C++ |
小金 | 100 | 0.022 s | 1.60 MiB | C++ |
kZime | 100 | 0.027 s | 1.71 MiB | C++ |
wdsjl | 100 | 0.031 s | 1.45 MiB | C++ |
sxysxy | 100 | 0.037 s | 1.34 MiB | C++ |
HeHe | 100 | 0.046 s | 1.46 MiB | C++ |
sxysxy | 100 | 0.065 s | 1.76 MiB | C++ |
Bennettz | 100 | 0.072 s | 2.45 MiB | C++ |
本题关联比赛 | |||
快乐小组互测赛2019-09-27 | |||
2024暑假C班集训9 |
关于 天才魔法少女琪露诺爱计数 的近10条评论(全部评论) | ||||
---|---|---|---|---|
Fuck :(
| ||||
出题人⑧要命了?加急名单预定!
数声风笛ovo
2019-07-09 16:23
12楼
| ||||
rvalue
2017-06-02 21:10
11楼
| ||||
sxysxy
2017-05-25 21:35
10楼
| ||||
C2H6
Ostmbh
2017-05-22 17:29
9楼
| ||||
主席树 ,线段树, zkw, 树状数组
卡常卡常卡常卡常 | ||||
下面是题解:(白色的字体,选中即可看到)
维护一个滑动矩形内的权值和,这个矩形的宽度是固定R-L+1的,因此我们把矩形 [i-R, i-L] 这一段直接合并了就好了,然后 一般的线段树/树状数组 就可以维护了,并不需要可持久化数据/树套树等。 | ||||
起初40行的地方没有膜于是溢出了0.0
| ||||
前几次智障一样的错误没1A。。
让我去冷静冷静。。。 | ||||
第一发主席树
|
琪露诺闲来无事,用冰块制造了了$N$个台阶,沿直线依次摆放,编号$1, 2, 3...,⑨, ...N$,分别高$H(1)$, $H(2)$, ... $H(N)$
琪露诺很满意自己的作品,想把自己抓到的青蛙放到台阶上玩,玩法也很简单。 青蛙最开始在第一个台阶上,它只能往前面编号更大的台阶上跳。如果现在在第$k$个台阶上,它至少要跳到第$(k+L)$个台阶上,最多只能跳到第$(k+R)$个台阶上,而且目标台阶现在所在的这个台阶,它们高度的绝对值之差,不能超过$T$。否则青蛙会跳不上去或者摔死。(这时候只有琪露诺给它续它才能复活,而琪露诺是不会给青蛙续的)。
琪露诺想知道青蛙跳到第$N$个,也就是最后一个台阶上,有多少种路线呢?琪露诺是天才魔法少女,但是数数用的是⑨进制,她数出来的结果别人是无法理解的,所以她找你来帮忙了,请你告诉大家,青蛙有有多少条路线可以走呢?告诉大家方案数对998244353取模的结果就可以啦,无法到达的话,方案数自然就是0。
2017.09.28更新:对题目进行一些科学性的说明:
大家都想知道,为什么样例数据1里面,青蛙可以跳过去,原因是这样的,我们进行一个情景模拟:
现在琪露诺抓到的一只青蛙,在高台上准备跳跃:
然后她跳了起来(我们这里忽略阻力做功,机械能守恒),跳到了高度比当前高20000的地方(这意味着她的身体可以承受把她自己送到更高的20000高度的高空产生的反冲力)
然后再落下,即使两个高度为1的高台之间,有一座高度100的高台,也是无法阻挡她跳过去的。但是又有问题了:为什么她落地点所在高台,不能高于她跳跃之前所在高台太多呢?因为跳完一次她会比较累,会休息一会儿,而海拔高度差过大的话,氧气浓度减少的梯度太大,且时间较长,会导致她难受昏厥。那为什么落地点所在高台不能低于她跳跃之前所在高台太多呢?我们做一个定量的计算:
设这只青蛙的质量为$m$从最高点处落到目标高台上的落地点时,在竖直方向上的分速度为$v$
则有$v^2 = 2g(T+\Delta h), v = \sqrt{2g(T+\Delta h)}$,落地时在竖直方向上有动量$p = mv = m\sqrt{2g(T+\Delta h)}$,由于高台质量很大,与青蛙发生碰撞时,我们不妨看作所有动量都转化为了青蛙受到的冲量$I$,假设青蛙落到高台上受到竖直向上的力为$F$,作用时间为$t$,那么就有$I = Ft$,得$F = mv = \frac{m\sqrt{2g(T+\Delta h)}}{t}$,根据相关人生经验可知,这个$t$是很小的(不妨设$t = 0.05s$),而$I$是很大的。我们之前提到过,这只青蛙能够承受将她送到更高的$20000$高度的高空产生的反冲力,可以算出来,这个反冲力的,青蛙跳出去一直到最高点的过程中,在竖直方向上有跳跃需要的竖直方向初速度$v_{0}^2 = 2gT, v_{0} = \sqrt{2gT}$,同理根据动量守恒我们也可以算出跳跃需要的力$F_{0} = \frac{I_{0}}{t} = \frac{mv_{0}}{t} = \frac{m\sqrt{2gT}}{t} \ll F$,也就是说,在目标高台远远低于当前所在高台的时候,虽然这只青蛙能够承受跳跃出去产生的反冲力,但是会因为无法承受落地时收到的力的冲击而被摔死,而琪露诺并不会给她续使得她复活,所以青蛙为了生命安全是不能跳到跟当前比太低的高台上的。
第一行4个正整数,$N, L, R, T$,含义如题面所示
接下来第二行,$N$个正整数,依次表示这$N$个高台的高度。
青蛙跳到最后一个高台上面的方案数对998244353取模的结果。
3 2 2 0
1 100 1
1
只有一种方案,从第1个高台直接跳到第3个高台。第二个高台虽然高100但是并不会影响青蛙跳过它,因为这些青蛙是经过早苗开光的
5 1 2 5
1 2 3 4 5
5
#5条路线分别是(数字代表高台的编号):
1-2-3-4-5
1-2-3-5
1-2-4-5
1-3-4-5
1-3-5
20 1 4 12
1 2 3 4 5 6 7 100 9 10 11 12 11 100 1 2 3 4 5 6
27680
良心大♂样例
对于20%的数据:$N \leq 20$,
对于另外20%的数据:$N \leq 10000, R-L+1 \leq 1000$
对于另外20%的数据:$N \leq 20000,T = 0$
对于另外20%的数据:$N \leq 20000$。
对于100%的数据:$N \leq 100000, 1 \leq R-L+1 \leq N,1 \leq H(i) \leq 10000, T \leq 10000$
by sxysxy。