牛客872397712号

分类

cf(1) c语言(1) 动态规划(15) 未归档(7) 简约而不简单(57)

/ 注册

全部文章（共81篇）

DFS&BFS及其优化

DFS&BFS及其优化简介及声明本文所涉及的DFS/BFS仅指指数级以上复杂度的暴搜，不包括图和网格上 O ( n ) O(n) O(n)级别的搜索！ Part 1：DFS 例题1：[FAIOJ1220]字符序列直接暴力搜索每个位置填 A , B , C A,B,C A,B,...

2021-09-25

0 457

二分和分治

Part 1：二分查找二分法找零点 lower_bound LIS 数据结构上的二分注意：二分查找可行的前提条件是序列有序！例题1：[FAIOJ2333]乐谱直接在前缀和数组上lower_bound即可。复杂度 O ( n log ⁡ n ) O(n\lo...

2021-09-25

0 377

图论1-图的遍历

图的遍历图的遍历，就是在图上 D F S / B F S DFS/BFS DFS/BFS。是对图最基本的操作。图的存储方式邻接矩阵： O ( n 2 ) O(n^2) O(n2) 邻接链表： O ( m ) O(m) O(m) int e=0,fir[N],to[M],...

2021-09-25

0 401

图论2-并查集

并查集并查集维护一张无向图，支持以下两种操作： 1.连接两个点 2.查询一个点所在的连通块并查集的两种优化方式：路径压缩： O ( α ( n ) ) O(\alpha (n)) O(α(n)) 按秩合并： O ( log ⁡ n ) O(\log n) O(logn) Part...

2021-09-25

0 0

图论3-最小生成树

定义：生成树：无向图包含所有点的生成子图（即边集包含于原图），且是一棵树。最小生成树：边权和最小的生成树。基本性质：如果把边权看做代价，那么最小生成树就是使全图连通的最小代价。最小生成树同时满足整棵生成树上的最大边权最小，任意两点间的最大边权最小（这个性质由kruskal算法的执...

2021-09-25

0 590

图论4-最短路(I)

三种最短路算法 Floyd 可求出任意两点间最短路，适合小规模稠密图（点数不超过 500 500 500）。复杂度 O ( n 3 ) O(n^3) O(n3) 注意：如果 n n n超过 800 800 800，且图比较稀疏，可使用 n n n次dijkstra代替Floyd。 for...

2021-09-25

0 358

图论5-最短路(II)

Part 2.5.1 负环当一张图中有负环时，这张图中经过负环的两点间最短路就不存在。因为可以无限次经过这个负环，使代价不断减小。在三种最短路算法中，SPFA是唯一一种可以处理负环的算法。由SPFA的过程，每个点最多会被其他点各更新一次，即入队次数不会超过 n n n。因此如果一个点...

2021-09-25

0 373

简单数论(1)

【疯狂gcd】的推式子过程 ∑ i = 1 n ∑ j = 1 n g c d ( i , j ) \sum_{i=1}^n\sum_{j=1}^ngcd(i,j) ∑i=1n∑j=1ngcd(i,j) = 2 ∑ i = 1 n ∑ j = 1 i g c d ( i , j ) − ...

2021-09-25

0 457

「NOI大纲」

「NOI大纲」【X】表示难度系数 2.1 入门级 2.1.1计算机基础与编程环境【1】计算机的基本构成（CPU、内存、I/O设备等）【1】Windows、 Linux等操作系统的基本概念及其常见操作【1】计算机网络和Internet的基本概念【1】计算机的历史...

2021-09-25

0 638

神奇的幻方

题目描述幻方是一种很神奇的 N∗N 矩阵：它由数字构成，且每行、每列及两条对角线上的数字之和都相同。当 N 为奇数时，我们可以通过下方法构建一个幻方：首先将 1 写在第一行的中间。之后，按如下方式从小到大依次填写每个数若 (K−1) 在第一行但不在最后一列...

2021-09-25

0 489