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
Raw

北航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以及留下题解的助教们
  • 以及其他我见过博客交流过但是忘记了姓名的同学