一篇（正经的）Codeforces入门指南

今年ng秋招真的是地狱难度，lz也是挣扎数月侥幸上岸，现在终于有时间来搞一搞自己喜欢的东西。今天来给大家介绍一下除了LeetCode之外，另一个全球非常著名的竞赛向在线评测系统：Codeforces (codeforces.com).

众所周知，除了LeetCode之外，全世界还有许多非常优秀的OJ，比如国内的POJ，vjudge，洛谷，HDUOJ（好像被和谐了），BZOJ，牛客，计蒜客，ZOJ；国外的Codeforces，CodeChef，AtCoder，TopCoder等等。他们之中很多的题目难度、覆盖算法的广度、题目质量都远胜LeetCode。如果大家感觉在lc上学有余力，不满足于lc每周一次质量参差不齐的四题周赛，又或是对算法比较感兴趣，想学习更多和算法有关的知识，不妨来试试这个聚集全世界顶尖选手的竞赛平台Codeforces。
lz自己的lc周赛rating：

输入网址进入Codeforces首页。

顶部菜单栏可以看到一些选项，里面有几个会比较经常用到：
HOME：主页
GYM：一些非官方的比赛
CONTESTS：即将开始或者已经结束的官方赛事
PROBLEMSET：题库
RATING：所有用户的排名
HELP：比赛规则、测评环境等
HOME里面主要包含一些比较重要的posts，比如codeforces最近的更新、比赛的出题人对大家说的话等（虽然我只有遇到cf崩了或者题出bug回来点踩的时候会用到）。
点击菜单栏里面的CONTESTS进入比赛界面。

Codeforces的赛事机制非常有意思，和lc周赛有比较大的区别。首先可以注意到的是，cf的比赛时长一般都在两个小时以上，一般都在美国这边的上午、国内的晚上开始，每场比赛题目大概在六道左右。随着算法竞赛的推广，比赛的参赛人数也越来越多，时间比较合适的场次一般都会有超过两万人参加。
比赛根据难度分为Div1，Div2，Div3和Div4，其中Div1最难，Div4最简单（针对编程入门选手），一般来说Div1的第一题会是Div2的第三题，以此类推。Div3前几题的难度大致上和lc周赛差不多。每个选手和lc一样都会有一个自己的rating，不同分段的rating会有不同的颜色，rating，title和能参与的division的对应如下表所示：

所以如果你看到一个人的名字是红色的（红名爷），就可以扑上去喊大佬了。每个人也可以参加不属于自己分段的比赛（比如2100+分去打Div2），只不过不会参与排名。
Codeforces的比赛大致上可以分为两类：Codeforces Round和Educational Codeforces Round，两类比赛题目类型和难度差别不大，但在赛事规则上有所不同。
Codeforces Round：比赛采用积分制，每道题有初始分数，每过一分钟该分数都会下降，每次失败的提交（没过）这道题都会扣分，ac一道题的时候会获得这道题当前的分数，最后根据每个人得分总和排名。比赛进行时无法看到错误的样例。
每道题的测试数据会分为两类：preliminary tests和system tests。比赛过程中只会用pretests进行测试，也就是说即使通过了pretests也不能保证代码完全正确。比赛开始时，每个人会被随机分配到一个房间，一个房间大概有20人左右。在比赛过程中，当你的代码通过了pretests之后——如果你对你的代码正确性足够自信，就可以放弃re-submit的机会，lock你的solution，然后查看和你同一个房间的别的选手的代码并提供测试样例尝试对其进行hack。每次成功的hack（对方代码没过自己提供的样例）自己会获得100分，相应的失败的hack会扣50分，成功的hack数据会加入system tests。

赛后会对所有人ac的solution进行system test，也就是跑所有的样例，如果你的solution在system test没过（failed system test，也叫fst）则获得的相应分数会被扣除。Codeforces Round Div1和Div2采取这种赛制。
Educational Round：ICPC赛制，每道题不含分数，以过题数为第一关键字、每道题过题所花时间总和为第二关键字排名。同样地，每次失败的提交会有罚时。注意这里和lc不同，不是以比赛完成时间（写完最后一题时间）排名，而是每题所花时间总和。赛后会有12小时open hacking时间，可以查看并hack任何人的代码，所以同样有fst的可能。Educational Codeforces Round和Div3、Div4采取这种赛制。
点击PROBLEMSET可以进入cf题库。

