技术文档
社团公告
技术文档
社团公告
简体中文

天津中德应用技术大学开源鸿蒙社算法培养方案

青浩洋---2024-8-22

优秀程序员必须掌握的算法基础

想成为优秀的程序员，学习算法必要的，即使是开发岗，在很多工程之中也需要用到一些算法知识，比如你要写一个五子棋，判断是否五子连珠，就需要用到BFS（广度优先搜索）的知识，如果不用BFS，就只能每下一个棋子就全局每个点搜一遍，这样从加大了程序的运行效率，不过在实际工程当中，只要时间影响不大，就可以忽略这个问题，换句话说，省事就好，能省则省，不过有一些场景，算法又是必要的，比如消消乐，如果不用算法，就得写很长的屎山代码，一堆if else去做消除填充操作，换个词就是暴力解决，甚至可能解决不了。

如今的就业市场趋于饱和状态，如果你没有比别人更多的能力去把别人比下来，那么就是毕业即失业，特别是对于我们这些背景比较弱的学生，就要学习更多的知识技能，扩宽自己的能力，并且现在有些中大厂都要求手撕算法，没错，是手撕算法题，笔试手撕，要你写代码，而且还不简单。

  • 时间复杂度，空间复杂度，均摊复杂度，势能分析
  • 枚举
  • 模拟
  • 递归&分治
  • 贪心
  • 排序
  • 前缀和&差分
  • 二分，三分
  • 倍增
  • 构造
  • 搜索
  • 动态规划
  • 数论
  • 数据结构
  • 图论

这些都是基础中的基础，可以不深入，但是基本的知识和板子题都得自己能手敲出来才算勉强及格，板子题可以理解为某个算法知识点的模板题

入门算法学习路线-摘自OIWIKI

语言基础

这个就不仔细阐述了，依次推荐使用C++，JAVA，Python三大语言学习算法

枚举

枚举（英语：Enumerate）是基于已有知识来猜测答案的一种问题求解策略。

枚举的思想是不断地猜测，从可能的集合中一一尝试，然后再判断题目的条件是否成立。

模拟

模拟就是用计算机来模拟题目中要求的操作。

模拟题目通常具有码量大、操作多、思路繁复的特点。由于它码量大，经常会出现难以查错的情况，如果在考试中写错是相当浪费时间的。

递归

递归（英语：Recursion），在数学和计算机科学中是指在函数的定义中使用函数自身的方法，在计算机科学中还额外指一种通过重复将问题分解为同类的子问题而解决问题的方法。

递归的基本思想是某个函数直接或者间接地调用自身，这样原问题的求解就转换为了许多性质相同但是规模更小的子问题。求解时只需要关注如何把原问题划分成符合条件的子问题，而不需要过分关注这个子问题是如何被解决的。

分治

分治（英语：Divide and Conquer），字面上的解释是「分而治之」，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并

分治算法的核心思想就是「分而治之」。

大概的流程可以分为三步：分解 -> 解决 -> 合并。

  1. 分解原问题为结构相同的子问题。
  2. 分解到某个容易求解的边界之后，进行递归求解。
  3. 将子问题的解合并成原问题的解。

贪心

贪心算法（英语：greedy algorithm），是用计算机来模拟一个「贪心」的人做出决策的过程。这个人十分贪婪，每一步行动总是按某种指标选取最优的操作。而且他目光短浅，总是只看眼前，并不考虑以后可能造成的影响。

可想而知，并不是所有的时候贪心法都能获得最优解，所以一般使用贪心法的时候，都要确保自己能证明其正确性。

排序

是一种将一组特定的数据按某种顺序进行排列的算法。排序算法多种多样，性质也大多不同。

主要有以下排序：选择，冒泡，插入，计数，基数，快速，归并，堆，桶，希尔，锦标赛，tim

一般只需要会用sort排序相关STL就行了，除非要深入学习。

前缀和

前缀和可以简单理解为「数列的前n项的和」，是一种重要的预处理方式，能大大降低查询的时间复杂度。

