复习标题汇总,算是一份学习安排

1.模拟:

复习

联赛以前的搞搞(其实是无意间分类)

luogu p1563 玩具谜题   codevs等差数列  cogs  求和题材 积木大赛   扫雷游戏

基础算法:

文件类型和文书操作      高精度总括     数据排序     递推算法   
递归算法   搜索与纪念算法    贪心算法   分治算法   广度优先搜索   
动态规划

博弈论 poj3537 poj1704 hdu5996
多个插头 HDU1693 Eat the Trees COGS1283. [HNOI2004] 邮递员
kdtree板子1941: [Sdoi2010]Hide and Seek
旋转卡壳 pj2187
凸包 cogs896 bzoj2829 信用卡凸包
莫比乌斯反演基础 bzoj 4173 zhao gui lv bzoj 3529 mobiwus bzoj 4407
mobiwus 
bzoj 2818 mobiwus bzoj 2820 mobiwus bzoj 2005 mobiwus bzoj 2301
mobiwus
法法桶 uoj 34 fft cogs 1473 fft bzoj 3527 fft
bzoj 4721 [Noip2016]蚯蚓 神奇队列
bzoj 4010 [HNOI2015]小菜制作 神奇拓扑序
bzoj 2654 tree 神奇二分+最小生成树
bzoj 3033 太鼓达人 假装是欧拉图的大爆搜
bzoj 1104 [POI2007]洪水pow 并查集(Tarjan也可以)
bzoj 3198 [Sdoi2013]spring hash+dp
bzoj 3233 [Ahoi2013]找硬币 神奇大爆搜可过(正解dp还没看)
bzoj 3712 [PA2014]Fiolki 神奇重构树
bzoj 2339 [HNOI2011]卡农 神奇组合计数
bzoj 2111 [ZJOI2010]Perm 排列计数 普通组合计数+以后还不知底不互质
bzoj 4000 [TJOI2015]棋盘 一般般的矩阵乘法优化一般般的状压
liu_runda神题 便
NOIP 华容道 spfa+爆搜 
bzoj 1089 [SCOI2003]严格n元树 组合数dp+高精(屎题)
bzoj 1876 [SDOI2009]SuperGCD GCD+高精/更相减损+高精
codeforces 526 F 神奇二分
bzoj 4033: [HAOI2015]树上染色
hzoj 光 巧妙模拟
在行剖分
mex 莫队+分块
[Usaco2009 Feb]Revamping Trails 道路升高 二维spfa
[Sdoi2013]淘金 数位dp
PA2010 Riddle 2sat
[Jsoi2015]送礼物 单调队列的神奇用法
[JSOI2008]最小生成树计数 Kruskal类
Tree之最小方差树 枚举(乱搞) 
[Sdoi2016]齿轮 dfs
[Sdoi2013]直径 树dp
queue2 递推
[Tjoi2013]最长上涨子连串 数据结构傻题(树状数组的神级应用)
[Jsoi2015]非诚勿扰 瞎搞
[Scoi2015]小凸玩密室 树dp
[LNOI2014]LCA
启发式合并(就本身这么打)/树链刨分(分析性质+离线)/主席树(那几个还不会)
[Ceoi2010]A huge tower 傻dp
奇数国 神奇线段树(状态压缩)+欧拉
Contra 矩乘
不相同 神奇状态压缩dp(爆搜水过)
[Shoi2013]最佳跳马 矩乘
[Shoi2013]发微博 瞎搞
Crazy Rabbit 神TM结论(并不会证,只可以感性掌握,考试也只能猜了)
[Heoi2013]Alo 可持久化01Trie
翻硬币 神奇位运算推导
[SCOI2008]着色方案 搜索
[Hnoi2010]Planar 2sat
[Ahoi2008]Meet 热切集合 lca
[Haoi2016]放棋子 错排(公式还不会…..)
[Tjoi 2013]松鼠聚会
作者打大模拟,正解是切比雪夫距离与曼哈顿距离的转会(以后还不会)
[ZJOI2008]骑兵 环套树dp(小编打双层dp,有一种是拆环成树)
[Sdoi2010]高丽参部落 神奇递推,小编打的组合数递推
[HNOI2007]梦幻岛宝珠 神奇背包
会合计数 组合数递推
[USACO2008 Nov]toy 玩具 三分+贪心
[Apio2008]免费道路(bzoj3624) Kruskal类
[BeiJing2011]元素 线性基
阿狸和桃子的2二十十一日游 贪心
[JSOI2007]麻将 贪心
[ZJOI2008]杀蚂蚁antbuster 模拟
[Sdoi2010]猪国杀 模拟
[Ahoi2008]Pair 配对 正解dp,瞎贪A掉
[二零零六国家集训队]最大收入 神TM匈牙利(Magyarország)
[HAOI2008]降低的圆盘 总括几何+cmath
[Ahoi2014]宅男陈设 三分
[Usaco2010 Nov]Cow Photographs 小模拟
Spoj4060 game with probability Problem 颓式子+收敛性(用矩乘)
[POI2004]PTucsonZ 枚举子集+状态压缩
[Poi2011]Dynamite 贪心
[Zjoi2015]地震后的幻想乡 神奇状压(压TM图)(当时做死我了要)
[Scoi2010]打闹 被迫匈牙利(Hungary)
[Usaco2004 Open]Cube Stacking 方块游戏 带权并查集
列车 神奇并查集
[Usaco2013 Open]Photo 神奇单调队列优化dp
学习路线 忽视无关因素+矩乘
[NOIP2015]运输布署 树链刨分

