倍增求区间最大值板子
日后在写解析(如果不鸽,大概率考试考完) #include <iostream> #include <stdio.h> #include <algorithm> #include <cstring> #include <cmath> usi…
记于12月20日
今日,我原是高高兴兴地坐在机房电脑前,等着友人到来。却不料事情出乎我的意料,一进门,他便说道他要退役了。我是一个不善言词的人罢,没有说什么,我也不想再问他事情的确定性,我是坚信着对于一件事物的是与否,只要我不去听,不去想,不去观察,那么这件事就是没有定下来的。怀着这样的心理,我初时并没有说什么,也是…
判断质数
质数定义:一个数只能被1和自己整除,即因数只有1和本身 1.试除法 $O(\sqrt{N})$ 通过定义,我们清楚地明白,对于一个数n,我们只要判断它的因数有几个,就可以判断它是不是质数了。那么我们只要判断n能否整除2到n-1这个区间中的一个整数即可判断。 但是在数据过大时会有超时的现象,这时我们可…
最近公共祖先(LCA)
代码针对洛谷P3379 1.向上标记法 最朴素的求最近公共祖先的方法,两个子结点同时向上一个一个的跳,标记已经跳过的点,如果有一个点跳到了已经标记过的点,那么就说明这个点就是最近公共祖先。可以自己简单的推一下,查询的时间复杂度为 $ O(n) $ 。 2.倍增 总思路:用类似于二进制拆分的思想。 首…
造题目数据
今天心血来潮想造个OJ,数据难搞,于是随便搞了一会,先把写的都发上来,睡完觉再来补。 #include <iostream> #include <stdio.h> #include <algorithm> using namespace std; int main…
浅谈树状数组
浅谈树状数组和线段树 树状数组 类比: 其实可以把树状树组简单的看成一个帮你求前缀和的树组,add为单点修改值,query(x)即为询问1到x的前缀和的值。(至少我是这样看的)。 简介: 树状数组和线段树具有相似的功能,但他俩毕竟还有一些区别:树状数组能有的操作,线段树一定有;线段树有的操作,树状数…
浅谈图论
链式前向星 众所周知,存图的方式有多种,例如邻接矩阵,邻接表,这两种一般初学者都在用,并且十分的便于理解和使用。但是当图的边数过大或者说点数较大时以上两种存图方式不是十分的合适。 所以说,这时就要用到我们的链式前向星了。本质上来说是用链表实现的临接表,先放代码。 int e[N],w[…
浅谈近况
一 儒略日2459546日,于网上冲浪时,欲休息一番,便翻阅起友人写的文章来,有一份眼熟但有不是眼熟的文章,我原是内心波动不大的,但看这一篇文章在上一篇文章的上面,上一篇文章在这一篇文章的下面,我便发现这浑然是一篇不同的文章。看完这篇文章后,内心触动极深,他人的生涯之中有着帮助他的人,而我当时的碰壁…
浅谈二分
概述: 以前刚开始学二分的时候,只知道二分就是一半一半的分下去,对于边界问题一直都不是很懂,之前为了避免这问题想着用一个对拍程序来查看自己写的是否是对的,但是想了想还是要想一个正解。 注意点: 二分时主要是防止l和r的值都不发生改变,使得程序进入了死循环。 接下来是本人的一点理解。 本人理解: 整数…
NOIP 2021
虽然没参加,但是还是记录一下。(只会t1) t1 #include <iostream> #include <stdio.h> #include <cstring> #include <algorithm> using namespace std; const int N=1…