二维/多维前缀和

多维前缀和的普通求解方法几乎都是基于容斥原理。

差分

差分是一种和前缀和相对的策略，可以当做是求和的逆运算。

二分

二分查找（英语：binary search），也称折半搜索（英语：half-interval search）、对数搜索（英语：logarithmic search），是用来在一个有序数组中查找某一元素的算法。

它每次考察数组当前部分的中间元素，如果中间元素刚好是要找的，就结束搜索过程；如果中间元素小于所查找的值，那么左侧的只会更小，不会有所查找的元素，只需到右侧查找；如果中间元素大于所查找的值同理，只需到左侧查找。

三分

如果需要求出单峰函数的极值点，通常使用二分法衍生出的三分法求单峰函数的极值点

高精度

高精度计算（Arbitrary-Precision Arithmetic），也被称作大整数（bignum）计算，运用了一些算法结构来支持更大整数间的运算（数字大小超过语言内建整型）。

双指针

双指针是一种简单而又灵活的技巧和思想，单独使用可以轻松解决一些特定问题，和其他算法结合也能发挥多样的用处。

双指针顾名思义，就是同时使用两个指针，在序列、链表结构上指向的是位置，在树、图结构中指向的是节点，通过或同向移动，或相向移动来维护、统计信息。

倍增

倍增法（英语：binary lifting），顾名思义就是翻倍。它能够使线性的处理转化为对数级的处理，大大地优化时间复杂度。

这个方法在很多算法中均有应用，其中最常用的是 RMQ 问题和求 LCA

构造

构造题是比赛中常见的一类题型。

从形式上来看，问题的答案往往具有某种规律性，使得在问题规模迅速增大的时候，仍然有机会比较容易地得到答案。

这要求解题时要思考问题规模增长对答案的影响，这种影响是否可以推广。例如，在设计动态规划方法的时候，要考虑从一个状态到后继状态的转移会造成什么影响。

搜索

搜索，也就是对状态空间进行枚举，通过穷尽所有的可能来找到最优解，或者统计合法解的个数。

搜索有很多优化方式，如减小状态空间，更改搜索顺序，剪枝等。

搜索是一些高级算法的基础。在 OI 中，纯粹的搜索往往也是得到部分分的手段，但可以通过纯粹的搜索拿到满分的题目非常少。

DFS

DFS 全称是 Depth First Search，中文名是深度优先搜索，是一种用于遍历或搜索树或图的算法。所谓深度优先，就是说每次都尝试向更深的节点走。

该算法讲解时常常与 BFS 并列，但两者除了都能遍历图的连通块以外，用途完全不同，很少有能混用两种算法的情况。

DFS 常常用来指代用递归函数实现的搜索，但实际上两者并不一样。

BFS

BFS 全称是 Breadth First Search，中文名是宽度优先搜索，也叫广度优先搜索。

是图上最基础、最重要的搜索算法之一。

所谓宽度优先。就是每次都尝试访问同一层的节点。 如果同一层都访问完了，再访问下一层。

这样做的结果是，BFS 算法找到的路径是从起点开始的 最短 合法路径。换言之，这条路径所包含的边数最小。

在 BFS 结束时，每个节点都是通过从起点到该点的最短路径访问的。

算法过程可以看做是图上火苗传播的过程：最开始只有起点着火了，在每一时刻，有火的节点都向它相邻的所有节点传播火苗。

双向搜索

双向同时搜索的基本思路是从状态图上的起点和终点同时开始进行 广搜或深搜

如果发现搜索的两端相遇了，那么可以认为是获得了可行解。

启发式搜索

启发式搜索（英文：heuristic search）是一种在普通搜索算法的基础上引入了启发式函数的搜索算法。

启发式函数的作用是基于已有的信息对搜索的每一个分支选择都做估价，进而选择分支。简单来说，启发式搜索就是对取和不取都做分析，从中选取更优解或删去无效解。

A*

