7、8月刷题总结

准备开学了囧，7、8月刷题记录，以后好来复习，并且还要好好总结！

数据结构：

• splay：
  • 【BZOJ】1503: [NOI2004]郁闷的出纳员（Splay）
  • 【BZOJ】1269: [AHOI2006]文本编辑器editor（Splay）
  • 【BZOJ】1507: [NOI2003]Editor（Splay）
• treap：
  • 【BZOJ】1862: [Zjoi2006]GameZ游戏排名系统 & 1056: [HAOI2008]排名系统（treap+非常小心）
  • 【BZOJ】3224: Tyvj 1728 普通平衡树（某不科学的oj）
• link-cut tree：
  • 动态树之link-cut tree
  • 【BZOJ】2049: [Sdoi2008]Cave 洞穴勘测（lct/并查集）
  • 【BZOJ】1036: [ZJOI2008]树的统计Count（lct/树链剖分）
  • 【BZOJ】2002: [Hnoi2010]Bounce 弹飞绵羊（lct）
• 树链剖分：
  • 【SPOJ】375. Query on a tree（树链剖分）
  • 动态树之（雾）树链剖分
• 树套树：
  • 【BZOJ】1901: Zju2112 Dynamic Rankings（区间第k小+树状数组套可持久化线段树（主席树））
  • 【BZOJ】3196: Tyvj 1730 二逼平衡树（区间第k小+树套树）
  • 【BZOJ】1901: Zju2112 Dynamic Rankings（区间第k小+树套树）
• 主席树：
  • 【SPOJ】10628. Count on a tree（lca+主席树+dfs序）
  • 【BZOJ】1146: [CTSC2008]网络管理Network（树链剖分+线段树套平衡树+二分 / dfs序+树状数组+主席树）
  • 【POJ】2104 K-th Number（区间k大+主席树）
  • 主席树
• 树状数组：
  • 【BZOJ】1878: [SDOI2009]HH的项链（树状数组）
  • 【BZOJ】1012: [JSOI2008]最大数maxnumber（树状数组+区间最值）
• 线段树：
  • 【POJ】2828 Buy Tickets（线段树+特殊的技巧/splay）
  • 【wikioi】2216 行星序列（线段树）
  • 【wikioi】1690 开关灯（线段树）
  • 【wikioi】1191 数轴染色（线段树+水题）
  • 【BZOJ】3038: 上帝造题的七分钟2（线段树+暴力）

图论：

• 网络流：
  • 【wikioi】1904 最小路径覆盖问题（最大流+坑人的题+最小路径覆盖）
  • 【wikioi】1034 家园（最大流+特殊的技巧）
  • 【TYVJ】1982 武器分配（费用流）
  • 【BZOJ】1877: [SDOI2009]晨跑（最小费用最大流）
  • 【wikioi】1913 数字梯形问题（费用流）
  • 【wikioi】1033 蚯蚓的游戏问题（费用流）
  • 【wikioi】1227 方格取数 2（费用流）
  • 【BZOJ】1834: [ZJOI2010]network 网络扩容（最大流+费用流）
  • 【BZOJ】1934: [Shoi2007]Vote 善意的投票（网络流/-二分图匹配）
  • 【BZOJ】1066: [SCOI2007]蜥蜴（最大流）
  • 【wikioi】1907 方格取数3（最大流+最大权闭合子图）
  • 【wikioi】1922 骑士共存问题（网络流/二分图匹配）
  • 【TYVJ】1338 QQ农场（最大流+最大权闭合图）
  • 【BZOJ】1221: [HNOI2001] 软件开发（最小费用最大流）
  • 最大权闭合图 && 【BZOJ】1497: [NOI2006]最大获利
• 二分图：
  • 【wikioi】1022 覆盖（二分图匹配）
  • 【BZOJ】1191: [HNOI2006]超级英雄Hero（二分图匹配）
  • 【BZOJ】1059: [ZJOI2007]矩阵游戏（二分图匹配）
