日后在写解析（如果不鸽，大概率考试考完） #include <iostream> #include <stdio.h> #include <algorithm> #include <cstring> #include <cmath> usi…

质数定义：一个数只能被1和自己整除，即因数只有1和本身 1.试除法 $O(\sqrt{N})$ 通过定义，我们清楚地明白，对于一个数n，我们只要判断它的因数有几个，就可以判断它是不是质数了。那么我们只要判断n能否整除2到n-1这个区间中的一个整数即可判断。 但是在数据过大时会有超时的现象，这时我们可…

代码针对洛谷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[…

概述： 以前刚开始学二分的时候，只知道二分就是一半一半的分下去，对于边界问题一直都不是很懂，之前为了避免这问题想着用一个对拍程序来查看自己写的是否是对的，但是想了想还是要想一个正解。 注意点: 二分时主要是防止l和r的值都不发生改变，使得程序进入了死循环。 接下来是本人的一点理解。 本人理解： 整数…

虽然没参加，但是还是记录一下。（只会t1） t1 #include <iostream> #include <stdio.h> #include <cstring> #include <algorithm> using namespace std; const int N=1…

概述 以前对于对拍感觉不是很必要，但是今天在刷二分题目的时候对于二分的边界一直都不是很懂。所以在思考如何考虑这个问题的时候，想到另辟蹊径。既然我自己不知道二分是不是写对了，就让电脑来让我判断。所以我决定去网上学习对拍。 但是网上的对拍虽然可以实现判断程序的对错，但是却不能给出确切的每个程序的运行时间…

概述： 线段树是算法竞赛中常用的数据结构（虽然考场中很少用，毕竟调起来麻烦，区间求和用树状树组还是更加方便代码也短）。 线段树可以在O(logN)的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。简略的描述一下算法思路，线段树是一个二叉树，树的每一个节点存…