1.1
基本输入输出:LCY的 A+B 8题
(1089~1096)
1.2
C语言基础:基础入门题
(2104,2088,1076,2095,1061,1170,3361,1197)
1.3
排序,贪心:
1052 很恶心的一道贪心题
3177 我推荐的这题貌似卡了不少人,按照差值排序
(1236,1084,2093,2111,2187,1157)
2.1
简单数学题:GCD和素数生成占了很大一部分
1071 积分题
1717 这题比较麻烦
(1108,2138,2504,1215,1286,1060)
2.2
递归:Fibonacci,约瑟夫环,汉诺塔什么的,说是递归,for一下就好了,或者是找规律
1005 感觉找规律有问题,建议用矩阵
(1568,1443,1997,1222,1032,1013,1018)
2.3
大数,卡塔兰数:Java什么的最开心了
(1002,1063,1212,1130,1133,1131,1134,1267)
3.1
递推:推推题
2604 这题要用矩阵
(2041,2044,2046,2018,2050,2501,2563)
3.2
简单dp:数塔什么的
(1003,1159,1087,1058,1069,2084,1176,2571)
3.3
背包:各种背包
(2602,1114,1171,2844,1059,2955,1203,3466)
4.1
二分,三分:感觉这不能算是搜索
(2199,2899,1969,2298,2438,3400,1551,2178)
4.2
bfs:入门级的搜索
1175 连连看,dfs+减枝最快了
2531 以前想过这种模型,做steps才发现已经有人出过了,先扫一遍图,转化成单点情况
(1241,1242,1548,1372,1312,1495)
4.3
dfs:hh加了好多恶心的搜索进来,这关卡了不少人
1010 入门级的dfs,减枝很重要
1426 dlx水过~~
2553 我那邪恶的十层for打表,Matrix67博客有状态压缩版
2610 2611 这两题都在这一章,很少人过,不过也不是很难,dfs很快,我是bfs做的
(1016,3290,2821,2514)
5.1
并查集:并查集的题目还是很给力的
1598 枚举下界,判上界
2473 要删点的并查集,虚拟节点作为每个真实节点的父节点,对虚拟节点进行操作
(1829,1325,1558,3635,3047,3038)
5.2
字典树,拓扑排序,哈夫曼树:各种杂算法
1800 int就可以水过 - -|||
3518 比赛时hh用字典树过了这题,就加在这里了,卡了好多人,正解后缀数组
3231 一道很好的拓扑排序,每个立方体的每一个维度都拆成两个量来做,三个维度之间没有联系
(1075,1251,1285,1053,2527)
5.3
树状数组,RMQ,LCA:继续杂
2874 用Tarjan比较卡内存,两个图都用静态邻接表可以过,RMQ_LCA就很轻松了
3486 网上的二分方法是水过的
2688 abs(E-S)<=1000 这里用暴力的
(1166,1541,3584,2586,2838)
6.1
最小生成树:畅通工程
3367 也就这题比较给力了,并查集加一个变量记录有没有环
(1102,1162,1232,1233,1879,1301,3371)
6.2
最短路及相关:又被hh搞了几个恶心题在里面
2544 模板题,但是数据比较水,不能测模板来着
1142 题目意思还能再蛋疼一点吗
1596 求最大积,取log,因为都是0~1的直接乘也可以
3191 求次短路和次短路的条数,dijkstra
(2066,2722,1690,3339)
6.3
二分匹配:神奇的二分匹配,膜拜starfall大神全用网络流秒了
1151 最小路径覆盖
1507 很不错的一题,要求匹配方案
(1068,1150,1281,1498,1528/1962,3360)
7.1
简单计算几何:叉乘,多边形面积,凸包,重新翻出LCY课件来学了
2215 这题数据水
3661 这题加错地方了
(2108,1086,1115,1392,1147,2202)
7.2
简单数论:被小丽姐加了很多恶心题,后来看太BT了还删了几个
数学盲表示这节只贴题号
(2824,1787,1757,3579,3307,1299,3802,1573)
7.3
母函数,高斯消元:母函数用dp更容易,高斯消元表示不会,只贴题号
2451 打表,分情况讨论,然后再怎么搞,忘了
1028 卡塔兰数,应该是加错了
1027 - - 应该也是加错了
(1085,3571,1398,1709,3364)
8.1
队列,栈:STL给力的一节
1387 这题比较恶心
3328 这题很不错
1870 这个for一遍就好了
(1702,1022,1237,1873,1509)
8.2
简单博弈:简单的组合游戏,基本都不用求sg的
1907 anti-nim
(1846,1847,1848,1850,2149,2188,1851)
8.3
矩阵乘法:万能的矩阵
2254 这题描述很乱的说,不过很经典
2276 这题很神奇,竟然是矩阵
(1575,1757,2294,1588,2971,3519)
9.x 小结:这一章每个人都一样的,hh选的题目都很给力
9.1
2054 坑爹题,Java无压力
1789 简单的依赖背包模型
2159 二维背包
1401 双广,我的搜索专题里有题解
2818 并查集
3465 树状数组求逆序数对
2433 最短路,我暴力的
3524 矩阵
9.2
2052 水题
1871 贪心
1254 dfs+bfs
3350 递归
3234 并查集里面最烦的一题了
2642 二维树状数组
2833 最短路+dp
3483 矩阵,矩阵不太好推
9.3
2832 数学题
2604 矩阵,这题和前面重了
1429 搜索bfs
2782 搜索dfs,胆量题
1298 字典树,我写挫了,中间用一个dfs把字母树转为数字 树
2363 最短路,枚举上下界
3389 比较高级一点的博弈题
1496 把ab和cd分开打表,然后枚举一遍判另一边
10.1
最大团,稳定婚配,强连通,双连通:又是各种杂算法
1530 最大团模板题
1914 稳定婚配
3639 1827 1269 3072 强连通
2242 双连通
3594 Tarjan的活用,之前有该题的题解
10.2 2-sat,差分约束:继续各种杂算法
1824 3062 3622 直接看我的2-sat专题好了
2444 二分匹配+图染色
2666 差分约束,比较难
1534 3440 3592 差分约束
10.3 网络流:一切皆网络流
1532 入门题
3313 很烦的一题,解法很多
1269 经典模型
3035 转化为对偶图后求最短路
3046 最小割模型
3251 流过之后从源点和汇点分别染色判割边
1733 逐步加层做网络流,EK比较快
3061 费用流
11.1 线段树:这一节的线段树还是比较简单的,可以去看hh的线段树专题
1199 区间染色,离散化时加点离散
1543 离散+暴力,不会有人去写二维线段树吧
1828 求矩形并周长
1698 区间更新区间求和
1754 单点更新区间求最值
2795 忘了
1823 二维线段树
3458 被晓宇哥DP过了,线段树不会
11.2 线段树,后缀数组:较难的线段树,不过跟现在比赛中的线段树比起来简单多了,后缀数组都是论文题了
1403 简单后缀数组
2459 比较烦的一道
2890 离散化,论文里说用二分判可行,貌似不用也行,但要修改high函数
2665 划分树
2871 很麻烦的线段树了
3016 线段树+dp
1255 求矩形交
3333 离线+线段树/树状数组
11.3 KMP,AC自动机:KMP不知道为什么放在这么后面,还有几个AC自动机,看hh的AC自动机专题
1711 KMP入门题,或者RK
1358 fail(或叫next)数组活用
3336 同上
3374 最小表示
2222 AC自动机入门题
2825 AC自动机+状态压缩dp
3341 AC自动机+dp
3247 AC自动机+状态压缩dp+最短路,只取关键点的做法DBL
12.1
进阶搜索:本来以为搜索做的很多了,结果发现贴了两道之后就囧了
2757 简单的bfs
2128 要hash全图的bfs
3681 很牛逼的一题,先bfs出任意两个特殊点之间的最短路,然后只取几个特殊点状态压缩dp/搜索
1226 比较简单的bfs
1043 传说中的八数码
3085 双广,我的搜索专题有题解
3533 看似很麻烦的一道题
2471 bfs,题目太抽象了
12.2
A*,IDA*,预处理搜索
2691 1813 1430 1667 2234 我的搜索专题里都有题解
1664 如果知道两个数可以生成任意数的倍数就好做了,枚举1个数字的所有情况,如果没有再去枚举两个数字的所有情况,之后取其中字典序最小值
1067 胆量题,敢做就敢A,要hash全图
2259 随机水过了
12.3
DLX,进阶博弈:两道巨恶心的dlx都在,然后是博弈
2295 dlx重复覆盖
2518 这道恶心题居然都在
3156 很牛逼的一道dlx,和2295不同的,要枚举所有可能点,注意减枝
3498 dlx重复覆盖
3660 敌对搜索?
1809 博弈
3514 还没做
3197 Game
13 动归
14 几何
15 神题
16 综合