割线 二分法

```cpp namespace binarySearch { // 最后一个小于等于 template T* binarySearchLastSmall(T* l,T* r,int key) { while(l+1 T* binarySearchLastSmallEx(T* l,T* r,int ......

## 引入：什么是二分图，什么是匹配 口头语言描述：一个图，你把他的点集划为两个集合，让每个集合之间的点没有连边，就是一个二分图。 ![](https://img2023.cnblogs.com/blog/1646455/202308/1646455-20230808143311529-808821 ......

# 20230723与y总代码模板不同，为自己独立实现，不够美观，但便于自己理解 debug过程： - 需要注意到本题是无向图，所以add函数需要用两次，还有就是我们使用链式前向星结构去存图，所以ne和e数组需要开两倍的边数。 ##### 就是因为数组开小了，导致最后tle了，~~数组开小了什么报错 ......

$\sf{definition}$ 对于一个图 $G=(V,E)$，若能将 $G$ 分为两个子图 $G_1=(V_1,E_1),G_2=(V_2,E_2)$，且满足 $E_1=E_2=\emptyset,V_1\cap V_2=\emptyset,V_1 \cup V_2=V$，那么这个图就是一个* ......

**最长反链**：一张有向无环图的最长反链为一个集合 $S \subseteq V $，满足对于 $S$ 中的任意两个不同的点 $u, v \in S(u \ne v)$，$u$ 不能到达 $v$，$v$ 也不能到达 $u$，且 $S$ 的大小尽量大 **最小不可重链覆盖**：在 DAG 中选出若干 ......

**GDCPC A题** **原题链接：**https://cpc.csgrandeur.cn/csgoj/problemset/problem?pid=1168 **类似的题目及视频解释链接：** **题目：**https://www.acwing.com/problem/content/desc ......

//通往奥格瑞玛的道路 //二分最大的答案,然后有单点超过这个值就直接返回,继续二分 //每循环一次都要跑一遍最短路,这里选择时间复杂度更优的堆优化dijkstra //坑点的较多,还请注意 #include<bits/stdc++.h> #define int long long using na ......

# P2249 [深基13.例1] 查找 ```cpp #include #include using namespace std; const int MAXN = 1000005; int a[MAXN]; int main() { int n, m; scanf("%d%d", &n, &m) ......

# 通往奥格瑞玛的道路 ## 题目背景 在艾泽拉斯大陆上有一位名叫歪嘴哦的神奇术士，他是部落的中坚力量。 有一天他醒来后发现自己居然到了联盟的主城暴风城。 在被众多联盟的士兵攻击后，他决定逃回自己的家乡奥格瑞玛。 ## 题目描述 在艾泽拉斯，有 $n$ 个城市。编号为 $1,2,3,\ldots,n ......

- ### 最小生成树 - #### Prim算法 - 朴素版Prim ==O(n^2)== - 稠密图 - 步骤： - S：表示最小生成树的集合 - 初始化距离 - 找距离集合S最近的节点 - 将节点加入集合S - 用该节点更新非S点到集合S点的距离 - 代码： ```c ++ const int ......

### 题意： > 给定一个序列$a$，定义一次操作选择序列中一个元素$a[i]$， 使$a_i = \lfloor \frac{a_i}{2} \rfloor$，其中$a_i$为当前序列中的最大偶数，若没有则是最大奇数。 > > 有$q$组询问，每次给定$k, l, r$分别表示操作次数和操作区间 ......

设 $M$ 是 $G(V,E)$ 的一个匹配 1. 先称 $M$ 中的边为匹配边，不在 $M$ 中的边为非匹配边 2. 与匹配边相关联的点，称之为配对点，不与匹配点相关联的点，称之为非配对点 3. 如果 $G$ 中的每个点都是配对点，则称 $M$ 是 $G$ 的一个**完美匹配** 4. 在 $G$ ......

ROC https://zhuanlan.zhihu.com/p/246444894 Sure, let's create a random confusion matrix as an example, and then I'll explain what each element in the ......

# 网络流的定理与性质 ### 增广路定理 加了反向边之后网络流可以以任意顺序增广，增广路不存在时一定为最大流。 ### 最大流最小割定理 网络的最大流等于最小 $S-T$ 割。 从线性规划的角度看最大流与最小割互为对偶。 ### 增量加边 由于有增广路定理，在对网络流加边后，只要再跑一次网络流算法 ......

