程序设计入门指北¶

写在开头：笔者水平有限，本文仅作为一个入门参考。

关于程序设计（竞赛）¶

程序设计体现在方方面面，他可以离你很近，在大一的 C/C++ 课程中，乐学的编程作业就是一种程序设计，如果选择了计算机类专业，大二也会专门有一门程序设计课程学习。

程序设计离不开算法，我们往往会对一道题设计出许多不同的算法：一些算法效率更高，或者内存占用小，这就是复杂度更优秀的算法。在 oi 竞赛中，不同效率的算法可以得到不同的分数，这就是所谓的部分分；在 xcpc 赛事中，一道题必须通过所有测试点才能判定为通过，没有通过会被记一次罚时（最终的总用时包括通过题目的时间加上所有的罚时时间），最终的排名按通过题目数优先，总用时次者排名。

在这里需要指出：程序设计竞赛虽然含金量高，但其需要的付出也同样极高，甚至性价比是不如其他类型的竞赛。因此，学习程序设计竞赛最重要的是兴趣和热爱，可能短时间内不能见到很好的成效，需要保持耐心。

当然，也不要丧失对算法竞赛的信心，一点一点的进步，你总能体会到算法竞赛带来的长远收益：一方面，参加区域赛是绝佳的出省训练 ~~（旅游）~~ 机会；另一方面，算法竞赛终究和计算机挂钩，在学习过程中你总会多多少少的学习到计算机的知识！

一些玄学

笔者认为：程序设计的后期更偏向数学，需要强硬的数学和逻辑能力，举几个例子：

在贪心问题中，往往会使用调整法或反证法证明一个贪心策略。
线性代数的定理保证了矩阵幂的高效处理，同时在标记传递中用线性代数分析是有效的（比如这篇），一些定理也是线性代数分析的产物。
抽象代数也发挥着重要的角色，很多问题都可以抽象成一个抽象代数模型，也有诸如 Burnside，polya 定理等抽象代数定理。

学习资料¶

这里是笔者高中时期的一些学习方法，供参考：

书籍¶

算法竞赛入门经典（蓝书）
深入浅出程序设计竞赛（洛谷）基础 or 题高
算法导论，组合数学：作为辅助书目学习，更偏向科研性质

平台¶

OI WiKi：高质量的编程竞赛知识整合站点。
各种博客（以前喜欢看洛谷日报，集训游记等等，一些知识点也会有博客讲解，安利下笔者的）。
洛谷：国内的较为成熟的在线评测题库，也有模拟赛参加。
Codeforces：位于俄罗斯的著名竞赛平台，不定期就会有比赛，大部分时间在晚上 \(22:30\) ，为期 \(2-3\) 小时，时间有点阴间。
Atcoder：日本的竞赛平台，也会举办比赛，分为 abc,arc,agc,ahc 四种。abc 大部分为模板题，会出现一些很难的板子（比如会有论文题）；arc,agc 主考思维能力，题目通常思维含量大代码量小；ahc 是工程竞赛，完成一道很复杂的题目，这种题目没有最优解，谁的解更优分数越高，有点类似 ai 竞赛。
Libre OJ：通常能找到一些省选题，一些不好找的题。
UOJ：收录大部分 xcpc 赛事的题，也有许多国际比赛的题。

关于集训¶

北理每学期寒暑假都有集训，集训通常在线下举行，极少数情况会安排线上（但是可以申请线上训练，但是效果当然不如线下好）。

寒假集训：在上学期期中左右参与选拔，在寒假期间训练。选拔后分为 A 队和 B 队：B 队的集训内容为学长讲解知识点加一些模拟赛，A 队的集训内容为模拟赛，打完后排名并看题解补题查漏补缺。

A 队会在下学期组队参加 xcpc 的邀请赛，邀请赛名额要看负责人和一些运气（前年基本每队一个邀请赛，今年大一大二几乎没有邀请赛）。

B 队需要争取在下一赛季进入 A 队。

暑假集训：在学期末考完所有科目后选拔，也是选拔赛的形式，寒假集训 A 队的成员有特殊的一套选拔方式（例如结合本学期的训练情况）：B 队仍然以讲解知识点为主，A 队会打牛客多校和航电多校，一周大概 \(4-5\) 场模拟赛。

在下半学期，A 组成员会参加 xcpc 区域赛，一个队伍能参加的区域赛数量根据暑期集训状况确定，一般为 \(2-4\) 个。

区域赛成绩极其优秀的队伍有可能被选拔参加 world final 全球决赛，这就是所说的 出线，选拔方式根据排名从上到下筛选，并且一个学校最多 只能有一个队伍 出线。

日常集训：不定时开展，例如这个学期的航电集训，还有可能参与到一些外校的模拟赛！

一些比赛¶

除了邀请赛，区域赛等，还有一些额外的比赛，下面列举一些：

蓝桥杯：

每一年举办一次的全国赛事，为 oi 赛制（所有提交在结束比赛后统一测评，即写完后你不能立即知道得分），有部分分，没有大样例。这就需要对一些题对拍，自己造几个大一点的数据自测。

蓝桥杯分为省赛和国赛，省赛一等奖可以晋级国赛，国赛前 \(5\%\) 是全国一等奖。

难度上，省赛较为基础，会有一两道有难度的题，比如今年省赛有线段树和差分约束；国赛难度更大，今年有线段树，矩阵递推，欧拉定理等等，可以看笔者的省赛游记和国赛游记。

天梯赛

下学期举办，是名义上的组队赛：解题需要个人解题不能团队合作，最后一个团队的几个人分数加和再算一个团队得分。

为类ioi 赛制（每道题提交后就能查看是否通过，并且不记录罚时，有部分分）。

最后会评团队奖项和个人奖项，可以选择一个计入综测（指特立的规定），影响因子 \(0.6\) ，可以加的综测比较大。

题目上有 A,B,C 三类题，A 是模拟签到题，B 是中等难度，C 是进阶题，共 \(15\) 道。难度还行。

省（市）赛

可以视为邀请赛的一种，大部分省份会举办，本省的一些学校组队参加，也会有外省队伍前来打卡。

难度可简单可难，评奖仅根据本省学校的队伍排名定额，如果外省队伍排名强于获奖的省内队伍，则也能获奖。

北京市赛很难打，今年来了清华，北交，北航等等出线强队。