UOJ Logo OldDriverTree的博客

博客

[Ynoi2016]Day2题解

2018-12-11 12:14:12 By OldDriverTree

我感觉我信概药丸了(为啥非要作死写奇怪的东西呢)

T1:JabberWocky

Idea:lxl Solution:lxl Std:lxl Data:lxl&zcy

https://www.luogu.org/problemnew/show/P4118

https://www.lydsy.com/JudgeOnline/problem.php?id=5394

首先要会拓展欧拉定理(我一个出数据结构的怎么就开始数论了呢)

$a^x\;mod\; p\;=\;a^{x\;mod\;Φ(p)+(x>Φ(p)?Φ(p):0)}\;mod\;p$

然后可以发现对一个数取欧拉函数,log次就会变成1(这个性质烂大街了吧),然后任何数mod 1都是0就可以停下来了(不要停下来啊)

然后直接这样写会发现WA了(这种东西肯定会有一堆细节啦)

以下这段抄自zcy的题解:

首先我们发现后面的phi[p]这一项是可能不会加的。这个怎么办呢?

首先可以按照相逢是问候那题的套路返回判断是否取模,以此作为是否加上这一项的依据。

当然这么做需要讨论的东西会有点多,挺麻烦的。

后来就想到了也写在讲评里的办法,就是因为这个不断地幂次增长速度极快,很少几项就能够增长到远大于模数的地步。

那就先暴力的处理前面几项,然后再正常做,这样就减少了讨论次数。

但是这么搞还会存在一个问题,就是如果前几个常数次暴力处理的全是1,增长就是假的。

不过考虑到有1的话后面的全都被变成了1,所以完全没有必要担心这个,找到1就从1开始做好了。

然后还会存在一个问题,就是如果得到的是0次方,$x^0 = 1$

这个虽然数据不会存在这个问题,但是取模后会出现。

这个地方稍微注意一下就好了。

然后应该就没有什么坑了。

时间复杂度应该是 $O( mlognlog^*v )$

空间复杂度 $O( n + m )$

对这题的评价:3/11

T2:Which Dreamed It

Idea:lxl Solution:lxl Std:lxl Data:lxl

https://www.luogu.org/problemnew/show/P4692

https://www.lydsy.com/JudgeOnline/problem.php?id=5395

思路非常简单,就每个颜色在每一段开一个set,然后每次修改的时候计算一下贡献就可以了

有一些细节需要注意

时间复杂度 $O( ( n + m )logn )$ , 空间复杂度 $O( n + m )$

对这题的评价:3/11

T3:JabberWockyII

Idea:ccz Solution:ccz Std:ccz Data:ccz

https://www.luogu.org/problemnew/show/P4693

https://www.lydsy.com/JudgeOnline/problem.php?id=5396

这是一道简单模拟题。

可以将有根有序树动态地剖分为一些水平路径和竖直路径,满足性质:

1.竖直路径表示一个点序列,每个点是上一个点的孩子;

2.水平路径表示一个点序列,这些点的父亲相同,每个点是上一个点右边的第一个点;

3.树上每个点在且只在一条路径中出现;

4.对每个点,它的孩子可以被表示成0到2条水平路径,除了至多一个点在某条竖直路径上。

不难实现两个操作:

水平访问:给定一个点w,保证w有至少一个孩子,将w的孩子表示为一条水平路径;

竖直访问:给定一个点w,将w在树上到根的路径变为一条两端为w和根的竖直路径。

接下来不难进行每个操作:

A和B是把一条路径从水平变为竖直或从竖直变为水平,可以打标记实现,注意维护4条性质

C为换根,竖直访问然后打上翻转等标记,需要注意对孩子顺序的规定

D和E只需进行水平/竖直访问然后进行普通的区间修改查询

F为初始化,略

可以发现竖直路径的变化和lct很接近,因此复杂度分析可以参考lct的一些结论。

时间复杂度 $O( mlog^2n )$ , 空间复杂度 $O( n + m )$

据@negiizhao 说可以做到 $O( mlogn )$?

对这题的评价:10/11

这套题就T3比较毒瘤,其他都很简单吧

按照惯例放上可爱的妹子的图:

评论

zcysky
我的题解写的好垃圾啊
XLightGod
毒瘤

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。