Ynoi笔记本 & 本人题解导引

· · 个人记录

upd:2022/8/8 现在发现 Ynoi 的大部分 trick 都比较熟练了，于是就很久没更了，有空的时候可能还要 add 且重构一下。

个人认为 Ynoi 的题目基本都有 NOI 的难度了，再差放到 NOI 的 T1,T2 难度也是 OK 的。

Upd:其实现在发现也有一些比较水吧

坚持每周一道 Ynoi 吧，应该不算多。

在太阳西斜的这个世界里，置身天上之森。等这场战争结束之后，不归之人与望眼欲穿的人们，人人本着正义之名。长存不灭的过去，逐渐消逝的未来。我回来了，纵使日薄西山，即便看不到未来，此时此刻的光辉，盼君勿忘。

--世上最幸福的女孩《末日时在做什么?有没有空?可以来拯救吗?》

upd:2022/4/15 没想到还有人在看这个，但是已经小半年没更了（

P5355 [Ynoi2017] 由乃的玉米田

题解

核心思想：利用莫队和 $bitset$ 快速维护信息，由于莫队本身就是 $n \times sqrt(n)$ ，所以用根号分治维护除法操作。 此题对于日后的主要学习内容指导： - $bitset$ 的乱搞姿势，这里学习了一个区间是否可以选出两个数之和/差为，以后需要尽可能解锁更多 $bitset$ 乱搞姿势。 - 根号分治，一种技巧，以后离线题时如果有 $O(\sqrt{n})$ 可以考虑使用。 配套习题: 1.[小清新人渣的本愿](https://www.luogu.com.cn/problem/P3674) 2.…… 思考：如果现在需要一个LYC_data_struct： 1.查找一个区间内是否两个数 按位异或 为一个值 $x$ 。 2.查找一个区间内是否两个数 与 为一个值 $x$。 3.查找一个区间内是否两个数 或 为一个值 $x$。 # [P4688 [Ynoi2016] 掉进兔子洞](https://www.luogu.com.cn/problem/P4688) [题解](https://www.luogu.com.cn/blog/LOVENUTMEGFOREVER/ynoi2016-diao-jin-tu-zi-dong) 按理来说确确实实是自己想到了做法，但是不敢打。 说老实话，这道题做过来做过去还是卡参。 想到用 $bitset$ ，我们把所有数离散化下来不去重一个个往后面挪，最后把三个地方的 $bitset$ 与起来即可。 但是这样的话空间要爆，于是把原查询分成几个小查询即可。 卡参的话我也试了一下，其实卡到 $24000$ 就卡不动了，往大往小走反正我是越跑越慢。 此题对于日后的主要学习内容指导： - 以后如果用 $bitset$ 或者是其他什么奇奇怪怪的东西，如果空间复杂度涉及到 $O(x \times qtime)$ (其中 $x$ 可以是个常数或者变量都行)，就直接暴力拆成小询问卡空间…… 配套习题： 1.…… 思考：是否还有其他做法呢(如果有的话我们就可以把这道题~~卡一卡~~) # [P6018 [Ynoi2010] Fusion tree](https://www.luogu.com.cn/problem/P6018) (很久之前做的一道 $Trie$，有点忘题了，先咕着一些东西) [题解](https://www.luogu.com.cn/blogAdmin/article/edit/313007)谨慎食用陈年旧物。 # [[Ynoi2019 模拟赛] Yuno loves sqrt technology II](https://www.luogu.com.cn/problem/P5047) 二次离线莫队，具体可以参考我的[题解](https://www.luogu.com.cn/blog/LOVENUTMEGFOREVER/solution-p5047)。 此题对于日后的主要学习内容指导： - 二次离线莫队，可以多研究其性质。 - 值域分块，以后是不是得多研究一下这类查询修改时间复杂度不一的数据结构。 - 数据结构并不是查询修改都 $log$ 就最好，有时候一些东西的特性会导致不同的数据结构的选择。 配套习题： 1.[来者不拒，去者不追](https://www.luogu.com.cn/problem/P5501) 2.[~~二次离线莫队模板~~](https://www.luogu.com.cn/problem/P4887) 思考：不离线~~可不可以做~~呢？ # [P5607 [Ynoi2013] 无力回天 NOI2017](https://www.luogu.com.cn/problem/P5607) [题解](https://www.luogu.com.cn/blog/LOVENUTMEGFOREVER/solution-p5607) 此题对于日后的学习指导： - 数据结构套?的结构已经可以成一个体系了，树套树现在也显得单薄甚至有点特殊化，我们可否思考其他的一些非数据结构的东西(前提是最好与该数据结构有很好的相容性)被数据结构拿来套？ - 多学线性基，废物 & 败类 $FutaRi$ 一定要多做题才行。 - 线性基的一种 $trick$ ：差分后转区间异或修为单点异或修。 # [P4117 [Ynoi2018] 五彩斑斓的世界](https://www.luogu.com.cn/problem/P4117) [题解](https://www.luogu.com.cn/blog/LOVENUTMEGFOREVER/solution-p4117) 此题对于日后的学习指导： - 分块中，值域尤为重要！！！ - 均摊时间复杂度法，缩放区间法。 - 并查集……自己学的也太假了吧。 - 离线 + 答案可累加性 + 分块 = 可以压空间 # [P5309 [Ynoi2011] 初始化](https://www.luogu.com.cn/problem/P5309) [题解](https://www.luogu.com.cn/blog/LOVENUTMEGFOREVER/solution-p5309) 此题对于日后的学习指导： - 阈值分治，老生常谈的话题 - 从整体角度，进行维护 推荐一道有点像这道题的好题：(先报名[比赛](https://www.luogu.com.cn/contest/29674))[题目](https://www.luogu.com.cn/problem/T134240?contestId=29674) # [P5065 [Ynoi2014] 不归之人与望眼欲穿的人们](https://www.luogu.com.cn/problem/P5065) [题解](https://www.luogu.com.cn/blog/LOVENUTMEGFOREVER/solution-p5065) 此题对于日后的学习指导： - 双指针NB - 封装分块 - 在 $O(\sqrt n log_n)$ 的时间复杂度的时候，我们可以动态合并答案 - 或运算的NB性质 # [P5048 [Ynoi2019 模拟赛] Yuno loves sqrt technology III)](https://www.luogu.com.cn/problem/P5048) [题解](https://www.luogu.com.cn/blog/LOVENUTMEGFOREVER/solution-p5048) 此题对于日后的学习指导： - 对于整块的答案我们可以直接[L][R]方式进行存储或者预处理（这在没有修改的情况下是常见trick） - 在值域很小的情况下，$vector_i$ 存一下值i的出现情况，比较适用于区间众数或者一些很奇怪的东西吧。 # [P5072 [Ynoi2015] 盼君勿忘](https://www.luogu.com.cn/problem/P5072) [题解](https://www.luogu.com.cn/blog/LOVENUTMEGFOREVER/solution-p5072) 此题对于日后的学习指导： - 光速幂套阈值分治。 - 在一个答案表达式中，如果变量只有 $2$ 个的话我们可以考虑变化变量进行存储。 # [P5354 [Ynoi2017] 由乃的 OJ](https://www.luogu.com.cn/problem/P5354) [题解](https://www.luogu.com.cn/blog/LOVENUTMEGFOREVER/solution-p5354) 此题对于日后的学习指导： - 位运算性质并未理解透彻 - 分类讨论能力一点也不强…… 不过还是很开心的是应该是Ynoi系列里面完成度比较高的一道了。 # [P5071 [Ynoi2015] 此时此刻的光辉](https://www.luogu.com.cn/problem/P5071) [题解](https://www.luogu.com.cn/blog/LOVENUTMEGFOREVER/solution-p5071) 此题对于日后的学习指导： - 阈值分治在分解质因数中的应用 - 双重阈值分治 # [P7446 [Ynoi2007] rfplca](https://www.luogu.com.cn/problem/P7446) [题解](https://www.luogu.com.cn/blog/LOVENUTMEGFOREVER/solution-p7446) 此题对于日后的学习指导： - $\sqrt n \times \sqrt n \times \sqrt n = n \sqrt n

P5063 [Ynoi2014] 置身天上之森

题解

此题对于日后的学习指导：

P5527 [Ynoi2012] NOIP2016 人生巅峰

题解

此题对于日后的学习指导：

P6778 [Ynoi2009] rpdq

题解

此题对于日后的学习指导:

P5610 [Ynoi2013] 大学

题解

此题对于日后的学习指导：

配套习题：

P5528 [Ynoi2012] WC, THUWC, CTSC 与 APIO2017

现在这道题换了个名字

题解

此题对于日后的学习指导：

推荐习题可以见P5309。

P6779 [Ynoi2009] rla1rmdq

题解

此题对于日后的学习指导：

听说还有一道区间 K 级祖先区间和的一道题，自己想了一下貌似 n \sqrt n 时空很显然但是想必把空间卡了吧。

P6105 [Ynoi2010] y-fast trie

题解

此题对于日后的学习指导：

单说思维难度 Ynoi 最水无疑，但是说起码我是真的不会 STL 而且还有这么多细节……不骂了。

P5398 [Ynoi2018] GOSICK

题解

此题对于日后的学习指导：

P4692 [Ynoi2016] 谁的梦

题解

此题对于日后的学习指导：

P5313 [Ynoi2011] WBLT

题解

此题对于日后的学习指导：

P7447 [Ynoi2007] rgxsxrs

题解

此题对于日后的学习指导：

P7897 [Ynoi2006] spxmcq

题解

此题对于日后的学习指导：

P6783 [Ynoi2008] rrusq

题解

此题对于日后的学习指导：