OI Intro

Author Avatar
dozbear 8月 04, 2018
  • 在其它设备中阅读本文章

“说了我再也不写 OI 相关的东西了”

“真香”

严格来说这是一篇投给我校生活指南的稿件,并不是一篇博客,所以有的地方格式会有些奇怪

听说…最后地方不够了所以放了这个博客的链接…这么刺激的吗QAQ

顺便说一下我还是喜欢 medium …但是考虑到国内的访问还是写在了博客上

以下是正文

我是一个咸鱼学长,也是一个迫真 OI 选手,感谢某学生会の化学集训队先辈给我这个向大家介绍 OI 的机会(小并感)

正如文章标题,此文将会是一篇针对 OI 的简单介绍,文中将会涉及到 OI 的及其周边的客观问题。换句话说,如果你是大佬就可以不用看了。

Basic notions

OI 是什么东西,我怎么没听说过?

OI 全称 olympaid in informatics,中文名是青少年信息学奥林匹克竞赛。相对来说,OI 是五大竞赛里最阿卡林的一种(没错,它是和数学物理化学生物并列的五大竞赛之一),但它仍然具有和其他竞赛等同的各级奖项和高校自主招生政策。

所以请快来学吧!我什么都不会做的!

那么 OI 是要干什么呢?

一般来说,OI 中题目的形式是给你一个自然语言描述的问题,让你在电脑上编写一个可以在一定时间和内存占用限制内解决它的程序,然后评测系统会通过一系列的测试数据得到此程序的分数。

这个说法或许有点空洞,请看一个具体的例子。

某班有 $n$ 个男孩子和 $m$ 个女孩子,有一些男孩子和女孩子暗恋着对方。
为了方便表示,在 $n\times m$ 的矩阵 $A$ 中,每个元素都是 $0$ 或 $1$;其中 表示第 $i$ 个男孩子和第 $j$ 个女孩子是革命友谊,反之则说明他们愿意结为男女朋友。
现在他们决定使尽可能多的人摆脱单身,在每个同学只能有一个伴侣的情况下,请你最大化整个班的情侣数目。
$n$、$m$ 和矩阵 $A$ 都会在输入中给出。

显然,这个问题可以穷举每个同学的伴侣,选取最大的答案;但是电脑的运行速度是有限的,此时我们就要用一定的算法(algorithm)和数据结构(data structure)优化程序。

在这个题目中,穷举每个人的伴侣所需要的电脑运行时间和 $2^{n+m}$ 成正比,使用匈牙利算法可以优化到和 $(n+m)^3$ 成正比;如果使用 dinic 算法,可以做到运行时间和 $(n+m)^{2.5}$ 成正比。正常情况下,后两种算法的运行时间都足以通过这类题目。

那么如果这个问题更加复杂呢?例如不同的男女之间喜欢的程度不相同,又或者有一些人男女通吃?这个时候就要选择其他的算法,或者自己创造出新的算法(毒害后辈kana)。

有时题目会更加隐晦,例如用 $1 \times 2$ 的棋子覆盖一个有一些窟窿的 $n \times m$ 的棋牌;这就要做一些数学变形,找出其中隐藏的算法。对于这个问题,将棋盘上每个格子按照行号列号之和的奇偶性分类(黑白染色)后匹配,本质上和上文中男女朋友的问题是一样的。

看到这儿,你应该对 OI 有一个初步的认识了。

OI 比赛的时间安排如何?

一般来说(除了 1989 年),一个完整的 OI 赛季是从每年的十月份到次年的七月份。

全国青少年信息学奥林匹克省级联赛(也就是其他竞赛的高联)的初赛在每年的十月中旬举办,达到分数线的人可以参加十一月的复赛;在这场比赛中,你有机会拿到一般通过高校自主招生的敲门砖,也就是省级赛区一等奖(通常称为国一)。这两场考试的地点都是南京。

这里有一个小问题,就是省级赛区一等奖只有在江苏才被称为国一。在全国其他地区,省一就是江苏的国一,而国一指的是金牌。

次年寒假前后,联赛中的高分者将会获得清华或北大举办的冬令营的邀请。在这场比赛中,你有机会获得和高校一对一的自招协议,一般是决赛到达某名次或进入省队就降至一本线或降60/40/20分录取。如果你考得很好,也有可能收到一份令人生草的无条件一本录取协议。

一两天后会举行全国青少年信息学奥林匹克竞赛冬令营,在上一个赛季的国家集训队员中选出前 15 名。如果你不是集训队选手,参加这个比赛有机会获得一块没有什么用的奖牌。

次年四到五月,获得省级赛区一等奖的选手可以报名省队选拔,通常是考两轮,每轮分两天考两场,选出最多 16 名省队选手参加决赛。

次年五月底到六月初会在北京举行亚太信息学奥林匹克,可以和同学们(如果你有女朋友就更棒了)夜游帝都(bushi),当然也有机会获得一块出国有点用的奖牌。

一两天后会举行国家队选拔赛,在上一个赛季的国家集训队员前 15 名中选出前 4 名组成国家队参加国际信息学奥林匹克竞赛。如果你不是集训队选手前 15 名,参加这个比赛有机会获得一块没有什么用的奖牌。

