笃_定

每日算法打卡

2019 GDUT寒假集训解题报告(专题及训练赛)(14) 2019 GDUT寒假集训解题报告(排位赛)(15) 2020寒假集训(12) 2020牛客寒假算法基础集训营(2) codeforce比赛题(5) dfs(1) dp(1) 二分功能的简单实现(1) 常见数学结论(1) 未归档(1) 每日一题(77) 每日训练(1) 洛谷娱乐场(1) 算法学习过程中的心得(1) 网络赛(1) 随笔(12) 题解(1)

/ 注册

全部文章 / 每日算法打卡（共11篇）

POJ - 3162（树形dp + 二分 + 滑动窗口）

思路显然，可以通过树形dp求得树上每一点可以达到的最远距离参考博客得到d数组后，我们就可以发现这个区间长度符合二分性，所以我们可以二分区间长度在利用滑动窗口check合理性。注意求最大值，我一般用左闭右开区间。求最小值，我用的一般是左开右闭。树形dp模板(理解就可以认为是把子节点拎起来变成...

2019-11-14

0 595

马拉车算法（线性求回文串）

参考博客 AC代码（模板） #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int m...

2019-09-13

0 617

欧拉定理及扩展证明转载

链接引理 2 的证 ...

2019-09-02

0 578

Floyd算法求最小环

先放代码，再证明算法的正确性。证明我们给一个图做一个编号(1–n)，也就是表示n个点。对于每一个环（不包括自环），我们取这个环上点的最大编号k。那么也就说与k相邻的两个点的编号小与k，我们记为 i 和 j 。那么 i 与 j 之间的最短路经过点的编号显然小与 k ，不然 k 就要被赋予...

2019-08-21

0 492

二分图匹配专题总结

入门级必备知识点定理一：最小点覆盖：选取尽可能少的点，使得任意的一条边都有至少一个端点被选到。 |最小点覆盖| = |最大匹配数| 定理二：最大独立集：选取尽可能多的点，使得所取得点中，任意的两点均不相连。 |最大独立集| = |V| - |最大匹配数| 定理三：最小边覆盖: 选取...

2019-08-21

0 481

树的直径最简单证明及代码

转载博客补充说明之所以上图可以设一个点X，那是因为这是树的性质，任何两个点都可以通过某些路径使其连通模板题思路首先建一棵树，然后对树上的k个点求一个最大直径D，然后D/2上取整 AC代码 #include <bits/stdc++.h> using namespace s...

2019-08-04

0 478

并查集学习总结

新手入门必备并查集的定义：具有相同性质的集合可以拼成一个新的集合所谓的拼接就是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...

2019-06-14

0 448

单调栈

一、单调栈定义：单调栈，顾名思义就是说栈内的元素，按照某种方式排序下，必须是单调的。如果新入栈的元素破坏了单调性，就弹出栈内元素，知道满足单调性。它可以很方便地求出某个数的左边或者右边第一个比它大或者小的元素，而且总时间复杂度O(N)。　　向右看齐Look Up 模板题 AC代码 #i...

2019-06-05

0 515

单调队列

顾名思义单调队列这个名字就指明了它的性质——单调性说单调队列，那我们就先说说这个单调队列是个什么物种。单调队列从字面上看，无非就是有某种单调性的队列，没错，这就是所谓的单调队列。单调队列它分两种，一种是单调递增的，另外一种是单调递减的。在这搬出百度百科的解释：不断地向缓存数组里读入元素...

2019-05-30

0 570

KMP习题集

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

2019-05-01

0 591