莫负雨霁晴·戏逐荷间风
你好，欢迎来到星栈

璀璨星空愿

莫负雨霁晴·戏逐荷间风

  • 离散化

    例题 分析 离散化事实上就是当这个数据范围比较大的时候但是能用到的数比较少的时候需要用到的算法。就比如这个题，a_i 和 b_i 的数据范围超大但 n 的数据范围只有 2\times 10^5。这个时候我们可以将其压缩，使得所有内容之间没有空位。 以样例为例，实现如下图：

  • OI的一点点数论

    排列数：A_n^m=\frac{n!}{(n-m)!} 组合数：C_n^m=\frac{n!}{m!(n-m)!} 最小公倍数：lcm[a,b]=\frac{a}{gcd(a,b)}\times b 余数公式（两两互推）： a=kb+r k=\lfloor{\frac{a}{b}}\rfloor r

  • 区间问题

    线性差分：植树节 题目描述 植树节快要到了，学校要组织志愿者去给树苗浇水。 有一排树苗，编号依次是 0, 1, 2, ... 。 现有 n 个志愿者去给树苗浇水，第 i 个志愿者选定了一个区间 [a_i, b_i]，表示第 i 个志愿者将区间 [a_i, b_i] 内的每一棵树都浇一次水。 例如某个

  • [ABC378C] Repeating 题解

    [ABC378C] Repeating 题解 解题思路 我们需要为每个 A_i 找到它在序列 A 中上一次出现的位置。你可能第一想法是使用桶来进行记录当前数在此之前的位置是什么。普通的桶在这一题显然是开不了的，因为数据量达到了 10^9。但其实使用map进行存储也同样可以通过本题。用map的思路比较

  • 2024NOIP模板代码复习专用文章

    最短路 dijkstra题目 代码 #include<bits/stdc++.h> #define ll long long #define N 200001 // 最大的顶点数和边数 using namespace std; // 初始化全局变量 int a[N],n,m,ver[N],nxt

  • Sakurako 和 Water 题解

    问题概述 因为题面翻译很清楚且题面容易理解，在这里就不再解释了。 解题思路 读完题后，先看时间复杂度，再选择实现方法。一看 n\le500 ，直接 n^2 暴力就可以了。下面将具体讲解实现方法。 对角线独立处理： 矩阵中的每条主对角线可以单独进行操作，因为一次操作只影响一个正方形区域内的主对角线。

  • 爆炸的平衡树, 替罪羊树 - 指针神教教主Defad

    指针大师3F的博客

    爆炸的平衡树, 替罪羊树 由于Defad不太喜欢旋转, 所以一般用替罪羊树. 这里写个博客介绍一下. 什么是二叉搜索树 可以维护一个集合, 相比于权值线段树 (动态开点) 的时间复杂度 \(\log{N}\) 空间复杂度 \(N \log{N}\), 二叉搜索树理论上来说只需要 \(\log{N}\

  • 莫队2 这次需要带修改了 - 指针神教教主Defad

    指针大师3F的博客

    莫队2 这次需要带修改了 莫队1 走上骗分之路 实现修改 莫队是不支持修改的, 但是有后人加以改进, 就有了代修版本. 我们现在有一个东西叫时间轴 (类似函数式线段树的每个根都是关于某次之前的根修改或查询的), 每次询问都记录一下当前的时间轴, 每次修改都在时间轴上新建一个版本. typedef s

  • 莫队1 走上骗分之路 - 指针神教教主Defad

    指针大师3F的博客

    莫队1 走上骗分之路 新坑介绍莫队, 第一篇是不带修的线性莫队. 什么是莫队 一种硬往两边扩展 (可能是收缩) 的玄学算法, 是老前辈莫涛老师发明的算法, 又因为莫老师进了国家队, 所以叫莫队. Google搜索需要搜索"Mo's Algo". 莫队能解决什么问题 很多, 只要 \([l, r]\)

  • 重链剖分, 树上路径问题大杀器 - 指针神教教主Defad

    指针大师3F的博客

    重链剖分, 树上路径问题大杀器 首先, 什么是树链剖分 数组, 要进行修改查询是非常方便的, 一眼线段树. 但是树并不是. 看一下我们目前已有的树上修改查询技术. 树上差分 只能修改, 最后才能查询, 不然就只能很慢的单点查询, DFS 序 + 线段树 只能进行子树操作, 不能进行路径操作. BFS

  • 指针, C语言的精髓 - 指针神教教主Defad

    指针大师3F的博客

    指针, C语言的精髓 莫队先咕几天, 容我先讲完树剖 (因为后面树上的东西好多都要用树剖求 LCA, 树剖求 LCA 比倍增求 LCA 常数小). 什么是指针 保存变量地址的变量叫做指针. 这是大概的定义, 但是Defad认为这个定义不太好理解, 所以我们先不看. 我们的电脑里都有随机存储器 RAM

  • 树上主席树 - 指针神教教主Defad

    指针大师3F的博客

    树上主席树 主席树, 但是维护树上路径信息. 由于Defad今天忌离散化, 就不离散化了, 把值域开大点一般没啥问题. 上次的主席树有个朋友说没完全讲清楚, 这次先讲透了 主席树, 整体围绕的是前缀和, 用"批判的继承"维护前缀和, 然后在前缀和上二分. 为什么主席树不可修改, 就是因为这个前缀和思

  • 焦点推荐7月前 195°

    离散化

    例题 分析 离散化事实上就是当这个数据范围比较大的时候但是能用到的数比较少的时候需要用到的算法。就比如这个题，a_i 和 b_i 的数据范围超大但 n 的数据范围只有 2\times 10^5。这个时候我们可以将其压缩，使得所有内容之间没有空位。 以样例为例，实现如下图：

  • 焦点推荐7月前 50°

    [ABC378C] Repeating 题解

    [ABC378C] Repeating 题解 解题思路 我们需要为每个 A_i 找到它在序列 A 中上一次出现的位置。你可能第一想法是使用桶来进行记录当前数在此之前的位置是什么。普通的桶在这一题显然是开不了的，因为数据量达到了 10^9。但其实使用map进行存储也同样可以通过本题。用map的思路比较

  • 焦点推荐8月前 30°

    【2024】CSP-S 二轮考前模板代码大杂烩

    2024NOIP模板代码复习专用文章 复习用的文章 最短路 dijkstra题目 P3371 【模板】单源最短路径（弱化版） - 洛谷 | 计算机科学教育新生态 代码 #include<bits/stdc++.h> #define ll long long #define N 200001 //

    • 精选分类

    最新图文动态

    最新视频动态

    走心评论

    查看更多走心评论

    共赴三年之约

    留下温度不虚此行