置顶文章

精选分类

文章列表

1.8k 2 分钟

# 扩展欧几里得 求不定 ax+by=cax+by=cax+by=c 的所有整数解。 # 判断该方程是否有解 裴蜀定理:设 gcd⁡(a,b)=d\gcd(a, b) = dgcd(a,b)=d,则对任意整数 x, y,有 d|(ax + by) 成立; 特别地,一定存在 x, y 满足 ax + by = d 等价的表述:不定方程 ax + by = c (a, b, c 为整数) 有解的充要条件为 (a, b)|c 推论:a, b 互质等价于 ax + by = 1 有解 因此只要求出 ax+by=gcd⁡(a,b)ax+by=\gcd(a,b)ax+by=gcd(a,b)...
481 1 分钟

# LCA: Lowest common ancestor 最近公共祖先 # 倍增求 LCA 预处理向上跳 2^k 步的结果 f [k][x] O(nlog⁡n)O(n \log n)O(nlogn) 求的时候先把两个点跳到一个深度,这里有一个特判,如果重合直接返回这个点 然后 log 值从大往小枚举,两个点一起不断向上跳,直至父亲相同,直接返回父节点 可以O(n)O(n)O(n) 预处理 log 值,把复杂度降到 O(常数)O(常数)O(常数) # 欧拉序求 LCA 欧拉序:dfs 时的访问完整路径,回溯时也要把这个点算上 易知欧拉序的长度是...
3.8k 3 分钟

p{text-indent: 32px;} # 凝眉 他和她走下车。站台上熙熙攘攘的人守望在那里。没有人向他们看上一眼。 他们停下脚步,看着列车消失在金色的反光里,只留下无底的空白。 “所以…… 新见和五反田他们呢?” 高桥问道。 “他们?他们不会来了。”...
800 1 分钟

# 健身房的年轻后生不讲武德,把马保国老师的眼睛给打肿了 啊朋友们好啊,我是浑元形意太极门掌门人马保国。 刚才有个朋友,问我马老师发生甚么事了,我说怎么回事,给我发了几张截图。我一看,嗷,原来是左天,有两个年轻人,30 多岁,一个体重 90 多公斤,一个体重 80 多公斤。塔们说,诶,有一个说是,我在健身房练功,颈椎练坏了,马老师你能不能教教我婚缘功法,矮…...
3k 3 分钟

# 前置概念 时间戳:搜索时第几个搜索到这个点。如搜索顺序是 1->2->3->6,则 6 的时间戳为 4 # 对于无向图 连通分量:对于图 G 来的一个子图中,任意两个点都可以彼此到达,这个子图就被称为图 G 的连通分量(一个点就是最小的连通分量) 最大连通分量:对于图 G 的一个子图,这个子图为图 G 的连通分量,且是图 G 所有连通分量中包含节点数最多的那个,即为 G 的最大联通分量 # 算法流程 个人认为 Tarjan 是提高组范围内最难的一个算法了,我自己说不太明白。。。推荐看看这篇 # 简单应用 # 缩点 有向图强连通分量:在有向图 G...
9.3k 8 分钟

# P1020 导弹拦截 #include <stdio.h>#include <string.h>#include <iostream>#include <algorithm>using namespace std;const int N = 100010;int n = 0;int a[N], b[N], s[N], ls[N];void add(int x, int v) { for(; x<=n; x+=x&(-x)) s[x] = max(s[x], v);...
4k 4 分钟

# 常见的贪心技巧 货币使用问题: 尽可能少用,那么我们就先拿面值最大的,依次往下走,最后拿光了即可。 区间调度问题: 工作时间不能重叠,在可选工作中,每次都选取结束时间最早的作为选择,可以使工作量最大。 # 切题小技巧 递归,从后向前 预处理 划分子结构 单调队列、滑动窗口 能剪的枝一定要减!能剪的枝一定要减!能剪的枝一定要减! 但是剪枝别剪挂了…… # 手动扩栈 编译时指定参数 -Wl,--stack=sizesize 是栈的大小,单位为字节。 # P5686 [CSP-SJX2019] 和积和 #include <stdio.h>#include...
4.1k 4 分钟

# DFS 众所周知,搜索和 DP 是不分家的,几乎所有的 DP 都可以转化为搜索。当想不出正解时,DFS 也是骗分的好手段。 主要的搜索手段有: DFS/BFS 爆搜 双向 BFS 启发式搜索(又称 A*) 迭代加深搜索 IDA*(迭代加深 + 启发式) 记忆化搜索 剪枝 重要程度:1,7,6 - 4,3 - 5,2。 下面这几道题都是去年当时不会做的,结果一年过去了,还是不会,呜呜呜 # P3956 棋盘 NOIp 2017 普及 搜索裸题 显然不可以用 vis []...
3.3k 3 分钟

# 区间 DP # P1880 [NOI1995] 石子合并 #include <stdio.h>#include <string.h>#include <iostream>using namespace std;const int N = 220;int ans, dp[N][N], n, a[N], s[N];int main() { scanf("%d", &n); for(int i=1; i<=n; ++i)...