题目链接

最小点覆盖 同样的转化为图G=(V,E)，则问题转化为： 在图G中选取尽可能少的点，使得图中每一条边至少有一个端点被选中。 这个问题在二分图问题中被称为最小点覆盖问题。即用最少的点去覆盖所有的边。 结论：由König定理可知最小点覆盖的点数 = 二分图最大匹配 最大独立集 依旧转化为图G=(V,E)，则问题转化为： 在图G中选取尽可能多的点，使得任意两个点之间没有连边。 这个问题在二分图问题中被称为最大独立集问题。 结论：最大独立集的点数 = 总点数 – 二分图最大匹配 证明： 假设

题目链接：https://www.luogu.org/problem/T84891 题目 思路 如果零件A与零件B冲突，且零件A与零件C冲突，那么零件B与零件C也是冲突的。 也就是说在零件A、零件B、零件C中，我们只能选出其中一个零件。 而零件A 、零件B、零件C有一个共同的特征，那就是%K后为同一值。 所以只要把所有输入内容%K后塞入一个set，最后输出这个set的大小就可以了。 代码 #include <cstdio> #include <algorithm> #in

题目链接：https://www.luogu.org/problem/T84893 众所众知，二分用来查找单调序列中的内容，三分用来查找单峰序列中的内容。 题目 代码 #include <cstdio> #include <utility> #include <iostream> #include <vector> #include <cmath> using namespace std; const long long INF = 0

