Skip to content

Latest commit

 

History

History
331 lines (198 loc) · 25.6 KB

README.md

File metadata and controls

331 lines (198 loc) · 25.6 KB

北航OJ通关攻略企划

authored by GoatGirl98

如果对本项目的相关内容有疑问,或者希望补充其余未开放的课程部分

欢迎联系邮箱[email protected]

先安利一下,真诚的希望各位看到这个项目的同学们能star一下这个project。如果你们觉得这个项目能对你在coding的学习方面带来帮助的话,也希望可以帮忙安利给其他的同学。帮忙贡献一下star的数量,冲一波业绩(bushi)

拜托各位了,这会给我考研面试以及后续的工作生活带来比较大的帮助!在此先谢过各位同学了!!!QAQ

重要声明

  • 由于整理工作量较大,可能有的题目忘记上传AC代码,或者出现题解思路有误的情况,一旦发现,请及时通过上述联系方式或者项目的Issue一栏及时联系笔者!

  • 本项目不会公开”算法分析与设计“系列课程的未开放题目,如果有意向补充其他部分开放的系列课程的题解,欢迎联系笔者进行Contribute

镜像链接

本项目不提供百度云的下载地址(毕竟限速= =)

提供gitee的镜像网址,对应项目会进行定期的不实时进度同步,主要是针对无法访问外网,以致于无法下载本项目的pdf材料的同学。

github网址: https://github.com/GoatGirl98/Walkthrough-of-ACCoding-in-BUAA

gitee镜像网址: https://gitee.com/goatgirl98/Walkthrough-of-ACCoding-in-BUAA

友情链接

友情链接1:https://github.com/Great-designer/BUAA-OJ-Project

上面是当前总过题榜三,1821的great_designer佬的北航OJ标程备份库。这位大佬致力于将所有C++程序的代码尽可能地转化为C语言,以方便信息大类和航空航天大类初学C语言的同学(自从北航OJ在17年面向全校授课之后,程序设计的限定语言由曾经的C++改为了现在的C),以及对C和C++语法转换较为困难的学生,因此而做的一个仓库,有需要的同学可以在看着本题解项目的同时参考一下他的项目。

(本人是总过题榜一,现在也有参与到项目的补完中哦,嘿嘿_(:з」∠)_ )

友情链接2:https://github.com/DanielW10001/advised_untold_techniques_for_cser

北航6系的同学看过来呀~初入CS坑必备的经验都是不可少滴,希望这个项目能够帮到你哦,嘿嘿_(:з」∠)_

顺便,算法我不收的,本项目不收录算法分析与设计课程的不对外开放题目...

当前施工进度

序号 课程名称 开放状态 更新进度
0 0-所有的A+B 完全开放 更新完毕
1 2015级-软件学院-C++程序设计 完全开放 更新完毕
2 2014级-软件学院-算法分析与设计 完全开放 更新完毕
3 2015级-软件学院-数据结构 完全开放 暂时更新完毕(日后会重构)
4 2016级-软件学院-C++程序设计 完全开放 更新完毕
5 2015级-软件学院-算法分析与设计 完全开放 更新完毕
6 2016级-软件学院-数据结构 完全开放 暂时更新完毕(日后会重构)
7 2017级-信息大类-程序设计基础训练 完全开放 更新完毕
8 2016级-软件学院-算法分析与设计 部分开放 更新完毕
9 2017级-航空航天大类-C语言程序设计* 部分开放 更新完毕
10 2017级-理科-大学计算机基础 部分开放 更新完毕
11 2018级-信息大类-程序设计基础训练* 部分开放 更新完毕
12 2017级-软件学院-算法分析与设计 部分开放 更新完毕
13 2018级-航空航天大类-C语言程序设计* 部分开放 更新完毕
14 2018级-理科-大学计算机基础 部分开放 更新完毕
15 2018级-软件学院-算法分析与设计 部分开放 更新完毕
16 2019级-信息大类-程序设计基础训练* 部分开放 更新完毕
17 2019级-航空航天大类-C语言程序设计* 部分开放 更新完毕
18 2019级-理科-大学计算机基础 部分开放 更新完毕
19 2019级-软件学院-离散数学2 不开放 更新完毕
20 2020秋-计算机导论(英文) 完全开放 更新完毕
21 2020级-信息大类-程序设计基础训练** 不开放 更新完毕
22 2020级-航空航天大类-C语言程序设计** 部分开放 更新完毕
23 2021春-沙河高校联盟课-C语言程序设计 部分开放 更新完毕
24 2021春-河南师范大学-Python语言程序设计 部分开放 更新完毕
25 2021级-信息大类-程序设计基础训练** 不开放 更新完毕
26 2021秋-计算机导论(英文) 不开放 更新完毕
27 2021级-航空航天大类-C语言程序设计** 部分开放 更新完毕
28 2021级-软件学院-离散数学2 完全开放 更新完毕
29 《C语言程序设计基础题解与实训指南》专项练习 未更新完毕 即将更新
30 Other-其他比赛 部分开放 随时更新

