[Zzz]趁着不太清醒赶紧把题解补完 | JLOI2014

[JLOI2014]天天酷跑

某优雅的DP题。

dp[i][j][k]表示在位置 (i,j) 并且用了 k 次连跳的答案。

转移分三种:一是如果 j=0 也就是在地面那可以跑一格

或者 k<q 可以跳一下

或者如果可以的话,下落。

可以枚举跳跃高度和次数然后记搜。

[JLOI2014]松鼠的新家

年代久远了。如果我没记错应该是一个树上差分问题。

好像是什么树上差分的板子……随便写写。

这是我元旦那天做的第一题,或者也可以说18年第一道题。

[JLOI2014]路径规划

这题劲啊!这题可劲了

考虑对 k 也就是过红绿灯的次数分层。

然后还是不好搞,没有办法之后我们可以分第二层。

k 分层之后,对于每一层,枚举所有加油站,计算出这个加油站 i 分别到 所有层 的 所有加油站 的最短路。

然后这样建新图,直接在加油站-加油站之间连边。然后跑对于 k 的分层图最短路。

SPFA 不会被卡。

期望等待长度是 \frac{R^2}{2 \cdot (R+G)}

[JLOI2014]镜面通道

hhh如果想知道证明可以评论

可以证明如果透气就一定透光。

不会构造出虽然透气,但是光线一直循环地反射,从而出不去的情况。

 

简单计算几何+最小鸽

每个几何图形做一个点,连边双向边。

圆与正方形交的时候,如果解方程,注意精度。

首先对于一个数字 x 的唯一分解式设为 \prod _{i=1} ^{n} p_i^{a_i}

那么约数和就是 \prod _{i=1} ^{n} \sum _{j=0} ^{a_i} p_i^j , 这个非常显然 (?)

那么……我们可以猜出 xS 是同级的。

那么显然 p_i \leqslant \sqrt{S}

那么可以暴搜。枚举 p_ia_i

一个特判是如果当前的剩余数字 S_i 减去 1 之后为一个质数,并且不小于当前枚举到的最大质数,那么也要算进答案。

需要证明请在评论区留言。

QAQ (一瓶咖啡灌下去) 差不多清醒了…

发表评论

邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据