拼数  cover  被窃的项链  小A的糖果   P1583 魔法照片  模仿只会猜题意  1806. [NOIP2014]有线网路发射器选址  luogu P1307 数字反转  luogu P1422 小玉家的电费   luogu P1217 [USACO1.5]回文质数 Prime
Palindromes
  3D模型  luogu 金币

数据结构:

栈      队列     树     图论算法

(复习看看书,一本通过五次,不懂多牵挂,算法搜博客,瞻仰神牛思路清楚)

(没标题号的绝一大半都能在bzoj上找到)

cogs 求和

长远掌握(参考了神牛九野的算法入门安顿)

**BFS+DFS 搜索   
并查集、最小生成树、递推、同余**(注意知识点:树的概念、图的定义(格外重大,请自行百度))

背包、矩阵快捷幂、素数、二分查找

2.最短路:

专题资料推荐:背包九讲,素数表的三种打发(付出一种,另一种常有的是prime[i]

true表示i为素数)矩阵迅速幂模版

优先队列(最小堆)、状态压缩、单源最短路

最短路指出先读书spfa算法

 

 1     int dis[N];//N个点 此处给出邻接表写法(若不熟悉可以下拉查看邻接表的示意图)  
 2     int spfa(int start, int end, int n){//最短路的起点,终点,图的下标[1,n]  
 3         for(int i = 1; i <= n; i++)dis[i] = 100000000;  
 4         dis[start] = 0;  
 5         queue<int>q; q.push(start);   
 6         while(!q.empty()){  
 7             int u = q.front(); q.pop();  
 8             for(int i = head[u]; i!=-1; i = edge[i].next){  
 9                 int v = edge[i].to;        //遍历 以u为起点的边 的终点  
10                 if(dis[v] > dis[u]+edge[i].dis)  {  
11                     dis[v] = dis[u]+edge[i].dis;  
12                     q.push(v);  
13                 }  
14             }  
15         }  
16         return dis[end];  
17     }  

壹 、注意对于最短路中存在负环判定:对于spfa算法,当某些点入队列(入队列的含义就是该点被松弛了(更新))次数>n次,就认证该点在负环上(可以简单说爱他美个点至多被更新n次(n为图中的顶点数))。