A * 搜索算法（英文：A*search algorithm，A * 读作 A-star），简称 A * 算法，是一种在图形平面上，对于有多个节点的路径求出最低通过成本的算法。它属于图遍历（英文：Graph traversal）和最佳优先搜索算法（英文：Best-first search），亦是BFS的改进

迭代加深搜索

迭代加深搜索的本质还是深度优先搜索，只不过在搜索的同时带上了一个深度，当达到设定的深度时就返回，一般用于找最优解。如果一次搜索没有找到合法的解，就让设定的深度加一，重新从根开始。

既然是为了找最优解，为什么不用 BFS 呢？我们知道 BFS 的基础是一个队列，队列的空间复杂度很大，当状态比较多或者单个状态比较大时，使用队列的 BFS 就显出了劣势。事实上，迭代加深就类似于用 DFS 方式实现的 BFS，它的空间复杂度相对较小。

当搜索树的分支比较多时，每增加一层的搜索复杂度会出现指数级爆炸式增长，这时前面重复进行的部分所带来的复杂度几乎可以忽略，这也就是为什么迭代加深是可以近似看成 BFS 的。

IDA *

IDA * 为采用了迭代加深算法的 A * 算法。

数据结构

栈，队列，链表，哈希表，并查集，堆，单调栈，单调队列，ST表，树状数组，线段树，二叉搜索树，平衡树，动态树等

动态规划

动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

能用动态规划解决的问题，需要满足三个条件：最优子结构，无后效性和子问题重叠。

由于动态规划并不是某种具体的算法，而是一种解决特定问题的方法，因此它会出现在各式各样的数据结构中，与之相关的题目种类也更为繁杂。

在 OI 中，计数等非最优化问题的递推解法也常被不规范地称作 DP，因此本章将它们一并列出。事实上，动态规划与其它类型的递推的确有很多相似之处，学习时可以注意它们之间的异同。

记忆化搜索

记忆化搜索是一种通过记录已经遍历过的状态的信息，从而避免对同一状态重复遍历的搜索实现方式。

因为记忆化搜索确保了每个状态只访问一次，它也是一种常见的动态规划实现方式

背包DP

典型的例题有01背包，完全背包，多重背包，分组背包等。

区间DP

区间类动态规划是线性动态规划的扩展，它在分阶段地划分问题时，与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来有很大的关系。

DAG 上的 DP

DAG 即 有向无环图，一些实际问题中的二元关系都可使用 DAG 来建模，从而将这些问题转化为 DAG 上的最长（短）路问题。

树形 DP

即在树上进行的 DP。由于树固有的递归性质，树形 DP 一般都是递归进行的

状压 DP

状压 DP 是动态规划的一种，通过将状态压缩为整数来达到优化转移的目的。

数位 DP

数位DP用来解决一类特定问题，这种问题比较好辨认，一般具有这几个特征：

  1. 要求统计满足一定条件的数的数量（即，最终目的为计数）；
  2. 这些条件经过转化后可以使用「数位」的思想去理解和判断；
  3. 输入会提供一个数字区间（有时也只提供上界）来作为统计的限制；
  4. 上界很大（比如 10的18次方），暴力枚举验证会超时。

字符串

字典树，字符串哈希，前缀函数与KMP算法，AC自动机，后缀数组，后缀自动机，后缀树，回文数等

数学

概率论，博弈论，计算几何，线性代数，组合数学，质数相关算法，快速幂，位运算等

图论

最小生成树，最短路，k最短路，同余最短路，欧拉图，哈密顿图，拓扑排序，二分图，支配树，最小环等

推荐OJ（online judge）在线测评刷题网站

洛古

牛客

QOJ

ATC

CF

UOJ

OI 赛事与赛制-摘自OIWIKI

赛事简介

信息学奥林匹克竞赛（英语：Olympiad in Informatics，简称：OI）是一门在中学生中广泛开展的学科竞赛，和物理、数学等竞赛性质相同。OI 考察的内容是参赛者运用算法、数据结构和数学知识，通过编写计算机程序解决实际问题的能力。

