Algorithm Memo

Several STL functions

Read Fast!

Close the synchronous stream if you want to use cin/cout.

or just simply use the read() func:

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return x * f;
}

Remember to change this if the number is very large:

inline long long read() {
    long long x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return x * f;
}

And you should use cout << '\n'; instead of cout << endl;!

Sort very quickly

#include <iostream>
#include <cstdlib> // 用于 std::rand 和 std::srand
#include <ctime>   // 用于 std::time

// 模板函数：快速排序的核心函数，用于分区
template <typename T>
long long partition(T* arr, long long low, long long high) {
    // 随机选择基准值
    long long random_pivot_index = low + rand() % (high - low + 1);
    swap(arr[low], arr[random_pivot_index]); // 将随机选择的基准值放到第一个位置

    // 正常的分区逻辑
    T pivot = arr[low];
    long long i = low + 1;  // i 指向当前处理的元素
    long long j = high;     // j 指向末尾元素

    while (true) {
        // 向右移动 i，直到找到大于 pivot 的元素
        while (i <= j && arr[i] <= pivot) {
            i++;
        }
        // 向左移动 j，直到找到小于等于 pivot 的元素
        while (i <= j && arr[j] > pivot) {
            j--;
        }
        // 如果 i 和 j 交错，则停止循环
        if (i >= j) {
            break;
        }
        // 交换 arr[i] 和 arr[j]
        swap(arr[i], arr[j]);
    }
    // 将基准值放到正确的位置
    swap(arr[low], arr[j]);
    return j; // 返回基准值的最终位置
}

// 模板函数：快速排序的递归实现
template <typename T>
void quick_sort(T* arr, long long low, long long high) {
    if (low < high) {
        // 获取分区点
        long long pivot_index = partition(arr, low, high);
        // 对左子数组进行快速排序
        quick_sort(arr, low, pivot_index - 1);
        // 对右子数组进行快速排序
        quick_sort(arr, pivot_index + 1, high);
    }
}

Remember to use srand(time(0)); in your main function!

Several STL containers

Vector

#ifndef SJTU_VECTOR_HPP
#define SJTU_VECTOR_HPP

#include "exceptions.hpp"
#include <climits>
#include <cstddef>
#include <cmath>
#include <cmath>
#include <cstring>
#include <memory>

namespace sjtu {

/**
 * a data container like std::vector
 * store data in a successive memory and support random access.
 */
template<typename T>
class vector {
private:
    T *data; // for data storage
    size_t current_size; // the size of vector
    size_t max_size; // default value is 16

    /**
     * @brief expand the memory (the maxsize and data) to its double size
     * 
     * just expand the memory without allocating new members
     */
    void expandDouble() {
        std::allocator<T> alloc;
        size_t new_max_size = max_size * 2;
        T* new_data = alloc.allocate(new_max_size);

        // move to the new memory space
        for (size_t i = 0; i < current_size; ++i) {
            std::construct_at(new_data + i, std::move(data[i]));
            std::destroy_at(data + i);
        }

        // release old memory
        if (data) {
            alloc.deallocate(data, max_size);
        }

        // update the pointer
        data = new_data;
        new_data = nullptr;
        max_size = new_max_size;
    }

public:
    /**
     * @brief Tool function, delete all the elements but does not free the memory
     */
    void clear() {
        std::allocator<T> alloc;
        for (size_t i = 0; i < current_size; ++i) {
            std::destroy_at(data + i);
        }
        current_size = 0;
    }

public:
    class const_iterator;

    class iterator {
        // The following code is written for the C++ type_traits library.
        // Type traits is a C++ feature for describing certain properties of a type.
        // For instance, for an iterator, iterator::value_type is the type that the
        // iterator points to.
        // STL algorithms and containers may use these type_traits (e.g. the following
        // typedef) to work properly. In particular, without the following code,
        // @code{std::sort(iter, iter1);} would not compile.
        // See these websites for more information:
        // https://en.cppreference.com/w/cpp/header/type_traits
        // About value_type: https://blog.csdn.net/u014299153/article/details/72419713
        // About iterator_category: https://en.cppreference.com/w/cpp/iterator
    public:
        using difference_type = std::ptrdiff_t;
        using value_type = T;
        using pointer = T*;
        using reference = T&;
        using iterator_category = std::output_iterator_tag;

