OI竞赛的流程

对于一般高中生而言,OI竞赛有一下流程:

  1. 在9月份左右的时间,报名参加由中国计算机协会(简称CCF)举办的非专业级别软件能力认证 提高级(简称CSP-S)第一轮认证,竞赛形式是笔试,一般很容易通过;
  2. 大概一个月后,CSP-S第一轮认证通过了的选手就可以参加CSP-S第二轮认证,形式是上机编写程序,大概4个小时完成4道题,难度中等偏上;
  3. 如果CSP-S第二轮认证考了0分以上,在11月份的时候就可以去参加全国青少年信息学奥林匹克联赛(简称NOIP),形式为上机编写程序,难度中等偏上;
  4. 如果NOIP达到了所在省份的制定分数线后,次年4月就可以参加省队选拔赛(简称省选),难度较高;
  5. 入选省队后,在7月份就可以参加全国信息学奥林匹克竞赛(简称NOI),难度很高,正式选手前50名可入选国家集训队;
  6. 入选国家集训队后,参加当年的全国青少年信息学奥林匹克竞赛冬令营(简称WC),选拔15人进入国家候选队;
  7. 进入国家候选队后,参加国际信息学奥林匹克竞赛中国队选拔赛(简称CTS),选拔6人进入国家队,其中4人为正式选手,2人为替补选手;
  8. 进入国家队,最后参加国际信息学奥林匹克竞赛(简称IOI),与来自世界各地的OI选手们同台竞技,如果在IOI中获得了金牌,就可以报送清华大学了,自此,OI竞赛之旅就结束了。

OI要学什么?

以下内容参考自 Studying Father’s blog

  1. 入门阶段
    • 此阶段学习C++语法基础,主要包括循环、分支、数组、字符串、函数、结构体等;
  2. 基础算法
    • 模拟
    • 排序算法
    • 二分答案
    • 分治
    • 贪心
    • 构造
    • 高精度
    • 前缀和 & 差分
  3. 搜索
    • 深度优先搜索(DFS)
    • 广度优先搜索(BFS)
    • 记忆化搜索
    • 搜索的剪枝
    • 双向搜索
    • 启发式迭代加深搜索(IDA*)
  4. 动态规划(DP)
    • 线性动态规划
    • 背包动态规划
    • 区间动态规划
    • 树形动态规划
    • 动态规划优化类算法
  5. 字符串
    • 字符串哈希
    • KMP
    • Manacher
    • Trie树
    • AC自动机
    • 回文自动机
    • 后缀
  6. 数学
    • 位运算
    • 整除相关
      • 素数
      • 最大公约数
      • 欧拉函数
    • 同余方程
      • 线性同余方程&乘法逆元
      • 中国剩余定理
      • 高次同余方程
    • 博弈论
    • 概率与期望
    • 组合数学
      • 排列组合
      • 卡特兰数&斯特林数
      • 容斥原理
    • 线性代数
      • 矩阵
      • 高斯消元
      • 线性基
    • 多项式
    • 莫比乌斯反演
  7. 数据结构
    • 链表
    • 队列
    • 并查集
    • 二叉堆
    • ST表
    • 树状数组
    • 线段树
    • 分块
    • 平衡树
    • 珂朵莉树
  8. 图论
    • 图的存储与遍历
    • 最短路问题
    • 树上问题
      • 二叉树
      • 树的直径
      • 最近公共祖先
    • 生成树
    • 拓扑排序
    • 差分约束
    • 二分图
    • 2-SAT
    • 强连通分量
  9. 解析几何
    • 凸包
    • 旋转卡壳
  10. 随机化
    • 模拟退火
    • 爬山算法

大概要考的就这些了,其实也没有很不多。