OI 竞赛种类繁多，仅中国就包括：

  • 全国青少年信息学奥林匹克联赛（NOIP）
  • 全国青少年信息学奥林匹克竞赛（NOI）
  • 全国青少年信息学奥林匹克竞赛冬令营（WC）
  • 国际信息学奥林匹克竞赛中国队选拔赛（CTSC）

国际性的 OI 竞赛包括：

  • 国际信息学奥林匹克（IOI）

  • 美国计算机奥林匹克竞赛（USACO）

  • 日本信息学奥林匹克（JOI）

  • 亚太地区信息学奥林匹克（APIO）

    ……

对于大部分选手而言，每年的新赛季从 9 月的 CSP-J/S 第一轮开始。

在中国，OI 竞赛允许使用的语言只有 C++（曾经也开放过 C 和 Pascal 语言，但都已停止支持）。其中，不同的竞赛对 C++ 的版本有不同的规定。考试题目一般为算法或者数据结构相关的内容，题目形式包括传统题（最常见的规定输入和输出到文件的题目）和非传统题（提交答案题、交互题、补全代码题……等等）。

赛制介绍

OI 赛制

选手仅有一次提交机会。比赛时无法看到评测结果，评分会在赛后公布。每道题都有多个测试点，根据每道题通过的测试点的数量获得相应的分数；每个测试点还可能会有部分分，即使只有部分数据通过也能拿到分数。

CSP-J/S 第二轮、NOIP、省选、NOI 都是 OI 赛制。

IOI 赛制

选手在比赛时有多次提交机会。比赛实时评测并返回结果，如果提交的结果是错误的，不会有任何惩罚。每道题都有多个测试点，根据每道题通过的测试点的数量获得相应的分数。

APIO、IOI 都是 IOI 赛制。目前国内比赛也在逐渐向 IOI 赛制靠拢。

Codeforces (CF) 赛制

Codeforces 是一个在线评测系统，会定期举办比赛。

它的比赛特点是在比赛过程中只测试一部分数据（Pretests），而在比赛结束后返回完整的所有测试点的测试结果（System Tests）。比赛时可以多次提交，允许 Hack 别人的代码（此处 Hack 的意思是提交一个测试数据，使得别人的代码无法给出正确答案）。如果想要 Hack，选手必须要锁定自己的代码（换言之，比赛时无法重新提交该题）。Hack 时不允许将选手程序拷贝到本地进行测试，源代码会被转换成图片。

Codeforces 同时提供另外一种赛制，称作扩展 ICPC（Extended ICPC 或 ICPC+）。在这一赛制中，在比赛过程中会测试全部数据，但比赛结束以后会有 12 小时的全网 Hack 时间。Hack 时允许将选手程序拷贝到本地进行测试。

主要比赛

CSP-J/S

CSP-J/S（英文：Certified Software Professional Junior/Senior）是 NOIP 在 2019 年被取消之后，CCF 开设的非专业级软件能力认证测试，面向全年龄段。

CSP-J/S 分为入门级（Junior，简写为 CSP-J）与提高级（Senior，简写为 CSP-S）两组，赛程分为第一轮（一般在每年 9 月）和第二轮（一般在每年 10 月）两场。第一轮为笔试，考察计算机理论和操作常识和基本的算法与数学知识；第二轮为上机考试，入门组与提高组都为 4 题，其中入门组考试时间 3.5 个小时，提高组 4 个小时（CSP-S 2019 除外，该场比赛使用旧 NOIP 提高组赛制，赛程分为两天，一天 3 题 3.5 小时）。第一轮面向社会全体学生报名，经过一定的排名筛选后成绩优秀者有机会参加第二轮。

报名参加第一/二轮、第二轮后进行题目申诉等都需要向 CCF 缴费。

两轮测试都会以省为单位按照排名对选手成绩进行评级认证，分为一、二、三等。

NOIP