    private:
        T* ptr; // the pointer
        vector<T>* which_vector; // judge whether two pointers are pointing to the same vector

    public:
        // constructor
        iterator(T* ptr_, vector<T>* which_vec) : ptr(ptr_), which_vector(which_vec) {}

        iterator operator+(const int& n) const {
            iterator tmp = iterator(ptr + n, this->which_vector);
            if (tmp < (*which_vector).begin() || (*which_vector).end() < tmp) {
                throw invalid_iterator();
            }
            return tmp;
        }

        iterator operator-(const int& n) const {
            iterator tmp = iterator(ptr - n, this->which_vector);
            if (tmp < (*which_vector).begin() || (*which_vector).end() < tmp) {
                throw invalid_iterator();
            }
            return tmp;
        }

        // return the distance between two iterators,
        // if these two iterators point to different vectors, throw invalid_iterator.
        int operator-(const iterator& rhs) const {
            if (which_vector != rhs.which_vector) {
                // two iterators point to different vectors!
                throw invalid_iterator();
            }
            return ptr - rhs.ptr;
        }

        /**
         * @brief let the iterator to move towards n steps
         * 
         * @param n 
         * @return iterator& 
         */
        iterator& operator+=(const int& n) {
            ptr += n; // movement
            if (*this < (*which_vector).begin() || (*which_vector).end() < *this) {
                throw invalid_iterator();
            }
            return *this;
        }

        iterator& operator-=(const int& n) {
            ptr = ptr - n;
            if (*this < (*which_vector).begin() || (*which_vector).end() < *this) {
                throw invalid_iterator();
            }
            return *this;
        }

        iterator operator++(int) {
            iterator temp = *this;
            ++ptr;
            return temp;
        }

        iterator& operator++() {
            ++ptr;
            if (*this < (*which_vector).begin() || (*which_vector).end() < *this) {
                throw invalid_iterator();
            }
            return *this;
        }

        iterator operator--(int) {
            iterator tmp = *this;
            --ptr;
            return tmp;
        }

        iterator operator--() {
            --ptr;
            if (*this < (*which_vector).begin() || (*which_vector).end() < *this) {
                throw invalid_iterator();
            }
            return *this;
        }

        T& operator*() const {
            return *ptr;
        }

        bool operator==(const iterator& rhs) const {
            return (which_vector == rhs.which_vector) && (ptr == rhs.ptr);
        }

        bool operator==(const const_iterator& rhs) const {
            return (which_vector == rhs.which_vector) && (ptr == rhs.ptr);
        }

        bool operator!=(const iterator& rhs) const {
            return !(*this == rhs);
        }

        bool operator!=(const const_iterator& rhs) const {
            return !(*this == rhs);
        }

        bool operator<(const iterator& rhs) const {
            return (*this - rhs) < 0;
        }
    };

    class const_iterator {
    public:
        using difference_type = std::ptrdiff_t;
        using value_type = T;
        using pointer = T*;
        using reference = T&;
        using iterator_category = std::output_iterator_tag;

    private:
        const T* ptr;
        const vector<T>* which_vector;

    public:
        const_iterator(const T* p, const vector<T>* which_vec) : ptr(p), which_vector(which_vec) {}

        const_iterator operator+(const int n) const {
            return const_iterator(ptr + n);
        }

        const_iterator operator-(const int n) const {
            return const_iterator(ptr - n);
        }

        int operator-(const const_iterator& rhs) const {
            if (which_vector != rhs.which_vector) {
                throw invalid_iterator();
            } else {
                return ptr - rhs.ptr;
            }
        }

        const_iterator& operator+=(const int& n) {
            ptr = ptr + n;
            return *this;
        }

        const_iterator& operator-=(const int& n) {
            ptr = ptr - n;
            return *this;
        }

        const_iterator operator++(int) {
            const_iterator temp = *this;
            ++ptr;
            return temp;
        }

        const_iterator& operator++() {
            ++ptr;
            return *this;
        }

        const_iterator operator--() {
            --ptr;
            return *this;
        }