以下为大致的注意事项:

  • 题库地址为https://accoding.buaa.edu.cn ,本OJ为北航软件学院的第4代OJ,别称为“AC编程”或者“爱编程”(其前身第3代为acm.buaa.edu.cn)。当前OJ环境较为成熟稳定,面向全校授课。不过以防万一,还是需要声明,本题解项目在北航OJ更新至第5代之前将一直有效。
  • 所有本人整理的"部分开放"课程的更新完毕,表示现有的开放题目均已整理完毕,如果后续还有题目放出的话,则会随时跟进进度进行更新。
  • 标题带有星号的表示其他同学或者助教组整理的pdf格式或其他格式的题解,其余均为笔者本人所著,格式为md题解+源代码。(带两个星号即为又有助教组的又有本人写的)
  • 题解摆放方式与现在的北航OJ课程比赛命名方式类似,C开头代表上机,E开头代表练习赛。公开课程源代码根据题目编号命名,非公开课程源代码以对应比赛序号命名。
  • 由于后续课程名字的更新,导致命名稍有出入,“士谔书院”课程与“信息大类”的课程是完全一致的
  • 题解代码包括C C++ Python(大学计算机基础限定) 众所周知,任何C程序都是合法的C++程序,本题解相当多的C++程序只需要稍做改动即可用C语言编译通过。这需要同学对C++的一些基础知识有一定了解,并自行转换理解为C语言(并不难的,很多问题需要善用百度谷歌等搜索引擎以及博客哦~)。
  • 由于本人现已不在北航,获取信息渠道有限,故2022年秋季及之后的课程私有部分,本人将不再进行跟进更新。如果有同学希望对这部分进行整理贡献, 可以对联系笔者本人对仓库进行contribute,或者自己公开之后,在这边跟进仓库链接。

以下为重大的更新节点:

  • update20200703:添加17/18级航C以及18级程设的习题整理,感谢留下题解的助教组以及进行整理的冯如学部&士谔学部。

  • update20200724**:增加2017/2018/2019级这三届的理科类大学计算机基础的当前开放习题,但是并不是所有的题解全都是python代码,中间有部分C++代码,致真书院的同学需要对C++基础语法有一些了解才能有所理解,还望谅解

  • update20200926:上传了17程设脸熟赛压轴题 id753 来一场华丽的学级裁判吧 的题解+AC代码,至此,本项目收录课程的全部开放课程题目均可以AC,只需等待15和16数据结构上传完毕,题目的覆盖率即为100%

接下来的更新预告

  • 根据issue最新消息,2022年秋季之后的所有课程私有部分,将不再更新。
  • 2015级与2016级软件学院《数据结构》将会于近日进行重构,重构结束之后将删除原先的PDF文件
  • 2020年与2021年春季《高级算法设计与分析》将尽可能地给出对应题目的代码或者思路解析,并于之后更新
  • 2020年秋季到2022年春季这4个学期的课程私有部分,由于gitee链接随时有可能炸掉(或者改为私有),故提前进行上传备份
  • 《C语言程序设计基础题解与实训指南》专项练习,以及日后可能会出现的其他专项练习,会在题目更新完毕后统一更新

