12月刷题总结

各种被屠...学东西各种慢...

QAQ

 

字符串：

• sam：
  • 【SPOJ】7258. Lexicographical Substring Search（后缀自动机）
  • 【SPOJ】1812. Longest Common Substring II（后缀自动机）
  • 【BZOJ】2555: SubString（后缀自动机）
  • 【BZOJ】3172: [Tjoi2013]单词（后缀自动机）
  • 【wikioi】3160 最长公共子串（后缀自动机）
• lcp：
  • 【BZOJ】1014: [JSOI2008]火星人prefix（splay+hash+二分+lcp）

 

计算几何：

• 凸包及其拓展：
  • 【POJ】Beauty Contest（旋转卡壳）
  • 【BZOJ】1069: [SCOI2007]最大土地面积（凸包+旋转卡壳）
• 其它：
  • 【POJ】Triangle（pick定理）

 

数据结构：

• 平衡树：
  • 【BZOJ】3053: The Closest M Points（kdtree）
  • 【BZOJ】2648: SJY摆棋子 & 2716: [Violet 3]天使玩偶（kdtree）
  • 【BZOJ】3223: Tyvj 1729 文艺平衡树（splay）
  • 【BZOJ】2329: [HNOI2011]括号修复（splay+特殊的技巧）
  • 【BZOJ】2209: [Jsoi2011]括号序列（splay）
  • 【BZOJ】1251: 序列终结者（splay）
  • 【UOJ】【UR #2】猪猪侠再战括号序列（splay/贪心）
• 动态树：
  • 【BZOJ】3669: [Noi2014]魔法森林（lct+特殊的技巧）
  • 【BZOJ】1180: [CROATIAN2009]OTOCI & 2843: 极地旅行社（lct）
• 线段树：
  • 【BZOJ】3673: 可持久化并查集 by zky & 3674: 可持久化并查集加强版（可持久化线段树）
  • 【BZOJ】1798: [Ahoi2009]Seq 维护序列seq（线段树）
  • 【BZOJ】3339: Rmq Problem & 3585: mex（线段树+特殊的技巧）
• 并查集：
  • 【BZOJ】3319: 黑白树（并查集+特殊的技巧/-树链剖分+线段树）

分治：

• 【SPOJ】1825. Free tour II（点分治）
• 【BZOJ】2152: 聪聪可可（点分治）
• 【BZOJ】1468: Tree（点分治）
• 【BZOJ】1176: [Balkan2007]Mokia（cdq分治）
• 【BZOJ】1492: [NOI2007]货币兑换Cash（cdq分治）

 

数学：

• 数论：
  • 【BZOJ】1441: Min（裴蜀定理）
  • 【BZOJ】2818: Gcd（欧拉函数/莫比乌斯）
  • 【cf490】D. Chocolate（素数定理）
  • 【cf492】E. Vanya and Field（拓展欧几里得）
• 矩阵乘法：
  • 【BZOJ】2875: [Noi2012]随机数生成器（矩阵乘法+快速乘）
• 博弈论：
  • 【BZOJ】2463: [中山市选2009]谁能赢呢？（博弈论）

动态规划+递推：

• 【BZOJ】1055: [HAOI2008]玩具取名（dp）
• 【BZOJ】1097: [POI2007]旅游景点atr（spfa+状压dp）
• 【BZOJ】1049: [HAOI2006]数字序列（lis+特殊的技巧）
• 【BZOJ】1089: [SCOI2003]严格n元树（递推+高精度/fft）
• 【BZOJ】1090: [SCOI2003]字符串折叠（dp）
• 【BZOJ】2435: [Noi2011]道路修建（树形dp）
• 【BZOJ】1079: [SCOI2008]着色方案（dp+特殊的技巧）

 

图论：

• 网络流：
  • 【BZOJ】1070: [SCOI2007]修车（费用流+特殊的技巧）
  • 【BZOJ】1189: [HNOI2007]紧急疏散evacuate（二分+bfs+网络流）
  • 【BZOJ】2929: [Poi1999]洞穴攀行（最大流）
  • 【BZOJ】1458: 士兵占领（上下界网络流）
  • 【BZOJ】1927: [Sdoi2010]星际竞速（二分图+费用流）
• 连通性：
  • 【BZOJ】1098: [POI2007]办公楼biu（补图+bfs+链表）
  • 【BZOJ】1179: [Apio2009]Atm（tarjan+spfa）

 

贪心：

• 【BZOJ】3709: [PA2014]Bohater（贪心）
• 【BZOJ】2802: [Poi2012]Warehouse Store（贪心）

 

其它：

• 【BZOJ】1082: [SCOI2005]栅栏（二分+dfs）
• 【BZOJ】3781: 小B的询问（莫队算法）
• 【BZOJ】3289: Mato的文件管理（莫队算法+树状数组）
• 【BZOJ】2038: [2009国家集训队]小Z的袜子(hose)（组合计数+概率+莫队算法+分块）
• 【cf489】D. Unbearable Controversy of Being（暴力）
• 【cf492】D. Vanya and Computer Game（二分）

 

cf的一些题（被屠得好惨啊）：

• 蒟蒻修养之cf紫名计划