## 1.二分图的有关性质 首先二分图必定``不具有奇数环``。而``不具有奇数环``的图必定可以被染成相邻两个点都不是同个颜色的图（只用黑白两色）。 首先证明不具有奇数环的图是图在染色不存在矛盾的``充分必要条件``。 证明充分性，用反证法。图中无奇数环，但是染色存在矛盾，则有``白黑白黑...白 ......

## 网络流的求法 ## misc ### 复杂度分析 - Dinic 的复杂度上界为 $O(n^2m)$。 - 但是特殊情况下会更快，如二分图匹配是 $O(m\sqrt n)$ 的；确定流量上限 $f$ 时，复杂度为 $O(mf)$。 - 最小费用最大流的复杂度上界为 $O(nmf)$。 - 注意 ......

## 题目 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。 提示: 1. 你可以假设 nums 中的所有元素是不重复的。 2. n 将在 [1, 10000]之间。 3. nu ......

应用: 问 2人依次走, 但是不能走到历史状态 看题意是否满足 二分图建图 性质 结论: 如果起始点, 必然在 最大匹配上, 那么先手必赢 不一定在最大匹配上, 那么先手必败 实现: 利用网络流, 先让 和 开始点的边权为0,跑一次 在恢复边权跑一次, 看ans 变大没有 ......

package mainimport "fmt"func main() { array := []int{1, 5, 9, 15, 81, 89, 123, 189, 333} target := 500 result := BinarySearch(array, target, 0, len(ar ......

案例： def binary_search(li, val): left = 0 right = len(li) - 1 while left <= right: # 候选取有值 mid = (left + right) // 2 # mid 位置 if li[mid] == val: # 如果mi ......

# 博客来源： https://pythonjishu.com/papquwdlspdjnhr/ https://blog.csdn.net/Jack_user/article/details/130534926 这个写的比较好 1. 查找算法概述 查找算法是一种用在数据集合中查找特定元素的算法。常 ......

1.是什么 一种特殊的图，这种图可以把图中的点分成两个集合，所有的边都在这两个集合之间，也就是说集合内部的点之间是没有边的。 2.怎么判断 一般来说用染色法判断，从任意一个结点开始交替染色，若与某节点连边的结点已被染色，且颜色与该节点相同，则该图不是二分图。 代码： int paint(int x, ......

#### 二分图博弈 二分图博弈模型的描述为：在一张二分图上，给定一个起始点S，有两个玩家轮流操作，每轮玩家可以走到一个相邻的且之前没有走到过的点，不能移动的人输掉。 二分图博弈的结论为：如果起始点S一定属于二分图的最大匹配，则先手必胜，否则先手必败。 证明： 1.若S一定属于最大匹配，则先手只需要 ......

# 二分查找 前提：有序 思路： mid = (left + right) / 2 若 mid = value , 输出 mid 下标 若 mid value , mid = right - 1 ``` public class Test2 { @Test public void test1() { ......

[toc] # 二分图 ## 相关资料 ## 例题 ......

## 二分图的最小顶点覆盖 最大独立集 最大团 重要结论写在最前面： - ① 最小顶点覆盖等于二分图的最大匹配 - ② 最大独立集=所有顶点数-最小顶点覆盖 - ③ 二分图的最大团=补图的最大独立集 ### 一、二分图的最小顶点覆盖 **定义**：假如选了一个点就相当于覆盖了以它为端点的所有边。最小 ......

二分查找变种： 1. 查找大于target的所有值的最小索引； 2. 查找等于target的所有值的最大索引（上界）； 3. 查找大于target的所有值的最大索引； 代码示例： /** * 二分查找工具对象 */ const BinarySearch = (function() { return ......

# 二分答案 ## 例题 - [abc 312 C - Invisible Hand](https://atcoder.jp/contests/abc312/tasks/abc312_c) [qiansui_code](https://atcoder.jp/contests/abc312/submi ......

### 题目 [C - Invisible Hand](https://atcoder.jp/contests/abc312/tasks/abc312_c) ### 思路 - 二分X，同时二分得到buyer和seller的人数（很精巧的二分~）； - 当然，从复杂度角度，$O(N\log N)$ 也 ......

这个的思路就是再开一个数组，存储长度为i的最长上升子序列的最后一个数字是多少，这个数组可以保证递增，之后开始二分，只要当前这个数是大于i-1的数但小于i的数，那就可以更新i的数，这里就是贪心的思想，相同长度结尾数字越小越好 ```cpp int len=0; for(int i=1;i<=n;i++ ......