TG1 基础数据结构 & P2070题解 & P3372题解 约定：本文的下标从1开始，代码尽量从1开始（我在努力习惯），一般使用\(\LaTeX\)美化 这一节主要介绍了一些基础的数据结构 （废话），前缀和，差分，二分查找，离散化，ST表，线段树等。 来给大家一一介绍一下 前缀和 求解问题: 给你一个数组\(a\)，\(n\)次询问，每次输入\(l,r\),求\(\sum\limits_{i=l}^ra[i]\) (就是a[l...r]的和)。 基本思想: 计算数组\(b\)，对于每一个\(b[i]\),值就是\(\sum\limits...

递推，递归与分治 递推 什么是递推 递推，就是从小的解开始，一步一步推到最优解的过程。 如何递推 这就要看具体情况，想出递推式，然后一步一步递推即可。 递推如何应用 讲这个之前，我们不妨先讲一讲递推如何具体实现。 第一步是先初始化。切记！ 有两种表示方法： 数组递推法，如 f[i] = f[i-1]+f[i-2]; 记忆化搜索，若冗余状态比较多则需要记忆化，否则直接调用即可。注意递归的结束，否则MLE或TLE后果自负。 那...

推荐Markdown编辑器——Inspire Inspire是一款非常好用的编辑器，支持Markdown语法，当然，Inspire还有一些自己的语法。 本文就是在这款编辑器下编写的。 风格 像Visual Studio一样,Inspire也有自己的风格，按下Ctrl+T,Inspire就可以为您切换为深色的风格。 我如何找到它 在浏览Windows应用商店的时候，我就看到了这款非常好用的编辑器。 可以在应用商店里面搜索它，然后立刻下载这个非常好用的编辑器——Inspire！！ 我将如何使用它 由于日常的需要，我会用它来进行CS（计算机科学）方面的博客，日后，你会经常看...

1.排序模拟枚举 复杂度 一般（最坏）复杂度 ：记号为 O(……) 均摊复杂度 \(\qquad\quad\,\) ：记号为 Θ(……),但一般写成O(……) 约定 省略系数O(100n)=O(10n)=O(\(\frac{1}{2}\)n)=O(n). log底数省略 排序 选择排序 这个大家都会，就不详细解释了 （逃 插入排序 冒泡排序 归并排序 详情请见点我 void ms(int b, int e) { if(e-b <= 0) return ; ...

归并排序原理 先对源数组拆拆拆！拆成最小的单个元素，再分别合并，合并时保证两数组有序（单元素有序，尽管非常平凡）， 然后再一路合并下去，就得到有序的大数组了。 这种思想叫分治，就是"分而治之" 归并排序模版 使用前须将cnt置为0 void merge_sort(int *A,int x,int y,int *T,int &cnt) { if(y-x>1) { int m = x+(y-x)/2; int p = x,q = m,i = x; merge_sort(A,x,m,T,cnt...

废话不多说，先贴代码： 1 #include <iostream> 2 using namespace std; 3 bool is_prime(int n) 4 { 5 if (n == 1 || n == 0) 6 return false; 7 if (n == 2) 8 return true; 9 for (int i = 2; i < n; i++) 10 if (n % i == 0) 11 return false; 12 retu...

这是我第一次写博客，请多指教！ vector是一种向量容器，说白了就是可以改变大小的数组。 vector是一个模板类，如果直接这样会报错：  1 vector a; //报错，因为要指定模板。  需要像这样： vector<int> a; ^/*这里可以改成别的类型,float,long等等……*/ 那么，什么是 模板 呢？ 模板是C++支持参数化多态的工具，使用模板可以使用户为类或者函数声明一种一般模式，使得类中的某些数据成员或者成员函数的参数、返回值取得任意类型。   模板是一种对类型进行参数化的工具；   通常有两种形式：...