NOIP（英语：National Olympiad in Informatics in Provinces，中文：全国青少年信息学奥林匹克联赛）是中华人民共和国组织的、面向中国（含港澳）中学生的信息学竞赛。

2018 年及以前的旧赛制：NOIP 按参赛对象分为普及组和提高组，2018 年于上海试点入门组；按阶段分为初赛和复赛两个阶段。初赛会考察一些计算机基础知识和算法基础，复赛为上机考试。时间上一般是 11 月的第二个周末，周六上午提高组一试 8:30-12:00（3.5 小时，共 3 题），下午 14:30-18:00 普及组（3.5 小时，共 4 题），周日上午提高组二试 8:30-12:00（3.5 小时，共 3 题）。全国使用同一套试卷，但是评奖规则按照省内情况由 CCF（中国计算机学会）统一指定，并于赛后在 NOI 官方网站 上公布。各省的一等奖分数线略有不同。

NOIP 于 2019 年 8 月 16 日 被 CCF 暂停，于 2020 年 1 月 21 日 被宣布恢复。2020 年起的 NOIP 赛制与以往有所不同，具体如下：

  • 取消初赛，由 CSP-J/S 第一轮替代；
  • 取消普及组，由 CSP-J 替代，此后 NOIP 仅有一个组别，面向提高组水平选手；
  • 赛程由以往的两天共 6 题、每天 3.5 个小时，缩减为一天 4 题、共 4.5 个小时。
  • 选手需要在 CSP-S 第二轮中取得一定名次才能获得 NOIP 参赛资格，具体名额各省有所差异。NOIP 省级参赛资格由该省在去年赛季中的参赛人数和成绩等有关。

报名参加 NOIP 和进行题目申诉不需要额外缴费。

NOIP 以省为单位排名评奖。截至 2019 年，大部分高校的选手获得提高组省一等奖可以得到自主招生资格。

2020 年 1 月，中华人民共和国教育部发布 关于在部分高校开展基础学科招生改革试点工作的意见。意见指出，2020 年起，不再组织开展高校自主招生工作，并在部分一流大学建设高校开展基础学科招生改革试点（强基计划）。

省队选拔赛

省队选拔赛（简称：省选）用于选拔各省参加全国赛的代表队，一般举行于每年的 1~4 月。赛程上一般分为两天，每天 3 题 4.5 小时。

省选题目由各个省自行决定，目前的趋势是很多省份选择联合命题。

各个省队的名额有复杂的计算公式，一般和之前的成绩和参赛人数有关。通常来讲，NOIP 分数需要在省选的指标中占一定比例。根据规则，初中选手只能被选拔为 E 类选手，不能参加 A、B 类选拔。A 类选手有 5 人（4 男 1 女），其他选手根据给定名额和所得分数依次进入 B 队。一个学校参加 NOI 的名额不超过本省 A、B 名额总数的三分之一（四舍五入），得分最高且入选 A 队的女选手不占该比例（简称 ⅓ 限制或 ⅓ 淘汰）。

自 2020 年起，NOI 省队选拔由 CCF 统一命题和评测，有能力命题的省可自行命题，但选拔方式需得到 CCF 的批准。自 2024 年起，NOI 省队选拔恢复各省自主命题，有需求的省份可组织联考或使用他省试题，但具体方案需要得到 CCF 的批准。

NOI

NOI（英文：National Olympiad in Informatics，中文：全国信息学奥林匹克竞赛）是国内包括港澳在内的省级代表队最高水平的大赛。

NOI 一般在七月份举行，选手分为正式选手与夏令营选手两类。正式选手又分为三类，其中 A、B 类为省队正式选手，C 类选手为邀请赛选手。A、B 类对应省队的 A、B 类选手（其中 A 类在计算成绩时会有 5 分加分）；C 类名义上是学校对 CCF 做出突出贡献后的奖励名额。夏令营选手分为 D、E 类，分别对应以非正式选手身份参赛的高中组与初中组选手。夏令营选手如果成绩超过分数线的话，只有成绩证明而没有奖牌（同等分数含金量要低一些）。排名前 60 的正式选手组成国家集训队，获得保送资格。