如果该OJ不再有更新的公开内容,则本项目在更新完上述内容后将会无限期停更(直至出现新的公开部分为止)

本项目的用途

本项目旨在对北航软件学院OJ——accoding.cn的完整课程的习题进行整理,并且形成一个较为完整的开放式题解查询数据库。(这也是为什么我没选择博客而是选择了github的原因)

本OJ虽然现阶段为对外开放的状态,但是由于其用途主要在于进行校内课程的教学,所以并不能像那些用于练习与学习OI/XCPC知识的OJ那样,开放测试数据/题解/他人AC代码。

然而每当课程结束,其他同学想通过练习往届题目来提升自己的时候,却很多时候会因为对相关知识点不熟悉,或者卡在了一些非常细节的地方,AC苦手。投入足够多的时间却没有本质上的提升,会在学习兴趣上受到相当大的打击。

作为曾经经历过希望与绝望、喜悦与悲伤,被虐的死去活来却又依旧坚守在OJ前线,随时等待新题或者新比赛的开放的一位默默无闻的北航本科生,我非常可以理解这样的痛楚。

于是乎,笔者将自己这9个月以来在OJ所做过的全部题目进行上传。前人栽树后人乘凉,这也是我开启这个项目的初衷吧。哪怕知道自己是那么的渺小,我依旧希望能在哪里留下自己来过的痕迹,希望为后辈们做些什么,尽自己的绵薄之力。(其实,另外一个原因,还是希望能增加一个自己的阅历,争取考研复试的时候有一个加分项呀QAQ前提得是先能过初试再说T^T。)

至于题解的可靠性?不用担心。

笔者目前AC题目数量已达到1300左右,总过题数为排行榜第1 (前榜一的Kevin大神也是我之前一直学习的对象,他的博客对我的启发也非常大)。除去北航程序设计竞赛以及XCPC选拔赛(这一部分并不会在本项目中收录,笔者部分AC的代码已上传到隔壁的BUAAOJ图鉴当中,可前往对应项目进行查看),剩余的开放题库,笔者可以保证题解的100%覆盖(即一题不漏)。比较遗憾的是,笔者没有尽早意识到算法的重要性,而是在大三开设算法课之后才集中训练算法,错过了参加XCPC的大好时机,现在只能重心放在考研上,码力慢慢保持和提升了。

本项目的适用人群

  • 北京航空航天大学,正在学习信息类程序设计基础训练/航空航天类C语言程序设计/理科类大学计算机基础/信息类数据结构/软件学院算法分析与设计的本科生

  • 准备转入软件学院机试的北航本科生,准备保研机试的软件学院大四本科生,准备北航软件学院考研复试环节(初试专业课代码991)的考生

  • 其他希望在本OJ进行学习程序设计与算法或者来划划水的学生或者社会人士

课程难度比较

我们根据程序设计/数据结构/算法这3个档次来进行划分,其中信息类的程序设计和航空航天类的C语言可以基本等价地看做同一难度,其中前者会稍微更难一些。

那么在这些难度内部,笔者将会进行大致的横向对比,以供后人参考,并制定自己的练习攻略。

程序设计: 17级程设 < 15级C++ < 18级程设 < 16级C++ < 20级程设 < 19级程设

17年为大类试水的第一年,为了照顾大类同学的普遍水平,17年是最简单的一年

15年较为综合,各种基础训练,模拟类型的题,结构体,字符串处理,以及基础的动态规划相继出现,题库规模最大,题目难度分布均匀,基本等价于19年程设的容量,适合参考

16年较为创新,出现了八数码变种,数独搜索,图论等不太适合初学C语言者直接做的题目。在边界数据构造的思考锻炼上堪称一绝。题目难度分布两极分化,最难的题目与15级相当,但是想要在一道题中拿到满分,非常困难。