② 、优先队列:类似于堆,出队的因素不是在队尾的要素,而是队列中幽微的成分(大家有时候可以在队列中蕴藏结构体成分,只需重载运算符即可)。

实例:

1 struct node{
2     int x, y;
3     bool operator<(const node&a) const
4     { if(a.x==x) return a.y<y;  return a.x<x; } //根据x,y值比较node结构体的大小
5 };

三 、状态压缩:当某个状态唯有true or
false,时我们可以用2个整数来表示那几个状态。

示例:

有3块差其余蛋糕编号壹 、二 、3, 被老鼠啃过, 那么蛋糕唯有2种情景,
大家用0表示从未被啃过, 1代表被啃过。

可想而知大家可以收获全体情形:000、00壹 、0拾、01一 、100、10一 、1拾、111.

而上述二进制数对应的整数为 [0, 2^3) . (如二进制011 = 整数3意味
第三 、3块蛋糕被啃过,第贰块蛋糕没有被啃过)

大家得以用 for(int i = 0; i < (1<<3); i++)
来遍历全数的情事。

把多个东西的状态利用二进制含义压缩为三个平头称为状态压缩。

④ 、利用优先队列优化最短路时, 大家得以先出队距离起点如今的点,
则若出队的为极端显著大家曾经收获了一条最短路了。

树的遍历、容易博弈、欧拉路径、Floyd算法

对于图的仓储(邻接表、邻接矩阵)

简述下邻接表:

 1 struct Edge{  
 2     int to, next;  
 3 }edge[MAXN];//MAXN为边数  
 4 int head[N], edgenum;//N为点数  
 5 void addedge(int u, int v){  
 6     Edge E={v,head[u]};  
 7     edge[edgenum] = E;  
 8     head[u] = edgenum++;  
 9 }  
10 void init(){ memset(head, -1, sizeof(head)); edgenum = 0; }//注意表头的初始化 

网络流、互连网流求最小割、最小割定理

一 、简述一下纤维割:对于一个图,我们要删减一些边使得 1点与n点不联网。

删边的花费为边权值,则总边权和就是 三个管用解的割边集的权值

当资费最小时,我们称为最小割。

小小割 = 最大流 做1个简易表明:

我们要找八个 1点和n点的小不点儿割 边权和(那么些答案是 1点到n点的最大流)

率先我们把① 、n作为起源和汇点,跑一遍网络流

那么对于某条流, 鲜明表明了那条流是 连接着1点和n点的一条路线。

那条途径大家务必去掉,当然删除那条路径上的随机一条边就可以认为去掉了那条路子。

而那条路径上的任性边 边内的流量就是 那条路子的流量

据此为了拿到删除那条路线的微乎其微开支,大家挑选这条路子上满流的边(那样不会有结余的费用爆发)

那时删边的开支=边权值=流量

对此每条连接着1-n的门径都这么操作, 就能得到:最大流 = 最小割

(注意上述1点和n点只是举例,能够轮换为随意两点照旧私行五个点集,而非具体的定义)

补充:对于上述所说的某条路子:路径上的边必然有一条可能多条是满流的。

咱俩得以用反证法:如果全体边都以不满流的,此时大家还足以再在那条边上增添流量直到某条边满流为止。

二 、互联网流的建图是非常紧要。

1)可以透过编造五个源点(汇点)来界定流入(流出)整个网络的流量

比如说:当起源为1时,我们用 0 作为起点 并建一条 0->1
边权为C的边,那样就能限制流入流量为C。

2)当有广大个源点时,大家也足以建二个虚拟起源来三番五次全部起点,这样就只有贰个起点了。

3)对于某些点 i
,大家恐怕只同意流过C流量,则此时我们把i点拆开(就是用多个点来表示i点(比如
i 和 i+N )) 然后 i 与 i+N 中间建一条边权为C的边 来对i点限流。

③ 、可先学习白书的递归版dinic,然后手敲过题。

