NOI Online #2入门组

qwq不屑于打

是真的不敢打啊,太难了QAQ

看上去就很模拟?

对于所有测试点： $1 \leq n,q \leq 2 \times 10^5$ ， $1\leq v\leq L\leq 10^{9}$ $1\leq a_i < L$ $1 \leq t_i\leq 10^9$ 。

然而这个东西不能直接暴力了,你需要思考下

首先速度导致分数可以把要求的时间延长v倍,然后速度变为1

发现如果我用k个咒术可以那么k+1个也一定可以,而且越靠上越优

所以考虑把咒术从大到小排个序,然后一个个开始用,算出用完之后的时间

怎么算?细节问题

询问就相当于在这个数组上二分第一个时间大于他的次数是什么

如果您偏要直接做,每个询问都二分可以整体二分

大搜索题,题面自己看看吧

限制条件挺多,都没有华容道一个限制强力qwq

状态显然,为dp[i][j][c][c],如果在被看到格子就隐身,否则不隐身

转移显然,考虑瞬不瞬移,需不需要隐身

然后问题是怎么处理一个格子是被看到的,直接暴力不太行

多源广搜不太行的原因就是每个源点性质不同,这样性质就相同了,还是挺妙的吧

首先我们考虑第三个限制可以直接枚举转折点

然后问题就变成了 $f_{i,j}$ 表示长度为i构成值域在[1,j]的上升序列方案数

那么显然可以把 $f_{i,j}$ 的含义拓宽到值域程度为j,要么上升要么下降...

怎么求?dp毛线,组合意义会发现就是 $\binom{i+j-2}{i-1}$ ,表示我要插入i-1个板子,然后板子之间间隔多少个点就代表楼相差多高,第一个板子被硬点?

再考虑x,y在枚举转折点的哪里

如果在一侧,那么y-x+1个点高度相同可看为1个,所以是f(n-y+x,m)

如果在另一侧,那么我们要把区间一分为2单独去算,相当于四段区间,然后没有限制,f值乘起来就好

没有了

至于代码?看看吧qaq?

夏晓光(loveJY)的博客