在国际平台上，为了与其他同样称作 NOI 的比赛区分，有时会被称作 CNOI。

WC

WC（英文：Winter Camp，中文：全国青少年信息学奥林匹克竞赛冬令营）是每年冬天在当年 NOI 举办地进行的一项活动。

WC 的内容包括若干天的培训和一天的考试。这项考试主要用于从国家集训队（50 人）选拔国家候选队（15 人），但是前一年 NOIP 与 CSP-S 第二轮取得较好成绩的选手也可以参加（不参与选拔）。

APIO

APIO（英文：Asia-Pacific Informatics Olympiad，中文：亚太地区信息学奥林匹克竞赛）是一个面向亚太地区在校中学生的信息学学科竞赛。CCF 每年会在五月初举办中国赛区镜像赛。在比赛日前后会有培训活动。

CTS

CTS（旧称：CTSC, 英文：China Team Selection Competition，中文：国际信息学奥林匹克竞赛中国队选拔赛）用来从国家候选队（15 人）中选拔国家队（6 人）准备参加当年夏天的 IOI 比赛，其中正式选手 4 人，替补选手 2 人。与 WC 一样，前一年 NOIP 取得较好成绩的选手也可以参加（不参与选拔）。

APIO 和 CTS 都以省为单位报名，一般按照 NOIP 的成绩排序来确定参加 APIO 和 CTS 的人员（二者一般时间上非常接近）。

IOI

IOI（英文：International Olympiad in Informatics，中文：国际信息学奥林匹克竞赛）是一年一度的面向全球中学生的信息学科竞赛。每个国家有四人参赛，比赛一般会有直播。IOI 赛制中每个题目会有 Subtask（子任务），每个子任务对应一定的分数。

学科营

北京大学（PKU）
  • 北京大学信息学冬季体验营（PKUWC）：在冬令营前后举行。
  • 北京大学信息学体验营（PKUSC）：一般在六月份在校内举行。由于在学校机房比赛，机房环境是 Windows，比赛系统是 OpenJudge。
  • 北京大学中学生暑期课堂（信息学）：在暑假举行，面向高二年级理科学生。
清华大学（THU）
  • 计算机系 "大中衔接" 冬季研讨与教学活动：相当于信息学冬令营，有时也会用英文简写为 THUWC。一般共两天，上午为竞赛（第一天是标准 OI 竞赛，第二天为清华独创的 "工程题" 竞赛），下午为课程培训。

其他国家和地区的 OI 竞赛

美国：USACO

官网地址：http://www.usaco.org/

USACO 或许是国内选手最熟悉的外国 OI 竞赛（可能也是中文题解最多的外国 OI 竞赛）。

每年冬季到初春，USACO 会每月举办一场网络赛。一场比赛持续 3~5 个小时。

根据官网的介绍，USACO 的比赛分成这 4 档难度（2015~2016 学年之前为 3 档）：

  • 铜牌组，适合编程初学者，尤其是只学了最最基础的算法（如：排序，二分查找）的学生；
  • 银牌组，适合开始学习基本的算法技巧（如：递归，搜索，贪心算法）和基础数据结构的学生；
  • 金牌组，学生会遇到更复杂的算法（如：最短路径，DP）和更高级的数据结构；
  • 铂金组，适合有着扎实的算法设计能力的选手，铂金组可以帮助他们以复杂且更开放的问题来挑战自我。

在国内，目前 USACO 题目最齐全的 OJ 平台是洛谷。

波兰：POI

官网地址：https://oi.edu.pl/

官方提交地址：https://szkopul.edu.pl/p/default/problemset/

POI 是不少省选选手最常刷的外国 OI 比赛。

根据 http://main.edu.pl/en/ 的描述，POI 的流程如下：

  • 第一轮：五题，网络赛，公开赛；
  • 第二轮：包含一场练习赛，和两场正式比赛；
  • 第三轮：赛制同上。
  • ONTAK：POI 训练营（类似国内的集训队）。

