0nedeer小基地

oi-wiki/math szu acm 筛法素数筛法 如果我们想要知道小于等于 n 有多少个素数呢？ 埃拉托斯特尼筛法(埃氏筛)对于任意一个大于 1 的正整数 n，那么它的 x 倍就是合数（x > 1）。如果我们从小到大考虑每个数，然后同时把当前这个数的所有（比自己大的）倍数记为合数，那么运行结束的时候没有被标记的数就是素数了。 123456789101112131415161718// 𝑂 (𝑛 log log 𝑛)vector<int> prime;bool is_prime[N];void Eratosthenes(int n){ is_prime[0]=is_prime[1]=0; for(int i=2;i<=n;i++) is_prime[i]=1; for(int i=2;i<=n;i++) { if(is_prime[i]) { prime.push_back(i); for(int j=i* ...

指针使C语言威力无穷利用指针，可以高效地表示复杂数据结构，改变作为参数传送给函数的值，处理已经被“动态”分配的内存，以及更简洁、高效地处理数组。 指针（基本介绍）指针百度 指针，是C语言中的一个重要概念及其特点，也是掌握C语言比较困难的部分。指针也就是内存地址，指针变量是用来存放内存地址的变量，在同一CPU构架下，不同类型的指针变量所占用的存储单元长度是相同的，而存放数据的变量因数据的类型不同，所占用的存储空间长度也不同。有了指针以后，不仅可以对数据本身，也可以对存储数据的变量地址进行操作。 内存地址 变量 指向变量的指针 定义 int number int *p 变量值 5 000000000062FE08 地址 000000000062FE08 000000000062FE0F 指针和间接性 指针为访问一个具体数据项的取值提供了一种间接方式 1234567891011121314151617#include <stdio.h>int main(void){ int a; int *p=&a; printf(" ...