        const_iterator operator--(int) {
            const_iterator tmp = *this;
            --ptr;
            return tmp;
        }

        T operator*() const {
            return *ptr;
        }

        bool operator==(const const_iterator& rhs) const {
            return ptr == rhs.ptr;
        }

        bool operator==(const iterator& rhs) const {
            return ptr == rhs.ptr;
        }

        bool operator!=(const iterator& rhs) const {
            return !(*this == rhs);
        }

        bool operator!=(const const_iterator& rhs) const {
            return !(*this == rhs);
        }
    };

    /**
     * @brief Construct a new vector object (default)
     */
    vector() : current_size(0), max_size(16) {
        // default
        std::allocator<T> alloc;
        data = alloc.allocate(max_size);
    }

    /**
     * @brief Construct a new vector object
     * 
     * @param size_
     */
    vector(size_t size_) {
        current_size = 0;
        max_size = (current_size < 16) ? 16 : current_size;
        std::allocator<T> alloc;
        data = alloc.allocate(max_size);
    }

    vector(const vector& other) {
        current_size = other.current_size;
        max_size = other.max_size;
        std::allocator<T> alloc;
        data = alloc.allocate(max_size);
        for (int i = 0; i < current_size; ++i) {
            std::construct_at(data + i, other.data[i]);
        }
    }

    ~vector() {
        clear(); // destroy all data, not release memory
        if (data) {
            std::allocator<T> alloc;
            alloc.deallocate(data, max_size);
        }
    }

    /**
     * @brief assignment operator
     * 
     * @param other 
     * @return vector& the assigned operator
     */
    vector<T>& operator=(const vector& other) {
        if (this != &other) {
            clear();
            std::allocator<T> alloc;
            if (data) {
                alloc.deallocate(data, max_size);
            }
            data = alloc.allocate(other.max_size);
            max_size = other.max_size;
            current_size = other.current_size;
            for (size_t i = 0; i < current_size; ++i) {
                std::construct_at(data + i, other.data[i]);
            }
        }
        return *this;
    }

    /**
     * assigns specified element with bounds checking
     * throw index_out_of_bound if pos is not in [0, size)
     */
    T& at(const size_t& pos) {
        if (pos < 0 || pos >= current_size) {
            throw index_out_of_bound();
        } else {
            return data[pos];
        }
    }

    const T& at(const size_t& pos) const {
        if (pos < 0 || pos >= current_size) {
            throw index_out_of_bound();
        } else {
            return data[pos];
        }
    }

    /**
     * assigns specified element with bounds checking
     * throw index_out_of_bound if pos is not in [0, size)
     * !!! Pay attentions
     *   In STL this operator does not check the boundary but I want you to do.
     */
    T& operator[](const size_t& pos) {
        if (pos < 0 && pos >= current_size) {
            throw index_out_of_bound();
        } else {
            return data[pos];
        }
    }

    const T& operator[](const size_t& pos) const {
        if (pos < 0 && pos >= current_size) {
            throw index_out_of_bound();
        } else {
            return data[pos];
        }
    }

    /**
     * access the first element.
     * throw container_is_empty if size == 0
     */
    const T& front() const {
        if (current_size == 0) {
            throw container_is_empty();
        } else {
            return data[0];
        }
    }

    /**
     * access the last element.
     * throw container_is_empty if size == 0
     */
    const T& back() const {
        if (current_size == 0) {
            throw container_is_empty();
        } else {
            return data[current_size - 1];
        }
    }

    /**
     * returns an iterator to the beginning.
     */
    iterator begin() {
        if (empty()) {
            throw container_is_empty();
        }
        iterator tmp(data, this);
        return tmp;
    }

    const_iterator begin() const {
        if (empty()) {
            throw container_is_empty();
        } else {
            const_iterator tmp(data, this);
            return tmp;
        }
    }

    const_iterator cbegin() const {
        if (empty()) {
            throw container_is_empty();
        } else {
            const_iterator tmp(data, this);
            return tmp;
        }
    }

    /**
     * returns an iterator to the end.
     */
    iterator end() {
        if (empty()) {
            throw container_is_empty();
        } else {
            iterator tmp(data + current_size, this);
            return tmp;
        }
    }

