先放代码，再证明算法的正确性。 证明 我们给一个图做一个编号(1–n)，也就是表示n个点。 对于每一个环（不包括自环），我们取这个环上点的最大编号k。 那么也就说与k相邻的两个点的编号小与k，我们记为 i 和 j 。 那么 i 与 j 之间的最短路经过点的编号显然小与 k ，不然 k 就要被赋予这个更大的值 那么我们跑 k-1 次循环就可以找到 i 与 j 的最短路。 我们假设最短路长度是dis(i, j)。那么这个环长度就是dis(i,j) + val(i,k) + val(k,j)      v   a   l   (   i   ,   j   )   表   示   i   与   j...

入门级 必备知识点 定理一： 最小点覆盖：选取尽可能少的点，使得任意的一条边都有至少一个端点被选到。 |最小点覆盖| = |最大匹配数| 定理二： 最大独立集：选取尽可能多的点，使得所取得点中，任意的两点均不相连。 |最大独立集| = |V| - |最大匹配数| 定理三： 最小边覆盖: 选取最少边的让所有点都被覆盖 |最小边覆盖| = |V| - |最大匹配数| 最小路径覆盖：对于一个 DAG（有向无环图），选取最少条路径，使得每个顶点属于且仅属于一条路径。路径长可以为 0（即单个点）。 |最小路径覆盖| = |顶点数| - |最大匹配数| 具体最小路径覆盖分为路径可相交和路径不可相交，具体可...

转载博客  补充说明 之所以上图可以设一个点X，那是因为这是树的性质，任何两个点都可以通过某些路径使其连通 模板题  思路 首先建一棵树，然后对树上的k个点求一个最大直径D，然后D/2上取整 AC代码 #include <bits/stdc++.h> using namespace std; const int maxn=1e5+5; vector<int>tree[maxn]; struct node{ int val; int index; node(){ val=0; } }; int start,top; bool flag[maxn]; bool vis[ma...

题目链接  思路      字   典   树   的   模   板   题   ，   但   要   注   意   读   入   的   问   题   。   对   于   s   t   r   i   n   g   类   型   的   数   据   用   g   e   t   l   i   n   e   (   c   i   n   ,   w   o   r   d   )   。   而   对   于   c   h   a   r   [   ]   型   则    字典树的模板题，但要注意读入的问题。对于string类型的数据用getline(c...

题目链接 思路      由   于   数   据   很   大   ，   所   以   采   用   字   符   串   存   取   。   用   s   o   r   t   来   跑   出   最   大   值    由于数据很大，所以采用字符串存取。用sort来跑出最大值   由于数据很大，所以采用字符串存取。用sort来跑出最大值 AC #include <bits/stdc++.h> using namespace std; typedef long long ll; struct Node{ int loc; char s[105]; }n...

题目链接   Solution 1   手动操作具体可以参照下面的代码 AC代码 #include <bits/stdc++.h> using namespace std; const int maxn=1e6+5; char a[maxn],b[maxn]; int main(){ scanf("%s%s",a,b); int nb=strlen(b),na=strlen(a),bnum=0,ans=0; int p1=0,p2=nb-1,temp=0; for(int i=1;i<nb;i++) if(b[i-1]!=b[i]) bnum++; ///...

新手入门必备 并查集的定义：具有相同性质的集合可以拼成一个新的集合 所谓的拼接就是join（connect）函数 void join(int x,int y){ int x=find_pre(x); int y=find_pre(y); if(x==y) return ; pre[x]=y; }  find_pre函数是用来找一个集合的代表元 未优化前的find_pre(大概是O（n）) int find_pre(int x){ while(x!=pre[x]) x=pre[x]; return x; }  优化后的find_pre(大概是O（log(n)）） int find_pre(int...

一、单调栈 定义： 单调栈，顾名思义就是说栈内的元素，按照某种方式排序下，必须是单调的。如果新入栈的元素破坏了单调性，就弹出栈内元素，知道满足单调性。它可以很方便地求出某个数的左边或者右边第一个比它大或者小的元素，而且总时间复杂度O(N)。    向右看齐Look Up 模板题 AC代码 #include <bits/stdc++.h> using namespace std; const int maxn=1e6+5; int a[maxn],sta[maxn],query[maxn]; int main(){ int n; scanf("%d",&n...

顾名思义 单调队列这个名字就指明了它的性质——单调性 说单调队列，那我们就先说说这个单调队列是个什么物种。单调队列从字面上看，无非就是有某种单调性的队列，没错，这就是所谓的单调队列。 单调队列它分两种，一种是单调递增的，另外一种是单调递减的。 在这搬出百度百科的解释：不断地向缓存数组里读入元素，也不时地去掉最老的元素，不定期的询问当前缓存数组里的最小的元素。 用单调队列来解决问题，一般都是需要得到当前的某个范围内的最小值或最大值。 先摆出一个滑动窗口的模板供大家学习与参考，如有错误，望读者批评指正 typedef long long ll; const int maxn=; int a[max...

添加链接描述模板题 剪花布条 AC代码 #include <bits/stdc++.h> using namespace std; void getNext(char p[],int Next[]){ Next[0]=-1; int i=0,j=-1; int n=strlen(p); while(i<n){ if(j==-1||p[i]==p[j]){ i++; j++; Next[i]=j; } else j=Next[j]; } } int KMP(char t[],char p[],int Next[]){ int i=0,j=0; int n1=strlen(t);...

文章详解 具体操作：（以cb为例）  （1）新建一个项目然后输入源程序 （2） 然后找到源程序所在项目的路径然后建立一个A.in （3）在cb上编译运行后 （4） 自动生成一个out文件，然后里面就是程序运行的结果。 之所以使用freopen的原因是对于那些多数据的输入可以直接放到in文件里面，然后while()一个一个读取，结果存在文件里面便于操作

数的划分       转   载   洛   谷   d   f   s   暴   力   模   拟   过   程    转载洛谷dfs暴力模拟过程   转载洛谷dfs暴力模拟过程 #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int n,k,cnt=0; void dfs(int last,int sum,int cp){ if(cp==k){ if(sum==n) {cnt++;} re...

台阶问题  分析      第   一   眼   看   到   这   题   的   时   候   就   直   接   想   用   D   f   s   模   拟   走   路   的   过   程   ，   可   是   发   现   n   数   据   范   围   为   1   e   5   ，   就   计   算   一   下   复   杂   度   。   接   近   O   （    2   n    ）    第一眼看到这题的时候就直接想用Dfs模拟走路的过程，可是发现n数据范围为1e5，就计算一下复杂度。接近O（2^n）  ...

dp+二分（最长不降子序列问题）  题意 题目就是要你求出最长非递减的最长子序列长度 白书（挑战程序设计）中提供两种算法     O   (    n   2    )   和   O   （   n   l   o   g   n   ）    O(n^2)和O（nlogn）   O(n2)和O（nlogn）解决该问题 第一种算法用到的知识是dp      d   p   [   i   ]   表   示   以   a   [   i   ]   结   尾   的   最   长   子   序   列   ，   更   新   方   式   是   d   p   [   j  ...