Topological sorting拓扑排序：拓扑排序要解决的问题是给一个有向无环图的所有节点排序。拓扑排序的目标是将所有节点排序，使得排在前面的节点不能依赖于排在后面的节点。 DAG图(有向无环图) Directed Acyclic Graph 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include <bits/stdc++.h>using namespace std;const int N = 1e5+5, M = 2e5+5;int n, m, u, v, Cnt, head[N];struct node{ int nxt, to; node(){} node(int x, int v){ nxt = x, to = v; }}e[M];void Add_Edge(int u, int v){ e[Cn ...

oi-wiki 思想以及在几何问题上的应用 扫描线一般运用在图形上面，它和它的字面意思十分相似，就是一条线在整个图上扫来扫去，它一般被用来解决图形面积，周长，以及二维数点等问题。 1二维数点平面上n个点(xi,yi)回答q个询问，每个询问给定一个矩形[x1,x2]*[y1,y2],询问矩形里有多少个点 10^9 需要 离散化 1 2矩形面积并Atlantis 问题平面上n个矩形[xi1,xi2]*[yi1,yi2] (左上角[xi1,yi1]，右下角[xi2,yi2])。问面积并是多少？ 12 在序列问题上的应用3区间不同数之和有n个数a1,a2,…,an有q组询问，每次给一个区间[l,r],求区间不同的数字个数之和 12

并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。 并查集支持两种操作：合并（Union）：合并两个元素所属集合（合并对应的树）查询（Find）：查询某个元素所属集合（查询对应的树的根节点），这可以用于判断两个元素是否属于同一集合 (优化)路径压缩12345int find(int u){ if(f[u]==u) return u; else return f[u]=find(f[u]);} 种类并查集 带权并查集典！Monkeys 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869//正难则反#include <bits/stdc++.h>using namespace std;typedef long long ll;const int N =4e ...

Hash哈希 𝑠=“123abc”, 𝑏=97 𝐻𝑎𝑠ℎ(𝑠)=（1∗97^5+2∗97^4+3∗97^3+𝑎∗97^2+（ASCII）𝑏∗97^1+𝑐 ）𝑚𝑜𝑑 𝑚 它的作用在于把一个字符串转化为一个数字。 映射：string ——> intbase与m互质，则发生哈希碰撞概率减小 123456789101112131415161718192021222324252627282930313233343536373839404142434445//luoguP3370 模板【字符串哈希】// 给定 N 个字符串 ，请求出 N 个字符串中共有多少个不同的字符串#include <bits/stdc++.h>using namespace std;typedef unsigned long long ull;const int base=131;ull a[10010];char st[10010];int ans=1;inline void solve(){ int n; cin ...

堆是一棵树，其每个节点都有一个键值，且每个节点的键值都大于等于/小于等于其父亲的键值。每个节点的键值都大于等于其父亲键值的堆叫做小根堆，否则叫做大根堆。STL 中的 priority_queue 其实就是一个大根堆。堆主要支持的操作有：插入一个数、查询最小值、删除最小值、合并两个堆、减小一个元素的值。一些功能强大的堆（可并堆）还能（高效地）支持 merge 等操作。 二叉树满二叉树国内定义除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树。满二叉树满足如下性质：1、一个层数为k 的满二叉树总结点数为：(2^k)-1。因此满二叉树的结点树一定是奇数个。2、第i层上的结点数为：2^(i-1)3、一个层数为k的满二叉树的叶子结点个数（也就是最后一层）：2^(k-1)国际定义二叉树的结点要么是叶子结点，要么它有两个孩子结点。完全二叉树允许最后一层有空缺结点且空缺在右边 堆分类配对堆 二叉堆 左偏树 二项堆 斐波那契堆 大根堆小根堆二叉堆堆是一种完全二叉树对于任意一个父节点的序号n来说（这里n从0算），它的子节点的序号一定是2n+1,2n+2 左偏树操作以大根堆为例 ...

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。 链表——链式存储 what#include 是C++标准库中的头文件，用于引入双向链表（doubly linked list）的实现。 prev tail head -> item <- prev ↓ next -> item <- prev next -> item next -> null 基本操作 方法 含义 append() 向双向链表尾部追加元素 insert() 在双向链表的某个位置插入元素 get() 获取双向链表对应位置的元素 indexOf() 获取某元素在双向链表中的索引 update() 修改双向链表中某个位置上的元素的值 removeAt() 移除双向链 ...

动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程. 应用条件 1.最优化问题 2.重叠子问题 3.子问题空间不能太大，DP通常情况下需要求解每一个子问题的最优解来组合得到原问题的最优解。 最优子结构 无后效性 子问题重叠 基本流程1.刻画一个最优解的结构特征（状态设计） 2.递归的定义最优解的值（状态转移方程设计） 3.计算最优解的值，通常采用自底向上（递推）的方法（处理各种边界条件） 背包家族01背包你有一个容量固定为M的背包，以及N个物品。每一个物品具有一个固定的体积v和价值w。你需要在不超过背包容量的前提下最大化带走物品的价值。 状态转移方程 DP[i][j]=max(DP[i-1][j],DP[i-1][j-w[i]]+v[i]) 第 i 个物品不在最优方案中（不取第 i 个物品），问题变成了考虑了前 i-1 个物品，总体积不超过 j 时的情况。当前，一种潜在的最优方案是前 i-1个物品，总体积不超过 j 时的最优方案； 第 i 个物品在最优方案中（取了第 i 个物品），问题变成了考虑了前 ...

倍增法（binary lifting），顾名思义就是翻倍。它能够使线性的处理转化为对数级的处理，大大地优化时间复杂度。 当线性递推无法满足时空复杂度要求，则通过成倍增长的方式，只递推状态空间中2的整数次幂位置的值，将复杂度优化为log级别 应用RMQ问题Range Maximum/Minimum Query 区间最大（最小）值 给定n个数，有m个询问，对于每个询问，你需要回答区间[l,r]中的最大/小值。 ST表 ST表是基于倍增思想解决可重复贡献问题的数据结构。广泛应用于解决RMQ问题。 基于倍增思想，ST表可以做到 O(n log n) 预处理，O(1) 回答每个询问。但是不支持修改操作。 tip:与运算属于位运算a & b即把a和b拆成二进制，对应每一个二进制位，只有1&1==1，否则为0eg： D 5 & 6 B 101 & 110 ans 100 判断i是否为2的幂i&(i-1)==0 –> truei&(i-1)== ...