珂朵莉最可爱了 珂朵莉树最不可爱了
首先,珂朵莉树 一个十分暴力的算法,仅限于大量的随机数据,否则时间复杂度起飞,所以只要出题人想卡 就很容易GG

珂朵莉

出自《末日时在干什么?有没有空?可以来拯救吗?》的治愈番(万物皆可致郁)
(快去看!出门左转樱x动漫!)
珂朵莉的萌娘百科!


回归正题

到底珂朵莉可爱在哪里珂朵莉树是什么
阅读全文

有一个长为$a$, 值域为$[1,k]$的序列

对于每个询问区间$[l,r]$

$$
\sum^k_{i=1}{c^2_i}
$$

其中$c_i$表示数字$i$在$[l,r]$中出现的次数

莫队是由前国家队队长莫涛发明的

莫队算法的精髓就是通过合理地对询问排序,然后以较优的顺序暴力回答每个询问。处理完一个询问后,可以使用它的信息得到下一个询问区间的答案。(两个边界瞎跳)

考虑这个问题:对于上面这道题,我们知道区间$[1,5]$的答案,就可以求出$[2,6]$每个数的数量

莫队提供了这样一个排序方案:将原序列以$\sqrt{n}$为一块进行分块(分块的大小也珂以调整),排序第一关键字是询问的左端点所在块的编号,第二关键字是询问的右端点本身的位置,都是升序。然后我们用上面提到的“移动当前区间左右端点”的方法,按顺序求每个询问区间的答案,移动每一个询问区间左右端点可以求出下一个区间的答案。

1
return pos[a.l] == pos[b.l] ? a.r < b.r : pos[a.l] < pos[b.l];

这道题目只要分块排序亿下之后

阅读全文

P1081

题目简述

有一排高低不同的城市 城市距离=高度差

A和B自左向右开车旅行(出发点可以变)

A、B的开车风格:

1.A会前往右边距他第二近的城市
2.B会前往右边最近的城市
3.A和B开过的总里程不超过$X$

询问:

1.给定一个$X$ 求出从哪个城市出发 $A$的路程/$B$的路程 最大

2.给定$X_i$和出发城市$S_i$ 求$A$和$B$分别开的距离数

倍增

在没有修改的RMQ问题(区间最值问题) 基于倍增的ST表可以做到$O(1)$查询和$O(nlogn)$预处理

拿最大值来说我们用$Max[i][j]$表示,从$i$位置开始的$2^j$个数中的最大值,例如$Max[i][1]$表示的是$i$位置和$i+1$位置中两个数的最大值(也就是说当前位置是被包含进$2^j$个数去的)

那么转移的时候我们可以把当前区间拆成两个区间并分别取最大值

比如

阅读全文

题目描述

渡渡鸟国的每位国民都有一个长度为 $n$ 的身份证号,身份证号的每一位为 $[1,k]$ 内的一个整数。渡渡鸟国现在要设立若干个服务站,每个服务站有一个长度为 $2$ 的编号,每一位也是 $[1,k]$ 内的一个整数。

对于一只渡渡鸟,设其身份证号为 $s$,其中 $s$ 是一个长度为 $n$ 的字符串。对于一个服务站,设其编号为 $t$,其中 $t$ 是一个长度为 $2$ 的字符串。当且仅当 $t$ 是 $s$ 的子序列时,这只渡渡鸟可以被这个服务站服务。比如 $s=123,t=13$ 时,渡渡鸟可以被服务;而$s=123,t=31$ 时,渡渡鸟不能被服务。

渡渡鸟国王希望建设一些服务站,使得任意一只渡渡鸟都可以被至少一个服务站服务。它想知道最少需要建造多少个服务站。

通过并查集 首先最后要分成(k-1)组 然后求步数即可

这道题目可以算是一道set的板子题(在CJC大佬的提醒下恍然大悟,CJC的博客),于是这篇题解某种意义上其实是对于set的讲解和复习。关于STL的话,全称为Standard Template Library,说白了就是一个非常多功能的库,引用时按情况引用,可能会有set map algorithm等等,按情况来分析,用途很多,有封装好的快排、大根小根堆(优先队列)、二分查找、全排列、各种神仙玩意儿。set则是其中的一个工具。

阅读全文

学习了 LCA(最近公共祖先) 这个高级的东西。。
于是乎来发一些理解和题解以便以后复习。

什么是LCA

LCA就是LCA
就是求一棵树上两个节点最近的公共祖先,那么有什么用呢,用来做题。

LCA的实现

这里用到了“爬树”的方法找
例如两个节点$x,y$:
规定$deepth_x>deepth_y$
1.让深的那个节点,$x$往树上爬,直到$deepth_x = deepth_y$;
2.让两个节点一起向上跳,如果碰在一起了,那么就找到了。
嗯,真是生动形象好理解呢!

阅读全文