好像C++的STL默认的排序都是升序（除了priority_queue）   multiset使用总结 multiset就是一颗平衡二叉树，支持log插入，log查询，log删除，还有一个重点就是是能进行二分操作。  multiset<int> S;//声明 S.insert(val);//时间复杂度为logn S.insert(pos,val);//指定位置插入，可以提高插入速度 S.insert(S.end(),val);//常数是S.insert(val)的1/3 S.insert(S.begin(),val);//常数和S.insert(val)一样 auto pos=S....

求 其中为数 的约数的个数， 为常数。 结论发现 范围的数全部满足上述公式， 范围的数只有 个不满足上述公式。  时    t cnt    1 24387   2 6620   3 2172   4 699   5 214   6 54   7 11   8 0    时    t cnt    5 6310   6 2162   7 1047   8 353   9 152   10 93   11 19   12 5   13 0    时    t cnt    10 3391   11 1766   12 1009   13 692   14 250   15 137   16 70...

刚刚计算机组成原理讲到汇编语言的递归，很受启发，所以分享一个用模拟栈实现递归的通用方法。 在模拟递归过程中之前，肯定先得把递归过程弄明白 比如对于下面的递归（伪代码）： void dfs(int a0,int a1,...) { { 代码块0; } dfs(a00,a11,...); { 代码块1; } }  它的执行过程如下：  总的来说递归过程分为以下五步：  执行代码块0 保存现场准备进入下一层 接受下层返回的数据 恢复现场 继续执行代码块1  上述五步相当重要 在直接用递归程序实现递归时，第二步和第四步都是编译器在帮助你完成。而手写递归则需要自己用模拟栈来实现保存现场和恢复现场。 接下...

有一个多月没更新博客了，惭愧呀！！！说没时间（毕竟每天娱乐的时间都还是保质保量的… ）都是借口，懒才是真的。。。 划分树是基于线段树的一种数据结构，主要用于在     l   o   g   (   n   )    log(n)   log(n)内求出序列区间的第K大值； 划分树主要分为两部分，建树和查询。 插个模板例题Poj 2104 K-th Number 建树：   建树过程类似于快速排序，所建的树每一层都有n个元素，建树的核心就是根据根节点的信息将下一层分为左右子节点，使得左子节点内的所有元素严格不大于右子节点内的所有元素。也就是说在每次要递归的区间，找到其中位数，小于中位数的放到左...

先呈上原题链接"Ray, Pass me the dishes!" (vjudge) （大白书刷题笔记） 又是一道比较练代码能力的题目，开始的时候常数写太大了还写成了      O   (   n   ∗   log   ⁡   n   ∗   log   ⁡   n   )    O(n*\log n*\log n)   O(n∗logn∗logn)，数据范围又是      5   e   5    5e5   5e5 且多组数据，所以 TLE 了。。。后来全部改写过了。 还有就是里面有许多细节加之平时用结构体少，历时3天 边玩边写 :） 还是学到了不少。 题意： 给出长...

先呈上原题链接 Princess Principal 这是2018年牛客网国庆集训的题目，不会也没补，后来准备参加 秦皇岛 CCPC - Winter Camp 时在第一场热身赛时又遇到了。当时热身赛都过了一半了才想起这个事，在图书馆把签到题写了，刚看到这道题就被室友叫去打篮球了。虽然一直牵挂到这道题，直到今天才补上。。。 算是一道比较经典的括号序列题了吧。 题意： 要快速判断一个文档有没有语法错误。 有一个含有      n    n   n 个括号的文档。括号一共有      m    m   m 种，每种括号都有左括号和右括号两种形式，其中偶数为左括号，奇数为右括号，且      ⌊  ...

先呈上原题链接 题意： 在大学里选修过数据结构的同学大部分都知道      h   a   s   h    hash   hash 算法的线性探查法： 假设有一个元素互不相同的正整数数组      a   [   1   …   n   ]    a[1\ldots n]   a[1…n]，我们用以下方法得到数组      b   [   1   …   n   ]    b[1\ldots n]   b[1…n]： 初始时      b   [   i   ]    b[i]   b[i] 都为      −   1    -1   −1，我们对      i   =   1   …   ...