    const_iterator end() const {
        if (empty()) {
            throw container_is_empty();
        } else {
            const_iterator tmp(data + current_size, this);
            return tmp;
        }
    }

    const_iterator cend() const {
        if (empty()) {
            throw container_is_empty();
        } else {
            const_iterator tmp(data + current_size, this);
            return tmp;
        }
    }

    /**
     * checks whether the container is empty
     */
    bool empty() const {
        return current_size == 0;
    }

    /**
     * returns the number of elements
     */
    size_t size() const {
        return current_size;
    }

    /**
     * inserts value before pos
     * returns an iterator pointing to the inserted value.
     */
    iterator insert(iterator pos, const T& value) {
        // getting the inserted index
        const size_t index = pos - (this->begin());
        return insert(index, value);
    }

    /**
     * inserts value at index ind.
     * after inserting, this->at(ind) == value
     * returns an iterator pointing to the inserted value.
     * throw index_out_of_bound if ind > size (in this situation ind can be size because after inserting the size will increase 1.)
     */
    iterator insert(const size_t& pos, const T& value) {
        //check if it is valid
        if (pos > current_size) {
            throw index_out_of_bound();
        }
        //expand memory
        if (current_size == max_size) {
            expandDouble();
        }
        std::construct_at(data + current_size, value);

        //move backwards
        for (size_t i = current_size; i > pos; --i) {
            data[i] = std::move(data[i - 1]);
        }

        //create a new element
        data[pos] = value;
        ++current_size;

        return begin() + pos;
    }

    /**
     * removes the element at pos.
     * return an iterator pointing to the following element.
     * If the iterator pos refers the last element, the end() iterator is returned.
     */
    iterator erase(iterator pos) {
        if (pos == end()) {
            // like the push back
            return end();
        }
        iterator next_pos = pos + 1;
        std::move(next_pos, end(), pos);

        // update the vector
        std::destroy_at(data + current_size - 1);
        --current_size;
        return pos;
    }

    /**
     * removes the element with index ind.
     * return an iterator pointing to the following element.
     * throw index_out_of_bound if ind >= size
     */
    iterator erase(const size_t& ind) {
        if (ind >= current_size) {
            throw index_out_of_bound();
        } else {
            std::move(data + ind + 1, data + current_size, data + ind);
            std::destroy_at(data + current_size - 1);
            --current_size;
            return this->begin() + ind;
        }
    }

    /**
     * adds an element to the end.
     */
    void push_back(const T& value) {
        if (current_size == max_size) {
            // needs to expand
            expandDouble();
        }
        std::construct_at(data + current_size, value);
        ++current_size;
    }

    /**
     * remove the last element from the end.
     * throw container_is_empty if size() == 0
     */
    void pop_back() {
        if (size() == 0) {
            throw container_is_empty();
        } else {
            std::destroy_at(data + current_size - 1);
            --current_size;
        }
    }
};

} // namespace sjtu

#endif

Queue

// 顺序循环队列类的定义及基本操作实现

#ifndef SEQQUEUE_H_INCLUDED
#define SEQQUEUE_H_INCLUDED

class illegalSize{};
class outOfBound{};

template <class elemType>
class seqQueue
{    
    private:
        elemType *array;
        int maxSize;
        int Front, Rear;
        void doubleSpace(); //扩展队队列元素的存储空间为原来的2倍
    public:
        seqQueue(int size=10); //初始化队列元素的存储空间
        bool isEmpty(); //判断队空否，空返回true，否则为false
        bool isFull();  //判断队满否，满返回true，否则为false
        elemType front(); //读取队首元素的值，队首不变
        void enQueue(const elemType &x); //将x进队，成为新的队尾
        void deQueue(); //将队首元素出队
        ~seqQueue(); //释放队列元素所占据的动态数组
};

template <class elemType>
seqQueue<elemType>::seqQueue(int size) //初始化队列元素的存储空间
{
    array = new elemType[size]; //申请实际的队列存储空间

    if (!array) throw illegalSize();

    maxSize = size;
    Front = Rear = 0;
}