struct segment_tree_t { lli n; vector<lli> te; vector<lli> lz; segment_tree_t(lli n) : n(n), te(n << 2, 0), lz(n << 2, 0) { } lli ls(lli x) { return x << 1; } lli rs(lli x) { return x << 1 | 1; } void push_up(lli r

前缀和是用来快速实现区间加减的方法（O（N^2)–>O(N)），可分为单维和多维。其实现形式是通过数据离线将下面是两个单维前缀和的代码 #include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<cstring> using namespace std; int a[1000016]; int b[1000016];

#include <cstdlib> //头文件 srand(2333); //设置种子 long long x = (1LL * rand() << 15) + rand(); //取longlong类型的随机数 随机数范围是0~32767

目录1 题目描述1.1 输入描述1.2 输出描述1.3 示例12 题解2.1 完整代码 链接：https://ac.nowcoder.com/acm/contest/140/J?&headNav=www 题目描述 White Rabbit has a rectangular farmland of n*m. In each of the grid there is a kind of plant. The plant in the j-th column of the i-th row

目录1 题目描述1.1 输入描述1.2 输出描述1.3 示例12 题解 题目链接：https://ac.nowcoder.com/acm/contest/135/I?&headNav=acm 题目描述 Apojacsleam喜欢数组。 他现在有一个n个元素的数组a，而他要对a[L]-a[R]进行M次操作： 操作一：将a[L]-a[R]内的元素都加上P 操作二：将a[L]-a[R]内的元素都减去P 最后询问a[l]-a[r]内的元素之和 输入描述 输入共M+3行： 第一行两个数，n，M，意

题目链接

树状数组 重点是在树状的数组 大家都知道二叉树吧 叶子结点代表 A 数组 A[1]~A[8] 现在变形一下 现在定义每一列的顶端结点C[]数组 如下图 C[i]代表 子树的叶子结点的权值之和// 这里以求和举例 如图可以知道 C[1]=A[1]; C[2]=A[1]+A[2]; C[3]=A[3]; C[4]=A[1]+A[2]+A[3]+A[4]; C[5]=A[5]; C[6]=A[5]+A[6]; C[7]=A[7]; C[8]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+

在使用string类时，需要包含头文件 #include<string></string>。并且引入using std::string; using std::wstring;或using namespace std; 下面你就可以使用string/wstring了，它们两分别对应着char和wchar_t。 string和wstring的用法是一样的，以下只用string作介绍：

#include <cstdio> #include <string> #include <cstring> using namespace std; const int MAXN = 1e5 + 100; int main() { int temp; scanf("%d", &temp); getchar(); //如果在读入非字符串后要读入字符串，先吃回车 string str; str.resize(MAXN); //需要先开

目录1 大体题意1.1 输入1.2 输出2 思路2.1 博弈部分2.2 判断函数2.3 DFS函数2.4 状态压缩部分3 完整代码 题目传送门 大体题意 Alice 和 Bob 在玩一个游戏，Alice是先手，Bob是后手 给出一个数字序列，Alice和Bob每回合可以从中取出一个数 当序列变为不下降序列时，上一回合的玩家获胜 输入 第一行为 T[1<=T<=100] ，组数。 每组第一行为 N[2<=N<=15] ，序列长度。 后面是一个长度为 N 的序列 A ，其中

模板题：https://nanti.jisuanke.com/t/38232 可以求出一个序列中是否存在某个子序列 基本思想 定义一个next数组，用来存储在第i位后面出现的序列中的某一个元素的出现位置。 例如字符串abcdefg[字符串下标从一开始] 可以得到next的内容为： next[0]['a'] = 1; next[1]['a'] = -1; next[2]['a'] = -1; …… next[0]['b&

题目链接：https://vjudge.net/problem/HDU-4027 主要题意：区间开方，区间求和 #include <cstdio> #include <cmath> #include <algorithm> #include <cstring> using namespace std; const int N = 1e5 + 100; int n, m; int bl[N]; long long blo; long long sum

Dijkstra [ CF 20C – 模板 ] \Omicron(V \log V + E) struct disn_t { lli v; lli w; disn_t() { } disn_t(lli iv, lli iw) : v(iv), w(iw) { } friend bool operator <(const disn_t& a, const disn_t& b) { return a.w > b.w; } }; lli dis[maxn];

目录1 前言2 Floyd算法2.1 参数解释2.2 算法思想2.3 代码3 Dijkstra算法3.1 参数解释3.2 算法思想3.3 代码3.4 前向星版4 SPFA算法4.1 参数解释4.2 算法思想4.3 代码 前言 乍一看搜索跟这个一样都可以找出一个点到另一个点的最短距离，但是有些问题两者都可以解决，而另一些搜索就不能解决了，搜索有确定的方向一步一步走，而最短路是告诉你某两个点直接可以直接走，没有确定的方向。最短路问题，通俗的说就是就是给你n个点，m条边，然后找出某两个点之间的最短距离

目录1 定义2 Kruskal 算法2.1 伪代码2.2 完全代码3 Prim 算法3.1 伪代码3.2 完全代码 定义 连通图：任意两个顶点vi与vj都有路径相通。 强连通图：任意两个顶点vi与vj都有路径相通。 连通图：图的边具有一定的意义，每一条变都有对应着一个权。 生成树：一个连通图的生成树是指一个连通子图，它含有图中全部n个顶点。 最小生成树：建立生成树且所花费的权最少。 PS：如果生成树中再添加一条边，则必定成环。 最小生成树可以用kruskal（克鲁斯卡尔）算法或prim（普里姆）

前向星是一种特殊的边集数组,我们把边集数组中的每一条边按照起点从小到大排序,如果起点相同就按照终点从小到大排序, 并记录下以某个点为起点的所有边在数组中的起始位置和存储长度,那么前向星就构造好了.

基本解法 \Omicron(N^2) 譬如给定 2 个序列： 1 2 3 4 5 3 2 1 4 5 试求出最长的公共子序列。 显然长度是 3 ，包含 3 4 5 三个元素（不唯一） 我们可以用 dp[i][j] 来表示第一个串的前 i 位，第二个串的前 j 位的 LCS 的长度， 那么很容易想到状态转移方程： 如果当前的 A1[i]A1[i]A1[i] 和 A2[j]A2[j]A2[j] 相同（即是有新的公共元素）,那么 dp[i][j] = \max(dp[i][j], dp[i − 1][

可以将有序数列中的查找操作的时间复杂度优化到log N级别 数列为T获取查找部分的开头下标[start]和结束下标[end]以及要查找的数[x] 计算中间平分点下标[mid],即start和end的平均数

基础解法[O(N^2)] T为输入的序列,F为以第i个数结尾的最长上升子序列长度 可得到F[i]等于F[0 …… i – 1]中满足T[i] > T[0 …… i – 1]的数 例如序列T = {1, 5, 6, 4, 2, 9} 对应的F = {1, 2, 3, 2, 2, 4} F序列中最大的数即为最长上升子序列

1. 在关系数据库中，存放在数据库中的数据的逻辑结构以二维表为主。 2. ASCII 码的含义是美国信息交换标准代码。 3. 不存在一种算法，对任何一个程序及相应的输入数据，都可以判断是否会出现死循环，因而， 任何编译系统都不做死循环检验 。 4. ∧ = and丶∨ = or 丶 ¬ = 取反。

目录1 题目描述2 输入输出格式2.1 输入格式2.2 输出格式3 样例3.1 样例输入3.2 样例输出：4 题解 题目描述 辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。

用于快速查找某个点在哪个集合中，常用于有关图的题中，可查看洛谷 P3367 题。 #include <cstdio> #define _for(i, n) for(int i = 0; i < n; i++) using namespace std; const int MAXN = 1e6 + 100; int m, n, o, x, y; int map[MAXN]; int find(int u) { if(map[u] != u) map[u] = find(map[u

struct nodef { string name; int score; bool operator <(const nodef &n) const { return this -> score < n.score; } }; 这几句表示建立了一个名为nodef的结构体，其成员变量有name和score，重载了运算符<，表示当一个nodef与nodef做<运算时，第二个nodef作为参数n传入，并且运算的返回值为bool型，比较依据是score变量。

目录1 序列式容器1.1 向量[vector]1.2 列表[list]1.3 双端队列[deque]2 适配器容器2.1 栈[stack]2.2 队列[queue]2.3 优先队列[priority_queue]3 关联式容器3.1 集合[set]3.2 多重集合[multiset]3.3 映射[map]3.4 多重映射[multimap] 序列式容器 向量[vector] 列表[list] 双端队列[deque] 适配器容器 栈[stack] 队列[queue] 优先队列[priority_q

目录1 BFS – 广度优先遍历1.1 程序思路1.2 实现方法 – 存储方式为点对点1.3 程序实例 – 存储方式为点对点2 DFS – 深度优先遍历2.1 实现方法 – 存储方式为点对点2.2 程序实例 – 存储方式为点对点 BFS – 广度优先遍历 一种利用队列实现的搜索算法。简单来说，其搜索过程和 “湖面丢进一块石头激起层层涟漪” 类似。形象一点如下： 总的来说，就是先遍历离根节点近的，一层一层的。 程序

点对点 建立一个数组，用下标表示不同的点，用其内容表示这个点所连接的点。例如数组名为graph，然后可以用graph[0] = 1表示0点可以通向1点。 其中，如果一个点可以连向多个点，可以使用二维数组存储，例如graph[0][0] = 1和graph[0][1] = 2表示0点所连接的点有1点和2点。通常，这个二维数组的第二维不会被填满，所以，可以使用向量作为第二维，像下面一样： #include <vector> using namespace std; const int M

用于一些特殊的类进行遍历访问所用，类似于一个指针。 以下使用vector[向量]进行举例： 如何建立一个迭代器： list<int>::iterator it; 常用操作，迭代器进行遍历： for(it = l.begin(); it != l.end(); it++) 其中，l是一个list类型的变量，首先迭代器等于l的首地址然后自加到l的尾地址 PS：在大部分STL中， 尾地址是指向了一个空的元素，所以用！= 对迭代器进行访问： print(%d, *it); 这表示输出list

在这里，发布您有关C++的笔记共享给大家。