极光算法二轮考核

极光算法二轮考核

算法端概况

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

学习道路：

通过第一学期的算法学习，顺利成为一名算法竞赛选手。
学习目标：通过科学的方式学习算法，向 ACM-ICPC（是计算机类竞赛最有含金量的比赛）奖牌冲锋。
在第二学期参加比赛，比赛中学习，学习中比赛，其中每年能够有多次外出公费比赛的机会（深圳，广州，北京，杭州，沈阳等）。

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

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

考核内容

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

C with STL （string，map，set）

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

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

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

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

位运算

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

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

排序

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

冒泡排序
归并排序
桶排序
快速排序
排序相关 STL
*排序应用

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;
}