从18级开始本课程基本恢复了原有的难度水平,且能被同学们普遍接受,就是当17级的助教逐渐被18级助教取缔之后,题目难度开始一点点地越来越离谱了...

数据结构:15级数据结构 < 16级数据结构

由于17年大类招生开始施行,软件学院数据结构这门课程已经绝种。但是如果需要准备算法或者工作面试等,这门课程的知识集必不可少。相当多的内容在信息类数据结构中是学不到的。但是同样的,并不完全适合初学数据结构以及未接触过C++的同学直接尝试,请量力而行。

由于这门课程的开设时间是大一下,且上机的考查知识点有限,不会出现平衡搜索树与左式堆等数据结构,不会对开散列与闭散列的具体实现进行考察。

15年的题目较为综合,基本上囊括了数据结构基础内容。二叉树与广义表,二叉搜索树,KMP串匹配,最短路,并查集,最小生成树,拓扑排序应有具有,最难的题目在于线段树/树链剖分。知识点覆盖广泛,适合练习。

16年的题目较15年难出了许多,在15年的知识点进行浓缩的基础上,添加了许多新的题目,包括寻找规律,数论,数组操作,组合数学,以树为背景的计数dp,二分图的基础知识。

个人建议15级题库全部做完后再做16级。

算法分析与设计:14级算法 = 15级算法 < 16级算法 < 17级算法 < 18级算法 < 19级算法

全部开放的14和15级算法基本类似,考察点均为dp,贪心,摊还分析,二分图最大匹配,最大流的简单应用,图论的其他算法,快速傅里叶变换,计算几何。14/15级两个题库相辅相成,为对方所缺失的知识点进行补充。

P.S. 完全开放部分的习题仅用于参考,适合个人在私下练习的时候进行能力的提升。难度与现在课程的难度完全没有可比性。在课程难度的趋势上,基本遵循摩尔定律。

(以算法为例,课程安排都是固定的,虽然期末会调分,但是期末考试并不局限于这些知识点,比如说高精、快速幂等知识同样可能出现。19级程设的练习题难度也早就甩出15级的题目几条街了。)

本项目的一些注意事项

Q:如何查询题目代码?

A:首先查看本题对应的课程名称,再查找其对应的课程比赛,并且查询题解

Q:题解将会以什么样的形式放出?

A:每个课程比赛的文件夹当中,会出现readme的预览,题解思路将会写在这里。代码将会以c/cpp的形式单独存放,标注名称为题目的编号id(开放题目)或对应比赛序号(未开放题目)而非题目名称

Q:我需要到什么样的水平才能理解题解呢?

A:本题解不会像其他博客那样详细介绍编程语言和算法模板与细节,仅提供大致的知识点Tag和解题思路。这需要读者对C/C++的语法和库函数有一个大致的了解,仍处于C语言学习阶段的北航本科生需要自学C++的部分知识,并对C++题解进行转换,达到自己可以理解的程度为止。而对于题解给出的知识点,需要读者对其他博客进行查阅与进一步深入的学习。

再次强调:侃侃而谈不可取,通过AC的代码,你可以学习并且理解很多使用的技巧与知识。

Talk is cheap, show me the code.

Q:如果按照AC代码进行编写,甚至是几乎全篇抄过来,依旧会出现MLE/TLE等问题,如何解决?

A:部分问题将会在下一模块进行介绍,如果下面的问题无法帮到你的话,则很有可能是由于题目限制条件过于老旧,而评测机的环境更新,导致本题在现在的环境下根本无法AC。此时需要联系网站的管理员进行修复。现任管理员的邮箱:[email protected] OJ常年有团队进行维护与更新,要相信我们的管理员哥哥姐姐们呀~

北航OJ的一些注意事项

通过这几个月的摸爬滚打,笔者将会把北航OJ的一些注意事项进行汇总,尽量能避开这些坑就避开

1.对于一些空间限制较低的题出现MLE

尽量不要使用C++的STL库与iostream库的输出,一旦构造了对应的对象,使用了对应的方法,内存空间占用会瞬间涨至3000KB以上。另外,scanf/printf的参数也会带来内存提升的问题,建议使用putchar/getchar来优化卡常

