CYJian的水题大赛[第二弹] 题解

CYJian

2018-08-15 22:01:40

Personal

(由于今天晚上被爸妈拖到超市买开学要的东西去了..所以发题解的时间就推迟了这么久..) 为了更好的阅读体验,代码部分会在文末贴上云剪贴板的链接,不会放在题解部分浪费大家翻阅的时间(其实就是代码写得又丑又长..) ## 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)