- 博客(26)
- 收藏
- 关注
RSS订阅
原创 二分图最大独立集&最小路径点覆盖
一.二分图最大独立集定义：对于一张无向图G(V,E)G(V,E)G(V,E)，选出一个VVV的子集SSS，使得SSS中任意两点之间都没有边，且SSS是最大这样的子集。求解方法：二分图的最大独立集的点的数量=总点数N-最大匹配简单的证明：要使得独立集越大，那么删掉的点就要越少，同时话要保证删掉的点覆盖到所有边，所以删掉的因该是最小点覆盖。例题：Example1:[LGOJ]P3355 ...
2020-03-26 14:11:29
539
原创 dp复习---之01背包（第一章）
前言：最近学习了许多新的，高级的算法，但是------由于dp过菜，愤然决定开始dp复习qaq开始之前，关于动态规划：应用范围：动态规划方法一般用来求解最优化问题。这类问题可以有很多可行解，每个解都有一个值，我们希望找到具有最优值的解，我们称这样的解为问题的一个最优解，而不是最优解，因为可能有多个解都达到最优值。解决动态规划问题一般分为四步：1、定义一个状态，这是一个最优解的结构特征...
2020-03-25 22:37:14
235
原创 最大流学习笔记
最大流学习笔记Part1:最大流入门概念源点：所有流量都从源点出来；汇点：所有流量最终都流入汇点；最大流：对于一张图，从源点流向汇点的最大流量增广路：找到一条路径使得总流量增加残余网络：每搜一次相应建立“反悔机制”，即将路径上用掉的边建一条反向边，流量和原边相同，建完后的图称为残余网络结论定义w(x,y)为从x到y的流量限制，flow(x,y)表示实际从x到y的流量flow(...
2020-02-23 11:16:08
250
原创 USACO Bronze and Gold
Introduction：此次bronze silver正常难度，gold拉满，platinum不清楚，总体来说似乎有一点点毒瘤。。。主要出题人是传说中的Benjamin QiBronze T1有一说一，这题基本上读的懂题学过算法的人都基本能完成的标准签到题。题目大意就是给定7个数，分别为A,B,C,A+B,B+C,A+C,A+B+CA, B, C, A+B, B+C, A+C, A+B+CA,B,C,A+B,B+C,A+C,A+B+C, 根据这个数列求出A,B,CA,B,CA,B,C具体做法就
2020-12-29 16:09:52
432
原创 贪心算法
Foreward：Greed is human nature, curiosity is human motivation.贪婪是人类的本性，求知是人类的动力。今天要介绍的算法是贪心算法（Greedy），又名贪婪算法前面部分会比较基础易懂，后面有些部分会稍稍硬核所以 What’s the greedy algorithm?Definition:A greedy algorithm is a simple, intuitive algorithm that is used in optimi
2020-09-29 00:06:48
735
原创 poj1167 The Buses
算法：IDDFS思路筛出所有可行的线路；限制搜索深度depdepdep从111开始，搜索不同的路线组合尝试覆盖所有的公交车代码：#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int ...
2020-05-06 22:17:26
345
原创 迭代加深搜索（iddfs）
做法：从根节点开始dfsdfsdfs，用一个变量depdepdep限制dfsdfsdfs的深度，一旦达到depdepdep层，那么就看是否找到目标；如果在depdepdep层没有搜索到目标，那么就将深度的限制dep+1dep+1dep+1，继续从根节点重新开始dfsdfsdfs，如此反复直到找到目标，或者证明目标不存在；适用于的题目能够从题目中推断出答案的层次较浅；整个搜索树非常的深而且...
2020-05-04 15:46:57
610
原创 上下界网络流
I. DEFINITION上下界网络问题每条边不仅有一个容量上限C，还有容量下限b；像普通网络流一样，也要满足除源点汇点外的每一个点，inx=outxin_x=out_xinx=outxII. 无源点汇点上下界可行流（[LOJ]#115. 无源汇有上下界可行流）因为没有源点和汇点，那么每一个点都需要保证流量守恒；可行流的意思是可以分配出来，但不要求最大；Solution:...
2020-04-17 00:15:10
240
原创 [LGOJ]P3147 [USACO16OPEN]262144 P
这是一个有一点思维难度的题（至少我这么认为）首先我们定义f[i][j]f[i][j]f[i][j]表示以jjj为左端点合成出iii的右端点位置那么我们可以求出f[i−1][j]f[i-1][j]f[i−1][j]，也就是从jjj往后一直合并到哪个位置，可以最终合并出i−1i-1i−1，这个位置其实就是f[i−1][j]f[i-1][j]f[i−1][j]我们从这个位置继续向后，看看到哪个位置...
2020-04-15 23:01:16
226
原创 [LGOJ]P3033 [USACO11NOV]Cow Steeplechase G
算法标签：二分图最大独立集二分图各种类型题目数不胜数，这一题便是一个二分图的最大独立集问题前置芝士先简短介绍一下匈牙利算法其实匈牙利算法就是一个妥协的过程，即若一点AAA于另一点BBB相连，而该边已有匹配CCC，则尽可能的让CCC去寻求其他点进行匹配，然后让A,BA,BA,B完成匹配(不太地道的感觉）核心代码：inline bool dfs(int x){ for (int i=h...
2020-04-06 19:59:58
313
原创 分块
Problem Description很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。这让很多学生很反感。不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。 Input本题目包含多组测试，请处理到文件结束。在每个测试的第一行，有两个正整数 N 和 M ( 0<N<=200000,0<M<5000 )，分别代表学生的数目和操作的数目。学生ID编号分别从1编到N。第二行包含N个整数，代
2020-04-03 22:37:16
310
原创 二分图的最大团问题
定义&求法在一个无向图G中，选择一个最大点集VVV，使VVV中的点两两相等。最大团的点的数量=G′G'G′最大独立集其中，G′G'G′是无向图的补图，是指用跟GGG完全相同的点先构成一个完全图，然后删掉GGG中的边，剩下的图就是GGG的补图G′G'G′复杂度：非多项式的时间复杂度例题：1.POJ3692–Kindergarten代码：#include<iostrea...
2020-04-01 21:39:53
471
原创 [LGOJ]P4055 [JSOI2009]游戏
本题标签：博弈&二分图建议在做本题之前先看一看[LGOJ]P3386 【模板】二分图最大匹配[LGOJ]P4136 谁能赢呢？如果是大佬当我没说 好的进入正题题目大意：小AA和小YY玩游戏，在这个游戏中，同一个格子不能进入两次，且不能将棋子移动到某些格子中去。当玩家无法继续移动棋子时，游戏结束，最后一个移动棋子的玩家赢得了游戏。我们发现这题和[LGOJ]P4136 谁能赢呢是...
2020-04-01 20:39:54
362
1
原创 Ural1671 Anansi's Cobweb
题意：n个结点,m条边构成一个连通图， 删除t条边，输出没删除一条边， 图会被分成几块Solution反向并查集，同样不难~代码#include<bits/stdc++.h>using namespace std;const int maxn=100005;int n,m;int son[maxn][2],d[maxn],fa[maxn],a[maxn],sum[ma...
2020-03-26 22:03:32
194
原创 Ural1126 Magnetic Storms
一个双端队列裸题，和[LGOJ]窗口滑动几乎一模一样~代码：#include<bits/stdc++.h>using namespace std;const int maxn=1000005;int n,k,tot;int a[maxn],ans[maxn];struct node{ int val,pos;};deque <node> maxq;d...
2020-03-26 21:47:45
205
原创 Ural 1654 Cipher Message
Ural 1654 Cipher Message1654. Cipher MessageTime limit: 1.0 secondMemory limit: 64 MBMüller tried to catch Stierlitz red-handed many times, but always failed because Stierlitz could ever find som...
2020-03-26 20:53:14
227
原创 Ural1100 Final Standings
自此开始板刷Ural DataStructureUral1100:Find Standings(Data Structure)Old contest software uses bubble sort for generating final standings. But now, there are too many teams and that software works too sl...
2020-03-26 20:33:45
347
转载 BZOJ各题算法
1000:A+B1001:平面图最小割,转对偶图最短路1002:矩阵树定理,也可以通过推矩阵的递推关系得到递推式1003:最短路+DP1007:半平面交1008:组合数学,需要高精1010:斜率优化/四边形不等式推决策单调性1012:线段树1014:Splay维护字符串的Hash值1016:矩阵树定理,相同权值压联通块,对一个联通块用一次矩阵树定理计算方案数,累积答案 也可以DF...
2020-03-06 15:56:09
710
转载 POJ题目分类
OJ上的一些水题(可用来练手和增加自信)(poj3299,poj2159,poj2739,poj1083,poj2262,poj1503,poj3006,poj2255,poj3094)初期:一.基本算法:(1)枚举. (poj1753,poj2965)(2)贪心(poj1328,poj2109,poj2586)(3)递归和分治法.(4)递推.(5)构造法.(poj3295)(6...
2020-03-06 15:52:22
777
1
转载 HDU刷题攻略
基础题：1000、1001、1004、1005、1008、1012、1013、1014、1017、1019、1021、1028、1029、1032、1037、1040、1048、1056、1058、1061、1070、1076、1089、1090、1091、1092、1093、1094、1095、1096、1097、1098、1106、1108、1157、1163、1164、1170、1194、1...
2020-03-06 15:50:35
1669
1
转载 POJ题目难易总汇
POJ从简到难（按照AC数目排序）的列表如下，作为小弱的刷题顺序。大牛们可以看后面倒排的hard表，还有四道题没人拿到first blood.表格属性依次为：ID，Title, Ratio, AC, Submit1000 A+B Problem 0.55 188072 3389771004 Financial Management 0.41 58282 1403011003 Hangove...
2020-03-06 15:47:33
12697
原创 区间dp
Part1:总概区间dp顾名思义，就是解决一些区间内最优值的问题，通常的时间复杂度为n2n^2n2 或者 n3n^3n3大致思路：首先确定状态初始化长度为1（or 2,3…具体因题而异）的dp数组的值然后枚举区间长度，枚举区间的起始点，（有的题目还需要枚举断点） 由小区间转移到大区间。最后dp[1][n]dp[1][n]dp[1][n]往往就是答案。Part2:...
2020-03-06 15:44:13
222
转载 BZOJ刷题指南
BZOJ刷题指南巨水无比（4）：1214、3816:2B题；1000A+B；2462：输出10个1模拟/枚举/暴力（15）：4063傻子模拟；1968小学生暴力；1218前缀和暴力；3856读英文；4106直接算；1800暴力判断；2208暴力判断（要会邻接表）；1028枚举；1789&1830高能暴力；2241暴力；2120神奇的暴力；4145子集暴力；4029模拟处理；1086DF...
2020-03-06 15:12:02
1212
原创 dp刷题列表
刷dp的题qaq背包 bzoj2287（A）poj3093（A）Bzoj2748（A）*Bzoj2794（A）*bzoj1190（A）树形Bzoj4472（A）Bzoj1864（A）*Bzoj4033（A）*Bzoj3167（A）*Bzoj4446（A）状压Bzoj1087（A）Bzoj3195（A）Bzoj4145 *Bzoj1226...
2020-03-06 15:02:55
307
转载 dp难题
目录MemSQL Start[c]UP 3.0 - Round 1 C.Pie RulesAvito Cool Challenge 2018 C. Colorful Bricks(组合数学+dp)Codeforces Round #538 (Div. 2) D. Flood FillAtCoder Beginner Contest 118 D - Match MatchingCodef...
2020-03-06 11:41:28
639
原创 [LGOJ]P2754 【[CTSC1999]家园 / 星际转移问题】
算法：网络流（最大流）+并查集（判联通）思路：我们发现每一天飞船停靠的地方是不一样的，于是我们很自然佛瑞想到我们可以对每个空间站的每个时间点进行拆点（就相当于是一个动态图，每过一个时间点都可以建一个图）总结来说就是对于这种一个点（表面意义上的一个点，比如说一个位置）对应多种情况的（比如说随着时间的推移有着不同的状态，而且这种状态>2），我们考虑在类似于分层图上面跑网络流。接下来是建图...
2020-02-23 07:53:34
290
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人