• 最短路：
  • 【COGS】147. [USACO Jan08] 架设电话线（二分+spfa）
  • 【POJ】3255 Roadblocks（次短路+spfa）
  • 【POJ】1062 昂贵的聘礼（spfa）
  • 【POJ】2449 Remmarguts‘ Date（k短路）
  • 【wikioi】1269 匈牙利游戏（次短路+spfa）
  • 【BZOJ】1295: [SCOI2009]最长距离（spfa+暴力）
  • 【BZOJ】1491: [NOI2007]社交网络（floyd）对偶图 &&
  • 【BZOJ】1001: [BeiJing2006]狼抓兔子（对偶图+最短路）
  • 【BZOJ】1003: [ZJOI2006]物流运输trans（SPFA+DP）
• 连通性：
  • 【BZOJ】1051: [HAOI2006]受欢迎的牛（tarjan）
• 并查集：
  • 【BZOJ】1015: [JSOI2008]星球大战starwar（并查集）
• 生成树：
  • 【wikioi】1002 搭桥（dfs+最小生成树）
  • 【BZOJ】1821: [JSOI2010]Group 部落划分 Group（最小生成树+贪心）
  • 【TYVJ】1307 联络员（最小生成树）
• 最近公共祖先：
  • 最近公共祖先（lca）
• 基础：
  • 拓扑排序 
  • 二分图
  • 找割顶的模板

动态规划：

• • 【BZOJ】1040: [ZJOI2008]骑士（环套树dp）
  • 【BZOJ】1067: [SCOI2007]降雨量（rmq+变态题）
  • 【wikioi】1403 新三国争霸（dp+kruskal）
  • 【wikioi】2800 送外卖（状压dp+floyd）
  • 【BZOJ】1087: [SCOI2005]互不侵犯King（状压dp）
  • 【BZOJ】1084: [SCOI2005]最大子矩阵（DP）
  • 【BZOJ】3039: 玉蟾宫（DP/单调栈）
  • 【BZOJ】1270: [BeijingWc2008]雷涛的小猫（DP+水题）
  • 【BZOJ】1002: [FJOI2007]轮状病毒（DP+规律+高精度）

字符串：

• • 后缀数组
  • AC自动机
  • kmp模板

博弈论：

• • 【POJ】2234 Matches Game（博弈论）
  • 【POJ】A New Stone Game（博弈论）

数学：

• • 【BZOJ】1076: [SCOI2008]奖励关（状压dp+数学期望）
  • Catalan数 && 【NOIP2003】出栈序列统计
  • 【BZOJ】1008: [HNOI2008]越狱（快速幂）

搜索：

• • 【BZOJ】1054: [HAOI2008]移动玩具（bfs+hash）
  • 【NOIP2003】传染病控制（-贪心/dfs）
  • 【wikioi】2495 水叮当的舞步（A*+迭代加深搜索）
  • 【wikioi】1049 棋盘染色（迭代加深搜索）
  • 【BZOJ】1085: [SCOI2005]骑士精神（A*启发式搜索）

几何：

• • 【BZOJ】 1007: [HNOI2008]水平可见直线（凸壳）
  • 【COGS & USACO】896. 圈奶牛（凸包）
  • 【BZOJ】1041: [HAOI2008]圆上的整点（几何）

特殊的技巧：

• • 【TYVJ】1359 - 收入计划（二分）
  • 【BZOJ】2321: [BeiJing2011集训]星器（数学+特殊的技巧）
  • 【wikioi】1553 互斥的数（hash+set）
  • 【BZOJ】1303: [CQOI2009]中位数图（特殊的技巧）

水题：

• • 【COGS & USACO Training】710. 命名那个数字（hash+水题+dfs）
  • 【BZOJ】2761: [JLOI2011]不重复数字（set+巨水题+超坑题）
  • 【wikioi】1230 元素查找（巨水题+set/hash）
  • 【wikioi】1229 数字游戏（dfs+水题）
  • 【COGS】714. USACO 1.3.2混合牛奶（贪心+水题）
  • 【wikioi】1108 方块游戏（模拟） 
  • 【BZOJ】1192: [HNOI2006]鬼谷子的钱袋（水题）

7、8月刷题总结

原文：http://www.cnblogs.com/iwtwiioi/p/3942692.html