次年七月底会举办全国青少年信息学奥林匹克竞赛(也就是决赛)。在这场比赛中,前 50 名将会进入国家集训队获得保送资格,高校也会和选手自由签约。参加这个比赛,你有机会获得一块比较有用但是质量很差(血泪控诉)的奖牌。

据笔者所知 OI 决赛中高校还是非常愿意和选手签约的,一般来说金牌非集训队及银牌靠前可以获得 top2 高校降至一本线录取的自招合约,银牌可以获得上海交大及同等级学校降至一本线录取的自招合约,铜牌的上半部分可以获得中国人民大学及同等级学校降至一本线录取的自招合约。
如果你落选了省队但仍然在前 40 名,也可以购买额外名额参加决赛;但是你不能选入集训队,不能获得实物的奖牌,并且自招协议时会受到一定的歧视(例如银牌只能签人民大学)。

国际信息学奥林匹克竞赛也会在暑假举行,不过这个比赛是只有国家队选手才能去的……

所以学习 OI 会让你损失半个暑假和很多参加期中期末考试的机会(如果你运气很好还会损失参加高考的机会);不过你也因此有机会在全国各地留下自己的足迹。

一些细节问题

我将如何编写程序?

OI 中可以使用的编程语言有 CC++Pascal,其中 Pascal 将在 2020 年被废弃。

这三种都是高级语言,也就是说,OI 不包含任何和汇编、机器语言相关的内容,也就是和电脑硬件没有太大关系。

这三种语言都是以某些固定格式和固定词汇去控制计算机执行指令。如果你学过 Scratch 或者 Python 等更加抽象的语言,理解起来将会容易得多。

我不知道自己是否喜欢 OI,但是我对玩电脑很有兴趣…

事实上 OI 和玩电脑关系不大,“信息竞赛”这个名字本身就有很大的误导性;中文中合适的名字应该是“算法竞赛”或者“程序设计竞赛”。

相比“信息竞赛”,这两个名字突出了 OI 中更加数学的那一部分。你可以把 OI 中做题的过程视作条件限制更多、更加特殊、要求也更高的建模。

如果我是为国一而来…

这是一个有点困难的问题,因为笔者本人比较菜,和国一水平差距较大……

根据笔者对周围同学的观察,每周认真上竞赛课并保证三到四个小时的练习,每个暑假花上三四周集中训练,高二或者高三就可以达到国一水平以上。

竞赛有一定的偶然性,而且 OI 并不是高考科目,学习 OI 不会对你的高考有帮助。如果你希望通过不完整的学习和运气获得国一,OI 并不是一条合适的路。

如果我想成为决赛选手…

在决赛中获得奖项是一件耗费精力很多的事。

客观地说,目前江苏地区的学校并没有针对决赛选手的培养方法。如果你天赋异禀,在获得国一的途中就会找到自己的学习方式(例如隔壁学校的某些神仙);否则你需要在校外或网络上参加课程,或是去往全国各地的集训,但这会影响课内学习。相对的,决赛对升学的帮助也远大于联赛。

笔者本人并不能、也不打算劝任何人作出这种决定。如果你希望走这条路,可以和家人及信息组教练王老师交流;唯一要说的是,任何个人经验都只有参考价值,最终还是要自己权衡利弊。

如果我是妹子…

学 OI 的女孩并不多。

OI 的省队选拔有独特的“女队”政策,即无论如何都要保证省队中有一名女选手;这意味着只要你是所有女选手中名次最高的,就一定可以入选省队。

且不谈这是否是性别歧视或者逆向性别歧视,政策本身是客观存在的;如果你是妹子,你的 OI 之路会比男生更加轻松(?)。

如果我是为脱单而来…

如果你的取向是男,那希望还是比较大的。学 OI 的男生的形象可以参考日常生活中对程序员的 stereotype,但是会比一般程序员聪明一些,而且一部分人(不包括笔者)喜欢女装(划掉)。不过他们恐怕没有多少时间陪你……

如果你的取向是女,哪来的回哪去吧……

顺便一提,笔者认识的脱单 OI 选手的男/女朋友都不是学竞赛的(激寒劝退yamero)

还有就是女装只有零次和无数次的区别。

高级选项

阅读该章节的内容需要一点点 OI 基础。

我在哪做题比较好?