2.在时间复杂度没有问题的情况下出现不合常理的TLE

首先这个时候,检查一下是否使用了C++的cin和cout,while(cin >> x)的句式在一年前是最容易引发TLE的,建议加上以下两条语句

ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

另外,对于部分题目,直接使用cout输出也会无理由TLE。这里建议,如果非要使用C++的字符串处理,那么就先scanf,再对读入char数组调用string构造函数,输出的时候采用printf输出c_str()

另外还有一个原因

在取最大值最小值的时候,不要使用

std::max(a,b)

或者

#define Max(a,b) ((a)>(b)?(a):(b))
Max(a,b)

请老老实实地用if-else语句判断,否则会TLE

3.采用正则匹配会无法通过编译

嗯,别想了。虽然北航OJ支持C++14的语法,但是regex库是全面禁止的。不过你要是用java的话,嗯还是能过的。但是北航OJ对于其他语言并没有提升时间空间限制,所以...慎用吧

4.涉及字符串处理问题时出现莫名其妙的WA/PE

由于评测机的环境是linux(比如清华OJ的配置环境就是ubuntu16.04),所以会出现\r的情况

所以在使用getline/fgets/fread等函数的时候,如果本题偏向于字符串处理,请务必吃掉字符串末尾的\r

如果不是这个问题,而且是字符串问题的PE的话,那基本可以直接当WA来看,请修改自己的程序

5.部分题目仅允许使用C语言/Python怎么办?

不难解决,只需要使用可以支持前端网页修改的浏览器,点击F12进入编辑模式,在html中搜索“语言选择”一栏,并根据对应的格式,添加你想使用的语言即可。

6.一些老题使用Python总是WA怎么办?

首先,Python是一种纯解释型的语言,这也就导致其无法报出WA以外的任何错误(正常运行的情况下可以报出PE),远古题库开放的Python语言应该是Python2而非Python3,请务必注意这点,如果需要提交Python3,请修改提交代码页面的前端元素。

7.采用printf输出long long出现问题怎么办?

请注意,北航OJ采用printf的输出方式如下:

printf("%lld\n", a);

与hdu等oj不太一样,请尽量不要使用I64d这样的形式。

我自己遇到的,大概就这些吧,如果还有其他问题,欢迎私信补充。

关于Honor Code

在北航校内的课程,严禁在上机过程中串通作弊,具体细节请查看《学生手册》关于学术不端与考试违纪的相关章程。

同样的,对于已经结束的课程,也不要提交与题解重合度极高的代码,请勿将本仓库的代码直接复制粘贴,用来无意义地刷过题量,否则账号有可能遭到封禁处罚。

勿谓言之不预也!

update1003:关于校内课程有关串通作弊相关问题的更新

现在程设和算法的平时分占30%,只要每一次上机和练习赛做对1题即可获得满分的平时分,仅相当于上课签到的作用。是否抄袭都已经毫无意义,作为成年人,希望各位同学可以做到不自欺欺人,好好利用课程内的题库来锻炼,提升自己,以在最后的70%期末考试中获得满意的成绩。

关于作弊,举一个宋友老师分享的例子...

UC Berkeley的教授Brian Harvey在课堂上向他的学生解释为什么不要作弊,不是因为“作弊会对别的学生不公平”,也不是“作弊会败坏学校的风气”,而是作弊最终会把你困在一个自己不擅长也不喜欢的职业,困住你真正的人生追求。

靠作弊得高分,不会伤害老师,也不会伤害其他同学,最终只会伤害自己。

也正是因为宋友老师分享的这个例子,让我个人更加敬重这位老师了。将上机和练习赛的竞争性淡化,为学生指出应有的学习方向,通过平时的互相交流,让学习过程中的你放心大胆地“抄”,通与同学互相交流互相分享,通过其他丰富的开源学习社区的学习资源,通过一点点地”抄“他人的代码或者算法模板,一点点地构建属于自己的知识体系(毕竟前辈们所留下的智慧,并不是靠自己闭门造车就能学会的),并在最终验收你的学习成果。无论是程设还是算法,从咿呀学语到对课程内容有大概的了解与认识,这样做的目的都是希望你可以以这里为踏板,迈向更广阔的天空。

