简介 二分图又称作二部图，是图论中的一种特殊模型。 最大匹配数 = 最小点覆盖 = 总点数- 最大独立集 = 总点数- 最小路径点覆盖 比如下图： 二分图匹配的话我们可以用到——匈牙利算法，二分图判定的话我们可以直接用BFS，我看有些图是DFS也是一样的道理，就是判断邻边是否颜色相同（重点） 思路 1）我们首先定一个起点，将起点加入队列deque里面，每次bfs取出来顶端的 2）然后对其的所有邻边进行染色（染不同的色） i）情况一：相邻的边没有被染色 那么也就是还没有进入过队列，那么这个时候边染成不同的色，边将其压…
题目 给定一个有向图G和其中的两个结点s,t。询问这两个结点之间存在多少条经过了恰好k条边的道路。 注意：包括重边和自环！ 例如下图 从3到2，长度为5，我们有6条道路,分别是： 1. D,A,B,D,A 2. D,A,B,D,E 3. D,E,B,D,A 4. D,E,B,D,E 5. C,C,C,D,A 6. C,C,C,D,E 思路 这个题一开始我是没思路的，实际上就是一个板子题...只需要学过离散数学... 把邻接矩阵写出来为 然后对其进行K次幂计算（可用矩阵快速幂），得到： 因为起点s=3,终点t=2，所…
题意 给你一个字符串$s$，求$s$的最长回文子串 例如s="babad",ans=bab或者ans=aba都是答案 长度小于等于1000 思路 这个题完全可以暴力，但是为了突出区间DP，还是来考虑一下如何区间DP。 转移方程跟前一篇区间DP很像，f[i][j]需要从f[i+1][j-1]转移而来。 起始: f[i][i]=1;因为所有的单个也是子串，当然回文 f[i][i+1]=1;如果相邻的两个是相同的，这个也是回文 然后转移: f[i][j]=f[i+1][j-1];如果f[i+1][j-1]在区间[i+1,…
题目 题目链接：1471. 牛奶工厂 - AcWing题库 牛奶生意正红红火火！ 农夫约翰的牛奶加工厂内有 N 个加工站，编号为 1…N，以及 N−1 条通道，每条连接某两个加工站。（通道建设很昂贵，所以约翰选择使用了最小数量的通道，使得从每个加工站出发都可以到达所有其他加工站）。 为了创新和提升效率，约翰在每条通道上安装了传送带。 不幸的是，当他意识到传送带是单向的已经太晚了，现在每条通道只能沿着一个方向通行了！ 所以现在的情况不再是从每个加工站出发都能够到达其他加工站了。 然而，约翰认为事情可能还不算完全失败，…
【题目描述】 干了一整天的活，农夫约翰完全忘记了他把拖拉机落在田地中央了。 他的奶牛非常调皮，决定对约翰来场恶作剧。 她们在田地的不同地方放了 $N$ 捆干草，这样一来，约翰想要开走拖拉机就必须先移除一些干草捆。 拖拉机的位置以及 $N$ 捆干草的位置都是二维平面上的整数坐标点。 拖拉机的初始位置上没有干草捆。 当约翰驾驶拖拉机时，他只能沿平行于坐标轴的方向（北，南，东和西）移动拖拉机，并且拖拉机必须每次移动整数距离。 例如，驾驶拖拉机先向北移动 $2$ 单位长度，然后向东移动$3$单位长度。 拖拉机无法移动到干草…
题目链接 BJWC2011元素 题目描述 给出$n$对数字，每对第一个为$num$，每对第二个为$val$，求在若干个$num$异或和不为$0$的时候的$val$和的最大值。 题目思路 我们对每对数据的val进行排序，然后插入每个的$num$，如果能插入就加上此时的$val$，这运用了贪心的思想。 为什么呢？我一开始也提问，如果有$a,b,c,d,e$多组数据按照$val$依次递减，有没有可能不选$a$呢？（因为$a$的$num$是第一个插入的，必定选） 你认为$b$和$c$在一起搭配$val$的和可能比a的和大，…
题目链接 1738. 蹄球 - AcWing题库 题意 给出$n(1\leq n\leq 100)$头牛，每头牛有自己的位置$x_i(1\leq x_i\leq 1000)$。每头牛给两侧相邻的牛传球，规定是传给距离较小的那个，如果相同则选左边的，每个牛都需要传一次球，你可以一开始在若干个牛上放球，然后开始传，问开始需要放置多少个球使得所有牛都持球一次。 思路 有$n$个点，每个点传一次（这个是固定的），就是$n$条边。 $n$个点，$n$条边 —— 基环树 所以，这里面是若干个基环树，为什么说若干的，是因为有可能…
题目 POJ2955.Brackets We give the following inductive definition of a “regular brackets” sequence: the empty sequence is a regular brackets sequence, if $s$ is a regular brackets sequence, then (s) and [s] are regular brackets sequences, and if $a$ and $b$ are r…
大致题意 两种情况： 1）给出一个十进制数$x$，求$x$对应的的平衡三进制的数 2）给出一个平衡三进制的字符串$s$，求$s$对应的十进制数 tag 进制转换 模拟 解题思路 1）对于第一种情况： 例如将64转换成平衡三进制。 首先我们将64转化成标准三进制： $$ 64_{10}=02101_3 $$ 然后我们从最低位开始处理： 101 被跳过（因为在平衡三进制中允许 0 和 1）； 2 变成了 Z，它左边的数字加 1，得到 1Z101； 1 被跳过，得到 1Z101。 所以最后的结果是1Z101 2）对于第二…