另有 PA，大意为「算法大战」。

目前在国内 OJ 中，POI 题目最全的是 BZOJ。

克罗地亚：COCI

官网地址（英文）：http://www.hsin.hr/coci/

官网地址（克罗地亚语）：http://www.hsin.hr/honi/

难度跨度很大的比赛，大约是从普及 - 到省选 -。

以往 COCI 所有的题目均提供题目、数据、题解和标程。2017 年底起，COCI 的题解和标程停止了更新。2019-2020 赛季重新开始更新题解和标程。

洛谷、BZOJ 和 LibreOJ 都有少量的 COCI 题目。

日本：JOI

官网地址：https://www.ioi-jp.org/

JOI（日文：日本情報オリンピック，中文：日本信息学奥赛）所有的题目都提供题目、数据、题解和标程。近两年的 JOI 决赛和春训营提供了英语题面，但并没有英语题解。历年的 JOI Open 都提供了英语版题面和题解。

JOI 的流程：

  • 预赛（予選）
  • 决赛（本選/JOI Final）
  • 春训营（春季トレーニング合宿/JOI Spring Camp/JOISC）
  • 公开赛（通信教育/JOI Open Contest）

预赛难度较低，自 2019/2020 赛季起，预赛分为多轮。JOI Final 的难度从提高 - 到 提高 + 左右。JOISC 和 JOI Open 的题目的难度从提高到 NOI - 不等。

绝大部分 JOI 题可以前往 AtCoder 提交。你可以在 JOI 官网或者 AtCoder 上找到更多的 JOI 题（日文题面）。

目前 LibreOJ 和 BZOJ 有近些年的 JOI Final、JOISC 和 JOI Open 的题目。

俄罗斯：ROI

官网地址：http://neerc.ifmo.ru/school/archive/index.html

在线提交地址：https://contest.yandex.ru/roiarchive/ 和 Codeforces（部分）。

ROI（俄文：олимпиадная информатика，中文：俄罗斯信息学奥赛）是俄罗斯的信息学竞赛。

流程：

  • 市级比赛（Municipal Stage/Муниципальный этап）
  • 州级比赛（Regional Stage/Региональный этап）
  • 决赛（Final Stage/Заключительный этап）

目前 LibreOJ 有近几年的 ROI 决赛题的译文。

除此之外，俄罗斯较大型的、面向中学生的比赛还有：

加拿大：CCC & CCO

CCC（英文：Canadian Computing Competition），CCO（英文：Canadian Computing Olympiad），可在其 官网 查询历届的信息和试题等。

在 DMOJ 上可以提交 CCC 和 CCO，该 OJ 上还有 CCC 题解。

CCC Junior/Senior 贴近 NOIP 普及组/提高组难度。CCO 想要拿到金牌可能得有 NOI 银牌的水平。

新加坡：NOI SG

官网地址：https://noisg.comp.nus.edu.sg/noi/

全称 Singapore National Olympiad in Informatics，在新加坡国内语境且不引起歧义的情况下也作 NOI。赛制上分为 Online Qualification Contest（在线资格赛）和 Final Contest（全国决赛）。在线资格赛以学校为单位报名参加，选手在本校参赛，通过网络进行远程提交。资格赛成绩只在校内排名，前 5 名且非零分选手有资格作为校代表队参加全国决赛。

目前国内 OJ 对于 NOI SG 的题目收录比较匮乏，可以在 官方的 GitHub 帐号 上找到历年题面、测试数据和官方标准程序。

台湾地区：資訊奧林匹亞競賽

台湾地区把 OI 中的 informatics 翻译成「資訊」而非大陆通用的翻译「信息」。

台湾地区的选手如果想参加 IOI，需要经过这几轮比赛：

  • 區域資訊學科能力競賽
  • 全國資訊學科能力競賽
  • 資訊研習營（TOI）

