计划

Sgt_ · 2025-06-27 16:34:43 · 个人记录

信息学竞赛进阶学习规划（基础强化→提高阶段）

一、基础强化阶段（6-12个月）

1. 重点学习内容

数据结构

• 线性结构
  ✓ 循环队列
  ✓ 单调队列
  ✓ 双向链表
• 树结构
  ✓ 二叉树遍历（前/中/后序）
  ✓ 堆（优先队列）
  ✓ 并查集（路径压缩+按秩合并）
• 哈希
  ✓ 字符串哈希（BKDR）
  ✓ 冲突处理（开放寻址法）

算法

• 搜索
  ✓ DFS剪枝（可行性/最优性）
  ✓ BFS（双向BFS、A*）
• 图论
  ✓ 最短路（Dijkstra堆优化、SPFA判负环）
  ✓ 最小生成树（Kruskal、Prim）
  ✓ 拓扑排序（任务调度应用）
• 动态规划
  ✓ 背包（01/完全/多重）
  ✓ LIS/LCS
  ✓ 状态设计技巧（滚动数组、状态压缩）

2. 训练计划

3. 推荐资源

• 📚 书籍：《算法竞赛入门经典（第2版）》第7-11章
• 🌐 题库：
  • 洛谷「数据结构」和「图论」题单
  • LeetCode精选（标签：Graph、DP）
• ⚙️ 工具：Visualizer（可视化调试工具）

二、提高阶段（1-2年）

1. 高阶内容突破

数据结构

• 区间处理
  ✓ 线段树（懒标记）
  ✓ 树状数组（逆序对）
• 字符串
  ✓ Trie树（持久化）
  ✓ AC自动机（Fail指针优化）
• 高级树结构
  ✓ Splay树（了解思想）

算法

• 图论进阶
  ✓ 网络流（Dinic算法）
  ✓ 强连通分量（Tarjan）
• DP优化
  ✓ 斜率优化（单调队列维护凸包）
  ✓ 四边形不等式
• 数学
  ✓ 数论（扩展欧几里得、CRT）
  ✓ 组合数学（容斥原理）

2. 高强度训练

3. 备赛技巧

• 📜 代码模板管理：

  
  // 示例：快速幂模板
  ll qpow(ll a, ll b, ll mod) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
  }

https://www.cnblogs.com/fusiwei/p/11858363.html