首页 > 代码库 > 7、8月刷题总结

7、8月刷题总结

2024-07-20 01:35:11   221人阅读

准备开学了囧，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月刷题总结


联系
我们