其他国家

其它国际 OI 竞赛

BalticOI

BalticOI 面向的是波罗的海周边各国。BalticOI 2018 的参赛国有立陶宛、波兰、爱沙尼亚、芬兰等 9 国。题目难度大。

除了 2017 年，BalticOI 每年都公开题面、测试数据和题解。BalticOI 没有一个固定的官网，每年的主办方都会新建一个网站。历年的官网地址见 帖子。

目前 LibreOJ 有近十年的 BalticOI 题。

BalkanOI

BalkanOI 面向巴尔干地区周边各国。BalkanOI 2018 的参赛国有罗马尼亚、希腊、保加利亚、塞尔维亚等 12 国。题目难度大。

BalkanOI 只有某几年公开题面、测试数据和题解，官网地址见 帖子。

CEOI

CEOI 2018 的参赛国与上面两个比赛有部分重叠，包括波兰、罗马尼亚、格鲁吉亚、克罗地亚等国。题目难度大。

CEOI 每年都公开题面、测试数据和题解，官网地址见 帖子。

在国内 OJ 中，BZOJ 的 CEOI 题相对最齐。

eJOI

eJOI 全名 European Junior Olympiad in Informatics。参赛国包含俄罗斯、亚美尼亚、保加利亚、波兰等国。题目难度较大。

eJOI 每年都公开题面、测试数据和题解，官网地址见 帖子。

ISIJ

ISIJ 全名 International School in Informatics "Junior"，中文名「国际初中生信息学竞赛」。

官网地址：http://isi-junior.com/

XCPC考点大纲图览

XCPC就是ICPC国际大学生程序设计竞赛和CCPC中国大学生程序设计竞赛，想要以算法为未来发展主要道路，这些知识都是基础

img

ICPC/CCPC 赛事与赛制

赛事介绍

ICPC

ICPC（英文：International Collegiate Programming Contest，中文：国际大学生程序设计竞赛）由 ICPC 基金会（英文：ICPC Foundation）举办，是最具影响力的大学生计算机竞赛。由于以前 ACM 赞助这个竞赛，也有很多人习惯叫它 ACM 竞赛。

ICPC 主要分为区域赛（Regionals）和总决赛（World Finals）两部分。

官网地址：https://icpc.global

CCPC

官网地址：https://ccpc.io

中国大学生程序设计竞赛。

和 ICPC 显著的区别是很多学校是不报销的。

赛制介绍

一般是三个人组成一队使用一台机器，在比赛时有多次提交机会。比赛实时评测并返回结果，如果提交的结果错误会有 20 分钟的罚时，错误次数越多，加罚的时间也越长。每个题目只有在所有数据点全部正确后才能得到分数。比赛排名根据做题数来评判，做题数相同的，根据总用时来评判。总用时是每题用时的和。每题的用时是从比赛开始到做出该题的分钟数与该题的罚时之和。

一些 ICPC 相关赛事中，比赛结束前一小时进行封榜，封榜后的提交和排名将无法被其他选手看见。

在 ICPC 相关赛事中，选手允许带一定量的纸质资料。

除 ICPC 和 CCPC 外，众多比赛也采用该赛制，如 LeetCode 周赛及全国编程大赛、牛客小白赛练习赛挑战赛等。

赛季赛程
  • ICPC/CCPC 网络赛（8 月底至 9 月初）
  • ICPC/CCPC 区域赛（9 月底至 11 月底）
  • ICPC EC Final/CCPC Final（12 月中旬）
  • ICPC World Finals（次年 4 月至 6 月）
训练指南
多校联合训练

暑期在 HDU OJ 举行的训练赛。有奖金，题目质量高，历经多年积累已有丰富资源。

OJ 里查询用的关键词：Multi-University Training Contest。

国内区域赛

在 Virtual Judge 里可以搜到精选题集。

训练营
  • 寒假的时候头条/清华/CCPC (Wannafly Camp) 举办的 Camp
  • Wannafly Camp
大纲