白书模版请点笔者。←边板子的水题请点本人

各项互联网流模板:http://www.notonlysuccess.com/index.php/algorithm-of-network/

全然二叉树、线段树、线段树的Lazy操作

线段树资料:http://blog.csdn.net/metalseed/article/details/8039326

线段树的应用-04国家队杂文

胡浩线段树题集及代码方式:http://www.notonlysuccess.com/index.php/segment-tree-complete/

一个木有模板的专题,请多缜密翻阅质感(然后刷题)

线段树学习:

0、04年国家队散文、白书

壹 、提出学习胡浩版的线条树(即1个节点用一个结构体来表示)

1     struct node{  
2         int l, r;  
3         int val;  
4     }tree[N*4];  

这么简单精通线段树的结构(借使不熟知线段树的构造,可以在vs2011以上版本的编译器的单步调试中查阅tree那个变量,会比较清楚地看到线段树的酷炫结构,那是赞助精通的主要一步)

本博客的线条树也是hh牛那里学习的,较简单形成模版化收缩失误。

② 、线段树的另三个根本功用:延迟操作

诸如大家对五个数组a有2种操作

  一、区间[l,r] 每个数+ val

 ② 、单点求值

1 struct node{  
2     int l, r;  
3     int sum, lazy;  
4 }tree[N*4]; 

那么实际上只要大家修改了一千次[1,n]区间,而在第九0二遍才求某点的值,那么我们不用急着把各种点更新了

而是在[1,n]那个间隔做二个标志,表示这一体区间的数都被添加了二个值,那么前1000次操作都只须要对lazy修改即可。

等精通时再把那些lazy标记传到下边的区间去。

那种操作就叫延迟操作
③ 、线段树的推移操作,提议写成当下距离最新,即当这个区间有lazy的标志时,那个距离也要保持最新

2-SAT、不难博弈

(注意知识点:对STL的set集合学习)

set用法简介:wenku.baidu.com/view/b71a8b524431b90d6c85c746.html

2-sat的简要在↓前边,一般可以用dfs或许tarjan缩点判断,那里目前推荐dfs版本,较不难驾驭且编程复杂度不会太高。

2-sat
白书模版

字典树、KMP

字典树:一个至关主要特点就是本省存,
三个前缀相同的字符串只要求记录三次(话中有话:对于某节点的全体子树,他们的字符串都是有集体前缀的)

字典树资料:百度完善

字典树模版:blog.csdn.net/acmmmm/article/details/12250267

KMP个人简介(纯粹广告):blog.csdn.net/acmmmm/article/details/9863495

KMP其余资料:blog.csdn.net/yaochunnian/article/details/7059486

KMP的复杂度是线性的,即O(n+m);

有关KMP的二个版本:普通KMP的失配数组 next[0] = 0,
滑步函数优化的失配数组 next[0] = -1;

此处推荐先读书普通版本KMP,滑步函数听别人说速度稍快,但失去了KMP本人的意思,且一般KMP的快慢对于竞技一度足足快了。

有向图的强连通分量、缩点

 强连通是对有向图求环的算法,tarjan(相当于dfs)

主假如环具有个别天性,因而把围观为一个点,对图中环进行缩点,并给图再度标号

模版性较强。

强连通算法可参看白书319页 或
这里

更高端的在此间:www.byvoid.com/blog/scc-tarjan/

强连通模版

LANDMQ难题、LCA转途达MQ、树状数组

汉兰达MQ难题:区间求最值,可以用线段树等消除; 