一些比较著名的 Online Judge

  • Codeforces,题目多质量相对较高,虽然是俄罗斯网站但是提供英语选项
  • AtCoder,题目较多质量很高,虽然是日本网站但是提供英语选项
  • UOJ aka Universal Online Judge,题目较少质量极高,就是有点……大部分题目对集训队选手来说也挺难的,虽然是中文网站但是提供英语选项(划掉)
  • LibreOJ,顾名思义这是一个自♂由的 OJ,题目数量较多,其中不乏高质量的集训和模拟赛题目,相对来说难度较高
  • BZOJ,老牌 OJ,题目很多,包含了各省的省队选拔和集训等等,但是质量参差不齐,部分题目需要收费
  • GCJ aka Google Code Jam,谷歌出品,题目质量很高也很有趣,缺点是用起来 不那么爱国,访问时需要一些奇怪的科技(手动滑稽
  • CodeChef,个人感觉类型和 Codeforces 类型差不多,奇怪的数据结构题比较多,提供中文
  • Vjudge,这个严格来说不算 OJ,有点一言难尽,上去看了就懂了

我校也有一个自己的 NSFZOJ,目前处于维,就不说了(逃

人类看得懂的教材

对于想了解 c++ 语法的同学,推荐《C++ Primer》;这本书有一个山寨版本《C++ Primer Plus》,写的特别烂,注意别踩雷。

对于初学者,推荐东京大学 acm 队三位选手所著、巫泽俊翻译的《挑战程序设计竞赛》。这本书也有一个奇怪的版本,一定要选译者是巫泽俊的。

对于国一以上水平的选手,推荐刘汝佳所著的《算法艺术与信息学竞赛》;这本书有两个坑点,一个是“聪明的读者到这里已经发现”,一个是后缀数组的代码是错的。

为什么我总是写不出/写错程序

OI 和其他比赛最大的不同是它同时要求思维和实现(implement),类比到其他竞赛就是同时要求思维和计算,但是计算和实现并不是等同的。

然根据笔者的了解,在其他竞赛中,往往是思维占据了解题的主要部分,很少有人的计算能力成为瓶颈;但在 OI 中,实现比思维更加重要。如果想不出题目还能随便写个程序骗一点分,如果想到了写不出只能爆零;你也不可能像数竞那样在结束前的最后几分钟想到解法一转攻势,这个时间在 OI 里恐怕只能写完输入输出。

笔者提升代码能力的方法是写很恶心的模拟题。举两个印象深刻的例子,一个是要求实现一个自动通关某种奇怪的 rpg 游戏的系统,一个是要求实现自动配平化学方程式。笔者当时自然是写到吐,但写完后再写普通题就觉得舒服了很多。后一个程序还用来水了点化学作业(雾

当然这个方法肯定不适合所有人,比如你可以写大数据结构什么的……这就不展开了。

如何通过 OI 脱单?

如果你知道一定要告诉我啊TAT

谢谢茄子

One more thing…

最后是一点私货。

本来这篇文章包含了很多我自己的经历和主观看法,但在最终版本中删除了绝大部分。一方面我是一个菜鸡,主观的东西写出来恐怕只能贻笑大方;另一方面是在和几位同样学竞赛的同学交流之后,发现我们自己对很多问题分歧就已经很大了,强行写出其中的一部分恐怕不能让人信服。

这段话反过来说就成了上文中“个人经验都只有参考价值”的原因。所以,在这个章节中,我将讨论自己对几个更加基础的问题的看法。

竞赛隐形的优势

竞赛很大程度上消除了你选择一个行业时的信息不对称。

几年前,清华某知名专业某教授兼院长兼副校长在网络上放出了自己的演讲,被来自五湖四海和五大湖四大洋的 PhD 狂喷,其中最集中的喷点就是在高考填报志愿时招生人员和社会舆论对于某知名专业的过度美化,或者说对于其物质待遇情况的隐瞒。

对于很多重心放在课内学业上的同学来说,大学选择什么专业是没有认真考虑过的事情。其中一些较为相信招生老师,于是选择了某些二十一世纪专业;另一些的确遵循了自己的理想,但上了大学之后发现此专业和自己设想的并不一样。

当然这是一篇介绍 OI 的文章,上文中所说的知名专业也不是计算机。简单来说,短时间内了解一个专业是很难的,而竞赛可以给你一两年的时间和几个大类的专业深入地打交道。这是很难得的机会,因为你的专业只能选一次,很大程度上将决定你一生的发展方向。

真正的粉丝

如果你是一个真正热爱着某门竞赛(比如 OI 吧)的同学,看到这一定会奇怪,这篇文章中一直在讨论功利的好处,只字未提情怀等等等等之类的东西……

对于我来说,如果我是一个真正的粉丝,要不要选择自己喜欢的竞赛甚至不能成为一个问题。一方面是兴趣的力量比想象的强大(至少我周围的粉丝都吊打我);另一方面是,如果你选择了另一个什么学科或是文化课,心中始终会留下一点点后悔,说不定哪天考试考挂了或者学不动了就爆发了,这种滋味很难受的。

当然,如果你的内心十分强大,那就随你便吧。

竞赛的意义

这是一个留给你自己的问题。

很多人并没有想清楚自己选择竞赛时想获得什么,所以多费了很多功夫,甚至搭上了自己的整个高中却一无所获。

为了升学有为了升学的玩法,文艺青年有文艺青年的玩法,泡妹的有泡妹的的玩法,粉丝有粉丝的玩法。

不要弄混,最好也别改来改去的。

到这本文就完了,希望能够对你有一些帮助,看个乐子也行,peace out

事实上是熬夜赶稿困的不行熬不住了才有了这个激寒结尾

溜了溜了 rua!

本作品采用 CC BY-NC-SA 4.0 Unported 进行许可
本文链接:https://dozbear.com/oi-intro/