CSP-S复赛知识点

十月份目标

  1. 刷完算阶(这很重要)
  2. 熟练各种基础板子
  • 最短路:F l o y d FloydFloyd,B e l l m a n − F o r d Bellman-FordBellmanFord,D i j k s t r a DijkstraDijkstra, S P F A SPFASPFA
  • 最小生成树:p r i m primprim,k r u s k a l kruskalkruskal
  • 分治:二分答案,二分查找
  • 位运算
  • 排序算法
  • 字符串:K M P KMPKMP,T r i e TrieTrie树,A C ACAC自动机
  1. 熟练运用各种S T L STLSTL
  • 栈(s t a c k stackstack)(先进后出)
  • 队列(q u e u e queuequeue)(先进先出)
  • 优先队列(p r i o r i t y _ q u e u e priority\_queuepriority_queue)(堆)
  • 双端队列(d e q u e dequedeque
  • 平衡树(s e t setset)(m u l t i s e t multisetmultiset
  • 映射(m a p mapmap)(可代替h a s h hashhash表)
  • 随机数组(v e c t o r vectorvector)(可用来实现邻接表)
  • l o w e r _ b o u n d lower\_boundlower_bound与u p p e r _ b o u n d upper\_boundupper_bound(二分时候用)
  • 去重函数u n i q u e uniqueunique(可以用来离散化)

十一月目标

  1. 每天都要接触洛谷蓝以上难度的DP、图论、数论
  2. 掌握动态规划中的状态压缩DP、计数DP、树形DP与数位DP
  3. 进阶数据结构的模板
  • 树状数组
  • 线段树
  • 分块+莫队
  1. 图论
  • T a r j a n TarjanTarjan算法与图的连通性
  • 树的直径与L C A LCALCA
  1. 数论
  • 矩阵乘法
  • 组合计数
  • 概率与数学期望
  • 博弈论

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注