template<class elemType>
bool seqQueue<elemType>::isEmpty() //判断队空否，空返回 true,否则为false
{
    return Front == Rear;
}

template <class elemType>
bool seqQueue<elemType>::isFull() //判断队满否，满返回 true,否则为false
{
    return (Rear+1)%maxSize == Front;
}

template <class elemType>
elemType seqQueue<elemType>::front() //读取队首元素的值，队首不变
{
    if (isEmpty()) throw outOfBound(); //先判断

    return array[Front]; 
}

template <class elemType>
void seqQueue<elemType>::enQueue(const elemType &x)  //将x进队，成为新的队尾
{  
    if (isFull()) doubleSpace();

    array[Rear] = x;
    Rear = (Rear+1)%maxSize;
}

template <class elemType>
void seqQueue<elemType>::deQueue() //将队首元素出队
{  
    if (isEmpty()) throw outOfBound();

    Front = (Front+1)%maxSize;
}

template <class elemType>
seqQueue<elemType>::~seqQueue() //释放队列元素所占据的动态数组
{ 
    delete []array;
}

template <class elemType>
void seqQueue<elemType>::doubleSpace() //扩展队列元素的存储空间为原来的2倍
{
    elemType* newArray;
    int i, j;

    newArray = new elemType[2*maxSize];
    if (!newArray) throw illegalSize();

    for (i = 0, j = Front; j != Rear; i++, j = (j+1)%maxSize) //直接重排
        newArray[i] = array[j];

    delete []array; //释放原来的小空间

    array = newArray;
    Front = 0;
    Rear = i;
    maxSize = 2*maxSize;
}

#endif

Stack

// 顺序栈结构定义及基本操作的实现

// 顺序栈的描述：数组指针array，数组大小maxSize，栈顶下标Top
class illegalSize{};
class outOfBound{};

template <class elemType>
class seqStack
{  
    private:
        elemType *array;    //栈存储数组，存放实际的数据元素。
        int Top;            //栈顶下标。
        int maxSize;	    //栈中最多能存放的元素个数。
        void doubleSpace();
    public:
        seqStack(int initSize = 100); //初始化顺序栈
        bool isEmpty(){ return (Top == -1 ); } ; //栈空返回true,否则返回false
        bool isFull(){ return (Top == maxSize-1); }; //栈满返回true,否则返回false
        elemType top(); //返回栈顶元素的值，不改变栈顶
        void push(const elemType &e); //将元素e压入栈顶，使其成为新的栈顶
        void pop(); //将栈顶元素弹栈
        ~seqStack(){ delete []array; }; //释放栈占用的动态数组
};

template <class elemType>
seqStack<elemType>::seqStack(int initSize)//初始化顺序栈
{	
    array = new elemType[initSize];

	if (!array) throw illegalSize();

	Top = -1;    
    maxSize = initSize;
}

template <class elemType>
void seqStack<elemType>::doubleSpace() //分配2倍的空间
{
    elemType *tmp;
    int i;

    tmp = new elemType[maxSize*2];

    if (!tmp) throw illegalSize();

    for (i = 0; i <= Top; i++)
        tmp[i] = array[i];

    delete []array;
    array = tmp;
    maxSize = 2*maxSize;
}

template <class elemType>
elemType seqStack<elemType>::top () //返回栈顶元素的值，不改变栈顶
{   
    if (isEmpty()) throw outOfBound();

    return array[Top];
}

template <class elemType>
void seqStack<elemType>::push(const elemType &e )
//将元素e压入栈顶，使其成为新的栈顶元素
{     
    if (isFull()) doubleSpace(); //栈满时重新分配2倍的空间，并将原空间内容拷入
      
    array[++Top] = e; // 新结点放入新的栈顶位置。
}

template <class elemType>
void seqStack<elemType>::pop() //将栈顶元素弹栈
{  
    if (Top == -1) throw outOfBound();

    Top--; //不管此元素
}

// 函数initialize(seqStack)、isEmpty、isFull、top、pop、destroy（~seqStack）的时间复杂度均为O(1)
// push因某时可能扩大空间，造成O(n)时间消耗，但按照“分期付款式”法，分摊到单次的插入操作，时间复杂度仍为O(1)