极光算法二轮考核

• 极光算法二轮考核
  • 算法端概况
    • 考核内容
  • C with STL （string，map，set）
  • 位运算
  • 排序
  • 二轮考核练习

算法端概况

1. 获奖情况 ： 算法端曾荣获蓝桥杯国一3次、国二和国三多次，今年首次参加的比赛获得：睿抗国一，中国高校计算机大赛——团体程序设计天梯赛团队及个人国三，百度之星银奖等。

2. 学习道路：

   1. 通过第一学期的算法学习，顺利成为一名算法竞赛选手。

   2. 学习目标 ：通过科学的方式学习算法，向 ACM-ICPC（是计算机类竞赛最有含金量的比赛）奖牌冲锋。

   3. 在第二学期参加比赛，比赛中学习，学习中比赛，其中每年能够有多次外出公费比赛的机会（深圳，广州，北京，杭州，沈阳等）。

   参加的主要赛事（A类赛事或企业认可度高的赛事）：

   比赛	日期	赛制
   蓝桥杯	4/6月	OI
   天梯赛	4月	IOI
   广东省大学生程序设计竞赛	5月	ACM
   国际大学生程序设计邀请赛 & 中国大学生程序设计邀请赛	5月	ACM
   睿抗	7/8月	IOI
   百度之星	8/9月	ACM
   国际大学生程序设计区域赛 & 中国大学生程序设计分站赛	10/11月	ACM

   考核内容

   1. 机试，洛谷平台比赛IOI赛制 ：https://www.luogu.com.cn/
   2. 笔试，描述冒泡排序，归并排序，桶排序，快速排序的思想及应用，不需要写出代码

C with STL （string，map，set）

C++基础 学习网址 ： https://oi-wiki.org/lang/

1. Hello, World!
2. C，C++的输入输出
3. 变量
4. 运算
5. 流程控制语句
6. 高级数据类型
7. 函数
8. string
9. map，set(C++ 标准库 -> STL容器 -> 关联式容器)

推荐的学习视频：程序设计与算法（一）C语言程序设计 ： https://www.icourse163.org/course/PKU-1001553023

课后练习做他这个和我们都是一样的，但这个课程配套OJ太老了，还是推荐下面练习的题单

红色圈起来的部分是和考核强相关的，没圈起来并不意味着不重要

位运算

位运算 学习网址 ： https://oi-wiki.org/math/bit/

1. 与、或、异或
2. 取反
3. 左移和右移
4. 复合赋值位运算符
5. 关于优先级
6. 位运算的应用
   1. 有关 2 的幂的应用
   2. 判断两非零数符号是否相同
   3. 换两个数
   4. 操作一个数的二进制位
7. *内建函数（选学）

排序

排序 学习网址 ：https://oi-wiki.org/basic/sort-intro/

1. 冒泡排序
2. 归并排序
3. 桶排序
4. 快速排序
5. 排序相关 STL
6. *排序应用

Q ：排序的循环，递归都好抽象？我该如何快速掌握排序的算法？

A： 学习算法的快速方法就是将程序每次的执行过程打印出来，看出其交换元素或递归区间的改变，详细见代码块。

以冒泡排序为例，在学习其算法思想后，将每一阶段交换的位置及代码打印出来，或对着代码用纸笔模拟排序过程有助于掌握算法。

Q ：好多排序呀！这么多排序算法竞赛真的用的上吗？要不要学那么多，哪个排序最快，是不是会一个就够了？

A ： 各种排序都有其独特的应用场景，冒泡排序和归并排序经常处理有关逆序对的问题；归并排序和快速排序用到了分治，递归的思想，学习这个排序是为了初探分治，递归，让自己能写出具有分治和递归的算法；桶排序元素的值映射到数组下标上，在特定应用背景下和后面学习权值线段树中会用到；平时更多用到的是 sort(a + 1, a + 1 + n); ，这个功能很强大，对于string, pair,array,和重载了远算符的结构体也能进行排序，所以会在二轮考核的机试中考核 sort(); ，笔试中考察能否正确描述冒泡排序，归并排序，桶排序，快速排序的思想。

#include <bits/stdc++.h>

using namespace std;

int n = 5;
int a[10] = {0, 3, 4, 5, 1, 2};
int main()
{
    cout<<"init array : "<<a[1]<<" "<<a[2]<<" "<<a[3]<<" "<<a[4]<<" "<<a[5]<<'\n';
    cout<<'\n';
    for(int i = 1; i < n; i++)
    {
        for(int j = 1; j <= n - i; j++)
            if(a[j] > a[j + 1])
            {
                swap(a[j], a[j + 1]);
                cout<<"swap : ";
                cout<<"i : "<<i<<"  j  : "<<j<<'\n';
                cout<<a[1]<<" "<<a[2]<<" "<<a[3]<<" "<<a[4]<<" "<<a[5]<<'\n';
                cout<<'\n';
            }
    }
    cout<<"end sort : "<<a[1]<<" "<<a[2]<<" "<<a[3]<<" "<<a[4]<<" "<<a[5]<<'\n';
    return 0;
}

二轮考核练习

题单 ：https://www.luogu.com.cn/training/380528

注意！这个题单是动态更新的，对于题号CF或者AT开头的题目，需要你去题目来源网站注册账号，提交submit

对于不会的题目，可以再想想，也可以看题解或者在群里面问。