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)的做法,链接在此,还有这个也是)

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

写的比较丑,希望大佬勿喷..