LCA:近年来公共祖先,可以用离线的tarjan,在线的LCA转LacrosseMQ(预处理O(nlogn),询问O(1),LCA倍增法(预处理O(nlogn),询问O(logn))

模版变动不大,主要多做题。

树状数组:对于二个数组,可以间隔求和,辅助单点更新,复杂度均为O(logn);

拓展:树状数组的区间操作

LCA题集 

LCA倍增法模版

LCA转ENVISIONMQ解法示意

数位dp、单调队列、滚动数组、成本流    
 差分约束(拓展(引用自点击打开链接))

乘法逆元:

(a / b)%mod  =  a * (b^(mod-2))

b^(mod-2)套个飞跃幂,复杂度是log(mod), 基本是一个常数。

·无向图的割顶和桥、树的主心骨       ·无向图的双连通分量      
·无向图的双连通分量      ·拓展欧几Reade、AC自动机

·二分匹配、基数排序

二分匹配的图论相关:(1)(2

 二分匹配的概念:(1

·后缀数组       ·次小生成树、区间dp

 (1):Dijkstra  luogu 大陆争霸  luogu1576很小开销

当520走到此处时,再往前看,看在此之前的题和此前的自身,一定会惊讶本人走了这么远~

 

 

 

 (2):floyd     luogu 电车    牛大赛    最短路  希望小学    67. [NOI1997] 最优乘车  176. [USACO Feb07] 奶牛聚会 cogs 找最佳通路 

  (3):spfa    通向奥格瑞玛的征途    luogu 玛丽卡   最短路计数(spfa+dfs)    卫生院设置   P1772 [ZJOI2006]物流运输(spfa+dp)  libreoj最短路  tyvj
丛林探险
  P2296 寻找道路  cogs 2. 旅行安顿

  (4):topsoart  cogs 牛跑步  密林大礼包 

(5):最小环:新闻传送  vijos 观光旅游 最小环fl
呆详看

(6):k短路:牛跑步
A*k短路算法
   GF打dota

3.Dp

   luogu 乘积最大  过河(wd)  没有上边的舞会   贪得无厌的菜农  最大星型子矩(WD

  luogu  找GF    luogu1659养猪  P2066 机器分配  P2196 挖地雷  

  luogu 组合数难点   luogu P2285
[HNOI2004]打鼹鼠
  P1057
传球游戏

luogu  传纸条    luogu P1049 装箱难题

4.搜索:

 Bfs:luogu  位图  codevs 红与黑  codevs 游乐园的迷宫  codevs营救(wa球细胞数量   luogu 填涂颜色 血色先锋队 01迷宫  吸引那头牛  cogs世界树 (wa)
   马的遍历  传染病控制(wa)  codevs 1569 最佳绿草  单词方阵  油田

Dfs :  luogu 消息传送、   单词接龙   选数   最短路计数(spfa+dfs)  海战  luogu
1605 迷宫  [HAOI2016]食物链
记忆化
  cogs5.
P服务点设置(dfs+flyod)

P1434 滑雪   

5.分治:

 luogu 砍树  codevs 电话网络(二分答案+spfa) 最接近神的人_NOI导刊2010提高(02)逆序对  跳石头(二分答案)  想不到的函数  

6.并查集(图论) codevs 数轴染色  luogu星球大战 luogu 口袋的天幕  luogu 买礼物   兽径管理   151. [USACO Dec07] 建造路径 cogs 通讯线路  亲戚

6.贪心: 排队接水  tyvj回想品分组  tyvj羽毛  三角形牧场(贪心(WD)/dp)天王游戏(高精+贪心)  

7.数学:删掉的边  codevs 落单的数  总结数字  笨小猴(素筛)

8.线段树:线段树1  线段树2  线段树3  线段树4

10.树状数组 :树状数组1  树状数组2

11.队列,堆,栈,链表:

  luogu 队列安顿  小组队列  奶牛队列  luogu P3378 【模板】堆  P2564 [SCOI2009]生日礼物

12.莫队: luogu P2709 小B的询问  luogu cogs 421. HH的项链  cogs luogu 1901. [国家集训队二〇一三]数颜色(待修改莫队)  1619. [HEOI2012]采花(TLE3)(树状数组)

13.RMQ : poj Balanced Lineup
RMQ

 

405461326387

相关文章