先呈上原题链接 这是一道非常优秀的线段的题目，如此说的原因不是因为它的操作有多么新奇，而是因为解该题的思路有着很好的启发作用。 题意： 你有一个数列      a   1    ,    a   2    ,   …   ,    a   n     a_1, a_2, \dots, a_n   a1​,a2​,…,an​ ，你要模拟一个类似于快速排序的过程。有一个固定的数字      x    x   x。 你要支持三种操作：  询问区间      [   l   ,   r   ]    [l, r]   [l,r] 之间的元素的和，也就是      ∑    i   =   l    r...

如果不会线性筛素数的话，建议先看这篇博客了解一下线性筛素数。 线性寻找约数的个数（积性函数都可以线性筛）主要是在线性筛素数的基础上得到的 用      f   (   n   )    f(n)   f(n) 表示      n    n   n 的约数的个数 用      g   (   n   )    g(n)   g(n) 表示      n    n   n 的最小质因子的个数 我们知道： 若      n   =    ∏    i   =   1    n     p   i    t   i      n=\prod_{i=1}^n p_i^{t_i}   n=∏i=1n​pi...

如果不会线性筛素数的话，建议先看这篇博客了解一下线性筛素数。 莫比乌斯函数函数（积性函数都可以线性筛）主要是在线性筛素数的基础上得到的 我们知道： 若      n   =    ∏    i   =   1    n     p   i    t   i      n=\prod_{i=1}^n p_i^{t_i}   n=∏i=1n​piti​​ 则      μ   (   n   )   =    {     <mstyle displaystyle="false" scriptlevel="0">   (   −   1    ) ...

如果不会线性筛素数的话，建议先看这篇博客了解一下线性筛素数。 欧拉函数（积性函数都可以线性筛）主要是在线性筛素数的基础上得到的 欧拉函数：     φ   (   n   )   =   n   ∗   ∏    (   1   −    1    p   i     )     φ(n)=n* \prod \left(1-\frac{1}{p_i}\right)   φ(n)=n∗∏(1−pi​1​) 其中      p   i     p_i   pi​为     n    n   n的质因子 所以： 1、当      n    n   n 为质数的时候      φ   (   n   ...

线性筛素数，可以保证每一个数都是被其最小的质因子筛掉的，所以可以保证时间复杂度在O(n)。 算法分析： 算法的关键在于第二个for循环的break语句。此处的break是为了保证任何一个合数都是被它的最小质因子筛掉的，所以能够保证每个数都自会被访问一次，这也就保证了复杂度是线性的。 break处的再解释： 该算法的核心是保证每个数都只被它最小的质因子筛掉（理解这一点非常重要） 我们知道任意一个数a可以作如下分解：      a   =    p   1    t   1     ⋅    p   2    t   2     ⋅    p   3    t   3     ⋯    p   n...

先呈上原题链接[Codeforces Round #250 (Div. 1) D. The Child and Sequence] 题意： 给定一组数有三个操作： 区间每个值对  <math> <semantics> <mrow> <mi> P </mi> </mrow> <annotation encoding="application/x-tex"> P </annotation> </semantics> </math&gt...

先呈上原题链接[Codeforces Round #532 (Div. 2) E. Andrew and Taxi] 题意： 一个n个顶点m条边的有向图，每条边都有权值（即修改这条边方向所要付出的代价） 目的：改变部分边的方向，使图无环。 要求：寻找一种方案使改变的边的权值的最大值最小。输出权值和需要改变方向的边的编号。 思路： 先二分答案： 答案（ans）范围在0与这个图的最大权值之间，所以直接（在L和R之间）二分寻找答案。每给定一个值m=（L+R）/2 若所有边权大于该值的边构成的图存在环路，也就是说存在一些边权大于m的边是必须要改变方向的，则ans一定大于m，ans一定落在m到R区间内。...