望同学们务必珍惜这样开放的课程环境和学习氛围**,以及课程内质量极高的开源题库。专心于像更好的人与代码虚心地学习,最终一定会有验收学习成果的机会供你展示自己的所学所得(如果没有,那是课程自己的问题)。知识就摆在那里是真正的通过一道道好题学到东西,还是通过毫无意义的刷过题量来获得一时的快感,希望各位心中都有一个正确的答案。**

法律声明

虽然我知道不可能有人在乎这个,但是我还是需要提一下的

不会真有人觉得这项目会在北航火起来吧,不会吧不会吧不会吧?

本题解项目与accoding.cn的现有开放题目,完全免费,对社会开放,没有任何盈利性质。禁止任何个人或者机构(尤其是考研机构)对本项目或评测网站的内容进行盗取并用于盈利。一旦被发现,笔者有权追究其法律责任。

同样的,题库的版权归北航各课程组所有,禁止个人或团体进行抄袭或搬运。

(不过到处为北航学生或者考研党们进行免费的安利还是非常欢迎滴~

本项目所采用的协议 : CC-BY-NC-SA-4.0 ((Creative Commons BY-NC-SA 4.0) 知识共享署名 - 相同方式共享 4.0 国际许可协议)

本项目自身针对其他开源性知识产权的版权态度说明

update:2021-02-05

最近由于笔者面临毕设在即,加之未来的研究生规划带来的对于学术道德的一系列思考,笔者在此声明对其他开源性知识产权的态度

  • 本项目无意对其他开源的题解报告与博客进行抄袭,实际上在本项目成立之初已经将所有参考过的题解的所有者,一一放入了致谢名单,对于未公开课程的题解,也注明了gitee链接与其他出处

  • 本项目接下来将在有时间的情况下,具体落实到每一道题目,如果思路有参考本地的题解或者博客网址,将会补充注明参考的题解所有者或者博客链接

  • 欢迎各位同学在参考本题解项目的时候,对本项目进行监督,如果发现了本项目中的部分题解与其他网络题解思路重合,欢迎通过issue或者上述联系方式通知笔者本人,经过笔者确认为曾经参考过的资源之后,将会进行标注。

致谢名单

我在北航OJ进行历练的旅途当中,少不了这些人的存在。其中很多人都素未谋面,也有可能没有联系方式,甚至是素不相识。但是在向他们直接或者间接的学习当中,我收获到了很多东西,对于很多未学到的知识和不会的题都有了一个全新的认知。了解到了当年的前辈们在学些什么之后,瞬间觉得自己非常的渺小了。正是有了这些前辈后辈,有了与他们的充分交流,或是他们留下来的题解资源,才使得现在的题解仓库可以如此完整。也有很多的有志之士,也希望做出自己的一份贡献,无论是否有帮上忙,都应该为这份心意致敬。在此向以下的北航本科生致谢。

(下列名单的4位代码为入学年份+系号 名字均由网名或者名称缩写代替 排名不分先后)

  • 1006 DShawn
  • 1421 shiyi microhhh Magry 王木木
  • 1521 轻型王助教 modricWang mdd gzh DH AlvinZH redundant bamboo
  • 1606 coldwater gst
  • 1621 TQ QZZ yhy
  • 1706 影佑 QQL zhuziyu-edward MountVoom
  • 1721 rty mogg 宿命的轮回者
  • 1806 dragonLee potassium
  • 1818 空游无所依
  • 1821 wy qrn yhb aikx Kevin00 qxforever Great-designer
  • 1906 Pantw dhy2000
  • 1921 我要回幼儿园当学霸 小迷弟
  • 1942 流转起舞
  • 2002 凉宫秋月
  • 各位在出题前线brainstorm以及留下题解的助教们
  • 以及其他我见过博客交流过但是忘记了姓名的同学