CYJian的水题大赛[第二弹] 题解
CYJian
2018-08-15 22:01:40
(由于今天晚上被爸妈拖到超市买开学要的东西去了..所以发题解的时间就推迟了这么久..)
为了更好的阅读体验,代码部分会在文末贴上云剪贴板的链接,不会放在题解部分浪费大家翻阅的时间(其实就是代码写得又丑又长..)
## T1 JerryC Loves Driving
这道题乍一看好像是数论分块板子题。但是再仔细看一眼数据范围就会发现妥妥70分...
那怎么办呢??
首先需要对这个式子开个刀:
$$\sum_{i=A}^{B}\sum_{j=1}^{i}(-1)^j*\lfloor \frac{i}{j} \rfloor$$
$$=\sum_{i=1}^{B}((-1)^i*\sum_{j=A}^{B}\lfloor \frac{j}{i} \rfloor) $$
$$=\sum_{i=1}^{B}((-1)^i*(\sum_{j=0}^{B}\lfloor \frac{j}{i} \rfloor-\sum_{j=0}^{A-1}\lfloor \frac{j}{i} \rfloor))$$
这个变化应该没有什么问题吧..毕竟如果$i>j$的话,$\lfloor \frac{j}{i} \rfloor=0$,这样对答案就没有什么影响了..
然后我们就考虑如何$O(1)$求得第一个括号里面的式子。
首先我们可以发现,一段从0开始的连续整数除以另一个整数$x$向下取整就会像这样:
$$ \underbrace{0,0...0}_{x},\underbrace{1,1...1}_{x},\underbrace{2,2...2}_{x}...$$
这个应该没有什么问题吧..
所以我们就可以直接枚举$i$,然后对于每一个$i$算出0~B除以$i$向下取整的值,然后减去0~A-1得到的值,然后乘以个$(-1)^i$就好了..
注意:不要所有的数开long long,常数太大会卡TLE..
(这里有两位大佬给出了$\sqrt(N)$的做法,[链接在此](https://www.cnblogs.com/LonecharmRiver/articles/9499652.html),还有[这个也是](https://www.luogu.org/blog/zhoutb2333/dao-shi-hou-zai-gai-ba-post))
## T2 Jerry Loves Lines
首先需要知道一个~~常识~~:两条直线相交后,这两条直线在交点右侧的大小关系就会改变.如果有多条直线计算排名,则会导致两条直线交换排名,且这两条直线在交点附近排名必然相邻.所以可以直接把这两条直线的一条排名+1,一条排名-1,这样就可以稳定过了..
~~这个应该算是常识吧..或者说很显然~~
然后对于这道题,我们就只要算出所有直线两两之间的交点并且按照$x$排好序,然后把询问离线排序处理.
先将所有点按照最靠左的询问排好序,然后每经过一个交点就把直线的排名更新一下.处理询问的时候就直接用排名为$k$的直线更新就好了.
## T3 Samcompu Loves Water
~~这道题就是一并查集板子题..~~
如果没有失效的跳转方式的话,我们可以直接把所有的跳转方式按照危险程度排个序,然后一个一个按照并查集的方式加边,方案数的话就直接每次拿要合并的联通块的size的乘积加上去就好了..至于答案,先离线按照时间排个序,在加边前如果危险程度大于时间就直接把当前的总方案数*2(因为A->B和B->A算两种答案)当成答案就好了.
加上失效的跳转方式怎么办呢??
出题人非常良心的强调了不同的$K_i$最多只有$10^3$个..
所以就可以把这些可能失效的跳转方式专门拿出来,处理一个询问时就先备份好之前的数组,然后暴力加上需要加上的边,记录答案后就直接恢复原数组就好了..
(多亏 @Sooke 大佬看得起,竟然打了LCT..%%%蒟蒻根本不会LCT..)
## T4 Zrz_orz Loves Secondary Element
其实题目并不难,只是相当于做了两道题而已..
首先需要了解的一点是:我们最终需要回到1号点,所以每一条边肯定都会走至少2次,并且对于一棵树,一条边允许走两次的话存在一笔画的方案.所以我们直接把走的所需时间*2就好了.这样就不需要考虑回到1号点的问题了.
然后对于Subtask 0..
实际上就是Subtask 1的做法..
直接dfs暴力枚举和不和第$i$个角色对话并且记录愉悦值,然后直接暴力算出需要走多久.
然后把上面的东西按照走的时间排个序,然后对于每一个询问选择最大的愉悦值就好了..
Subtask 2的话..
树形DP..
我们可以定义状态$f[i][j]$表示在$i$的子树中走最多$j$的单位时间所能获得的最大愉悦值.
这个转移方程应该比较显然吧..如果不太清楚直接看代码部分就好了..(其实只是懒而已..)
## code
写的比较丑,希望大佬勿喷..
[T1](https://www.luogu.org/paste/2sfiqmcm)
[T2](https://www.luogu.org/paste/hp4loy5z)
[T3](https://www.luogu.org/paste/4x9ua5nq)
[T4](https://www.luogu.org/paste/9ysudvv6)