極光算法二輪考核

極光算法二輪考核

算法端概況

獲獎情況：算法端曾榮獲藍橋杯國一3次、國二和國三多次，今年首次參加的比賽獲得：睿抗國一，中國高校計算機大賽——團體程序設計天梯賽團隊及個人國三，百度之星銀獎等。

學習道路：

通過第一學期的算法學習，順利成為一名算法競賽選手。
學習目標：通過科學的方式學習算法，向 ACM-ICPC（是計算機類競賽最有含金量的比賽）獎牌沖鋒。
在第二學期參加比賽，比賽中學習，學習中比賽，其中每年能夠有多次外出公費比賽的機會（深圳，廣州，北京，杭州，沈陽等）。

參加的主要賽事（A類賽事或企業認可度高的賽事）：

比賽	日期	賽制
藍橋杯	4/6月	OI
天梯賽	4月	IOI
廣東省大學生程序設計競賽	5月	ACM
國際大學生程序設計邀請賽 & 中國大學生程序設計邀請賽	5月	ACM
?？?/td>	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;
}