每道题后面都会有tag和难度，数字越大代表题目越难。数字可以这样理解：如果一道题难度是2100，那代表一名2100的选手第一次见有50%的概率能做出这道题。
题目的覆盖类型非常非常多，竞赛向的算法/数据结构远比找工向要多且难，包括但不限于：AC自动机，后缀数组，树链剖分，FFT&NTT，狄利克雷卷积，杜教筛，插头dp，树套树，网络流，计算几何……按照单页题目数量*页数进行估计，Codeforces现在大约有8000+道题。
相比于LeetCode，Codeforces的题目更注重思维难度，不少题目都是需要花很多时间思考，实际落到代码上行数可能并不多，尤其是每个division前几题，可能用不着很高级的算法和数据结构，但需要自己多加思考（cf上有些构造题真的是一绝）。
还有每年绝对不能错过的愚人节专场，在里面你会遇到一些非常好玩的题目：

比如这个C题：

观察题目名字，发现正确的语序应该是And they lived happily ever after，所以答案是把输入的数字对应的bit位置交换。
另一个codeforces上非常有意思的是他的好友系统。每个人都可以关注别的选手（单向的，无需对方同意），然后在比赛中实时看到好友的排名（codeforces的榜单几乎是实时更新的，只有1-2min的延迟）。

所以比赛的另一大乐趣就是题目不会做了之后看你的好友和你一起坐牢（
当然也可以关注别的大佬看看自己和大佬的差距，比如当今算法竞赛真正的神，托爷tourist：

Codeforces有史以来唯一3900+选手，和第二有断层级的差距；14年包揽Facebook Hacker cup, TopCoder Open, Google Code Jam三大个人国际顶级程序竞赛冠军；2013、2015年两届ACM-ICPC World Final冠军，15年也是首次在World Final上的AK记录；其他各种奖项更是数不胜数（https://en.wikipedia.org/wiki/Gennady_Korotkevich）。
我的目标就是在tourist AK前做出第四题orz
Anyway，介绍的内容差不多到这里就结束了。算法的世界真的非常广阔，如果脱离面试的枯燥乏味（低质量的题目，毫无意义地追求O1 space和one-pass），仅把算法竞赛当作一个个人爱好——高兴了就学点新算法整理下模板，看不懂了不高兴了就明天再说，其实算法真的是一个很有意思的东西。把一个陌生的问题抽丝剥茧、转化成自己熟悉的算法模型，或者是在比赛的最后几分钟猜出结论然后过掉题目，这样的感觉光是想想就让人心潮澎湃。我永远怀念那段本科打比赛的时光——和队友一起深夜在学校活动室一边吃烧烤一边写题，没有生活中各种琐事的打扰，大家都很菜但是真的很快乐。
祝大家都能在做题中找到属于自己的乐趣：）

yoshua 发表于 2022-11-06 07:58:13
关注楼主很久了，偏题问一下，不知道楼主是上岸了tiktok吗？

上岸了开花堡开始躺平啦

現在竟然卷到力扣都不够用了

13年我还在读高中的时候为了模拟acm，熬夜打CF(坐牢)，当时tourist已经无敌了，没想到10年过去了，越来越牛逼了…

感谢干货。请问下最开始入门有没有什么刷题清单或者书之类的覆盖cf基本题型和模版。

yyds1995 发表于 2022-11-05 21:43:06
感谢干货。请问下最开始入门有没有什么刷题清单或者书之类的覆盖cf基本题型和模版。

清单好像没有……不过可以从cf比赛开始打，赛中不会的赛后去补题，当作查漏补缺

haha lc都刷不完 我就不刷这个了

残酷群友来帮顶

感谢lz推荐！cf确实不错就是时间对北美不是很友好

Erik_ 发表于 2022-11-05 23:46:14
感谢lz推荐！cf确实不错就是时间对北美不是很友好

对西海岸太早了

15年打acm的时候tourist神就已经封神了，没想到现在神威更甚lol

感谢大佬分享！
cf很多算法介绍太很棒的

感谢楼主分享，还挺有意思的